SQLite

/*
** 2004 April 6
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.222 2004/11/22 05:26:27 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.

  u16 nSize;     /* Size of the cell content on the main b-tree page */
};

/*
** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.
**
** Normally, the BtCursor.delShift variable is 0. If non-zero, this
** indicates that the entry to which the cursor logically points 
** was deleted (by a BtreeDelete() call). If this is the case, the
** BtreeKeySize() and BtreeDataSize() calls both return 0. 

** If BtCursor.delShift is +1, then do not move the cursor for a 
** BtreeNext() operation (it was already advanced when the entry the
** cursor logically points to was deleted). If BtCursor.delShift is
** -1, then ignore the next BtreePrevious() call.
*/
struct BtCursor {
  Btree *pBt;               /* The Btree to which this cursor belongs */
  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
  int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
  void *pArg;               /* First arg to xCompare() */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */
  u8 isValid;               /* TRUE if points to a valid entry */
  u8 status;                /* Set to SQLITE_ABORT if cursors is invalidated */
  int delShift;             /* See above. */
};

/*
** Forward declaration
*/
static int checkReadLocks(Btree*,Pgno,BtCursor*);

  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur;
  }
  pCur->pPrev = 0;
  pBt->pCursor = pCur;
  pCur->isValid = 0;
  pCur->status = SQLITE_OK;
  pCur->delShift = 0;
  *ppCur = pCur;
  return SQLITE_OK;

create_cursor_exception:
  if( pCur ){
    releasePage(pCur->pPage);
    sqliteFree(pCur);

** the key for the current entry.  If the cursor is not pointing
** to a valid entry, *pSize is set to 0. 
**
** For a table with the INTKEY flag set, this routine returns the key
** itself, not the number of bytes in the key.
*/
int sqlite3BtreeKeySize(BtCursor *pCur, i64 *pSize){
  if( !pCur->isValid || pCur->delShift ){
    *pSize = 0;
  }else{
    getCellInfo(pCur);
    *pSize = pCur->info.nKey;
  }
  return SQLITE_OK;
}

/*
** Set *pSize to the number of bytes of data in the entry the
** cursor currently points to.  Always return SQLITE_OK.
** Failure is not possible.  If the cursor is not currently
** pointing to an entry (which can happen, for example, if
** the database is empty) then *pSize is set to 0.
*/
int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
  if( !pCur->isValid || pCur->delShift ){
    /* Not pointing at a valid entry - set *pSize to 0. */
    *pSize = 0;
  }else{
    getCellInfo(pCur);
    *pSize = pCur->info.nData;
  }
  return SQLITE_OK;

** begins at "offset".
**
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  if( !pCur->isValid || pCur->delShift ){
    return pCur->status;
  }
  assert( pCur->pPage!=0 );
  assert( pCur->pPage->intKey==0 );
  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  return getPayload(pCur, offset, amt, (unsigned char*)pBuf, 0);
}

