/ Check-in [a80939ef]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:More bug fixes in btree.c. (CVS 1322)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: a80939ef714ec884950b4a1f4f809ffa37fdfa59
User & Date: drh 2004-05-07 23:50:57
Context
2004-05-08
02:03
More bug fixes in btree.c. (CVS 1323) check-in: 2d64cba3 user: drh tags: trunk
2004-05-07
23:50
More bug fixes in btree.c. (CVS 1322) check-in: a80939ef user: drh tags: trunk
17:57
The btree.c module compiles and links and passes some tests. Many tests still fail, though. (CVS 1321) check-in: d394b2b2 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btree.c,v 1.111 2004/05/07 17:57:50 drh Exp $
           12  +** $Id: btree.c,v 1.112 2004/05/07 23:50:57 drh Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** For a detailed discussion of BTrees, refer to
    16     16   **
    17     17   **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
    18     18   **     "Sorting And Searching", pages 473-480. Addison-Wesley
    19     19   **     Publishing Company, Reading, Massachusetts.
................................................................................
   262    262     BtCursor *pShared;        /* Loop of cursors with the same root page */
   263    263     int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
   264    264     void *pArg;               /* First arg to xCompare() */
   265    265     Pgno pgnoRoot;            /* The root page of this tree */
   266    266     MemPage *pPage;           /* Page that contains the entry */
   267    267     int idx;                  /* Index of the entry in pPage->aCell[] */
   268    268     u8 wrFlag;                /* True if writable */
   269         -  u8 eSkip;                 /* Determines if next step operation is a no-op */
   270    269     u8 iMatch;                /* compare result from last sqlite3BtreeMoveto() */
          270  +  u8 isValid;               /* TRUE if points to a valid entry */
          271  +  u8 status;                /* Set to SQLITE_ABORT if cursors is invalidated */
   271    272   };
   272    273   
   273         -/*
   274         -** Legal values for BtCursor.eSkip.
   275         -*/
   276         -#define SKIP_NONE     0   /* Always step the cursor */
   277         -#define SKIP_NEXT     1   /* The next sqlite3BtreeNext() is a no-op */
   278         -#define SKIP_PREV     2   /* The next sqlite3BtreePrevious() is a no-op */
   279         -#define SKIP_INVALID  3   /* Calls to Next() and Previous() are invalid */
   280         -
   281    274   /*
   282    275   ** Read or write a two-, four-, and eight-byte big-endian integer values.
   283    276   */
   284    277   static u32 get2byte(unsigned char *p){
   285    278     return (p[0]<<8) | p[1];
   286    279   }
   287    280   static u32 get4byte(unsigned char *p){
................................................................................
   401    394     oldPage = pPage->aData;
   402    395     hdr = pPage->hdrOffset;
   403    396     addr = 3+hdr;
   404    397     n = 6+hdr;
   405    398     if( !pPage->leaf ){
   406    399       n += 4;
   407    400     }
          401  +  memcpy(&newPage[hdr], &oldPage[hdr], n-hdr);
   408    402     start = n;
   409    403     pc = get2byte(&oldPage[addr]);
   410    404     i = 0;
   411    405     while( pc>0 ){
   412    406       assert( n<pPage->pBt->pageSize );
   413    407       size = cellSize(pPage, &oldPage[pc]);
   414    408       memcpy(&newPage[n], &oldPage[pc], size);
   415    409       put2byte(&newPage[addr],n);
   416         -    pPage->aCell[i] = &oldPage[n];
          410  +    pPage->aCell[i++] = &oldPage[n];
   417    411       n += size;
   418    412       addr = pc;
   419    413       pc = get2byte(&oldPage[pc]);
   420    414     }
          415  +  assert( i==pPage->nCell );
   421    416     leftover = pPage->pBt->pageSize - n;
   422    417     assert( leftover>=0 );
   423    418     assert( pPage->nFree==leftover );
   424    419     if( leftover<4 ){
   425    420       oldPage[hdr+5] = leftover;
   426    421       leftover = 0;
   427    422       n = pPage->pBt->pageSize;
   428    423     }
   429         -  memcpy(&oldPage[start], &newPage[start], n-start);
          424  +  memcpy(&oldPage[hdr], &newPage[hdr], n-hdr);
   430    425     if( leftover==0 ){
   431         -    put2byte(&oldPage[hdr+3], 0);
          426  +    put2byte(&oldPage[hdr+1], 0);
   432    427     }else if( leftover>=4 ){
   433         -    put2byte(&oldPage[hdr+3], n);
          428  +    put2byte(&oldPage[hdr+1], n);
   434    429       put2byte(&oldPage[n], 0);
   435    430       put2byte(&oldPage[n+2], leftover);
   436    431       memset(&oldPage[n+4], 0, leftover-4);
   437    432     }
          433  +  oldPage[hdr+5] = 0;
   438    434   }
   439    435   
   440    436   /*
   441    437   ** Allocate nByte bytes of space on a page.  If nByte is less than
   442    438   ** 4 it is rounded up to 4.
   443    439   **
   444    440   ** Return the index into pPage->aData[] of the first byte of
................................................................................
  1077   1073     int rc;
  1078   1074     rc = pBt->readOnly ? SQLITE_OK : sqlite3pager_commit(pBt->pPager);
  1079   1075     pBt->inTrans = 0;
  1080   1076     pBt->inStmt = 0;
  1081   1077     unlockBtreeIfUnused(pBt);
  1082   1078     return rc;
  1083   1079   }
         1080  +
         1081  +/*
         1082  +** Invalidate all cursors
         1083  +*/
         1084  +static void invalidateCursors(Btree *pBt){
         1085  +  BtCursor *pCur;
         1086  +  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
         1087  +    MemPage *pPage = pCur->pPage;
         1088  +    if( pPage && !pPage->isInit ){
         1089  +      releasePage(pPage);
         1090  +      pCur->pPage = 0;
         1091  +      pCur->isValid = 0;
         1092  +      pCur->status = SQLITE_ABORT;
         1093  +    }
         1094  +  }
         1095  +}
  1084   1096   
  1085   1097   /*
  1086   1098   ** Rollback the transaction in progress.  All cursors will be
  1087   1099   ** invalided by this operation.  Any attempt to use a cursor
  1088   1100   ** that was open at the beginning of this operation will result
  1089   1101   ** in an error.
  1090   1102   **
  1091   1103   ** This will release the write lock on the database file.  If there
  1092   1104   ** are no active cursors, it also releases the read lock.
  1093   1105   */
  1094   1106   int sqlite3BtreeRollback(Btree *pBt){
  1095   1107     int rc;
  1096         -  BtCursor *pCur;
  1097   1108     if( pBt->inTrans==0 ) return SQLITE_OK;
  1098   1109     pBt->inTrans = 0;
  1099   1110     pBt->inStmt = 0;
  1100   1111     rc = pBt->readOnly ? SQLITE_OK : sqlite3pager_rollback(pBt->pPager);
  1101         -  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
  1102         -    MemPage *pPage = pCur->pPage;
  1103         -    if( pPage && !pPage->isInit ){
  1104         -      releasePage(pPage);
  1105         -      pCur->pPage = 0;
  1106         -    }
  1107         -  }
         1112  +  invalidateCursors(pBt);
  1108   1113     unlockBtreeIfUnused(pBt);
  1109   1114     return rc;
  1110   1115   }
  1111   1116   
  1112   1117   /*
  1113   1118   ** Set the checkpoint for the current transaction.  The checkpoint serves
  1114   1119   ** as a sub-transaction that can be rolled back independently of the
................................................................................
  1151   1156   **
  1152   1157   ** All cursors will be invalided by this operation.  Any attempt
  1153   1158   ** to use a cursor that was open at the beginning of this operation
  1154   1159   ** will result in an error.
  1155   1160   */
  1156   1161   int sqlite3BtreeRollbackStmt(Btree *pBt){
  1157   1162     int rc;
  1158         -  BtCursor *pCur;
  1159   1163     if( pBt->inStmt==0 || pBt->readOnly ) return SQLITE_OK;
  1160   1164     rc = sqlite3pager_stmt_rollback(pBt->pPager);
  1161         -  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
  1162         -    MemPage *pPage = pCur->pPage;
  1163         -    if( pPage && !pPage->isInit ){
  1164         -      releasePage(pPage);
  1165         -      pCur->pPage = 0;
  1166         -    }
  1167         -  }
         1165  +  invalidateCursors(pBt);
  1168   1166     pBt->inStmt = 0;
  1169   1167     return rc;
  1170   1168   }
  1171   1169   
  1172   1170   /*
  1173   1171   ** Default key comparison function to be used if no comparison function
  1174   1172   ** is specified on the sqlite3BtreeCursor() call.
................................................................................
  1261   1259       goto create_cursor_exception;
  1262   1260     }
  1263   1261     pCur->xCompare = xCmp ? xCmp : dfltCompare;
  1264   1262     pCur->pArg = pArg;
  1265   1263     pCur->pBt = pBt;
  1266   1264     pCur->wrFlag = wrFlag;
  1267   1265     pCur->idx = 0;
  1268         -  pCur->eSkip = SKIP_INVALID;
  1269   1266     pCur->pNext = pBt->pCursor;
  1270   1267     if( pCur->pNext ){
  1271   1268       pCur->pNext->pPrev = pCur;
  1272   1269     }
  1273   1270     pCur->pPrev = 0;
  1274   1271     pRing = pBt->pCursor;
  1275   1272     while( pRing && pRing->pgnoRoot!=pCur->pgnoRoot ){ pRing = pRing->pNext; }
................................................................................
  1276   1273     if( pRing ){
  1277   1274       pCur->pShared = pRing->pShared;
  1278   1275       pRing->pShared = pCur;
  1279   1276     }else{
  1280   1277       pCur->pShared = pCur;
  1281   1278     }
  1282   1279     pBt->pCursor = pCur;
         1280  +  pCur->isValid = 0;
         1281  +  pCur->status = SQLITE_OK;
  1283   1282     *ppCur = pCur;
  1284   1283     return SQLITE_OK;
  1285   1284   
  1286   1285   create_cursor_exception:
  1287   1286     *ppCur = 0;
  1288   1287     if( pCur ){
  1289   1288       releasePage(pCur->pPage);
................................................................................
  1347   1346   ** to a valid entry, *pSize is set to 0. 
  1348   1347   **
  1349   1348   ** For a table with the INTKEY flag set, this routine returns the key
  1350   1349   ** itself, not the number of bytes in the key.
  1351   1350   */
  1352   1351   int sqlite3BtreeKeySize(BtCursor *pCur, u64 *pSize){
  1353   1352     MemPage *pPage;
         1353  +  unsigned char *cell;
  1354   1354   
  1355         -  pPage = pCur->pPage;
  1356         -  assert( pPage!=0 );
  1357         -  if( pCur->idx >= pPage->nCell ){
         1355  +  if( !pCur->isValid ){
  1358   1356       *pSize = 0;
  1359   1357     }else{
  1360         -    unsigned char *cell = pPage->aCell[pCur->idx];
         1358  +    pPage = pCur->pPage;
         1359  +    assert( pPage!=0 );
         1360  +    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
         1361  +    cell = pPage->aCell[pCur->idx];
  1361   1362       cell += 2;   /* Skip the offset to the next cell */
  1362   1363       if( !pPage->leaf ){
  1363   1364         cell += 4;  /* Skip the child pointer */
  1364   1365       }
  1365   1366       if( !pPage->zeroData ){
  1366   1367         while( (0x80&*(cell++))!=0 ){}  /* Skip the data size number */
  1367   1368       }
................................................................................
  1390   1391     int rc;
  1391   1392     MemPage *pPage;
  1392   1393     Btree *pBt;
  1393   1394     u64 nData, nKey;
  1394   1395     int maxLocal, ovflSize;
  1395   1396   
  1396   1397     assert( pCur!=0 && pCur->pPage!=0 );
         1398  +  assert( pCur->isValid );
  1397   1399     pBt = pCur->pBt;
  1398   1400     pPage = pCur->pPage;
  1399   1401     assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  1400   1402     aPayload = pPage->aCell[pCur->idx];
  1401   1403     aPayload += 2;  /* Skip the next cell index */
  1402   1404     if( !pPage->leaf ){
  1403   1405       aPayload += 4;  /* Skip the child pointer */
................................................................................
  1470   1472   ** begins at "offset".
  1471   1473   **
  1472   1474   ** Return SQLITE_OK on success or an error code if anything goes
  1473   1475   ** wrong.  An error is returned if "offset+amt" is larger than
  1474   1476   ** the available payload.
  1475   1477   */
  1476   1478   int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  1477         -  MemPage *pPage;
  1478         -
  1479   1479     assert( amt>=0 );
  1480   1480     assert( offset>=0 );
         1481  +  if( pCur->isValid==0 ){
         1482  +    return pCur->status;
         1483  +  }
  1481   1484     assert( pCur->pPage!=0 );
  1482         -  pPage = pCur->pPage;
  1483         -  if( pCur->idx >= pPage->nCell || pPage->intKey ){
  1484         -    assert( amt==0 );
  1485         -    return SQLITE_OK;
  1486         -  }
         1485  +  assert( pCur->pPage->intKey==0 );
         1486  +  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  1487   1487     return getPayload(pCur, offset, amt, (unsigned char*)pBuf, 0);
  1488   1488   }
  1489   1489   
  1490   1490   /*
  1491   1491   ** Return a pointer to the key of record that cursor pCur
  1492   1492   ** is point to if the entire key is in contiguous memory.
  1493   1493   ** If the key is split up among multiple tables, return 0.
................................................................................
  1508   1508   */
  1509   1509   void *sqlite3BtreeKeyFetch(BtCursor *pCur){
  1510   1510     unsigned char *aPayload;
  1511   1511     MemPage *pPage;
  1512   1512     Btree *pBt;
  1513   1513     u64 nData, nKey;
  1514   1514   
  1515         -  assert( pCur!=0 && pCur->pPage!=0 );
         1515  +  assert( pCur!=0 );
         1516  +  if( !pCur->isValid ){
         1517  +    return 0;
         1518  +  }
         1519  +  assert( pCur->pPage!=0 );
         1520  +  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  1516   1521     pBt = pCur->pBt;
  1517   1522     pPage = pCur->pPage;
  1518   1523     assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
         1524  +  assert( pPage->intKey==0 );
  1519   1525     aPayload = pPage->aCell[pCur->idx];
  1520   1526     aPayload += 2;  /* Skip the next cell index */
  1521   1527     if( !pPage->leaf ){
  1522   1528       aPayload += 4;  /* Skip the child pointer */
  1523   1529     }
  1524   1530     if( !pPage->zeroData ){
  1525   1531       aPayload += getVarint(aPayload, &nData);
  1526   1532     }
  1527   1533     aPayload += getVarint(aPayload, &nKey);
  1528         -  if( pPage->intKey || nKey>pBt->maxLocal ){
         1534  +  if( nKey>pBt->maxLocal ){
  1529   1535       return 0;
  1530   1536     }
  1531   1537     return aPayload;
  1532   1538   }
  1533   1539   
  1534   1540   
  1535   1541   /*
................................................................................
  1537   1543   ** cursor currently points to.  Always return SQLITE_OK.
  1538   1544   ** Failure is not possible.  If the cursor is not currently
  1539   1545   ** pointing to an entry (which can happen, for example, if
  1540   1546   ** the database is empty) then *pSize is set to 0.
  1541   1547   */
  1542   1548   int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
  1543   1549     MemPage *pPage;
         1550  +  unsigned char *cell;
         1551  +  u64 size;
  1544   1552   
         1553  +  if( !pCur->isValid ){
         1554  +    return pCur->status ? pCur->status : SQLITE_INTERNAL;
         1555  +  }
  1545   1556     pPage = pCur->pPage;
  1546   1557     assert( pPage!=0 );
  1547         -  if( pCur->idx >= pPage->nCell || pPage->zeroData ){
         1558  +  assert( pPage->isInit );
         1559  +  if( pPage->zeroData ){
  1548   1560       *pSize = 0;
  1549   1561     }else{
  1550         -    unsigned char *cell;
  1551         -    u64 size;
         1562  +    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  1552   1563       cell = pPage->aCell[pCur->idx];
  1553   1564       cell += 2;   /* Skip the offset to the next cell */
  1554   1565       if( !pPage->leaf ){
  1555   1566         cell += 4;  /* Skip the child pointer */
  1556   1567       }
  1557   1568       getVarint(cell, &size);
  1558   1569       assert( (size & 0x00000000ffffffff)==size );
................................................................................
  1567   1578   ** begins at "offset".
  1568   1579   **
  1569   1580   ** Return SQLITE_OK on success or an error code if anything goes
  1570   1581   ** wrong.  An error is returned if "offset+amt" is larger than
  1571   1582   ** the available payload.
  1572   1583   */
  1573   1584   int sqlite3BtreeData(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  1574         -  MemPage *pPage;
  1575         -
         1585  +  if( !pCur->isValid ){
         1586  +    return pCur->status ? pCur->status : SQLITE_INTERNAL;
         1587  +  }
  1576   1588     assert( amt>=0 );
  1577   1589     assert( offset>=0 );
  1578   1590     assert( pCur->pPage!=0 );
  1579         -  pPage = pCur->pPage;
  1580         -  if( pCur->idx >= pPage->nCell ){
  1581         -    return 0;
  1582         -  }
         1591  +  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  1583   1592     return getPayload(pCur, offset, amt, pBuf, 1);
  1584   1593   }
  1585   1594   
  1586   1595   /*
  1587   1596   ** Move the cursor down to a new child page.  The newPgno argument is the
  1588   1597   ** page number of the child page in the byte order of the disk image.
  1589   1598   */
  1590   1599   static int moveToChild(BtCursor *pCur, u32 newPgno){
  1591   1600     int rc;
  1592   1601     MemPage *pNewPage;
  1593   1602     MemPage *pOldPage;
  1594   1603     Btree *pBt = pCur->pBt;
  1595   1604   
         1605  +  assert( pCur->isValid );
  1596   1606     rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage);
  1597   1607     if( rc ) return rc;
  1598   1608     pNewPage->idxParent = pCur->idx;
  1599   1609     pOldPage = pCur->pPage;
  1600   1610     pOldPage->idxShift = 0;
  1601   1611     releasePage(pOldPage);
  1602   1612     pCur->pPage = pNewPage;
................................................................................
  1633   1643   */
  1634   1644   static void moveToParent(BtCursor *pCur){
  1635   1645     Pgno oldPgno;
  1636   1646     MemPage *pParent;
  1637   1647     MemPage *pPage;
  1638   1648     int idxParent;
  1639   1649   
         1650  +  assert( pCur->isValid );
  1640   1651     pPage = pCur->pPage;
  1641   1652     assert( pPage!=0 );
  1642   1653     assert( !isRootPage(pPage) );
  1643   1654     pParent = pPage->pParent;
  1644   1655     assert( pParent!=0 );
  1645   1656     idxParent = pPage->idxParent;
  1646   1657     sqlite3pager_ref(pParent->aData);
................................................................................
  1682   1693   */
  1683   1694   static int moveToRoot(BtCursor *pCur){
  1684   1695     MemPage *pRoot;
  1685   1696     int rc;
  1686   1697     Btree *pBt = pCur->pBt;
  1687   1698   
  1688   1699     rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0);
  1689         -  if( rc ) return rc;
         1700  +  if( rc ){
         1701  +    pCur->isValid = 0;
         1702  +    return rc;
         1703  +  }
  1690   1704     releasePage(pCur->pPage);
  1691   1705     pCur->pPage = pRoot;
  1692   1706     pCur->idx = 0;
  1693   1707     if( pRoot->nCell==0 && !pRoot->leaf ){
  1694   1708       Pgno subpage;
  1695   1709       assert( pRoot->pgno==1 );
  1696   1710       subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+6]);
  1697   1711       assert( subpage>0 );
  1698   1712       rc = moveToChild(pCur, subpage);
  1699   1713     }
         1714  +  pCur->isValid = pCur->pPage->nCell>0;
  1700   1715     return rc;
  1701   1716   }
  1702   1717   
  1703   1718   /*
  1704   1719   ** Move the cursor down to the left-most leaf entry beneath the
  1705   1720   ** entry to which it is currently pointing.
  1706   1721   */
  1707   1722   static int moveToLeftmost(BtCursor *pCur){
  1708   1723     Pgno pgno;
  1709   1724     int rc;
  1710   1725     MemPage *pPage;
  1711   1726   
         1727  +  assert( pCur->isValid );
  1712   1728     while( !(pPage = pCur->pPage)->leaf ){
  1713   1729       assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  1714   1730       pgno = get4byte(&pPage->aCell[pCur->idx][2]);
  1715   1731       rc = moveToChild(pCur, pgno);
  1716   1732       if( rc ) return rc;
  1717   1733     }
  1718   1734     return SQLITE_OK;
................................................................................
  1726   1742   ** finds the right-most entry beneath the *page*.
  1727   1743   */
  1728   1744   static int moveToRightmost(BtCursor *pCur){
  1729   1745     Pgno pgno;
  1730   1746     int rc;
  1731   1747     MemPage *pPage;
  1732   1748   
         1749  +  assert( pCur->isValid );
  1733   1750     while( !(pPage = pCur->pPage)->leaf ){
  1734   1751       pgno = get4byte(&pPage->aData[pPage->hdrOffset+6]);
  1735   1752       pCur->idx = pPage->nCell;
  1736   1753       rc = moveToChild(pCur, pgno);
  1737   1754       if( rc ) return rc;
  1738   1755     }
  1739   1756     pCur->idx = pPage->nCell - 1;
................................................................................
  1742   1759   
  1743   1760   /* Move the cursor to the first entry in the table.  Return SQLITE_OK
  1744   1761   ** on success.  Set *pRes to 0 if the cursor actually points to something
  1745   1762   ** or set *pRes to 1 if the table is empty.
  1746   1763   */
  1747   1764   int sqlite3BtreeFirst(BtCursor *pCur, int *pRes){
  1748   1765     int rc;
  1749         -  if( pCur->pPage==0 ) return SQLITE_ABORT;
         1766  +  if( pCur->status ){
         1767  +    return pCur->status;
         1768  +  }
  1750   1769     rc = moveToRoot(pCur);
  1751   1770     if( rc ) return rc;
  1752         -  if( pCur->pPage->nCell==0 ){
         1771  +  if( pCur->isValid==0 ){
         1772  +    assert( pCur->pPage->nCell==0 );
  1753   1773       *pRes = 1;
  1754   1774       return SQLITE_OK;
  1755   1775     }
         1776  +  assert( pCur->pPage->nCell>0 );
  1756   1777     *pRes = 0;
  1757   1778     rc = moveToLeftmost(pCur);
  1758         -  pCur->eSkip = SKIP_NONE;
  1759   1779     return rc;
  1760   1780   }
  1761   1781   
  1762   1782   /* Move the cursor to the last entry in the table.  Return SQLITE_OK
  1763   1783   ** on success.  Set *pRes to 0 if the cursor actually points to something
  1764   1784   ** or set *pRes to 1 if the table is empty.
  1765   1785   */
  1766   1786   int sqlite3BtreeLast(BtCursor *pCur, int *pRes){
  1767   1787     int rc;
  1768         -  if( pCur->pPage==0 ) return SQLITE_ABORT;
         1788  +  if( pCur->status ){
         1789  +    return pCur->status;
         1790  +  }
  1769   1791     rc = moveToRoot(pCur);
  1770   1792     if( rc ) return rc;
  1771         -  assert( pCur->pPage->isInit );
  1772         -  if( pCur->pPage->nCell==0 ){
         1793  +  if( pCur->isValid==0 ){
         1794  +    assert( pCur->pPage->nCell==0 );
  1773   1795       *pRes = 1;
  1774   1796       return SQLITE_OK;
  1775   1797     }
         1798  +  assert( pCur->isValid );
  1776   1799     *pRes = 0;
  1777   1800     rc = moveToRightmost(pCur);
  1778         -  pCur->eSkip = SKIP_NONE;
  1779   1801     return rc;
  1780   1802   }
  1781   1803   
  1782   1804   /* Move the cursor so that it points to an entry near pKey/nKey.
  1783   1805   ** Return a success code.
  1784   1806   **
  1785   1807   ** For INTKEY tables, only the nKey parameter is used.  pKey is
................................................................................
  1805   1827   **                  exactly matches pKey.
  1806   1828   **
  1807   1829   **     *pRes>0      The cursor is left pointing at an entry that
  1808   1830   **                  is larger than pKey.
  1809   1831   */
  1810   1832   int sqlite3BtreeMoveto(BtCursor *pCur, const void *pKey, u64 nKey, int *pRes){
  1811   1833     int rc;
  1812         -  if( pCur->pPage==0 ) return SQLITE_ABORT;
  1813         -  pCur->eSkip = SKIP_NONE;
         1834  +
         1835  +  if( pCur->status ){
         1836  +    return pCur->status;
         1837  +  }
  1814   1838     rc = moveToRoot(pCur);
  1815   1839     if( rc ) return rc;
         1840  +  assert( pCur->pPage );
         1841  +  assert( pCur->pPage->isInit );
         1842  +  if( pCur->isValid==0 ){
         1843  +    assert( pCur->pPage->nCell==0 );
         1844  +    return SQLITE_OK;
         1845  +  }
  1816   1846     for(;;){
  1817   1847       int lwr, upr;
  1818   1848       Pgno chldPg;
  1819   1849       MemPage *pPage = pCur->pPage;
  1820   1850       int c = -1;  /* pRes return if table is empty must be -1 */
  1821   1851       lwr = 0;
  1822   1852       upr = pPage->nCell-1;
................................................................................
  1861   1891       }else if( lwr>=pPage->nCell ){
  1862   1892         chldPg = get4byte(&pPage->aData[pPage->hdrOffset+6]);
  1863   1893       }else{
  1864   1894         chldPg = get4byte(&pPage->aCell[lwr][2]);
  1865   1895       }
  1866   1896       if( chldPg==0 ){
  1867   1897         pCur->iMatch = c;
         1898  +      assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  1868   1899         if( pRes ) *pRes = c;
  1869   1900         return SQLITE_OK;
  1870   1901       }
  1871   1902       pCur->idx = lwr;
  1872   1903       rc = moveToChild(pCur, chldPg);
  1873         -    if( rc ) return rc;
         1904  +    if( rc ){
         1905  +      return rc;
         1906  +    }
  1874   1907     }
  1875   1908     /* NOT REACHED */
  1876   1909   }
         1910  +
         1911  +/*
         1912  +** Return TRUE if the cursor is not pointing at an entry of the table.
         1913  +**
         1914  +** TRUE will be returned after a call to sqlite3BtreeNext() moves
         1915  +** past the last entry in the table or sqlite3BtreePrev() moves past
         1916  +** the first entry.  TRUE is also returned if the table is empty.
         1917  +*/
         1918  +int sqlite3BtreeEof(BtCursor *pCur){
         1919  +  return pCur->isValid==0;
         1920  +}
  1877   1921   
  1878   1922   /*
  1879   1923   ** Advance the cursor to the next entry in the database.  If
  1880   1924   ** successful then set *pRes=0.  If the cursor
  1881   1925   ** was already pointing to the last entry in the database before
  1882   1926   ** this routine was called, then set *pRes=1.
  1883   1927   */
  1884   1928   int sqlite3BtreeNext(BtCursor *pCur, int *pRes){
  1885   1929     int rc;
  1886   1930     MemPage *pPage = pCur->pPage;
  1887   1931     assert( pRes!=0 );
  1888         -  if( pPage==0 ){
  1889         -    *pRes = 1;
  1890         -    return SQLITE_ABORT;
  1891         -  }
  1892         -  assert( pPage->isInit );
  1893         -  assert( pCur->eSkip!=SKIP_INVALID );
  1894         -  if( pPage->nCell==0 ){
         1932  +  if( pCur->isValid==0 ){
  1895   1933       *pRes = 1;
  1896   1934       return SQLITE_OK;
  1897   1935     }
         1936  +  assert( pPage->isInit );
  1898   1937     assert( pCur->idx<pPage->nCell );
  1899         -  if( pCur->eSkip==SKIP_NEXT ){
  1900         -    pCur->eSkip = SKIP_NONE;
  1901         -    *pRes = 0;
  1902         -    return SQLITE_OK;
  1903         -  }
  1904         -  pCur->eSkip = SKIP_NONE;
  1905   1938     pCur->idx++;
  1906   1939     if( pCur->idx>=pPage->nCell ){
  1907   1940       if( !pPage->leaf ){
  1908   1941         rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+6]));
  1909   1942         if( rc ) return rc;
  1910   1943         rc = moveToLeftmost(pCur);
  1911   1944         *pRes = 0;
  1912   1945         return rc;
  1913   1946       }
  1914   1947       do{
  1915   1948         if( isRootPage(pPage) ){
  1916   1949           *pRes = 1;
         1950  +        pCur->isValid = 0;
  1917   1951           return SQLITE_OK;
  1918   1952         }
  1919   1953         moveToParent(pCur);
  1920   1954         pPage = pCur->pPage;
  1921   1955       }while( pCur->idx>=pPage->nCell );
  1922   1956       *pRes = 0;
  1923   1957       return SQLITE_OK;
................................................................................
  1936   1970   ** was already pointing to the first entry in the database before
  1937   1971   ** this routine was called, then set *pRes=1.
  1938   1972   */
  1939   1973   int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){
  1940   1974     int rc;
  1941   1975     Pgno pgno;
  1942   1976     MemPage *pPage;
  1943         -  pPage = pCur->pPage;
  1944         -  if( pPage==0 ){
  1945         -    *pRes = 1;
  1946         -    return SQLITE_ABORT;
  1947         -  }
  1948         -  assert( pPage->isInit );
  1949         -  assert( pCur->eSkip!=SKIP_INVALID );
  1950         -  if( pPage->nCell==0 ){
         1977  +  if( pCur->isValid==0 ){
  1951   1978       *pRes = 1;
  1952   1979       return SQLITE_OK;
  1953   1980     }
  1954         -  if( pCur->eSkip==SKIP_PREV ){
  1955         -    pCur->eSkip = SKIP_NONE;
  1956         -    *pRes = 0;
  1957         -    return SQLITE_OK;
  1958         -  }
  1959         -  pCur->eSkip = SKIP_NONE;
         1981  +  pPage = pCur->pPage;
         1982  +  assert( pPage->isInit );
  1960   1983     assert( pCur->idx>=0 );
  1961   1984     if( !pPage->leaf ){
  1962   1985       pgno = get4byte(&pPage->aCell[pCur->idx][2]);
  1963   1986       rc = moveToChild(pCur, pgno);
  1964   1987       if( rc ) return rc;
  1965   1988       rc = moveToRightmost(pCur);
  1966   1989     }else{
  1967   1990       while( pCur->idx==0 ){
  1968   1991         if( isRootPage(pPage) ){
  1969         -        if( pRes ) *pRes = 1;
         1992  +        pCur->isValid = 0;
         1993  +        *pRes = 1;
  1970   1994           return SQLITE_OK;
  1971   1995         }
  1972   1996         moveToParent(pCur);
  1973   1997         pPage = pCur->pPage;
  1974   1998       }
  1975   1999       pCur->idx--;
  1976   2000       rc = SQLITE_OK;
................................................................................
  2920   2944     int loc;
  2921   2945     int szNew;
  2922   2946     MemPage *pPage;
  2923   2947     Btree *pBt = pCur->pBt;
  2924   2948     unsigned char *oldCell;
  2925   2949     unsigned char newCell[MX_CELL_SIZE];
  2926   2950   
  2927         -  if( pCur->pPage==0 ){
  2928         -    return SQLITE_ABORT;  /* A rollback destroyed this cursor */
         2951  +  if( pCur->status ){
         2952  +    return pCur->status;  /* A rollback destroyed this cursor */
  2929   2953     }
  2930   2954     if( !pBt->inTrans || nKey+nData==0 ){
  2931   2955       /* Must start a transaction before doing an insert */
  2932   2956       return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  2933   2957     }
  2934   2958     assert( !pBt->readOnly );
  2935   2959     if( !pCur->wrFlag ){
................................................................................
  2965   2989       assert( pPage->leaf );
  2966   2990     }
  2967   2991     insertCell(pPage, pCur->idx, newCell, szNew);
  2968   2992     rc = balance(pPage);
  2969   2993     /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  2970   2994     /* fflush(stdout); */
  2971   2995     moveToRoot(pCur);
  2972         -  pCur->eSkip = SKIP_INVALID;
  2973   2996     return rc;
  2974   2997   }
  2975   2998   
  2976   2999   /*
  2977   3000   ** Delete the entry that the cursor is pointing to.  The cursor
  2978   3001   ** is left pointing at a random location.
  2979   3002   */
................................................................................
  2981   3004     MemPage *pPage = pCur->pPage;
  2982   3005     unsigned char *pCell;
  2983   3006     int rc;
  2984   3007     Pgno pgnoChild;
  2985   3008     Btree *pBt = pCur->pBt;
  2986   3009   
  2987   3010     assert( pPage->isInit );
  2988         -  if( pCur->pPage==0 ){
  2989         -    return SQLITE_ABORT;  /* A rollback destroyed this cursor */
         3011  +  if( pCur->status ){
         3012  +    return pCur->status;  /* A rollback destroyed this cursor */
  2990   3013     }
  2991   3014     if( !pBt->inTrans ){
  2992   3015       /* Must start a transaction before doing a delete */
  2993   3016       return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  2994   3017     }
  2995   3018     assert( !pBt->readOnly );
  2996   3019     if( pCur->idx >= pPage->nCell ){
................................................................................
  3272   3295     }
  3273   3296     if( !pPage->leaf ){
  3274   3297       printf("right_child: %d\n", get4byte(&pPage->aData[6]));
  3275   3298     }
  3276   3299     nFree = 0;
  3277   3300     i = 0;
  3278   3301     idx = get2byte(&pPage->aData[hdrOffset+1]);
  3279         -  while( idx>0 && idx<SQLITE_USABLE_SIZE ){
         3302  +  while( idx>0 && idx<pPage->pBt->pageSize ){
  3280   3303       int sz = get2byte(&pPage->aData[idx+2]);
  3281   3304       sprintf(range,"%d..%d", idx, idx+sz-1);
  3282   3305       nFree += sz;
  3283   3306       printf("freeblock %2d: i=%-10s size=%-4d total=%d\n",
  3284   3307          i, range, sz, nFree);
  3285   3308       idx = get2byte(&pPage->aData[idx]);
  3286   3309       i++;
................................................................................
  3342   3365     }else{
  3343   3366       aResult[3] = 0;
  3344   3367       aResult[6] = 0;
  3345   3368     }
  3346   3369     aResult[4] = pPage->nFree;
  3347   3370     cnt = 0;
  3348   3371     idx = get2byte(&pPage->aData[pPage->hdrOffset+1]);
  3349         -  while( idx>0 && idx<SQLITE_USABLE_SIZE ){
         3372  +  while( idx>0 && idx<pPage->pBt->pageSize ){
  3350   3373       cnt++;
  3351   3374       idx = get2byte(&pPage->aData[idx]);
  3352   3375     }
  3353   3376     aResult[5] = cnt;
  3354   3377     aResult[7] = pPage->leaf ? 0 : get4byte(&pPage->aData[pPage->hdrOffset+6]);
  3355   3378     return SQLITE_OK;
  3356   3379   }
................................................................................
  3703   3726   */
  3704   3727   int sqlite3BtreeCopyFile(Btree *pBtTo, Btree *pBtFrom){
  3705   3728     int rc = SQLITE_OK;
  3706   3729     Pgno i, nPage, nToPage;
  3707   3730   
  3708   3731     if( !pBtTo->inTrans || !pBtFrom->inTrans ) return SQLITE_ERROR;
  3709   3732     if( pBtTo->pCursor ) return SQLITE_BUSY;
  3710         -  memcpy(pBtTo->pPage1, pBtFrom->pPage1, SQLITE_USABLE_SIZE);
         3733  +  memcpy(pBtTo->pPage1, pBtFrom->pPage1, pBtFrom->pageSize);
  3711   3734     rc = sqlite3pager_overwrite(pBtTo->pPager, 1, pBtFrom->pPage1);
  3712   3735     nToPage = sqlite3pager_pagecount(pBtTo->pPager);
  3713   3736     nPage = sqlite3pager_pagecount(pBtFrom->pPager);
  3714   3737     for(i=2; rc==SQLITE_OK && i<=nPage; i++){
  3715   3738       void *pPage;
  3716   3739       rc = sqlite3pager_get(pBtFrom->pPager, i, &pPage);
  3717   3740       if( rc ) break;

Changes to src/btree.h.

     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This header file defines the interface that the sqlite B-Tree file
    13     13   ** subsystem.  See comments in the source code for a detailed description
    14     14   ** of what each interface routine does.
    15     15   **
    16         -** @(#) $Id: btree.h,v 1.38 2004/05/07 13:30:42 drh Exp $
           16  +** @(#) $Id: btree.h,v 1.39 2004/05/07 23:50:57 drh Exp $
    17     17   */
    18     18   #ifndef _BTREE_H_
    19     19   #define _BTREE_H_
    20     20   
    21     21   /*
    22     22   ** Forward declarations of structure
    23     23   */
................................................................................
    68     68   int sqlite3BtreeMoveto(BtCursor*, const void *pKey, u64 nKey, int *pRes);
    69     69   int sqlite3BtreeDelete(BtCursor*);
    70     70   int sqlite3BtreeInsert(BtCursor*, const void *pKey, u64 nKey,
    71     71                                     const void *pData, int nData);
    72     72   int sqlite3BtreeFirst(BtCursor*, int *pRes);
    73     73   int sqlite3BtreeLast(BtCursor*, int *pRes);
    74     74   int sqlite3BtreeNext(BtCursor*, int *pRes);
           75  +int sqlite3BtreeEof(BtCursor*);
    75     76   int sqlite3BtreePrevious(BtCursor*, int *pRes);
    76     77   int sqlite3BtreeKeySize(BtCursor*, u64 *pSize);
    77     78   int sqlite3BtreeKey(BtCursor*, u32 offset, u32 amt, void*);
    78     79   void *sqlite3BtreeKeyFetch(BtCursor*);
    79     80   int sqlite3BtreeDataSize(BtCursor*, u32 *pSize);
    80     81   int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void*);
    81     82   

Changes to src/test3.c.

     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Code for testing the btree.c module in SQLite.  This code
    13     13   ** is not included in the SQLite library.  It is used for automated
    14     14   ** testing of the SQLite library.
    15     15   **
    16         -** $Id: test3.c,v 1.27 2004/05/07 17:57:50 drh Exp $
           16  +** $Id: test3.c,v 1.28 2004/05/07 23:50:57 drh Exp $
    17     17   */
    18     18   #include "sqliteInt.h"
    19     19   #include "pager.h"
    20     20   #include "btree.h"
    21     21   #include "tcl.h"
    22     22   #include <stdlib.h>
    23     23   #include <string.h>
................................................................................
   805    805       Tcl_AppendResult(interp, errorName(rc), 0);
   806    806       return TCL_ERROR;
   807    807     }
   808    808     sprintf(zBuf,"%d",res);
   809    809     Tcl_AppendResult(interp, zBuf, 0);
   810    810     return SQLITE_OK;
   811    811   }
          812  +
          813  +/*
          814  +** Usage:   btree_eof ID
          815  +**
          816  +** Return TRUE if the given cursor is not pointing at a valid entry.
          817  +** Return FALSE if the cursor does point to a valid entry.
          818  +*/
          819  +static int btree_eof(
          820  +  void *NotUsed,
          821  +  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
          822  +  int argc,              /* Number of arguments */
          823  +  const char **argv      /* Text of each argument */
          824  +){
          825  +  BtCursor *pCur;
          826  +  char zBuf[50];
          827  +
          828  +  if( argc!=2 ){
          829  +    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
          830  +       " ID\"", 0);
          831  +    return TCL_ERROR;
          832  +  }
          833  +  if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR;
          834  +  sprintf(zBuf, "%d", sqlite3BtreeEof(pCur));
          835  +  Tcl_AppendResult(interp, zBuf, 0);
          836  +  return SQLITE_OK;
          837  +}
   812    838   
   813    839   /*
   814    840   ** Usage:   btree_keysize ID
   815    841   **
   816    842   ** Return the number of bytes of key.  
   817    843   */
   818    844   static int btree_keysize(
................................................................................
  1018   1044        { "btree_cursor",             (Tcl_CmdProc*)btree_cursor             },
  1019   1045        { "btree_close_cursor",       (Tcl_CmdProc*)btree_close_cursor       },
  1020   1046        { "btree_move_to",            (Tcl_CmdProc*)btree_move_to            },
  1021   1047        { "btree_delete",             (Tcl_CmdProc*)btree_delete             },
  1022   1048        { "btree_insert",             (Tcl_CmdProc*)btree_insert             },
  1023   1049        { "btree_next",               (Tcl_CmdProc*)btree_next               },
  1024   1050        { "btree_prev",               (Tcl_CmdProc*)btree_prev               },
         1051  +     { "btree_eof",                (Tcl_CmdProc*)btree_eof                },
  1025   1052        { "btree_keysize",            (Tcl_CmdProc*)btree_keysize            },
  1026   1053        { "btree_key",                (Tcl_CmdProc*)btree_key                },
  1027   1054        { "btree_data",               (Tcl_CmdProc*)btree_data               },
  1028   1055        { "btree_payload_size",       (Tcl_CmdProc*)btree_payload_size       },
  1029   1056        { "btree_first",              (Tcl_CmdProc*)btree_first              },
  1030   1057        { "btree_last",               (Tcl_CmdProc*)btree_last               },
  1031   1058        { "btree_cursor_dump",        (Tcl_CmdProc*)btree_cursor_dump        },

Changes to test/btree.test.

     7      7   #    May you find forgiveness for yourself and forgive others.
     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #***********************************************************************
    11     11   # This file implements regression tests for SQLite library.  The
    12     12   # focus of this script is btree database backend
    13     13   #
    14         -# $Id: btree.test,v 1.16 2004/05/07 17:57:50 drh Exp $
           14  +# $Id: btree.test,v 1.17 2004/05/07 23:50:58 drh Exp $
    15     15   
    16     16   
    17     17   set testdir [file dirname $argv0]
    18     18   source $testdir/tester.tcl
    19     19   
    20     20   # Basic functionality.  Open and close a database.
    21     21   #
................................................................................
   181    181   do_test btree-3.18 {
   182    182     btree_next $::c1
   183    183     btree_key $::c1
   184    184   } {600}
   185    185   do_test btree-3.19 {
   186    186     btree_data $::c1
   187    187   } {6.00}
   188         -do_test btree-3.20 {
          188  +do_test btree-3.20.1 {
   189    189     btree_next $::c1
   190    190     btree_key $::c1
   191    191   } {0}
          192  +do_test btree-3.20.2 {
          193  +  btree_eof $::c1
          194  +} {1}
   192    195   do_test btree-3.21 {
   193         -  btree_data $::c1
   194         -} {}
          196  +  set rc [catch {btree_data $::c1} res]
          197  +  lappend rc $res
          198  +} {1 SQLITE_INTERNAL}
   195    199   
   196    200   # Commit the changes, reopen and reread the data
   197    201   #
   198    202   do_test btree-3.22 {
   199    203     set rc [catch {btree_close_cursor $::c1} msg]
   200    204     lappend rc $msg
   201    205   } {0 {}}
................................................................................
   266    270     btree_data $::c1
   267    271   } {6.00}
   268    272   do_test btree-3.39 {
   269    273     btree_next $::c1
   270    274     btree_key $::c1
   271    275   } {0}
   272    276   do_test btree-3.40 {
   273         -  btree_data $::c1
   274         -} {}
          277  +  set rc [catch {btree_data $::c1} res]
          278  +  lappend rc $res
          279  +} {1 SQLITE_INTERNAL}
   275    280   do_test btree-3.41 {
   276    281     lindex [btree_pager_stats $::b1] 1
   277    282   } {1}
   278    283   
   279    284   
   280    285   # Now try a delete
   281    286   #
................................................................................
   303    308     btree_key $::c1
   304    309   } {400}
   305    310   do_test btree-4.4 {
   306    311     btree_move_to $::c1 0
   307    312     set r {}
   308    313     while 1 {
   309    314       set key [btree_key $::c1]
   310         -    if {$key==0} break
          315  +    if {[btree_eof $::c1]} break
   311    316       lappend r $key
   312    317       lappend r [btree_data $::c1]
   313    318       btree_next $::c1
   314    319     }
   315    320     set r   
   316    321   } {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}
   317    322   
................................................................................
   319    324   #
   320    325   do_test btree-4.5 {
   321    326     btree_commit $::b1
   322    327     btree_move_to $::c1 0
   323    328     set r {}
   324    329     while 1 {
   325    330       set key [btree_key $::c1]
   326         -    if {$key==0} break
          331  +    if {[btree_eof $::c1]} break
   327    332       lappend r $key
   328    333       lappend r [btree_data $::c1]
   329    334       btree_next $::c1
   330    335     }
   331    336     set r   
   332    337   } {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}
   333    338   
................................................................................
   348    353     lindex [btree_pager_stats $::b1] 1
   349    354   } {1}
   350    355   do_test btree-4.9 {
   351    356     set r {}
   352    357     btree_first $::c1
   353    358     while 1 {
   354    359       set key [btree_key $::c1]
   355         -    if {$key==0} break
          360  +    if {[btree_eof $::c1]} break
   356    361       lappend r $key
   357    362       lappend r [btree_data $::c1]
   358    363       btree_next $::c1
   359    364     }
   360    365     set r   
   361    366   } {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}
   362    367   
................................................................................
   392    397        140 150
   393    398     btree_commit $::b1
   394    399     btree_get_meta $::b1
   395    400   } {0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150}
   396    401   
   397    402   proc select_all {cursor} {
   398    403     set r {}
   399         -  btree_move_to $cursor {}
   400         -  while 1 {
          404  +  btree_first $cursor
          405  +  while {![btree_eof $cursor]} {
   401    406       set key [btree_key $cursor]
   402         -    if {$key==""} break
   403         -    lappend r $key
   404         -    lappend r [btree_data $cursor]
   405         -    btree_next $cursor
   406         -  }
   407         -  return $r
   408         -}
   409         -proc select_all_intkey {cursor} {
   410         -  set r {}
   411         -  btree_move_to $cursor 0
   412         -  while 1 {
   413         -    set key [btree_key $cursor]
   414         -    if {$key==0} break
   415    407       lappend r $key
   416    408       lappend r [btree_data $cursor]
   417    409       btree_next $cursor
   418    410     }
   419    411     return $r
   420    412   }
   421    413   proc select_keys {cursor} {
   422    414     set r {}
   423         -  btree_move_to $cursor {}
   424         -  while 1 {
          415  +  btree_first $cursor
          416  +  while {![btree_eof $cursor]} {
   425    417       set key [btree_key $cursor]
   426         -    if {$key==""} break
   427    418       lappend r $key
   428    419       btree_next $cursor
   429    420     }
   430    421     return $r
   431    422   }
   432    423   
   433    424   # Try to create a new table in the database file
................................................................................
   445    436   } {1}
   446    437   do_test btree-6.2.2 {
   447    438     set ::c2 [btree_cursor $::b1 $::t2 1]
   448    439     lindex [btree_pager_stats $::b1] 1
   449    440   } {2}
   450    441   do_test btree-6.2.3 {
   451    442     btree_insert $::c2 ten 10
          443  +  btree_move_to $::c2 ten
   452    444     btree_key $::c2
   453    445   } {ten}
   454    446   do_test btree-6.3 {
   455    447     btree_commit $::b1
   456    448     set ::c1 [btree_cursor $::b1 1 1]
   457    449     lindex [btree_pager_stats $::b1] 1
   458    450   } {2}
   459    451   do_test btree-6.3.1 {
   460         -  select_all_intkey $::c1
          452  +  select_all $::c1
   461    453   } {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}
   462    454   #btree_page_dump $::b1 3
   463    455   do_test btree-6.4 {
   464    456     select_all $::c2
   465    457   } {ten 10}
   466    458   
   467    459   # Drop the new table, then create it again anew.
................................................................................
   493    485   } {2}
   494    486   
   495    487   do_test btree-6.9.1 {
   496    488     btree_move_to $::c2 {}
   497    489     btree_key $::c2
   498    490   } {}
   499    491   
   500         -# If we drop table 2 it just clears the table.  Table 2 always exists.
          492  +# If we drop table 1 it just clears the table.  Table 1 always exists.
   501    493   #
   502    494   do_test btree-6.10 {
   503    495     btree_close_cursor $::c1
   504         -  btree_drop_table $::b1 2
   505         -  set ::c1 [btree_cursor $::b1 2 1]
   506         -  btree_move_to $::c1 {}
   507         -  btree_key $::c1
   508         -} {}
          496  +  btree_drop_table $::b1 1
          497  +  set ::c1 [btree_cursor $::b1 1 1]
          498  +  btree_first $::c1
          499  +  btree_eof $::c1
          500  +} {1}
   509    501   do_test btree-6.11 {
   510    502     btree_commit $::b1
   511    503     select_all $::c1
   512    504   } {}
   513    505   do_test btree-6.12 {
   514    506     select_all $::c2
   515    507   } {}
   516    508   do_test btree-6.13 {
   517    509     btree_close_cursor $::c2
   518    510     lindex [btree_pager_stats $::b1] 1
   519         -} {2}
          511  +} {1}
   520    512   
   521    513   # Check to see that pages defragment properly.  To do this test we will
   522    514   # 
   523         -#   1.  Fill the first page table 2 with data.
   524         -#   2.  Delete every other entry of table 2. 
          515  +#   1.  Fill the first page of table 1 with data.
          516  +#   2.  Delete every other entry of table 1.
   525    517   #   3.  Insert a single entry that requires more contiguous
   526    518   #       space than is available.
   527    519   #
   528    520   do_test btree-7.1 {
   529    521     btree_begin_transaction $::b1
   530    522   } {}
   531    523   catch {unset key}
   532    524   catch {unset data}
   533    525   do_test btree-7.2 {
   534         -  for {set i 0} {$i<36} {incr i} {
   535         -    set key [format %03d $i]
   536         -    set data "*** $key ***"
          526  +  # Each record will be 10 bytes in size.
          527  +  #   + 100 bytes of database header
          528  +  #   + 6 bytes of table header
          529  +  #   + 91*10=910 bytes of cells
          530  +  # Totals 1016 bytes.  8 bytes left over
          531  +  # Keys are 1000 through 1090.
          532  +  for {set i 1000} {$i<1091} {incr i} {
          533  +    set key $i
          534  +    set data [format %5d $i]
   537    535       btree_insert $::c1 $key $data
   538    536     }
   539    537     lrange [btree_cursor_dump $::c1] 4 5
   540    538   } {8 1}
   541    539   do_test btree-7.3 {
   542         -  btree_move_to $::c1 000
   543         -  while {[btree_key $::c1]!=""} {
          540  +  for {set i 1001} {$i<1091} {incr i 2} {
          541  +    btree_move_to $::c1 $i
   544    542       btree_delete $::c1
   545         -    btree_next $::c1
   546         -    btree_next $::c1
   547    543     }
          544  +  # Freed 45 blocks.  Total freespace is 458
          545  +  # Keys remaining are even numbers between 1000 and 1090, inclusive
   548    546     lrange [btree_cursor_dump $::c1] 4 5
   549         -} {512 19}
          547  +} {458 46}
   550    548   #btree_page_dump $::b1 2
   551    549   do_test btree-7.4 {
   552         -  btree_insert $::c1 018 {*** 018 ***+++}
          550  +  # The largest free block is 10 bytes long.  So if we insert
          551  +  # a record bigger than 10 bytes it should force a defrag
          552  +  # The record is 20 bytes long.
          553  +  btree_insert $::c1 2000 {123456789_12345}
          554  +  btree_move_to $::c1 2000
   553    555     btree_key $::c1
   554         -} {018}
          556  +} {2000}
   555    557   do_test btree-7.5 {
   556    558     lrange [btree_cursor_dump $::c1] 4 5
   557         -} {480 1}
          559  +} {438 1}
   558    560   #btree_page_dump $::b1 2
   559    561   
   560    562   # Delete an entry to make a hole of a known size, then immediately recreate
   561    563   # that entry.  This tests the path into allocateSpace where the hole exactly
   562    564   # matches the size of the desired space.
   563    565   #
          566  +# Keys are even numbers between 1000 and 1090 and one record of 2000.
          567  +# There are 47 keys total.
          568  +#
   564    569   do_test btree-7.6 {
   565         -  btree_move_to $::c1 007
          570  +  btree_move_to $::c1 1006
   566    571     btree_delete $::c1
   567         -  btree_move_to $::c1 011
          572  +  btree_move_to $::c1 1010
   568    573     btree_delete $::c1
   569    574   } {}
   570    575   do_test btree-7.7 {
   571         -  lindex [btree_cursor_dump $::c1] 5
   572         -} {3}
          576  +  lrange [btree_cursor_dump $::c1] 4 5
          577  +} {458 3}   ;# Create two new holes of 10 bytes each
   573    578   #btree_page_dump $::b1 2
   574    579   do_test btree-7.8 {
   575         -  btree_insert $::c1 007 {*** 007 ***}
   576         -  lindex [btree_cursor_dump $::c1] 5
   577         -} {2}
          580  +  btree_insert $::c1 1006 { 1006}
          581  +  lrange [btree_cursor_dump $::c1] 4 5
          582  +} {448 2}   ;# Filled in the first hole
   578    583   #btree_page_dump $::b1 2
   579    584   
   580    585   # Make sure the freeSpace() routine properly coaleses adjacent memory blocks
   581    586   #
   582    587   do_test btree-7.9 {
   583         -  btree_move_to $::c1 013
          588  +  btree_move_to $::c1 1012
          589  +  btree_delete $::c1
          590  +  lrange [btree_cursor_dump $::c1] 4 5
          591  +} {458 2}  ;# Coalesce with the whole before
          592  +do_test btree-7.10 {
          593  +  btree_move_to $::c1 1008
          594  +  btree_delete $::c1
          595  +  lrange [btree_cursor_dump $::c1] 4 5
          596  +} {468 2}  ;# Coalesce with whole after
          597  +do_test btree-7.11 {
          598  +  btree_move_to $::c1 1030
   584    599     btree_delete $::c1
   585    600     lrange [btree_cursor_dump $::c1] 4 5
   586         -} {536 2}
   587         -do_test btree-7.10 {
   588         -  btree_move_to $::c1 009
          601  +} {478 3}   ;# Make a new hole
          602  +do_test btree-7.13 {
          603  +  btree_move_to $::c1 1034
   589    604     btree_delete $::c1
   590    605     lrange [btree_cursor_dump $::c1] 4 5
   591         -} {564 2}
   592         -do_test btree-7.11 {
   593         -  btree_move_to $::c1 018
          606  +} {488 4}   ;# Make another hole
          607  +do_test btree-7.14 {
          608  +  btree_move_to $::c1 1032
   594    609     btree_delete $::c1
   595    610     lrange [btree_cursor_dump $::c1] 4 5
   596         -} {596 2}
   597         -do_test btree-7.13 {
   598         -  btree_move_to $::c1 033
   599         -  btree_delete $::c1
   600         -  lrange [btree_cursor_dump $::c1] 4 5
   601         -} {624 3}
   602         -do_test btree-7.14 {
   603         -  btree_move_to $::c1 035
   604         -  btree_delete $::c1
   605         -  lrange [btree_cursor_dump $::c1] 4 5
   606         -} {652 2}
          611  +} {498 3}   ;# The freed space should coalesce on both ends
   607    612   #btree_page_dump $::b1 2
   608    613   do_test btree-7.15 {
   609    614     lindex [btree_pager_stats $::b1] 1
   610         -} {2}
          615  +} {1}
   611    616   
   612    617   # Check to see that data on overflow pages work correctly.
   613    618   #
   614    619   do_test btree-8.1 {
   615    620     set data "*** This is a very long key "
   616         -  while {[string length $data]<256} {append data $data}
          621  +  while {[string length $data]<1234} {append data $data}
   617    622     set ::data $data
   618         -  btree_insert $::c1 020 $data
          623  +  btree_insert $::c1 2020 $data
   619    624   } {}
   620    625   #btree_page_dump $::b1 2
   621    626   do_test btree-8.1.1 {
   622    627     lindex [btree_pager_stats $::b1] 1
   623         -} {2}
          628  +} {1}
   624    629   #btree_pager_ref_dump $::b1
   625    630   do_test btree-8.2 {
          631  +  btree_move_to $::c1 2020
   626    632     string length [btree_data $::c1]
   627    633   } [string length $::data]
   628    634   do_test btree-8.3 {
   629    635     btree_data $::c1
   630    636   } $::data
   631    637   do_test btree-8.4 {
   632    638     btree_delete $::c1
................................................................................
   634    640   do_test btree-8.4.1 {
   635    641     lindex [btree_get_meta $::b1] 0
   636    642   } [expr {int(([string length $::data]-238+1019)/1020)}]
   637    643   do_test btree-8.5 {
   638    644     set data "*** This is an even longer key"
   639    645     while {[string length $data]<2000} {append data $data}
   640    646     set ::data $data
   641         -  btree_insert $::c1 020 $data
          647  +  btree_insert $::c1 2030 $data
   642    648   } {}
   643    649   do_test btree-8.6 {
          650  +  btree_move_to 2030
   644    651     string length [btree_data $::c1]
   645    652   } [string length $::data]
   646    653   do_test btree-8.7 {
   647    654     btree_data $::c1
   648    655   } $::data
   649    656   do_test btree-8.8 {
   650    657     btree_commit $::b1
   651    658     btree_data $::c1
   652    659   } $::data
   653    660   do_test btree-8.9 {
   654    661     btree_close_cursor $::c1
   655    662     btree_close $::b1
   656    663     set ::b1 [btree_open test1.bt 2000 0]
   657         -  set ::c1 [btree_cursor $::b1 2 1]
   658         -  btree_move_to $::c1 020
          664  +  set ::c1 [btree_cursor $::b1 1 1]
          665  +  btree_move_to $::c1 2030
   659    666     btree_data $::c1
   660    667   } $::data
   661    668   do_test btree-8.10 {
   662    669     btree_begin_transaction $::b1
   663    670     btree_delete $::c1
   664    671   } {}
   665    672   do_test btree-8.11 {
   666    673     lindex [btree_get_meta $::b1] 0
   667         -} [expr {int(([string length $::data]-238+1019)/1020)}]
          674  +} {}
   668    675   
   669    676   # Now check out keys on overflow pages.
   670    677   #
   671    678   do_test btree-8.12 {
   672    679     set ::keyprefix "This is a long prefix to a key "
   673    680     while {[string length $::keyprefix]<256} {append ::keyprefix $::keyprefix}
   674    681     btree_close_cursor $::c1