Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | More tests and bug fixes in btree.c (CVS 229) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
6b9b298b2846146b95d7df7f42386797 |
User & Date: | drh 2001-06-25 02:11:07.000 |
Context
2001-06-28
| ||
01:54 | Got a lot of BTree tests working. Still lots more needed. (CVS 230) (check-in: 9cfeeb5896 user: drh tags: trunk) | |
2001-06-25
| ||
02:11 | More tests and bug fixes in btree.c (CVS 229) (check-in: 6b9b298b28 user: drh tags: trunk) | |
2001-06-24
| ||
20:39 | The first test file for BTree added. Simple insert and delete tests pass. There is still a lot of work to be done, though. (CVS 228) (check-in: 85f015c975 user: drh tags: trunk) | |
Changes
Changes to src/btree.c.
︙ | ︙ | |||
17 18 19 20 21 22 23 | ** Boston, MA 02111-1307, USA. ** ** Author contact information: ** drh@hwaci.com ** http://www.hwaci.com/drh/ ** ************************************************************************* | | | 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | ** Boston, MA 02111-1307, USA. ** ** Author contact information: ** drh@hwaci.com ** http://www.hwaci.com/drh/ ** ************************************************************************* ** $Id: btree.c,v 1.15 2001/06/25 02:11:07 drh 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. |
︙ | ︙ | |||
137 138 139 140 141 142 143 | ** for additional information.) Page 0 does not exist and a page ** number of 0 is used to mean "no such page". */ struct PageOne { char zMagic[MAGIC_SIZE]; /* String that identifies the file as a database */ int iMagic; /* Integer to verify correct byte order */ Pgno freeList; /* First free page in a list of all free pages */ | > | | 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 | ** for additional information.) Page 0 does not exist and a page ** number of 0 is used to mean "no such page". */ struct PageOne { char zMagic[MAGIC_SIZE]; /* String that identifies the file as a database */ int iMagic; /* Integer to verify correct byte order */ Pgno freeList; /* First free page in a list of all free pages */ int nFree; /* Number of pages on the free list */ int aMeta[SQLITE_N_BTREE_META-1]; /* User defined integers */ }; /* ** Each database page has a header that is an instance of this ** structure. ** ** PageHdr.firstFree is 0 if there is no free space on this page. |
︙ | ︙ | |||
201 202 203 204 205 206 207 | ** The maximum amount of payload (in bytes) that can be stored locally for ** a database entry. If the entry contains more data than this, the ** extra goes onto overflow pages. ** ** This number is chosen so that at least 4 cells will fit on every page. */ #define MX_LOCAL_PAYLOAD \ | | | 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 | ** The maximum amount of payload (in bytes) that can be stored locally for ** a database entry. If the entry contains more data than this, the ** extra goes onto overflow pages. ** ** This number is chosen so that at least 4 cells will fit on every page. */ #define MX_LOCAL_PAYLOAD \ (((SQLITE_PAGE_SIZE-sizeof(PageHdr))/4-(sizeof(CellHdr)+sizeof(Pgno)))&~3) /* ** Data on a database page is stored as a linked list of Cell structures. ** Both the key and the data are stored in aPayload[]. The key always comes ** first. The aPayload[] field grows as necessary to hold the key and data, ** up to a maximum of MX_LOCAL_PAYLOAD bytes. If the size of the key and ** data combined exceeds MX_LOCAL_PAYLOAD bytes, then Cell.ovfl is the |
︙ | ︙ | |||
360 361 362 363 364 365 366 | FreeBlk *pFBlk; char newPage[SQLITE_PAGE_SIZE]; pc = sizeof(PageHdr); pPage->u.hdr.firstCell = pc; memcpy(newPage, pPage->u.aDisk, pc); for(i=0; i<pPage->nCell; i++){ | | | > > > | 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 | FreeBlk *pFBlk; char newPage[SQLITE_PAGE_SIZE]; pc = sizeof(PageHdr); pPage->u.hdr.firstCell = pc; memcpy(newPage, pPage->u.aDisk, pc); for(i=0; i<pPage->nCell; i++){ Cell *pCell = pPage->apCell[i]; /* This routine should never be called on an overfull page. The ** following asserts verify that constraint. */ assert( Addr(pCell) > Addr(pPage) ); assert( Addr(pCell) < Addr(pPage) + SQLITE_PAGE_SIZE ); n = cellSize(pCell); pCell->h.iNext = pc + n; memcpy(&newPage[pc], pCell, n); pPage->apCell[i] = (Cell*)&pPage->u.aDisk[pc]; pc += n; } assert( pPage->nFree==SQLITE_PAGE_SIZE-pc ); memcpy(pPage->u.aDisk, newPage, pc); if( pPage->nCell>0 ){ pPage->apCell[pPage->nCell-1]->h.iNext = 0; } pFBlk = (FreeBlk*)&pPage->u.aDisk[pc]; pFBlk->iSize = SQLITE_PAGE_SIZE - pc; pFBlk->iNext = 0; pPage->u.hdr.firstFree = pc; memset(&pFBlk[1], 0, SQLITE_PAGE_SIZE - pc - sizeof(FreeBlk)); } |
︙ | ︙ | |||
725 726 727 728 729 730 731 | sqlitepager_unref(pBt->page1); pBt->page1 = 0; pBt->inTrans = 0; } } /* | | < | | 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 | sqlitepager_unref(pBt->page1); pBt->page1 = 0; pBt->inTrans = 0; } } /* ** Commit the transaction currently in progress. */ int sqliteBtreeCommit(Btree *pBt){ int rc; if( pBt->inTrans==0 ) return SQLITE_ERROR; rc = sqlitepager_commit(pBt->pPager); pBt->inTrans = 0; unlockBtree(pBt); return rc; } /* |
︙ | ︙ | |||
886 887 888 889 890 891 892 | if( a+offset>MX_LOCAL_PAYLOAD ){ a = MX_LOCAL_PAYLOAD - offset; } memcpy(zBuf, &aPayload[offset], a); if( a==amt ){ return SQLITE_OK; } | | > | | > | 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 | if( a+offset>MX_LOCAL_PAYLOAD ){ a = MX_LOCAL_PAYLOAD - offset; } memcpy(zBuf, &aPayload[offset], a); if( a==amt ){ return SQLITE_OK; } offset = 0; zBuf += a; amt -= a; } if( amt>0 ){ nextPage = pCur->pPage->apCell[pCur->idx]->ovfl; } while( amt>0 && nextPage ){ OverflowPage *pOvfl; rc = sqlitepager_get(pCur->pBt->pPager, nextPage, (void**)&pOvfl); if( rc!=0 ){ return rc; } nextPage = pOvfl->iNext; if( offset<OVERFLOW_SIZE ){ int a = amt; if( a + offset > OVERFLOW_SIZE ){ a = OVERFLOW_SIZE - offset; } memcpy(zBuf, &pOvfl->aPayload[offset], a); offset = 0; amt -= a; zBuf += a; }else{ offset -= OVERFLOW_SIZE; } sqlitepager_unref(pOvfl); } return amt==0 ? SQLITE_OK : SQLITE_CORRUPT; } /* ** Read part of the key associated with cursor pCur. A total |
︙ | ︙ | |||
1263 1264 1265 1266 1267 1268 1269 1270 1271 | if( rc ) return rc; rc = sqlitepager_write(pOvfl); if( rc ){ sqlitepager_unref(pOvfl); return rc; } pPage1->freeList = pOvfl->iNext; *ppPage = (MemPage*)pOvfl; }else{ | > | | 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 | if( rc ) return rc; rc = sqlitepager_write(pOvfl); if( rc ){ sqlitepager_unref(pOvfl); return rc; } pPage1->freeList = pOvfl->iNext; pPage1->nFree--; *ppPage = (MemPage*)pOvfl; }else{ *pPgno = sqlitepager_pagecount(pBt->pPager) + 1; rc = sqlitepager_get(pBt->pPager, *pPgno, (void**)ppPage); if( rc ) return rc; rc = sqlitepager_write(*ppPage); } return rc; } |
︙ | ︙ | |||
1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 | int rc; int needOvflUnref = 0; if( pgno==0 ){ assert( pOvfl!=0 ); pgno = sqlitepager_pagenumber(pOvfl); } rc = sqlitepager_write(pPage1); if( rc ){ return rc; } if( pOvfl==0 ){ assert( pgno>0 ); rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pOvfl); if( rc ) return rc; needOvflUnref = 1; } rc = sqlitepager_write(pOvfl); if( rc ){ if( needOvflUnref ) sqlitepager_unref(pOvfl); return rc; } pOvfl->iNext = pPage1->freeList; pPage1->freeList = pgno; memset(pOvfl->aPayload, 0, OVERFLOW_SIZE); ((MemPage*)pPage)->isInit = 0; assert( ((MemPage*)pPage)->pParent==0 ); rc = sqlitepager_unref(pOvfl); return rc; } | > > | 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 | int rc; int needOvflUnref = 0; if( pgno==0 ){ assert( pOvfl!=0 ); pgno = sqlitepager_pagenumber(pOvfl); } assert( pgno>2 ); rc = sqlitepager_write(pPage1); if( rc ){ return rc; } if( pOvfl==0 ){ assert( pgno>0 ); rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pOvfl); if( rc ) return rc; needOvflUnref = 1; } rc = sqlitepager_write(pOvfl); if( rc ){ if( needOvflUnref ) sqlitepager_unref(pOvfl); return rc; } pOvfl->iNext = pPage1->freeList; pPage1->freeList = pgno; pPage1->nFree++; memset(pOvfl->aPayload, 0, OVERFLOW_SIZE); ((MemPage*)pPage)->isInit = 0; assert( ((MemPage*)pPage)->pParent==0 ); rc = sqlitepager_unref(pOvfl); return rc; } |
︙ | ︙ | |||
1336 1337 1338 1339 1340 1341 1342 | while( ovfl ){ rc = sqlitepager_get(pPager, ovfl, (void**)&pOvfl); if( rc ) return rc; nextOvfl = pOvfl->iNext; rc = freePage(pBt, pOvfl, ovfl); if( rc ) return rc; ovfl = nextOvfl; | < | 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 | while( ovfl ){ rc = sqlitepager_get(pPager, ovfl, (void**)&pOvfl); if( rc ) return rc; nextOvfl = pOvfl->iNext; rc = freePage(pBt, pOvfl, ovfl); if( rc ) return rc; ovfl = nextOvfl; } return SQLITE_OK; } /* ** Create a new cell from key and data. Overflow pages are allocated as ** necessary and linked to this cell. |
︙ | ︙ | |||
1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 | ** routine will be called soon after this routine in order to rebuild ** the linked list. */ static void insertCell(MemPage *pPage, int i, Cell *pCell, int sz){ int idx, j; assert( i>=0 && i<=pPage->nCell ); assert( sz==cellSize(pCell) ); for(j=pPage->nCell; j>i; j--){ pPage->apCell[j] = pPage->apCell[j-1]; } pPage->nCell++; | > < | 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 | ** routine will be called soon after this routine in order to rebuild ** the linked list. */ static void insertCell(MemPage *pPage, int i, Cell *pCell, int sz){ int idx, j; assert( i>=0 && i<=pPage->nCell ); assert( sz==cellSize(pCell) ); idx = allocateSpace(pPage, sz); for(j=pPage->nCell; j>i; j--){ pPage->apCell[j] = pPage->apCell[j-1]; } pPage->nCell++; if( idx<=0 ){ pPage->isOverfull = 1; pPage->apCell[i] = pCell; }else{ memcpy(&pPage->u.aDisk[idx], pCell, sz); pPage->apCell[i] = (Cell*)&pPage->u.aDisk[idx]; } |
︙ | ︙ | |||
1998 1999 2000 2001 2002 2003 2004 | return SQLITE_OK; } /* ** Erase the given database page and all its children. Return ** the page to the freelist. */ | | | > | | > > | > > > > | | | < > | | | > | > > | | | | 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 | return SQLITE_OK; } /* ** Erase the given database page and all its children. Return ** the page to the freelist. */ static int clearDatabasePage(Btree *pBt, Pgno pgno, int freePageFlag){ MemPage *pPage; int rc; Cell *pCell; int idx; rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pPage); if( rc ) return rc; idx = pPage->u.hdr.firstCell; while( idx>0 ){ pCell = (Cell*)&pPage->u.aDisk[idx]; idx = pCell->h.iNext; if( pCell->h.leftChild ){ rc = clearDatabasePage(pBt, pCell->h.leftChild, 1); if( rc ) return rc; } rc = clearCell(pBt, pCell); if( rc ) return rc; } if( pPage->u.hdr.rightChild ){ rc = clearDatabasePage(pBt, pPage->u.hdr.rightChild, 1); if( rc ) return rc; } if( freePageFlag ){ rc = freePage(pBt, pPage, pgno); }else{ zeroPage(pPage); } return rc; } /* ** Delete all information from a single table in the database. */ int sqliteBtreeClearTable(Btree *pBt, int iTable){ int rc; if( !pBt->inTrans ){ return SQLITE_ERROR; /* Must start a transaction first */ } rc = clearDatabasePage(pBt, (Pgno)iTable, 0); if( rc ){ sqliteBtreeRollback(pBt); } return rc; } /* ** Erase all information in a table and add the root of the table to ** the freelist. Except, the root of the principle table (the one on ** page 2) is never added to the freelist. */ int sqliteBtreeDropTable(Btree *pBt, int iTable){ int rc; MemPage *pPage; if( !pBt->inTrans ){ return SQLITE_ERROR; /* Must start a transaction first */ } rc = sqlitepager_get(pBt->pPager, (Pgno)iTable, (void**)&pPage); if( rc ) return rc; rc = sqliteBtreeClearTable(pBt, iTable); if( rc ) return rc; if( iTable>2 ){ rc = freePage(pBt, pPage, iTable); }else{ zeroPage(pPage); sqlitepager_unref(pPage); } return rc; } /* ** Read the meta-information out of a database file. */ int sqliteBtreeGetMeta(Btree *pBt, int *aMeta){ PageOne *pP1; int rc; rc = sqlitepager_get(pBt->pPager, 1, (void**)&pP1); if( rc ) return rc; aMeta[0] = pP1->nFree; memcpy(&aMeta[1], pP1->aMeta, sizeof(pP1->aMeta)); sqlitepager_unref(pP1); return SQLITE_OK; } /* ** Write meta-information back into the database. */ int sqliteBtreeUpdateMeta(Btree *pBt, int *aMeta){ PageOne *pP1; int rc; if( !pBt->inTrans ){ return SQLITE_ERROR; /* Must start a transaction first */ } pP1 = pBt->page1; rc = sqlitepager_write(pP1); if( rc ) return rc; memcpy(pP1->aMeta, &aMeta[1], sizeof(pP1->aMeta)); return SQLITE_OK; } #ifdef SQLITE_TEST /* ** Print a disassembly of the given page on standard output. This routine ** is used for debugging and testing only. |
︙ | ︙ | |||
2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 | } i = 0; idx = pPage->u.hdr.firstCell; while( idx>0 && idx<=SQLITE_PAGE_SIZE-MIN_CELL_SIZE ){ Cell *pCell = (Cell*)&pPage->u.aDisk[idx]; int sz = cellSize(pCell); sprintf(range,"%d..%d", idx, idx+sz-1); if( sz>sizeof(payload)-1 ) sz = sizeof(payload)-1; memcpy(payload, pCell->aPayload, sz); for(j=0; j<sz; j++){ if( payload[j]<0x20 || payload[j]>0x7f ) payload[j] = '.'; } payload[sz] = 0; printf( "cell %2d: i=%-10s chld=%-4d nk=%-3d nd=%-3d payload=%s\n", i, range, (int)pCell->h.leftChild, pCell->h.nKey, pCell->h.nData, | > | > > > > > > > | > > > > > > | > > | > > > > > > > > > > > > > > > > > | 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 | } i = 0; idx = pPage->u.hdr.firstCell; while( idx>0 && idx<=SQLITE_PAGE_SIZE-MIN_CELL_SIZE ){ Cell *pCell = (Cell*)&pPage->u.aDisk[idx]; int sz = cellSize(pCell); sprintf(range,"%d..%d", idx, idx+sz-1); sz = pCell->h.nKey + pCell->h.nData; if( sz>sizeof(payload)-1 ) sz = sizeof(payload)-1; memcpy(payload, pCell->aPayload, sz); for(j=0; j<sz; j++){ if( payload[j]<0x20 || payload[j]>0x7f ) payload[j] = '.'; } payload[sz] = 0; printf( "cell %2d: i=%-10s chld=%-4d nk=%-3d nd=%-3d payload=%s\n", i, range, (int)pCell->h.leftChild, pCell->h.nKey, pCell->h.nData, payload ); if( pPage->apCell[i]!=pCell ){ printf("**** apCell[%d] does not match on prior entry ****\n", i); } i++; idx = pCell->h.iNext; } if( idx!=0 ){ printf("ERROR: next cell index out of range: %d\n", idx); } printf("right_child: %d\n", pPage->u.hdr.rightChild); nFree = 0; i = 0; idx = pPage->u.hdr.firstFree; while( idx>0 && idx<SQLITE_PAGE_SIZE ){ FreeBlk *p = (FreeBlk*)&pPage->u.aDisk[idx]; sprintf(range,"%d..%d", idx, idx+p->iSize-1); nFree += p->iSize; printf("freeblock %2d: i=%-10s size=%-4d total=%d\n", i, range, p->iSize, nFree); idx = p->iNext; i++; } if( idx!=0 ){ printf("ERROR: next freeblock index out of range: %d\n", idx); } sqlitepager_unref(pPage); return SQLITE_OK; } #endif #ifdef SQLITE_TEST /* ** Fill aResult[] with information about the entry and page that the ** cursor is pointing to. ** ** aResult[0] = The page number ** aResult[1] = The entry number ** aResult[2] = Total number of entries on this page ** aResult[3] = Size of this entry ** aResult[4] = Number of free bytes on this page ** aResult[5] = Number of free blocks on the page ** aResult[6] = Page number of the left child of this entry ** aResult[7] = Page number of the right child for the whole page */ int sqliteBtreeCursorDump(BtCursor *pCur, int *aResult){ int cnt, idx; MemPage *pPage = pCur->pPage; aResult[0] = sqlitepager_pagenumber(pPage); aResult[1] = pCur->idx; aResult[2] = pPage->nCell; if( pCur->idx>=0 && pCur->idx<pPage->nCell ){ aResult[3] = cellSize(pPage->apCell[pCur->idx]); aResult[6] = pPage->apCell[pCur->idx]->h.leftChild; }else{ aResult[3] = 0; aResult[6] = 0; } aResult[4] = pPage->nFree; cnt = 0; idx = pPage->u.hdr.firstFree; while( idx>0 && idx<SQLITE_PAGE_SIZE ){ cnt++; idx = ((FreeBlk*)&pPage->u.aDisk[idx])->iNext; } aResult[5] = cnt; aResult[7] = pPage->u.hdr.rightChild; return SQLITE_OK; } #endif |
Changes to src/btree.h.
︙ | ︙ | |||
20 21 22 23 24 25 26 | ** drh@hwaci.com ** http://www.hwaci.com/drh/ ** ************************************************************************* ** This header file defines the interface that the sqlite B-Tree file ** subsystem. ** | | | 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | ** drh@hwaci.com ** http://www.hwaci.com/drh/ ** ************************************************************************* ** This header file defines the interface that the sqlite B-Tree file ** subsystem. ** ** @(#) $Id: btree.h,v 1.6 2001/06/25 02:11:07 drh Exp $ */ typedef struct Btree Btree; typedef struct BtCursor BtCursor; int sqliteBtreeOpen(const char *zFilename, int mode, Btree **ppBtree); int sqliteBtreeClose(Btree*); |
︙ | ︙ | |||
48 49 50 51 52 53 54 | int sqliteBtreeNext(BtCursor*, int *pRes); int sqliteBtreeKeySize(BtCursor*, int *pSize); int sqliteBtreeKey(BtCursor*, int offset, int amt, char *zBuf); int sqliteBtreeDataSize(BtCursor*, int *pSize); int sqliteBtreeData(BtCursor*, int offset, int amt, char *zBuf); int sqliteBtreeCloseCursor(BtCursor*); | | | 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | int sqliteBtreeNext(BtCursor*, int *pRes); int sqliteBtreeKeySize(BtCursor*, int *pSize); int sqliteBtreeKey(BtCursor*, int offset, int amt, char *zBuf); int sqliteBtreeDataSize(BtCursor*, int *pSize); int sqliteBtreeData(BtCursor*, int offset, int amt, char *zBuf); int sqliteBtreeCloseCursor(BtCursor*); #define SQLITE_N_BTREE_META 4 int sqliteBtreeGetMeta(Btree*, int*); int sqliteBtreeUpdateMeta(Btree*, int*); #ifdef SQLITE_TEST int sqliteBtreePageDump(Btree*, int); int sqliteBtreeCursorDump(BtCursor*, int*); #endif |
Changes to src/test3.c.
︙ | ︙ | |||
21 22 23 24 25 26 27 | ** http://www.hwaci.com/drh/ ** ************************************************************************* ** Code for testing the btree.c module in SQLite. This code ** is not included in the SQLite library. It is used for automated ** testing of the SQLite library. ** | | | 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | ** http://www.hwaci.com/drh/ ** ************************************************************************* ** Code for testing the btree.c module in SQLite. This code ** is not included in the SQLite library. It is used for automated ** testing of the SQLite library. ** ** $Id: test3.c,v 1.3 2001/06/25 02:11:07 drh Exp $ */ #include "sqliteInt.h" #include "pager.h" #include "btree.h" #include "tcl.h" #include <stdlib.h> #include <string.h> |
︙ | ︙ | |||
606 607 608 609 610 611 612 | free(zBuf); return SQLITE_OK; } /* ** Usage: btree_cursor_dump ID ** | | | > > > > > > > > > > | | > | > > > | | 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 | free(zBuf); return SQLITE_OK; } /* ** Usage: btree_cursor_dump ID ** ** Return eight integers containing information about the entry the ** cursor is pointing to: ** ** aResult[0] = The page number ** aResult[1] = The entry number ** aResult[2] = Total number of entries on this page ** aResult[3] = Size of this entry ** aResult[4] = Number of free bytes on this page ** aResult[5] = Number of free blocks on the page ** aResult[6] = Page number of the left child of this entry ** aResult[7] = Page number of the right child for the whole page */ static int btree_cursor_dump( void *NotUsed, Tcl_Interp *interp, /* The TCL interpreter that invoked this command */ int argc, /* Number of arguments */ char **argv /* Text of each argument */ ){ BtCursor *pCur; int rc; int i, j; int aResult[8]; char zBuf[400]; if( argc!=2 ){ Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0], " ID\"", 0); return TCL_ERROR; } if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR; rc = sqliteBtreeCursorDump(pCur, aResult); if( rc ){ Tcl_AppendResult(interp, errorName(rc), 0); return TCL_ERROR; } j = 0; for(i=0; i<sizeof(aResult)/sizeof(aResult[0]); i++){ sprintf(&zBuf[j]," %d", aResult[i]); j += strlen(&zBuf[j]); } Tcl_AppendResult(interp, &zBuf[1], 0); return SQLITE_OK; } /* ** Register commands with the TCL interpreter. */ int Sqlitetest3_Init(Tcl_Interp *interp){ |
︙ | ︙ |
Changes to test/btree.test.
︙ | ︙ | |||
19 20 21 22 23 24 25 | # drh@hwaci.com # http://www.hwaci.com/drh/ # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this script is btree database backend # | | | 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | # drh@hwaci.com # http://www.hwaci.com/drh/ # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this script is btree database backend # # $Id: btree.test,v 1.2 2001/06/25 02:11:07 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl if {$dbprefix!="memory:" && [info commands btree_open]!=""} { |
︙ | ︙ | |||
283 284 285 286 287 288 289 290 | } set r } {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00} # Commit and make sure the delete is still there. # do_test btree-4.5 { btree_close_cursor $::c1 | > > > > > > > > > > > > > > > > > | > < > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < | 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 | } set r } {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00} # Commit and make sure the delete is still there. # do_test btree-4.5 { btree_commit $::b1 btree_move_to $::c1 {} set r {} while 1 { set key [btree_key $::c1] if {$key==""} break lappend r $key lappend r [btree_data $::c1] btree_next $::c1 } set r } {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00} # Completely close the database and reopen it. Then check # the data again. # do_test btree-4.6 { btree_close_cursor $::c1 btree_close $::b1 set ::b1 [btree_open test1.bt] set ::c1 [btree_cursor $::b1 2] set r {} while 1 { set key [btree_key $::c1] if {$key==""} break lappend r $key lappend r [btree_data $::c1] btree_next $::c1 } set r } {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00} # Try to read and write meta data # do_test btree-5.1 { btree_get_meta $::b1 } {0 0 0 0} do_test btree-5.2 { set rc [catch {btree_update_meta $::b1 1 2 3 4} msg] lappend rc $msg } {1 SQLITE_ERROR} do_test btree-5.3 { btree_begin_transaction $::b1 set rc [catch {btree_update_meta $::b1 1 2 3 4} msg] lappend rc $msg } {0 {}} do_test btree-5.4 { btree_get_meta $::b1 } {0 2 3 4} do_test btree-5.5 { btree_close_cursor $::c1 btree_rollback $::b1 btree_get_meta $::b1 } {0 0 0 0} do_test btree-5.6 { btree_begin_transaction $::b1 btree_update_meta $::b1 999 10 20 30 btree_commit $::b1 btree_get_meta $::b1 } {0 10 20 30} proc select_all {cursor} { set r {} btree_move_to $cursor {} while 1 { set key [btree_key $cursor] if {$key==""} break lappend r $key lappend r [btree_data $cursor] btree_next $cursor } return $r } # Try to create a new table in the database file # do_test btree-6.1 { set rc [catch {btree_create_table $::b1} msg] lappend rc $msg } {1 SQLITE_ERROR} do_test btree-6.2 { btree_begin_transaction $::b1 set ::t2 [btree_create_table $::b1] } {3} do_test btree-6.2.1 { set ::c2 [btree_cursor $::b1 $::t2] btree_insert $::c2 ten 10 btree_key $::c2 } {ten} do_test btree-6.3 { btree_commit $::b1 set ::c1 [btree_cursor $::b1 2] select_all $::c1 } {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00} #btree_page_dump $::b1 3 do_test btree-6.4 { select_all $::c2 } {ten 10} # Drop the new table, then create it again anew. # do_test btree-6.5 { btree_begin_transaction $::b1 } {} do_test btree-6.6 { btree_close_cursor $::c2 } {} do_test btree-6.7 { btree_drop_table $::b1 $::t2 } {} do_test btree-6.7.1 { lindex [btree_get_meta $::b1] 0 } {1} do_test btree-6.8 { set ::t2 [btree_create_table $::b1] } {3} do_test btree-6.8.1 { lindex [btree_get_meta $::b1] 0 } {0} do_test btree-6.9 { set ::c2 [btree_cursor $::b1 $::t2] btree_move_to $::c2 {} btree_key $::c2 } {} # If we drop table 2 it just clears the table. Table 2 always exists. # do_test btree-6.10 { btree_close_cursor $::c1 btree_drop_table $::b1 2 set ::c1 [btree_cursor $::b1 2] btree_move_to $::c1 {} btree_key $::c1 } {} do_test btree-6.11 { btree_commit $::b1 select_all $::c1 } {} do_test btree-6.12 { select_all $::c2 } {} # Check to see that pages defragment properly. To do this test we will # # 1. Fill the first page table 2 with data. # 2. Delete every other entry of table 2. # 3. Insert a single entry that requires more contiguous # space than is available. # do_test btree-7.1 { btree_begin_transaction $::b1 } {} do_test btree-7.2 { for {set i 0} {$i<36} {incr i} { set key [format %03d $i] set data "*** $key ***" btree_insert $::c1 $key $data } lrange [btree_cursor_dump $::c1] 4 5 } {8 1} do_test btree-7.3 { btree_move_to $::c1 000 while {[btree_key $::c1]!=""} { btree_delete $::c1 btree_next $::c1 btree_next $::c1 } lrange [btree_cursor_dump $::c1] 4 5 } {512 19} #btree_page_dump $::b1 2 do_test btree-7.4 { btree_insert $::c1 018 {*** 018 ***+++} btree_key $::c1 } {018} do_test btree-7.5 { lrange [btree_cursor_dump $::c1] 4 5 } {480 1} #btree_page_dump $::b1 2 # Delete an entry to make a hole of a known size, then immediately recreate # that entry. This tests the path into allocateSpace where the hole exactly # matches the size of the desired space. # do_test btree-7.6 { btree_move_to $::c1 007 btree_delete $::c1 btree_move_to $::c1 011 btree_delete $::c1 } {} do_test btree-7.7 { lindex [btree_cursor_dump $::c1] 5 } {3} #btree_page_dump $::b1 2 do_test btree-7.8 { btree_insert $::c1 007 {*** 007 ***} lindex [btree_cursor_dump $::c1] 5 } {2} #btree_page_dump $::b1 2 # Make sure the freeSpace() routine properly coaleses adjacent memory blocks # do_test btree-7.9 { btree_move_to $::c1 013 btree_delete $::c1 lrange [btree_cursor_dump $::c1] 4 5 } {536 2} do_test btree-7.10 { btree_move_to $::c1 009 btree_delete $::c1 lrange [btree_cursor_dump $::c1] 4 5 } {564 2} do_test btree-7.11 { btree_move_to $::c1 018 btree_delete $::c1 lrange [btree_cursor_dump $::c1] 4 5 } {596 2} do_test btree-7.13 { btree_move_to $::c1 033 btree_delete $::c1 lrange [btree_cursor_dump $::c1] 4 5 } {624 3} do_test btree-7.14 { btree_move_to $::c1 035 btree_delete $::c1 lrange [btree_cursor_dump $::c1] 4 5 } {652 2} #btree_page_dump $::b1 2 # Check to see that both key and data on overflow pages work correctly. # do_test btree-8.1 { set data "*** This is a very long key " while {[string length $data]<256} {append data $data} set ::data $data btree_insert $::c1 020 $data } {} #btree_page_dump $::b1 2 do_test btree-8.2 { string length [btree_data $::c1] } [string length $::data] do_test btree-8.3 { btree_data $::c1 } $::data do_test btree-8.4 { btree_delete $::c1 } {} do_test btree-8.4.1 { lindex [btree_get_meta $::b1] 0 } [expr {int(([string length $::data]-238+1019)/1020)}] do_test btree-8.5 { set data "*** This is an even longer key" while {[string length $data]<2000} {append data $data} set ::data $data btree_insert $::c1 020 $data } {} do_test btree-8.6 { string length [btree_data $::c1] } [string length $::data] do_test btree-8.7 { btree_data $::c1 } $::data do_test btree-8.8 { btree_commit $::b1 btree_data $::c1 } $::data do_test btree-8.9 { btree_close_cursor $::c1 btree_close $::b1 set ::b1 [btree_open test1.bt] set ::c1 [btree_cursor $::b1 2] btree_move_to $::c1 020 btree_data $::c1 } $::data do_test btree-8.10 { btree_begin_transaction $::b1 btree_delete $::c1 } {} do_test btree-8.11 { lindex [btree_get_meta $::b1] 0 } [expr {int(([string length $::data]-238+1019)/1020)}] puts [btree_get_meta $::b1] do_test btree-99.1 { btree_close $::b1 } {} } ;# end if( not mem: and has pager_open command ); finish_test |