/*
** Read part of the data associated with cursor pCur.  Exactly
** "amt" bytes will be transfered into pBuf[].  The transfer
** begins at "offset".
**
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeData(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  if( !pCur->isValid || pCur->delShift ){
    return pCur->status ? pCur->status : SQLITE_INTERNAL;
  }
  assert( pCur->pPage!=0 );
  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  return getPayload(pCur, offset, amt, pBuf, 1);
}

    assert( pRoot->pgno==1 );
    subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+8]);
    assert( subpage>0 );
    pCur->isValid = 1;
    rc = moveToChild(pCur, subpage);
  }
  pCur->isValid = pCur->pPage->nCell>0;
  pCur->delShift = 0;
  return rc;
}

/*
** Move the cursor down to the left-most leaf entry beneath the
** entry to which it is currently pointing.
*/

  if( pCur->isValid==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }
  assert( pPage->isInit );
  assert( pCur->idx<pPage->nCell );

  /* If BtCursor.delShift is 1, the cursor has already been advanced. */
  if( pCur->delShift==1 ){
    *pRes = 0;
    pCur->delShift = 0;
    return SQLITE_OK;
  }else{
    pCur->delShift = 0;
  }

  pCur->idx++;
  pCur->info.nSize = 0;
  if( pCur->idx>=pPage->nCell ){
    if( !pPage->leaf ){
      rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+8]));
      if( rc ) return rc;
      rc = moveToLeftmost(pCur);

  Pgno pgno;
  MemPage *pPage;
  if( pCur->isValid==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }

  /* If BtCursor.delShift is -1, the cursor has already been advanced. */
  if( pCur->delShift==-1 ){
    *pRes = 0;
    pCur->delShift = 0;
    return SQLITE_OK;
  }else{
    pCur->delShift = 0;
  }

  pPage = pCur->pPage;
  assert( pPage->isInit );
  assert( pCur->idx>=0 );
  if( !pPage->leaf ){
    pgno = get4byte( findCell(pPage, pCur->idx) );
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;

  u8 *apDiv[NB];               /* Divider cells in pParent */
  int cntNew[NB+2];            /* Index in aCell[] of cell after i-th page */
  int szNew[NB+2];             /* Combined size of cells place on i-th page */
  u8 **apCell;                 /* All cells begin balanced */
  int *szCell;                 /* Local size of all cells in apCell[] */
  u8 *aCopy[NB];               /* Space for holding data of apCopy[] */
  u8 *aSpace;                  /* Space to hold copies of dividers cells */
  BtCursor *pCur;

  /* 
  ** Find the parent page.
  */
  assert( pPage->isInit );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;

      rc = allocatePage(pBt, &pNew, &pgnoNew[i], pgnoNew[i-1], 0);
      if( rc ) goto balance_cleanup;
      apNew[i] = pNew;
    }
    nNew++;
    zeroPage(pNew, pageFlags);
  }











  /*
  ** Put the new pages in accending order.  This helps to
  ** keep entries in the disk file in order so that a scan
  ** of the table is a linear scan through the file.  That
  ** in turn helps the operating system to deliver pages
  ** from the disk more rapidly.

    nOld>=3 ? pgnoOld[2] : 0,
    pgnoNew[0], szNew[0],
    nNew>=2 ? pgnoNew[1] : 0, nNew>=2 ? szNew[1] : 0,
    nNew>=3 ? pgnoNew[2] : 0, nNew>=3 ? szNew[2] : 0,
    nNew>=4 ? pgnoNew[3] : 0, nNew>=4 ? szNew[3] : 0,
    nNew>=5 ? pgnoNew[4] : 0, nNew>=5 ? szNew[4] : 0));

  /* If there are other cursors that refer to one of the pages involved
  ** in the balancing, then adjust these cursors so that they still
  ** point to the same cells.
  */
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    int nCellCnt = 0;
    int iCell = -1;
    Pgno pgno = pCur->pPage->pgno;

    /* If the cursor is not valid, do not do anything with it. */
    if( !pCur->isValid ) continue;

    /* If the cursor pointed to one of the cells moved around during the
    ** balancing, then set variable iCell to the index of the cell in apCell.
    ** This is used by the block below to figure out where the cell was
    ** moved to, and adjust the cursor appropriately.
    **
    ** If the cursor points to the parent page, but the cell was not involved
    ** in the balance, then declare the cache of the cell-parse invalid, as a
    ** defragmentation may of occured during  the balance. Also, if the index
    ** of the cell is greater than that of the divider cells, then it may
    ** need to be adjusted (in case there are now more or less divider cells
    ** than there were before the balancing).
    */
    for(i=0; iCell<0 && i<nOld; i++){
      if( pgno==apCopy[i]->pgno ){
        iCell = nCellCnt + pCur->idx;
        break;
      }
      nCellCnt += (apCopy[i]->nCell + apCopy[i]->nOverflow) + (leafData?0:1);
    }
    if( pgno==pParent->pgno ){
      assert( !leafData );
      assert( iCell==-1 );
      if( pCur->idx>=nxDiv && pCur->idx<(nxDiv+nOld-1) ){
        for(i=0; i<=(pCur->idx-nxDiv); i++){
          iCell += (apCopy[i]->nCell + apCopy[i]->nOverflow + 1);
        }
      }
      if( pCur->idx>=(nxDiv+nOld-1) ){
        TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
            pCur, pgno, pCur->idx, pgno, pCur->idx+(nNew-nOld)));
        pCur->idx += (nNew-nOld);
      }
      pCur->info.nSize = 0;
    }

    /* If iCell is greater than or equal to zero, then pCur points at a
    ** cell that was moved around during the balance. Figure out where
    ** the cell was moved to and adjust pCur to match.
    */
    if( iCell>=0 ){
      int idxNew;
      Pgno pgnoNew;
      int x = 0;

      assert( iCell<nCell );
      while( cntNew[x]<=iCell ) x++;
      if( x>0 && !leafData && cntNew[x-1]==iCell ){
        /* The cell that pCur points to is a divider cell in pParent. */
        pgnoNew = pParent->pgno;
        idxNew = nxDiv + x-1;
      }else{
        /* The cell that pCur points to is on page apNew[x]. */
        idxNew = iCell-(x>0?cntNew[x-1]:0)-((leafData||x==0)?0:1);
        pgnoNew = apNew[x]->pgno;
      }

      TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
          pCur, pgno, pCur->idx, pgnoNew, idxNew));

      pCur->idx = idxNew;
      releasePage(pCur->pPage);
      rc = getPage(pBt, pgnoNew, &pCur->pPage);
      assert( rc==SQLITE_OK );
      assert( pCur->pPage->isInit );
      pCur->info.nSize = 0;
    }
  }

  /* Free any old pages that were not reused as new pages.
  */
  for(i=nNew; i<nOld; i++){
    rc = freePage(apOld[i]);
    if( rc ) goto balance_cleanup;
    releasePage(apOld[i]);
    apOld[i] = 0;
  }

  /*
  ** Evenly distribute the data in apCell[] across the new pages.
  ** Insert divider cells into pParent as necessary.
  */
  j = 0;
  for(i=0; i<nNew; i++){
    MemPage *pNew = apNew[i];

      rc = initPage(pChild, pPage);
      if( rc ) goto end_shallow_balance;
      assert( pChild->nOverflow==0 );
      if( pChild->nFree>=100 ){
        /* The child information will fit on the root page, so do the
        ** copy */
        int i;
        BtCursor *pCur;
        zeroPage(pPage, pChild->aData[0]);
        for(i=0; i<pChild->nCell; i++){
          apCell[i] = findCell(pChild,i);
          szCell[i] = cellSizePtr(pChild, apCell[i]);
        }
        assemblePage(pPage, pChild->nCell, apCell, szCell);
        freePage(pChild);
        TRACE(("BALANCE: child %d transfer to page 1\n", pChild->pgno));
        /* If there were cursors pointing at this page, point them at the 
        ** new page instead. Decrement the reference count for the old 
        ** page and increment it for the new one.
        */
        for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
          if( pCur->pPage==pChild ){
            TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
                pCur, pPage->pgno, pCur->idx, pPage->pgno, pCur->idx));
            releasePage(pCur->pPage);
            rc = getPage(pBt, 1,  &pCur->pPage);
            assert( rc==SQLITE_OK );
          }
        }
      }else{
        /* The child has more information that will fit on the root.
        ** The tree is already balanced.  Do nothing. */
        TRACE(("BALANCE: child %d will not fit on page 1\n", pChild->pgno));
      }
    }else{
      BtCursor *pCur;
      memcpy(pPage->aData, pChild->aData, pPage->pBt->usableSize);
      pPage->isInit = 0;
      pPage->pParent = 0;
      rc = initPage(pPage, 0);
      assert( rc==SQLITE_OK );
      freePage(pChild);
      TRACE(("BALANCE: transfer child %d into root %d\n",
              pChild->pgno, pPage->pgno));
      for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
        if( pCur->pPage==pChild ){
          TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
              pCur, pChild->pgno, pCur->idx, pPage->pgno, pCur->idx));
          releasePage(pCur->pPage);
          rc = getPage(pBt, pPage->pgno,  &pCur->pPage);
          assert( rc==SQLITE_OK );
        }
      }
    }
    rc = reparentChildPages(pPage);
    if( rc!=SQLITE_OK ) goto end_shallow_balance;
    releasePage(pChild);
  }
end_shallow_balance:
  sqliteFree(apCell);

  Pgno pgnoChild;     /* Page number of the new child page */
  Btree *pBt;         /* The BTree */
  int usableSize;     /* Total usable size of a page */
  u8 *data;           /* Content of the parent page */
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int brk;            /* Offset to content of first cell in parent */
  BtCursor *pCur;

  assert( pPage->pParent==0 );
  assert( pPage->nOverflow>0 );
  pBt = pPage->pBt;
  rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0);
  if( rc ) return rc;
  assert( sqlite3pager_iswriteable(pChild->aData) );

  if( pChild->nOverflow ){
    pChild->nFree = 0;
  }
  assert( pChild->nCell==pPage->nCell );
  zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
  put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild);
  TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, pChild->pgno));

  /* If there were cursors pointing at this page, point them at the new
  ** page instead. Decrement the reference count for the old page and
  ** increment it for the new one.
  */
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    if( pCur->pPage==pPage ){
      TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
          pCur, pPage->pgno, pCur->idx, pChild->pgno, pCur->idx));
      releasePage(pCur->pPage);
      rc = getPage(pBt, pChild->pgno,  &pCur->pPage);
      assert( rc==SQLITE_OK );
    }
  }

  rc = balance_nonroot(pChild);
  releasePage(pChild);
  return rc;
}

/*
** Decide if the page pPage needs to be balanced.  If balancing is

/*
** This routine checks all cursors that point to table pgnoRoot.
** If any of those cursors other than pExclude were opened with 
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
** cursors that point to pgnoRoot were opened with wrFlag==1
** then this routine returns SQLITE_OK.








*/
static int checkReadLocks(Btree *pBt, Pgno pgnoRoot, BtCursor *pExclude){








  return SQLITE_OK;
}

/*
** Insert a new record into the BTree.  The key is given by (pKey,nKey)
** and the data is given by (pData,nData).  The cursor is used only to
** define what table the record should be inserted into.  The cursor

  int rc;
  int loc;
  int szNew;
  MemPage *pPage;
  Btree *pBt = pCur->pBt;
  unsigned char *oldCell;
  unsigned char *newCell = 0;
  BtCursor *pCur2;

  if( pCur->status ){
    return pCur->status;  /* A rollback destroyed this cursor */
  }
  if( pBt->inTrans!=TRANS_WRITE ){
    /* Must start a transaction before doing an insert */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;

    assert( pPage->leaf );
    pCur->idx++;
    pCur->info.nSize = 0;
  }else{
    assert( pPage->leaf );
  }
  rc = insertCell(pPage, pCur->idx, newCell, szNew, 0);
  pCur->isValid = 1;

  /* If there are other cursors pointing at this page with a BtCursor.idx
  ** field greater than or equal to 'i', then the cell they refer to
  ** has been modified or moved within the page. Fix the cursor.
  */
  for(pCur2=pPage->pBt->pCursor; pCur2; pCur2 = pCur2->pNext){
    if( pCur2->pPage==pPage ){
      if( pCur2->idx>=pCur->idx && pCur!=pCur2 && loc!=0 ){
	/* The cell pointed to by pCur2 was shifted one to the right on it's
	** page by this Insert(). 
        */
        TRACE(("INSERT: Cursor %p migrates from %d,%d to %d,%d\n", 
            pCur2, pPage->pgno, pCur2->idx, pPage->pgno, pCur2->idx+1));
        pCur2->idx++;
      }
      pCur2->info.nSize = 0;
    }
  }

  if( rc!=SQLITE_OK ) goto end_insert;
  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */



end_insert:
  sqliteFree(newCell);
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor
** is left pointing at a random location.
*/
int sqlite3BtreeDelete(BtCursor *pCur){
  MemPage *pPage = pCur->pPage;
  unsigned char *pCell;
  int rc;
  Pgno pgnoChild = 0;
  Btree *pBt = pCur->pBt;
  int idx;                /* Index of the cell to delete */
  BtCursor *pCur2;        /* Iterator variable for the pBt.pCursor link-list */

  assert( pPage->isInit );
  if( pCur->status ){
    return pCur->status;  /* A rollback destroyed this cursor */
  }
  if( pBt->inTrans!=TRANS_WRITE ){
    /* Must start a transaction before doing a delete */

  }
  if( checkReadLocks(pBt, pCur->pgnoRoot, pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlite3pager_write(pPage->aData);
  if( rc ) return rc;

  /* Set index to the index in pPage that contains the cell to delete. Also
  ** increment the reference count for pPage. This allows us to move the
  ** cursor pCur before the delete takes place.
  */
  idx = pCur->idx;
  rc = getPage(pBt, pPage->pgno, &pPage);
  if( rc ) return rc;
  assert( pPage==pCur->pPage );

  /* If there are any cursors that point to the cell being deleted, 
  ** move them to the next or previous entry in the table. It is preferable
  ** to move the cursor to the 'next' location, rather than the 'previous'
  ** one, as most table scans are done in the forward direction (also, code
  ** below depends on this). If neither entry exists, declare the cursor
  ** invalid.
  */ 
  for(pCur2=pBt->pCursor; pCur2; pCur2 = pCur2->pNext){
    if( pCur2->pPage==pPage && pCur2->idx==idx && pCur2->isValid ){
      int res;
      pCur2->delShift = 0;
      rc = sqlite3BtreeNext(pCur2, &res);
      if( rc ) goto delete_out;
      if( res ){
        /* If the next tree entry cannot be found, then the cursor must
        ** already point to the last table entry. So point it to the
        ** second last by calling BtreeLast(), BtreePrevious().
        */
        rc = sqlite3BtreeLast(pCur2, &res);
        if( rc ) goto delete_out;
        assert( res==0 );
        rc = sqlite3BtreePrevious(pCur2, &res);
        if( rc ) goto delete_out;
        pCur2->delShift = -1;
      }else{
        pCur2->delShift = 1;
      }
    }
  }

  /* Locate the cell within it's page and leave pCell pointing to the
  ** data. The clearCell() call frees any overflow pages associated with the
  ** cell. The cell itself is still intact.
  */
  pCell = findCell(pPage, idx);
  if( !pPage->leaf ){
    pgnoChild = get4byte(pCell);
  }
  clearCell(pPage, pCell);

  if( !pPage->leaf ){
    /*
    ** The entry we are about to delete is not a leaf so if we do not
    ** do something we will leave a hole on an internal page.
    ** We have to fill the hole by moving in a cell from a leaf.  The
    ** next Cell after the one to be deleted is guaranteed to exist and
    ** to be a leaf so we can use it. Conveniantly, pCur now points
    ** at this cell (because it was advanced above).
    */
    BtCursor leafCur;
    unsigned char *pNext;
    int szNext;

    unsigned char *tempCell;
    assert( !pPage->leafData );

    /* Make a copy of *pCur in leafCur. leafCur now points to the cell 
    ** that will be moved into the space left by the cell being deleted.
    */
    assert( pCur->delShift==1 );
    assert( pCur->isValid );
    getTempCursor(pCur, &leafCur);

    if( rc!=SQLITE_OK ){
      if( rc!=SQLITE_NOMEM ){
        rc = SQLITE_CORRUPT;  /* bkpt-CORRUPT */
      }
      goto delete_out;
    }
    rc = sqlite3pager_write(leafCur.pPage->aData);
    if( rc ) goto delete_out;
    TRACE(("DELETE: table=%d delete internal from %d,%d replace "
        "from leaf %d,%d\n", pCur->pgnoRoot, pPage->pgno, idx, 
        leafCur.pPage->pgno, leafCur.idx));

    /* Drop the cell from the internal page. Make a copy of the cell from
    ** the leaf page into memory obtained from malloc(). Insert it into
    ** the internal page, at the position vacated by the delete. There
    ** are now two copies of the leaf-cell in the tree.
    */
    dropCell(pPage, idx, cellSizePtr(pPage, pCell));
    pNext = findCell(leafCur.pPage, leafCur.idx);
    szNext = cellSizePtr(leafCur.pPage, pNext);
    assert( MX_CELL_SIZE(pBt)>=szNext+4 );
    tempCell = sqliteMallocRaw( MX_CELL_SIZE(pBt) );
    if( tempCell==0 ){
       rc = SQLITE_NOMEM;
       goto delete_out;
    }
    rc = insertCell(pPage, idx, pNext-4, szNext+4, tempCell);
    if( rc!=SQLITE_OK ) goto delete_out;
    put4byte(findOverflowCell(pPage, idx), pgnoChild);
    pPage->idxShift = 0;

    /* If there are any cursors that point to the leaf-cell, move them
    ** so that they point at internal cell. This is easiest done by
    ** calling BtreePrevious().
    **
    ** Also, any cursors that point to the internal page have their
    ** cached parses invalidated, as the insertCell() above may have 
    ** caused a defragmation.
    */
    for(pCur2=pBt->pCursor; pCur2; pCur2 = pCur2->pNext){
      if( pCur2->pPage==leafCur.pPage && pCur2->idx==leafCur.idx ){
        int res;
        int delShiftSave = pCur2->delShift; 
        assert( leafCur.idx==0 );
        pCur2->delShift = 0;
        rc = sqlite3BtreePrevious(pCur2, &res);
        if( rc ) goto delete_out;
        assert( res==0 );
        assert( pCur2->pPage==pPage );
        assert( pCur2->idx==idx );
        pCur2->delShift = delShiftSave;
      }
      if( pCur2->pPage==pPage ){
        pCur2->info.nSize = 0;
      }
    }

    /* Balance the internal page. Free the memory allocated for the 
    ** copy of the leaf cell. Then delete the cell from the leaf page.
    */
    rc = balance(pPage);
    sqliteFree(tempCell);
    if( rc ) goto delete_out;
    dropCell(leafCur.pPage, leafCur.idx, szNext);

    for(pCur2=pBt->pCursor; pCur2; pCur2 = pCur2->pNext){
      if( pCur2->pPage==leafCur.pPage && pCur2->idx>leafCur.idx ){
        TRACE(("DELETE: Cursor %p migrates from %d,%d to %d,%d\n", pCur2, 
            leafCur.pPage->pgno,pCur2->idx,leafCur.pPage->pgno, pCur2->idx-1));
        pCur2->idx--;
        pCur2->info.nSize = 0;
      }
    }

    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete %d from leaf %d\n",
       pCur->pgnoRoot, idx, pPage->pgno));
    dropCell(pPage, idx, cellSizePtr(pPage, pCell));

    /* If there were cursors pointing to cells on pPage with index values
    ** greater than idx, decrement the index values now.
    */
    for(pCur2=pBt->pCursor; pCur2; pCur2 = pCur2->pNext){
      assert( !pCur2->isValid || pCur2->pPage!=pPage || pCur2->idx!=idx );
      if( pCur2->pPage==pPage && pCur2->idx>idx ){
        TRACE(("DELETE: Cursor %p migrates from %d,%d to %d,%d\n", 
            pCur2, pPage->pgno, pCur2->idx, pPage->pgno, pCur2->idx-1));
        pCur2->idx--;
        pCur2->info.nSize = 0;
      }
    }

    rc = balance(pPage);
  }

delete_out:
  releasePage(pPage);
  return rc;
}

/*
** Create a new BTree table.  Write into *piTable the page
** number for the root page of the new table.
**

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle DELETE FROM statements.
**
** $Id: delete.c,v 1.89 2004/11/16 15:50:20 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** Look up every table that is named in pSrc.  If any table is not found,
** add an error message to pParse->zErrMsg and return NULL.  If all tables
** are found, return a pointer to the last table.

  Table *pTab     /* The table to be opened */
){
  sqlite3VdbeAddOp(v, OP_Integer, pTab->iDb, 0);
  sqlite3VdbeAddOp(v, OP_OpenRead, iCur, pTab->tnum);
  VdbeComment((v, "# %s", pTab->zName));
  sqlite3VdbeAddOp(v, OP_SetNumColumns, iCur, pTab->nCol);
}


/*
** Process a DELETE FROM statement.
*/
void sqlite3DeleteFrom(
  Parse *pParse,         /* The parser context */
  SrcList *pTabList,     /* The table from which we should delete things */
  Expr *pWhere           /* The WHERE clause.  May be null */
){
  Vdbe *v;               /* The virtual database engine */
  Table *pTab;           /* The table from which records will be deleted */
  const char *zDb;       /* Name of database holding pTab */
  int addr = 0;          /* A couple addresses of generated code */
  int i;                 /* Loop counter */
  WhereInfo *pWInfo;     /* Information about the WHERE clause */
  Index *pIdx;           /* For looping over indices of the table */
  int iCur;              /* VDBE Cursor number for pTab */
  sqlite3 *db;           /* Main database structure */
  AuthContext sContext;  /* Authorization context */
  int oldIdx = -1;       /* Cursor for the OLD table of AFTER triggers */

  /* Allocate a cursor used to store the old.* data for a trigger.
  */
  if( row_triggers_exist ){ 
    oldIdx = pParse->nTab++;
  }

  /* Resolve the column names in all the expressions. Allocate cursors
  ** for the table and indices first, in case an expression needs to use
  ** a cursor (e.g. an IN() expression).
  */
  assert( pTabList->nSrc==1 );
  iCur = pTabList->a[0].iCursor = pParse->nTab++;
  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
    pParse->nTab++;
  }
  if( sqlite3ExprResolveAndCheck(pParse, pTabList, 0, pWhere, 0, 0) ){
    goto delete_from_cleanup;
  }

  /* Start the view context
  */
  if( isView ){

  else{
    /* Ensure all required collation sequences are available. */
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      if( sqlite3CheckIndexCollSeq(pParse, pIdx) ){
        goto delete_from_cleanup;
      }
    }

















    /* Open the pseudo-table used to store OLD if there are triggers.
    */
    if( row_triggers_exist ){
      sqlite3VdbeAddOp(v, OP_OpenPseudo, oldIdx, 0);
      sqlite3VdbeAddOp(v, OP_SetNumColumns, oldIdx, pTab->nCol);
    }

    /* Open cursors for the table and indices we are deleting from. */
    if( !isView ){
      sqlite3OpenTableAndIndices(pParse, pTab, iCur, OP_OpenWrite);
    }

    /* Begin the database scan

    */
    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 0, isView?0:iCur);
    if( pWInfo==0 ) goto delete_from_cleanup;
    addr = pWInfo->iContinue;

    /* If row-triggers exist, copy the record being deleted into the
    ** oldIdx psuedo-table. Then invoke the BEFORE triggers.
    */
    if( row_triggers_exist ){






      sqlite3VdbeAddOp(v, OP_Recno, iCur, 0);
      sqlite3VdbeAddOp(v, OP_RowData, iCur, 0);
      sqlite3VdbeAddOp(v, OP_PutIntKey, oldIdx, 0);




      (void)sqlite3CodeRowTrigger(pParse, TK_DELETE, 0, TK_BEFORE, pTab, -1, 
          oldIdx, (pParse->trigStack)?pParse->trigStack->orconf:OE_Default,
	  addr);
    }

    /* Delete the row. Increment the callback value if the count-rows flag 
    ** is set. 





    */

    if( db->flags & SQLITE_CountRows ){



      sqlite3VdbeAddOp(v, OP_AddImm, 1, 0);
    }
    sqlite3VdbeAddOp(v, OP_Recno, iCur, 0);

    sqlite3GenerateRowDelete(db, v, pTab, iCur, pParse->nested==0);



    /* Code the AFTER triggers.  */

    if( row_triggers_exist ){






      (void)sqlite3CodeRowTrigger(pParse, TK_DELETE, 0, TK_AFTER, pTab, -1, 
          oldIdx, (pParse->trigStack)?pParse->trigStack->orconf:OE_Default,
	  addr);
    }

    /* End the database scan loop and close indices. */



    sqlite3WhereEnd(pWInfo);


    for(i=1, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
      sqlite3VdbeAddOp(v, OP_Close, iCur + i, pIdx->tnum);


    }
  }

  /*
  ** Return the number of rows that were deleted. If this routine is 
  ** generating code because of a call to sqlite3NestedParse(), do not
  ** invoke the callback function.

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.214 2004/11/16 15:50:20 danielk1977 Exp $
*/
#include "sqliteInt.h"


/*
** Allocate a new Select structure and return a pointer to that
** structure.

  }else{
    distinct = -1;
  }

  /* Begin the database scan
  */
  pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 
                            pGroupBy ? 0 : &pOrderBy, -1);
  if( pWInfo==0 ) goto select_end;

  /* Use the standard inner loop if we are not dealing with
  ** aggregates
  */
  if( !isAgg ){
    if( selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, distinct, eDest,

/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.341 2004/11/20 19:18:01 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** These #defines should enable >2GB file support on Posix if the
** underlying operating system supports it.  If the OS lacks

Select *sqlite3SelectNew(ExprList*,SrcList*,Expr*,ExprList*,Expr*,ExprList*,
                        int,int,int);
void sqlite3SelectDelete(Select*);
void sqlite3SelectUnbind(Select*);
Table *sqlite3SrcListLookup(Parse*, SrcList*);
int sqlite3IsReadOnly(Parse*, Table*, int);
void sqlite3OpenTableForReading(Vdbe*, int iCur, Table*);
void sqlite3OpenTable(Vdbe*, int iCur, Table*, int);
void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
WhereInfo *sqlite3WhereBegin(Parse*, SrcList*, Expr*, int, ExprList**, int);
void sqlite3WhereEnd(WhereInfo*);
void sqlite3ExprCode(Parse*, Expr*);
int sqlite3ExprCodeExprList(Parse*, ExprList*);
void sqlite3ExprIfTrue(Parse*, Expr*, int, int);
void sqlite3ExprIfFalse(Parse*, Expr*, int, int);
void sqlite3NextedParse(Parse*, const char*, ...);
Table *sqlite3FindTable(sqlite3*,const char*, const char*);

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle UPDATE statements.
**
** $Id: update.c,v 1.95 2004/11/16 15:50:20 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** Process an UPDATE statement.
**
**   UPDATE OR IGNORE table_wxyz SET a=b, c=d WHERE e<5 AND f NOT NULL;

    pView = sqlite3SelectDup(pTab->pSelect);
    sqlite3Select(pParse, pView, SRT_TempTable, iCur, 0, 0, 0, 0);
    sqlite3SelectDelete(pView);
  }

  /* Begin the database scan
  */
  pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 1, 0, -1);
  if( pWInfo==0 ) goto update_cleanup;

  /* Remember the index of every item to be updated.
  */
  sqlite3VdbeAddOp(v, OP_ListWrite, 0, 0);

  /* End the database scan loop.

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.
**
** $Id: where.c,v 1.117 2004/11/16 15:50:20 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.

** one.
*/
WhereInfo *sqlite3WhereBegin(
  Parse *pParse,        /* The parser context */
  SrcList *pTabList,    /* A list of all tables to be scanned */
  Expr *pWhere,         /* The WHERE clause */
  int pushKey,          /* If TRUE, leave the table key on the stack */
  ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
  int iTabCur           /* Cursor for pTabList->aSrc[0] */
){
  int i;                     /* Loop counter */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  int brk, cont = 0;         /* Addresses used during code generation */
  int nExpr;           /* Number of subexpressions in the WHERE clause */
  int loopMask;        /* One bit set for each outer loop */

  sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  for(i=0; i<pTabList->nSrc; i++){
    Table *pTab;
    Index *pIx;

    pTab = pTabList->a[i].pTab;
    if( pTab->isTransient || pTab->pSelect ) continue;
    if( i>0 || iTabCur<0 ){
      sqlite3OpenTableForReading(v, pTabList->a[i].iCursor, pTab);
    }
    sqlite3CodeVerifySchema(pParse, pTab->iDb);
    if( (pIx = pWInfo->a[i].pIdx)!=0 ){
      sqlite3VdbeAddOp(v, OP_Integer, pIx->iDb, 0);
      sqlite3VdbeOp3(v, OP_OpenRead, pWInfo->a[i].iCur, pIx->tnum,
                     (char*)&pIx->keyInfo, P3_KEYINFO);
    }
  }