Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Changes to btree for the new file format are mostly complete. Still need to test and debug. (CVS 1311) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
0eee3b5cd400e9548437632ec1dfe625 |
User & Date: | drh 2004-05-02 21:12:19.000 |
Context
2004-05-03
| ||
19:49 | Incremental btree.c changes. (CVS 1312) (check-in: fdc629dbbf user: drh tags: trunk) | |
2004-05-02
| ||
21:12 | Changes to btree for the new file format are mostly complete. Still need to test and debug. (CVS 1311) (check-in: 0eee3b5cd4 user: drh tags: trunk) | |
2004-04-29
| ||
14:42 | Sync all version 3 changes. (CVS 1309) (check-in: 51892d6cdc user: drh tags: trunk) | |
Changes
Changes to src/btree.c.
1 2 3 4 5 6 7 8 9 10 11 | /* ** 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. ** ************************************************************************* | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /* ** 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.107 2004/05/02 21:12:19 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. |
︙ | ︙ | |||
148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 | ** * zero or more pages numbers of leaves */ #include "sqliteInt.h" #include "pager.h" #include "btree.h" #include <assert.h> /* Forward declarations */ typedef struct MemPage MemPage; /* ** This is a magic string that appears at the beginning of every ** SQLite database in order to identify the file as a real database. ** 0123456789 123456 */ static const char zMagicHeader[] = "SQLite version 3"; /* | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > > < | 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 | ** * zero or more pages numbers of leaves */ #include "sqliteInt.h" #include "pager.h" #include "btree.h" #include <assert.h> /* Maximum page size. The upper bound on this value is 65536 (a limit ** imposed by the 2-byte offset at the beginning of each cell.) The ** maximum page size determines the amount of stack space allocated ** by many of the routines in this module. On embedded architectures ** or any machine where memory and especially stack memory is limited, ** one may wish to chose a smaller value for the maximum page size. */ #ifndef MX_PAGE_SIZE # define MX_PAGE_SIZE 1024 #endif /* Individual entries or "cells" are limited in size so that at least ** this many cells will fit on one page. Changing this value will result ** in an incompatible database. */ #define MN_CELLS_PER_PAGE 4 /* The following value is the maximum cell size assuming a maximum page ** size give above. */ #define MX_CELL_SIZE ((MX_PAGE_SIZE-10)/MN_CELLS_PER_PAGE) /* The maximum number of cells on a single page of the database. This ** assumes a minimum cell size of 3 bytes. Such small cells will be ** exceedingly rare, but they are possible. */ #define MX_CELL ((MX_PAGE_SIZE-10)/3) /* Forward declarations */ typedef struct MemPage MemPage; /* ** This is a magic string that appears at the beginning of every ** SQLite database in order to identify the file as a real database. ** 0123456789 123456 */ static const char zMagicHeader[] = "SQLite version 3"; /* ** Page type flags. An ORed combination of these flags appear as the ** first byte of every BTree page. */ #define PTF_LEAF 0x01 #define PTF_ZERODATA 0x02 #define PTF_INTKEY 0x04 /* Idea for the future: PTF_LEAFDATA */ /* ** As each page of the file is loaded into memory, an instance of the following ** structure is appended and initialized to zero. This structure stores ** information about the page that is decoded from the raw file page. ** ** The pParent field points back to the parent page. This allows us to ** walk up the BTree from any leaf to the root. Care must be taken to ** unref() the parent page pointer when this page is no longer referenced. ** The pageDestructor() routine handles that chore. */ struct MemPage { |
︙ | ︙ | |||
190 191 192 193 194 195 196 197 198 199 200 201 202 203 | u8 zeroData; /* True if zero data flag is set */ u8 hdrOffset; /* 100 for page 1. 0 otherwise */ Pgno pgno; /* Page number for this page */ MemPage *pParent; /* The parent of this page. NULL for root */ int idxParent; /* Index in pParent->aCell[] of this node */ int nFree; /* Number of free bytes on the page */ int nCell; /* Number of entries on this page */ unsigned char **aCell; /* Pointer to start of each cell */ }; /* ** The in-memory image of a disk page has the auxiliary information appended ** to the end. EXTRA_SIZE is the number of bytes of space needed to hold ** that extra information. | > | 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 | u8 zeroData; /* True if zero data flag is set */ u8 hdrOffset; /* 100 for page 1. 0 otherwise */ Pgno pgno; /* Page number for this page */ MemPage *pParent; /* The parent of this page. NULL for root */ int idxParent; /* Index in pParent->aCell[] of this node */ int nFree; /* Number of free bytes on the page */ int nCell; /* Number of entries on this page */ int nCellAlloc; /* Number of slots allocated in aCell[] */ unsigned char **aCell; /* Pointer to start of each cell */ }; /* ** The in-memory image of a disk page has the auxiliary information appended ** to the end. EXTRA_SIZE is the number of bytes of space needed to hold ** that extra information. |
︙ | ︙ | |||
427 428 429 430 431 432 433 | int size; unsigned char *data; #ifndef NDEBUG int cnt = 0; #endif data = pPage->aData; | | | 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 | int size; unsigned char *data; #ifndef NDEBUG int cnt = 0; #endif data = pPage->aData; assert( sqlitepager_iswriteable(data->aData) ); assert( pPage->pBt ); if( nByte<4 ) nByte = 4; if( pPage->nFree<nByte || pPage->isOverfull ) return 0; hdr = pPage->hdrOffset; if( data[hdr+5]>=252 ){ defragmentPage(pPage); } |
︙ | ︙ | |||
484 485 486 487 488 489 490 | int addr, pbegin, pend; #ifndef NDEBUG int tsize = 0; /* Total size of all freeblocks */ #endif unsigned char *data = pPage->aData; assert( pPage->pBt!=0 ); | | | 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 | int addr, pbegin, pend; #ifndef NDEBUG int tsize = 0; /* Total size of all freeblocks */ #endif unsigned char *data = pPage->aData; assert( pPage->pBt!=0 ); assert( sqlitepager_iswriteable(data->aData) ); assert( start>=pPage->hdrOffset+6+(pPage->leaf?0:4) ); assert( end<=pPage->pBt->pageSize ); if( size<4 ) size = 4; /* Add the space back into the linked list of freeblocks */ addr = pPage->hdrOffset + 1; while( (pbegin = get2byte(&data[addr]))<start && pbegin>0 ){ |
︙ | ︙ | |||
531 532 533 534 535 536 537 538 539 540 541 542 543 544 | #if 0 /* ** The following is the default comparison function for (non-integer) ** keys in the btrees. This function returns negative, zero, or ** positive if the first key is less than, equal to, or greater than ** the second. ** */ static int keyComp( void *userData, int nKey1, const unsigned char *aKey1, int nKey2, const unsigned char *aKey2, ){ | > > > > > > > > > > > > > > > > > > > > | 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 | #if 0 /* ** The following is the default comparison function for (non-integer) ** keys in the btrees. This function returns negative, zero, or ** positive if the first key is less than, equal to, or greater than ** the second. ** ** The key consists of multiple fields. Each field begins with a variable ** length integer which determines the field type and the number of bytes ** of key data to follow for that field. ** ** initial varint bytes to follow type ** -------------- --------------- --------------- ** 0 0 NULL ** 1 1 signed integer ** 2 2 signed integer ** 3 4 signed integer ** 4 8 signed integer ** 5 8 IEEE float ** 6..12 reserved for expansion ** N>=12 and even (N-12)/2 BLOB ** N>=13 and odd (N-13)/2 text ** ** For a particular database, text is always either UTF-8, UTF-16BE, or ** UTF-16LE. Which of these three formats to use is determined by one ** of the meta values in the file header. ** */ static int keyComp( void *userData, int nKey1, const unsigned char *aKey1, int nKey2, const unsigned char *aKey2, ){ |
︙ | ︙ | |||
596 597 598 599 600 601 602 603 604 605 606 607 608 609 | } return 0; bad_key: return 1; } #endif /* ** Initialize the auxiliary information for a disk block. ** ** The pParent parameter must be a pointer to the MemPage which ** is the parent of the page being initialized. The root of a ** BTree has no parent and so for that page, pParent==NULL. | > > > > > > > > > > > > > > > | 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 | } return 0; bad_key: return 1; } #endif /* ** Resize the aCell[] array of the given page so that it is able to ** hold at least nNewSz entries. ** ** Return SQLITE_OK or SQLITE_NOMEM. */ static int resizeCellArray(MemPage *pPage, int nNewSz){ if( pPage->nCellAlloc<nNewSize ){ pPage->aCell = sqliteRealloc(pPage->aCell, nNewSz*sizeof(pPage->aCell[0]) ); if( sqlite_malloc_failed ) return SQLITE_NOMEM; pPage->nCellAlloc = nNewSize; } return SQLITE_OK; } /* ** Initialize the auxiliary information for a disk block. ** ** The pParent parameter must be a pointer to the MemPage which ** is the parent of the page being initialized. The root of a ** BTree has no parent and so for that page, pParent==NULL. |
︙ | ︙ | |||
618 619 620 621 622 623 624 625 | MemPage *pPage, /* The page to be initialized */ MemPage *pParent /* The parent. Might be NULL */ ){ int c, pc, i, hdr; int sumCell = 0; /* Total size of all cells */ assert( pPage->pBt!=0 ); assert( pPage->aData == &((unsigned char*)pPage)[pPage->pBt->pageSize] ); | > > > | | | < < < | < | | | < | | 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 | MemPage *pPage, /* The page to be initialized */ MemPage *pParent /* The parent. Might be NULL */ ){ int c, pc, i, hdr; int sumCell = 0; /* Total size of all cells */ assert( pPage->pBt!=0 ); assert( pParent==0 || pParent->pBt==pPage->pBt ); assert( pPage->pgno==sqlitepager_pagenumber(pPage->aData) ); assert( pPage->aData == &((unsigned char*)pPage)[pPage->pBt->pageSize] ); assert( pPage->isInit==0 || pPage->pParent==pParent ); if( pPage->isInit ) return SQLITE_OK; assert( pPage->pParent==0 ); pPage->pParent = pParent; if( pParent ){ sqlitepager_ref(pParent->aData); } pPage->nCell = pPage->nCellAlloc = 0; pPage->hdrOffset = hdr = pPage->pgno==1 ? 100 : 0; c = pPage->aData[hdr]; pPage->intKey = (c & PTF_INTKEY)!=0; pPage->zeroData = (c & PTF_ZERODATA)!=0; pPage->leaf = (c & PTF_LEAF)!=0; /* Initialize the cell count and cell pointers */ pc = get2byte(&data[hdr+3]); while( pc>0 ){ if( pc>=pBt->pageSize ) return SQLITE_CORRUPT; if( pPage->nCell>pBt->pageSize ) return SQLITE_CORRUPT; pPage->nCell++; pc = get2byte(&data[pc]); } if( resizeCellArray(pPage, pPage->nCell) ){ return SQLITE_NOMEM; } pc = get2byte(&data[hdr+3]); for(i=0; pc>0; i++){ pPage->aCell[i] = &data[pc]; pc = get2byte(&data[pc]); sumCell += cellSize(pPage, &data[pc]); |
︙ | ︙ | |||
688 689 690 691 692 693 694 | */ static void zeroPage(MemPage *pPage, int flags){ unsigned char *data = pPage->aData; Btree *pBt = pPage->pBt; int hdr = pPage->hdrOffset; int first; | | | 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 | */ static void zeroPage(MemPage *pPage, int flags){ unsigned char *data = pPage->aData; Btree *pBt = pPage->pBt; int hdr = pPage->hdrOffset; int first; assert( sqlitepager_iswriteable(data->aData) ); memset(&data[hdr], 0, pBt->pageSize - hdr); data[hdr] = flags; first = hdr + 6 + 4*((flags&0x01)!=0); put2byte(&data[hdr+1], first); put2byte(&data[first+2], pBt->pageSize - first); sqliteFree(pPage->aCell); pPage->aCell = 0; |
︙ | ︙ | |||
726 727 728 729 730 731 732 | return SQLITE_OK; } /* ** Release a MemPage. This should be called once for each prior ** call to getPage. */ | | | 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 | return SQLITE_OK; } /* ** Release a MemPage. This should be called once for each prior ** call to getPage. */ static void releasePage(MemPage *pPage){ if( pPage ){ assert( pPage->aData ); assert( pPage->pBt ); assert( &pPage->aData[pPage->pBt->pageSize]==(unsigned char*)pPage ); sqlitepager_unref(pPage->aData); } } |
︙ | ︙ | |||
804 805 806 807 808 809 810 | *ppBtree = 0; return rc; } sqlitepager_set_destructor(pBt->pPager, pageDestructor); pBt->pCursor = 0; pBt->page1 = 0; pBt->readOnly = sqlitepager_isreadonly(pBt->pPager); | | | | 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 | *ppBtree = 0; return rc; } sqlitepager_set_destructor(pBt->pPager, pageDestructor); pBt->pCursor = 0; pBt->page1 = 0; pBt->readOnly = sqlitepager_isreadonly(pBt->pPager); pBt->pageSize = SQLITE_PAGE_SIZE; /* FIX ME - read from header */ pBt->maxLocal = (pBt->pageSize-10)/4-12; *ppBtree = pBt; return SQLITE_OK; } /* ** Close an open database and invalidate all cursors. */ |
︙ | ︙ | |||
1149 1150 1151 1152 1153 1154 1155 | int rc; BtCursor *pCur, *pRing; if( pBt->readOnly && wrFlag ){ *ppCur = 0; return SQLITE_READONLY; } | | | | 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 | int rc; BtCursor *pCur, *pRing; if( pBt->readOnly && wrFlag ){ *ppCur = 0; return SQLITE_READONLY; } if( pBt->pPage1==0 ){ rc = lockBtree(pBt); if( rc!=SQLITE_OK ){ *ppCur = 0; return rc; } } pCur = sqliteMalloc( sizeof(*pCur) ); if( pCur==0 ){ rc = SQLITE_NOMEM; goto create_cursor_exception; } pCur->pgnoRoot = (Pgno)iTable; rc = getPage(pBt, pCur->pgnoRoot, &pCur->pPage); if( rc!=SQLITE_OK ){ goto create_cursor_exception; } rc = initPage(pCur->pPage, 0); if( rc!=SQLITE_OK ){ goto create_cursor_exception; } |
︙ | ︙ | |||
1256 1257 1258 1259 1260 1261 1262 | } /* ** Set *pSize to the size of the buffer needed to hold the value of ** the key for the current entry. If the cursor is not pointing ** to a valid entry, *pSize is set to 0. ** | | | 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 | } /* ** Set *pSize to the size of the buffer needed to hold the value of ** 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, u64 *pSize){ MemPage *pPage; pPage = pCur->pPage; assert( pPage!=0 ); |
︙ | ︙ | |||
1408 1409 1410 1411 1412 1413 1414 | ** If pCur is not pointing to a valid entry return 0. ** ** The pointer returned is ephemeral. The key may move ** or be destroyed on the next call to any Btree routine. ** ** This routine is used to do quick key comparisons in the ** common case where the entire key fits in the payload area | | > > > > > > | 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 | ** If pCur is not pointing to a valid entry return 0. ** ** The pointer returned is ephemeral. The key may move ** or be destroyed on the next call to any Btree routine. ** ** This routine is used to do quick key comparisons in the ** common case where the entire key fits in the payload area ** of a cell and does not overflow onto secondary pages. If ** this routine returns 0 for a valid cursor, the caller will ** need to allocate a buffer big enough to hold the whole key ** then use sqlite3BtreeKey() to copy the key value into the ** buffer. That is substantially slower. But fortunately, ** most keys are small enough to fit in the payload area so ** the slower method is rarely needed. */ void *sqlite3BtreeKeyFetch(BtCursor *pCur){ unsigned char *aPayload; MemPage *pPage; Btree *pBt; u64 nData, nKey; |
︙ | ︙ | |||
1605 1606 1607 1608 1609 1610 1611 | pCur->pPage = pRoot; pCur->idx = 0; if( pRoot->nCell==0 && !pRoot->leaf ){ Pgno subpage; assert( pRoot->pgno==1 ); subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+6]); assert( subpage>0 ); | | | 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 | pCur->pPage = pRoot; pCur->idx = 0; if( pRoot->nCell==0 && !pRoot->leaf ){ Pgno subpage; assert( pRoot->pgno==1 ); subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+6]); assert( subpage>0 ); rc = moveToChild(pCur, subpage); } return rc; } /* ** Move the cursor down to the left-most leaf entry beneath the ** entry to which it is currently pointing. |
︙ | ︙ | |||
2059 2060 2061 2062 2063 2064 2065 | if( rc ) return rc; sqlitepager_unref(pOvfl->aData); } return SQLITE_OK; } /* | | | | 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 | if( rc ) return rc; sqlitepager_unref(pOvfl->aData); } return SQLITE_OK; } /* ** Compute the number of bytes required by a cell header. Fill in ** the nData and nKey values of the header that pHeader points to. */ static int makeCellHeader( MemPage *pPage, /* The page that will contain the cell */ u64 nKey, /* Size of key, or the key value if intKey */ int nData, /* Size of data. Ignored for zerodata */ unsigned char *pHeader /* Write header bytes here */ ){ |
︙ | ︙ | |||
2084 2085 2086 2087 2088 2089 2090 | /* ** Fill in the payload section of a cell into the space provided. If ** the payload will not completely fit in the cell, allocate additional ** overflow pages and fill them in. */ static int fillInCell( MemPage *pPage, /* The page that contains the cell */ | | < | > > > > > > > > | 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 | /* ** Fill in the payload section of a cell into the space provided. If ** the payload will not completely fit in the cell, allocate additional ** overflow pages and fill them in. */ static int fillInCell( MemPage *pPage, /* The page that contains the cell */ unsigned char *pCell, /* Complete text of the cell */ const void *pKey, u64 nKey, /* The key */ const void *pData,int nData, /* The data */ int *pnSize /* Write cell size here */ ){ int nPayload; const void *pSrc; int nSrc, nSrc2; int spaceLeft; MemPage *pOvfl = 0; unsigned char *pPrior; unsigned char *pPayload; Btree *pBt = pPage->pBt; Pgno pgnoOvfl = 0; int nHeader; nHeader = makeCellHeader(pPage, pCell, nKey, nData); nPayload = nData; if( pPage->intKey ){ pSrc = pData; nSrc = nData; nSrc2 = 0; }else{ nPayload += nKey; pSrc = pKey; nSrc = nKey; } if( nPayload>pBt->maxLocal ){ *pnSize = nHeader + pBt->maxLocal + 4; }else{ *pnSize = nHeader + nPayload; } spaceLeft = pBt->maxLocal; pPayload = &pCell[nHeader]; pPrior = &pPayload[pBt->maxLocal]; while( nPayload>0 ){ if( spaceLeft==0 ){ rc = allocatePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl); |
︙ | ︙ | |||
2149 2150 2151 2152 2153 2154 2155 | } /* ** Change the MemPage.pParent pointer on the page whose number is ** given in the second argument so that MemPage.pParent holds the ** pointer in the third argument. */ | | > | | > | | | | > > | > | > > | | | | | > > | | | | > | | | | | | | < | | | | | | < > | | | | > > | > > > > > | > > | | | | | | | 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 | } /* ** Change the MemPage.pParent pointer on the page whose number is ** given in the second argument so that MemPage.pParent holds the ** pointer in the third argument. */ static void reparentPage(Btree *pBt, Pgno pgno, MemPage *pNewParent, int idx){ MemPage *pThis; unsigned char *aData; if( pgno==0 ) return; assert( pBt->pPager!=0 ); aData = sqlitepager_lookup(pBt->pPager, pgno); pThis = (MemPage)&aData[pBt->pageSize]; if( pThis && pThis->isInit ){ if( pThis->pParent!=pNewParent ){ if( pThis->pParent ) sqlitepager_unref(pThis->pParent->aData); pThis->pParent = pNewParent; if( pNewParent ) sqlitepager_ref(pNewParent->aData); } pThis->idxParent = idx; sqlitepager_unref(aData); } } /* ** Change the pParent pointer of all children of pPage to point back ** to pPage. ** ** In other words, for every child of pPage, invoke reparentPage() ** to make sure that each child knows that pPage is its parent. ** ** This routine gets called after you memcpy() one page into ** another. */ static void reparentChildPages(MemPage *pPage){ int i; Btree *pBt; if( pPage->left ) return; pBt = pPage->pBt; for(i=0; i<pPage->nCell; i++){ reparentPage(pBt, get4byte(&pPage->aCell[i][2]), pPage, i); } reparentPage(pBt, get4byte(&pPage->aData[pPage->hdrOffset+6]), pPage, i); pPage->idxShift = 0; } /* ** Remove the i-th cell from pPage. This routine effects pPage only. ** The cell content is not freed or deallocated. It is assumed that ** the cell content has been copied someplace else. This routine just ** removes the reference to the cell from pPage. ** ** "sz" must be the number of bytes in the cell. ** ** Do not bother maintaining the integrity of the linked list of Cells. ** Only the pPage->apCell[] array is important. The relinkCellList() ** routine will be called soon after this routine in order to rebuild ** the linked list. */ static void dropCell(MemPage *pPage, int idx, int sz){ int j; assert( idx>=0 && idx<pPage->nCell ); assert( sz==cellSize(pPage, pPage->aCell[idx]) ); assert( sqlitepager_iswriteable(pPage->aData) ); assert( pPage->aCell[idx]>=pPage->aData ); assert( pPage->aCell[idx]<&pPage->aData[pPage->pBt->pageSize-sz] ); freeSpace(pPage, idx, sz); for(j=idx; j<pPage->nCell-1; j++){ pPage->aCell[j] = pPage->aCell[j+1]; } pPage->nCell--; pPage->idxShift = 1; } /* ** Insert a new cell on pPage at cell index "i". pCell points to the ** content of the cell. ** ** If the cell content will fit on the page, then put it there. If it ** will not fit, then just make pPage->apCell[i] point to the content ** and set pPage->isOverfull. ** ** Do not bother maintaining the integrity of the linked list of Cells. ** Only the pPage->apCell[] array is important. The relinkCellList() ** routine will be called soon after this routine in order to rebuild ** the linked list. */ static void insertCell(MemPage *pPage, int i, unsigned char *pCell, int sz){ int idx, j; assert( i>=0 && i<=pPage->nCell ); assert( sz==cellSize(pBt, pCell) ); assert( sqlitepager_iswriteable(pPage->aData) ); idx = allocateSpace(pBt, pPage, sz); resizeCellArray(pPage, pPage->nCell+1); for(j=pPage->nCell; j>i; j--){ pPage->aCell[j] = pPage->aCell[j-1]; } pPage->nCell++; if( idx<=0 ){ pPage->isOverfull = 1; pPage->aCell[i] = pCell; }else{ memcpy(&pPage->aData[idx], pCell, sz); pPage->aCell[i] = &pPage->aData[idx]; } pPage->idxShift = 1; } /* ** Rebuild the linked list of cells on a page so that the cells ** occur in the order specified by the pPage->aCell[] array. ** Invoke this routine once to repair damage after one or more ** invocations of either insertCell() or dropCell(). */ static void relinkCellList(MemPage *pPage){ int i, idxFrom; assert( sqlitepager_iswriteable(pPage->aData) ); idxFrom = pPage->hdrOffset+3; for(i=0; i<pPage->nCell; i++){ int idx = Addr(pPage->aCell[i]) - Addr(pPage); assert( idx>pPage->hdrOffset && idx<pPage->pBt->pageSize ); put2byte(&pPage->aData[idxFrom], idx); idxFrom = idx; } put2byte(&pPage->aData[idxFrom], 0); } /* ** Make a copy of the contents of pFrom into pTo. The pFrom->aCell[] ** pointers that point into pFrom->aData[] must be adjusted to point ** into pTo->aData[] instead. But some pFrom->aCell[] entries might ** not point to pFrom->aData[]. Those are unchanged. */ static void copyPage(MemPage *pTo, MemPage *pFrom){ uptr from, to; int i; int pageSize; int ofst; assert( pTo->hdrOffset==0 ); ofst = pFrom->hdrOffset; pageSize = pTo->pBt->pageSize; memcpy(pTo->aData, &pFrom->aData[ofst], pageSize - ofst); pTo->pParent = 0; pTo->isInit = 1; resizeCellArray(pTo, pFrom->nCell); pTo->nCell = pFrom->nCell; pTo->nFree = pFrom->nFree + ofst; assert( pTo->aData[5]<155 ); pTo->aData[5] += ofst; pTo->isOverfull = pFrom->isOverfull; to = Addr(pTo->aData); from = Addr(pFrom->aData); for(i=0; i<pTo->nCell; i++){ uptr x = Addr(pFrom->aCell[i]); if( x>from && x<from+pageSize ){ *((uptr*)&pTo->aCell[i]) = x + to - from; }else{ pTo->aCell[i] = pFrom->aCell[i]; } } } /* ** The following parameters determine how many adjacent pages get involved ** in a balancing operation. NN is the number of neighbors on either side |
︙ | ︙ | |||
2321 2322 2323 2324 2325 2326 2327 | ** The number of siblings of pPage might be increased or decreased by ** one in an effort to keep pages between 66% and 100% full. The root page ** is special and is allowed to be less than 66% full. If pPage is ** the root page, then the depth of the tree might be increased ** or decreased by one, as necessary, to keep the root page from being ** overfull or empty. ** | | < < < < < | | | > < > | | < | > | > | < | | | < > | > | | | | > > > > > > > | > | > > > > | > | < < | < < | | | < < | | | < < < < < < | | | | > | < | | > | | | > | | | | < < < < < < < < < < < < < < < < < < < < < < < < > > > | > > > > > > > > | | | | | | | | > > > > | > > > | > | | > > | | | | 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 | ** The number of siblings of pPage might be increased or decreased by ** one in an effort to keep pages between 66% and 100% full. The root page ** is special and is allowed to be less than 66% full. If pPage is ** the root page, then the depth of the tree might be increased ** or decreased by one, as necessary, to keep the root page from being ** overfull or empty. ** ** This routine alwyas calls relinkCellList() on its input page regardless of ** whether or not it does any real balancing. Client routines will typically ** invoke insertCell() or dropCell() before calling this routine, so we ** need to call relinkCellList() to clean up the mess that those other ** routines left behind. ** ** Note that when this routine is called, some of the Cells on pPage ** might not actually be stored in pPage->aData[]. This can happen ** if the page is overfull. Part of the job of this routine is to ** make sure all Cells for pPage once again fit in pPage->aData[]. ** ** In the course of balancing the siblings of pPage, the parent of pPage ** might become overfull or underfull. If that happens, then this routine ** is called recursively on the parent. ** ** If this routine fails for any reason, it might leave the database ** in a corrupted state. So if this routine fails, the database should ** be rolled back. */ static int balance(MemPage *pPage){ MemPage *pParent; /* The parent of pPage */ Btree *pBt; /* The whole database */ int nCell; /* Number of cells in apCell[] */ int nOld; /* Number of pages in apOld[] */ int nNew; /* Number of pages in apNew[] */ int nDiv; /* Number of cells in apDiv[] */ int i, j, k; /* Loop counters */ int idx; /* Index of pPage in pParent->apCell[] */ int nxDiv; /* Next divider slot in pParent->apCell[] */ int rc; /* The return code */ int iCur; /* apCell[iCur] is the cell of the cursor */ MemPage *pOldCurPage; /* The cursor originally points to this page */ int subtotal; /* Subtotal of bytes in cells on one page */ MemPage *apOld[NB]; /* pPage and up to two siblings */ Pgno pgnoOld[NB]; /* Page numbers for each page in apOld[] */ MemPage *apCopy[NB]; /* Private copies of apOld[] pages */ MemPage *apNew[NB+1]; /* pPage and up to NB siblings after balancing */ Pgno pgnoNew[NB+1]; /* Page numbers for each page in apNew[] */ int idxDiv[NB]; /* Indices of divider cells in pParent */ u8 *apDiv[NB]; /* Divider cells in pParent */ u8 aTemp[NB][MX_CELL_SIZE]; /* Temporary holding area for apDiv[] */ int cntNew[NB+1]; /* Index in apCell[] of cell after i-th page */ int szNew[NB+1]; /* Combined size of cells place on i-th page */ u8 *apCell[(MX_CELL+2)*NB]; /* All cells from pages being balanced */ int szCell[(MX_CELL+2)*NB]; /* Local size of all cells */ u8 aCopy[NB][MX_PAGE_SIZE+sizeof(MemPage)]; /* Space for apCopy[] */ /* ** Return without doing any work if pPage is neither overfull nor ** underfull. */ assert( sqlitepager_iswriteable(pPage->aData) ); pBt = pPage->pBt; if( !pPage->isOverfull && pPage->nFree<pBt->pageSize/2 && pPage->nCell>=2){ relinkCellList(pPage); return SQLITE_OK; } /* ** Find the parent of the page to be balanced. If there is no parent, ** it means this page is the root page and special rules apply. */ pParent = pPage->pParent; if( pParent==0 ){ Pgno pgnoChild; MemPage *pChild; assert( pPage->isInit ); if( pPage->nCell==0 ){ if( pPage->leaf ){ /* The table is completely empty */ relinkCellList(pPage); }else{ /* The root page is empty but has one child. Transfer the ** information from that one child into the root page if it ** will fit. This reduces the depth of the BTree by one. ** ** If the root page is page 1, it has less space available than ** its child (due to the 100 byte header that occurs at the beginning ** of the database fle), so it might not be able to hold all of the ** information currently contained in the child. If this is the ** case, then do not do the transfer. Leave page 1 empty except ** for the right-pointer to the child page. The child page becomes ** the virtual root of the tree. */ pgnoChild = get4byte(pPage->aData[pPage->hdrOffset+6]); assert( pgnoChild>0 && pgnoChild<=sqlit3pager_pagecount(pBt->pPager) ); rc = getPage(pBt, pgnoChild, &pChild); if( rc ) return rc; if( pPage->pgno==1 ){ rc = initPage(pChild, pPage); if( rc ) return rc; if( pChild->nFree>=100 ){ /* The child information will fit on the root page, so do the ** copy */ zeroPage(pPage, pChild->aData[0]); resizeCellArray(pPage, pChild->nCell); for(i=0; i<pChild->nCell; i++){ insertCell(pPage, i, pChild->aCell[i], cellSize(pChild, pChild->aCell[i])); } freePage(pChild); }else{ /* The child has more information that will fit on the root. ** The tree is already balanced. Do nothing. */ } }else{ memcpy(pPage, pChild, pBt->pageSize); pPage->isInit = 0; pPage->pParent = 0; rc = initPage(pPage, 0); assert( rc==SQLITE_OK ); freePage(pChild); } reparentChildPages(pPage); releasePage(pChild); }else{ relinkCellList(pPage); } return SQLITE_OK; } if( !pPage->isOverfull ){ /* It is OK for the root page to be less than half full. */ relinkCellList(pBt, pPage); return SQLITE_OK; } /* ** If we get to here, it means the root page is overfull. ** When this happens, Create a new child page and copy the ** contents of the root into the child. Then make the root ** page an empty page with rightChild pointing to the new ** child. Then fall thru to the code below which will cause ** the overfull child page to be split. */ rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno); if( rc ) return rc; assert( sqlitepager_iswriteable(pChild->aData) ); copyPage(pChild, pPage); pChild->pParent = pPage; pChild->idxParent = 0; sqlitepager_ref(pPage->aData); pChild->isOverfull = 1; zeroPage(pPage, pPage->aData[pPage->hdrOffset] & ~PTF_LEAF); put4byte(&pPage->aData[pPage->hdrOffset+6], pChild->pgno); pParent = pPage; pPage = pChild; } rc = sqlitepager_write(pParent->aData); if( rc ) return rc; assert( pParent->isInit ); /* ** Find the cell in the parent page whose left child points back ** to pPage. The "idx" variable is the index of that cell. If pPage ** is the rightmost child of pParent then set idx to pParent->nCell */ if( pParent->idxShift ){ Pgno pgno, swabPgno; pgno = pPage->pgno; assert( pgno==sqlitepager_pagenumber(pPage->aData) ); for(idx=0; idx<pParent->nCell; idx++){ if( get4byte(pParent->aCell[idx][2])==pgno ){ break; } } assert( idx<pParent->nCell || get4byte(&pParent->aData[pParent->hdrOffset+6])==pgno ); }else{ idx = pPage->idxParent; } /* ** Initialize variables so that it will be safe to jump ** directly to balance_cleanup at any moment. */ nOld = nNew = 0; sqlitepager_ref(pParent->aData); /* ** Find sibling pages to pPage and the cells in pParent that divide ** the siblings. An attempt is made to find NN siblings on either ** side of pPage. More siblings are taken from one side, however, if ** pPage there are fewer than NN siblings on the other side. If pParent ** has NB or fewer children then all children of pParent are taken. */ nxDiv = idx - NN; if( nxDiv + NB > pParent->nCell ){ nxDiv = pParent->nCell - NB + 1; } if( nxDiv<0 ){ nxDiv = 0; } nDiv = 0; for(i=0, k=nxDiv; i<NB; i++, k++){ if( k<pParent->nCell ){ idxDiv[i] = k; apDiv[i] = pParent->aCell[k]; nDiv++; assert( !pParent->left ); pgnoOld[i] = get4byte(&apDev[i][2]); }else if( k==pParent->nCell ){ pgnoOld[i] = get4byte(&pParent->aData[pParent->hdrOffset+6]); }else{ break; } rc = getPage(pBt, pgnoOld[i], &apOld[i]); if( rc ) goto balance_cleanup; rc = initPage(apOld[i], pParent); if( rc ) goto balance_cleanup; apOld[i]->idxParent = k; nOld++; } /* ** Make copies of the content of pPage and its siblings into aOld[]. ** The rest of this function will use data from the copies rather ** that the original pages since the original pages will be in the ** process of being overwritten. */ for(i=0; i<nOld; i++){ apCopy[i] = (MemPage*)&aCopy[i+1][-sizeof(MemPage)]; memset(apCopy[i], 0, sizeof(MemPage)); apCopy[i]->aData = &((u8*)apCopy)[-pBt->pageSize]; copyPage(apCopy[i], apOld[i]); } /* ** Load pointers to all cells on sibling pages and the divider cells ** into the local apCell[] array. Make copies of the divider cells ** into aTemp[] and remove the the divider Cells from pParent. ** ** If the siblings are on leaf pages, then the child pointers of the ** divider cells are stripped from the cells before they are copied ** into aTemp[]. In this wall, all cells in apCell[] are without ** child pointers. If siblings are not leaves, then all cell in ** apCell[] include child pointers. Either way, all cells in apCell[] ** are alike. */ nCell = 0; leafCorrection = pPage->leaf*4; for(i=0; i<nOld; i++){ MemPage *pOld = apCopy[i]; for(j=0; j<pOld->nCell; j++){ apCell[nCell] = pOld->aCell[j]; szCell[nCell] = cellSize(pOld, apCell[nCell]); nCell++; } if( i<nOld-1 ){ szCell[nCell] = cellSize(pParent, apDiv[i]) - leafCorrection; memcpy(aTemp[i], apDiv[i], szCell[nCell] + leafCorrection); apCell[nCell] = &aTemp[i][leafCorrection]; dropCell(pParent, nxDiv, szCell[nCell]); assert( get4byte(&apCell[nCell][2])==pgnoOld[i] ); if( !pOld->leaf ){ assert( leafCorrection==0 ); /* The right pointer of the child page pOld becomes the left ** pointer of the divider cell */ memcpy(&apCell[nCell][2], &pOld->aData[pOld->hdrOffset+6], 4); }else{ assert( leafCorrection==4 ); } nCell++; } } /* ** Figure out the number of pages needed to hold all nCell cells. ** Store this number in "k". Also compute szNew[] which is the total ** size of all cells on the i-th page and cntNew[] which is the index ** in apCell[] of the cell that divides page i from page i+1. ** cntNew[k] should equal nCell. ** ** This little patch of code is critical for keeping the tree ** balanced. */ usableSpace = pBt->pageSize - 10 + leafCorrection; for(subtotal=k=i=0; i<nCell; i++){ subtotal += szCell[i]; if( subtotal > usableSpace ){ szNew[k] = subtotal - szCell[i]; cntNew[k] = i; subtotal = 0; k++; } } szNew[k] = subtotal; cntNew[k] = nCell; k++; for(i=k-1; i>0; i--){ while( szNew[i]<usableSpace/2 ){ cntNew[i-1]--; assert( cntNew[i-1]>0 ); szNew[i] += szCell[cntNew[i-1]]; szNew[i-1] -= szCell[cntNew[i-1]-1]; } } assert( cntNew[0]>0 ); /* ** Allocate k new pages. Reuse old pages where possible. */ assert( pPage->pgno>1 ); pageFlags = pPage->aData[0]; for(i=0; i<k; i++){ if( i<nOld ){ apNew[i] = apOld[i]; pgnoNew[i] = pgnoOld[i]; apOld[i] = 0; sqlitepager_write(apNew[i]); }else{ rc = allocatePage(pBt, &apNew[i], &pgnoNew[i], pgnoNew[i-1]); if( rc ) goto balance_cleanup; } nNew++; zeroPage(apNew[i], pageFlags); apNew[i]->isInit = 1; } /* Free any old pages that were not reused as new pages. */ while( i<nOld ){ rc = freePage(apOld[i]); if( rc ) goto balance_cleanup; sqlitepager_unref(apOld[i]->aData); apOld[i] = 0; i++; } /* ** Put the new pages in accending order. This helps to ** keep entries in the disk file in order so that a scan |
︙ | ︙ | |||
2694 2695 2696 2697 2698 2699 2700 2701 2702 | /* ** 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]; while( j<cntNew[i] ){ assert( pNew->nFree>=szCell[j] ); | > > < | | > | < > > > | > > | > > | > > | < < < < < < < < < < | | | < < < | | < < < < | < | 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 | /* ** 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]; assert( pNew->pgno==pgnoNew[i] ); resizeCellArray(pNew, cntNew[i] - j); while( j<cntNew[i] ){ assert( pNew->nFree>=szCell[j] ); insertCell(pBt, pNew, pNew->nCell, apCell[j], szCell[j]); j++; } assert( pNew->nCell>0 ); assert( !pNew->isOverfull ); relinkCellList(pNew); if( i<nNew-1 && j<nCell ){ u8 *pCell = apCell[j]; if( !pNew->leaf ){ memcpy(&pNew->aData[6], &apCell[j][2], 4); }else{ pCell -= 4; } insertCell(pParent, nxDiv, pCell, szCell[j]+leafCorrection); put4byte(&pParent->aCell[nxDiv][2], pNew->pgno); j++; nxDiv++; } } assert( j==nCell ); if( (pageFlags & PTF_LEAF)==0 ){ memcpy(&apNew[nNew-1]->aData[6], &apCopy[nOld-1]->aData[6], 4); } if( nxDiv==pParent->nCell ){ /* Right-most sibling is the right-most child of pParent */ put4byte(&pParent->aData[pParent->hdrOffset+6], pgnoNew[nNew-1]); }else{ /* Right-most sibling is the left child of the first entry in pParent ** past the right-most divider entry */ put4byte(&pParent->apCell[nxDiv][2], pgnoNew[nNew-1]); } /* ** Reparent children of all cells. */ for(i=0; i<nNew; i++){ reparentChildPages(apNew[i]); } reparentChildPages(pParent); /* ** balance the parent page. */ rc = balance(pParent); /* ** Cleanup before returning. */ balance_cleanup: for(i=0; i<nOld; i++){ if( apOld[i]!=0 ) sqlitepager_unref(apOld[i]->aData); } for(i=0; i<nNew; i++){ sqlitepager_unref(apNew[i]->aData); } sqlitepager_unref(pParent->aData); return rc; } /* ** This routine checks all cursors that point to the same table ** as pCur points to. If any of those cursors were opened with ** wrFlag==0 then this routine returns SQLITE_LOCKED. If all |
︙ | ︙ | |||
2798 2799 2800 2801 2802 2803 2804 | 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 database the record should be inserted into. The cursor | | > > > | < > > | | > > | > > > > | | | | | | > | < | < < < < < < < < < | | 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 2907 2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942 2943 2944 2945 2946 2947 2948 2949 2950 2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 | 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 database the record should be inserted into. The cursor ** is left pointing at a random location. ** ** For an INTKEY table, only the nKey value of the key is used. pKey is ** ignored. For a ZERODATA table, the pData and nData are both ignored. */ int sqlite3BtreeInsert( BtCursor *pCur, /* Insert data into the table of this cursor */ const void *pKey, u64 nKey, /* The key of the new record */ const void *pData, int nData /* The data of the new record */ ){ int rc; int loc; int szNew; MemPage *pPage; Btree *pBt = pCur->pBt; unsigned char newCell[MX_CELL_SIZE], *oldCell; if( pCur->pPage==0 ){ return SQLITE_ABORT; /* A rollback destroyed this cursor */ } if( !pBt->inTrans || nKey+nData==0 ){ /* Must start a transaction before doing an insert */ return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR; } assert( !pBt->readOnly ); if( !pCur->wrFlag ){ return SQLITE_PERM; /* Cursor not open for writing */ } if( checkReadLocks(pCur) ){ return SQLITE_LOCKED; /* The table pCur points to has a read lock */ } rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc); if( rc ) return rc; pPage = pCur->pPage; assert( nData==0 || pPage->zeroData!=0 ); assert( pPage->isInit ); rc = sqlitepager_write(pPage); if( rc ) return rc; rc = fillInCell(pPage, &newCell, pKey, nKey, pData, nData, &szNew); if( rc ) return rc; assert( szNew==cellSize(pPage, newCell) ); if( loc==0 ){ int szOld assert( pCur->idx>=0 && pCur->idx<pPage->nPage ); oldCell = pPage->aCell[pCur->idx]; if( !pPage->leaf ){ memcpy(&newCell[2], &oldCell[2], 4); } szOld = cellSize(pPage, oldCell); rc = clearCell(pPage, oldCell); if( rc ) return rc; dropCell(pPage, pCur->idx, szOld); }else if( loc<0 && pPage->nCell>0 ){ assert( pPage->leaf ); pCur->idx++; }else{ assert( pPage->leaf ); } insertCell(pPage, pCur->idx, &newCell, szNew); rc = balance(pPage); /* sqliteBtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */ /* fflush(stdout); */ moveToRoot(pCur); pCur->eSkip = SKIP_INVALID; 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; Btree *pBt = pCur->pBt; assert( pPage->isInit ); if( pCur->pPage==0 ){ return SQLITE_ABORT; /* A rollback destroyed this cursor */ |
︙ | ︙ | |||
2895 2896 2897 2898 2899 2900 2901 | return SQLITE_PERM; /* Did not open this cursor for writing */ } if( checkReadLocks(pCur) ){ return SQLITE_LOCKED; /* The table pCur points to has a read lock */ } rc = sqlitepager_write(pPage); if( rc ) return rc; | | > | > | | | | | | < | > | < | | | < < < < < < < < < < < | > | 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 | return SQLITE_PERM; /* Did not open this cursor for writing */ } if( checkReadLocks(pCur) ){ return SQLITE_LOCKED; /* The table pCur points to has a read lock */ } rc = sqlitepager_write(pPage); if( rc ) return rc; pCell = pPage->aCell[pCur->idx]; if( !pPage->leaf ){ pgnoChild = get4byte(&pCell[2]); } 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. */ BtCursor leafCur; unsigned char *pNext; int szNext; int notUsed; getTempCursor(pCur, &leafCur); rc = sqlite3BtreeNext(&leafCur, ¬Used); if( rc!=SQLITE_OK ){ if( rc!=SQLITE_NOMEM ) rc = SQLITE_CORRUPT; return rc; } rc = sqlitepager_write(leafCur.pPage); if( rc ) return rc; dropCell(pPage, pCur->idx, cellSize(pPage, pCell)); pNext = leafCur.pPage->aCell[leafCur.idx]; szNext = cellSize(leafCur.pPage, pNext); insertCell(pPage, pCur->idx, &pNext[-4], szNext+4); put4byte(&pNext[-2], pgnoChild); rc = balance(pPage); if( rc ) return rc; dropCell(leafCur.pPage, leafCur.idx, szNext); rc = balance(leafCur.pPage); releaseTempCursor(&leafCur); }else{ dropCell(pPage, pCur->idx, cellSize(pPage, pCell)); rc = balance(pPage); } moveToRoot(pCur); return rc; } /* ** Create a new BTree table. Write into *piTable the page ** number for the root page of the new table. ** |
︙ | ︙ | |||
2970 2971 2972 2973 2974 2975 2976 | return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR; } if( pBt->readOnly ){ return SQLITE_READONLY; } rc = allocatePage(pBt, &pRoot, &pgnoRoot, 0); if( rc ) return rc; | | | > > > > > | | | | | | < | < | | | | | | | | | 3046 3047 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 | return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR; } if( pBt->readOnly ){ return SQLITE_READONLY; } rc = allocatePage(pBt, &pRoot, &pgnoRoot, 0); if( rc ) return rc; assert( sqlitepager_iswriteable(pRoot->aData) ); zeroPage(pBt, pRoot); sqlitepager_unref(pRoot); *piTable = (int)pgnoRoot; return SQLITE_OK; } /* ** Erase the given database page and all its children. Return ** the page to the freelist. */ static int clearDatabasePage( Btree *pBt, /* The BTree that contains the table */ Pgno pgno, /* Page number to clear */ MemPage *pParent, /* Parent page. NULL for the root */ int freePageFlag /* Deallocate page if true */ ){ MemPage *pPage; int rc; unsigned char *pCell; int i; rc = getPage(pBt, pgno, &pPage); if( rc ) return rc; rc = sqlitepager_write(pPage->aData); if( rc ) return rc; rc = initPage(pPage, pParent); if( rc ) return rc; for(i=0; i<pPage->nCell; i++){ pCell = pPage->aCell[i]; if( !pPage->leaf ){ rc = clearDatabasePage(pBt, get4byte(&pCell[2]), 1); if( rc ) return rc; } rc = clearCell(pPage, pCell); if( rc ) return rc; } if( !pPage->left ){ rc = clearDatabasePage(pBt, get4byte(&pPage->aData[6]), 1); if( rc ) return rc; } if( freePageFlag ){ rc = freePage(pPage); }else{ zeroPage(pPage, pPage->aData[0]); } releasePage(pPage); return rc; } /* ** Delete all information from a single table in the database. */ int sqlite3BtreeClearTable(Btree *pBt, int iTable){ |
︙ | ︙ | |||
3056 3057 3058 3059 3060 3061 3062 | return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR; } for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){ if( pCur->pgnoRoot==(Pgno)iTable ){ return SQLITE_LOCKED; /* Cannot drop a table that has a cursor */ } } | | | | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < > > | < < < | > | > | | < < > | | > > | | > > > | | > > > > > > < < | | | | > | > | | | | | | | | | | | | | 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191 3192 3193 3194 3195 3196 3197 3198 3199 3200 3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 3225 3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 3240 3241 3242 3243 3244 3245 3246 3247 3248 3249 3250 3251 3252 3253 3254 3255 3256 3257 3258 3259 3260 3261 3262 3263 3264 3265 3266 3267 3268 3269 3270 3271 3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 | return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR; } for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){ if( pCur->pgnoRoot==(Pgno)iTable ){ return SQLITE_LOCKED; /* Cannot drop a table that has a cursor */ } } rc = getPage(pBt, (Pgno)iTable, pPage); if( rc ) return rc; rc = sqlite3BtreeClearTable(pBt, iTable); if( rc ) return rc; if( iTable>1 ){ rc = freePage(pBt, pPage, iTable); }else{ zeroPage(pBt, pPage); } releasePage(pPage); return rc; } /* ** Read the meta-information out of a database file. */ int sqlite3BtreeGetMeta(Btree *pBt, int idx, u32 *pMeta){ int rc; int i; unsigned char *pP1; assert( idx>=0 && idx<15 ); rc = sqlitepager_get(pBt->pPager, 1, (void**)&pP1); if( rc ) return rc; *pMeta = get4byte(&pP1[40 + idx*4]); sqlitepager_unref(pP1); return SQLITE_OK; } /* ** Write meta-information back into the database. */ int sqlite3BtreeUpdateMeta(Btree *pBt, int idx, u32 iMeta){ unsigned char *pP1; int rc, i; assert( idx>=0 && idx<15 ); if( !pBt->inTrans ){ return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR; } rc = sqlitepager_get(pBt->pPager, 1, (void**)&pP1); if( rc ) return rc; rc = sqlitepager_write(pP1); if( rc ) return rc; put4byte(&pP1[40 + idx*4], iMeta); return SQLITE_OK; } /****************************************************************************** ** The complete implementation of the BTree subsystem is above this line. ** All the code the follows is for testing and troubleshooting the BTree ** subsystem. None of the code that follows is used during normal operation. ******************************************************************************/ /* ** Print a disassembly of the given page on standard output. This routine ** is used for debugging and testing only. */ #ifdef SQLITE_TEST static int fileBtreePageDump(Btree *pBt, int pgno, int recursive){ int rc; MemPage *pPage; int i, j; int nFree; u16 idx; int hdrOffset; char range[20]; unsigned char payload[20]; rc = getPage(pBt, (Pgno)pgno, &pPage); if( rc ){ return rc; } printf("PAGE %d: flags=0x%02x frag=%d\n", pgno, pPage->aData[0], pPage->aData[5]); i = 0; hdrOffset = pgno==1 ? 100 : 0; idx = get2byte(&pPage->aData[hdrOffset+3]); while( idx>0 && idx<=pBt->pageSize ){ u64 nData, nKey; int nHeader; Pgno child; unsigned char *pCell = &pPage->aData[idx]; int sz = cellSize(pPage, pCell); sprintf(range,"%d..%d", idx, idx+sz-1); parseCellHeader(pPage, pCell, &nData, &nKey, &nHeader); if( pPage->leaf ){ child = 0; }else{ child = get4byte(&pCell[2]); } sz = NKEY(pBt, pCell->h) + NDATA(pBt, pCell->h); 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=%-4d nd=%-4d payload=%s\n", i, range, child, (int)nKey, (int)nData, payload ); if( pPage->isInit && pPage->aCell[i]!=pCell ){ printf("**** aCell[%d] does not match on prior entry ****\n", i); } i++; idx = get2byte(pCell); } if( idx!=0 ){ printf("ERROR: next cell index out of range: %d\n", idx); } if( !pPage->leaf ){ printf("right_child: %d\n", get4byte(&pPage->aData[6])); } nFree = 0; i = 0; idx = get2byte(&pPage->aData[hdrOffset+1]); while( idx>0 && idx<SQLITE_USABLE_SIZE ){ int sz = get2byte(&pPage->aData[idx+2]); sprintf(range,"%d..%d", idx, idx+sz-1); nFree += sz; printf("freeblock %2d: i=%-10s size=%-4d total=%d\n", i, range, sz, nFree); idx = get2byte(&pPage->aData[idx]); i++; } if( idx!=0 ){ printf("ERROR: next freeblock index out of range: %d\n", idx); } if( recursive && !pPage->left ){ idx = get2byte(&pPage->aData[hdrOffset+3]); while( idx>0 && idx<SQLITE_USABLE_SIZE-MIN_CELL_SIZE ){ unsigned char *pCell = &pPage->aData[idx]; fileBtreePageDump(pBt, get4byte(&pPage->aData[idx+2]), 1); idx = get2byte(&pPage->aData[idx]); } fileBtreePageDump(pBt, get4byte(&pPage->aData[hdrOffset+6]), 1); } sqlitepager_unref(pPage); return SQLITE_OK; } #endif #ifdef SQLITE_TEST |
︙ | ︙ | |||
3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 | ** ** This routine is used for testing and debugging only. */ static int fileBtreeCursorDump(BtCursor *pCur, int *aResult){ int cnt, idx; MemPage *pPage = pCur->pPage; Btree *pBt = pCur->pBt; aResult[0] = sqlitepager_pagenumber(pPage); aResult[1] = pCur->idx; aResult[2] = pPage->nCell; if( pCur->idx>=0 && pCur->idx<pPage->nCell ){ | > | | | | | | 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 | ** ** This routine is used for testing and debugging only. */ static int fileBtreeCursorDump(BtCursor *pCur, int *aResult){ int cnt, idx; MemPage *pPage = pCur->pPage; Btree *pBt = pCur->pBt; assert( pPage->isInit ); 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, pPage->aCell[pCur->idx]); aResult[6] = pPage->leaf ? 0 : get4byte(&pPage->aCell[pCur->idx][2]); }else{ aResult[3] = 0; aResult[6] = 0; } aResult[4] = pPage->nFree; cnt = 0; idx = get2byte(&pPage->aData[pPage->hdrOffset+1]); while( idx>0 && idx<SQLITE_USABLE_SIZE ){ cnt++; idx = get2byte(&pPage->aData[idx]); } aResult[5] = cnt; aResult[7] = pPage->leaf ? 0 : get4byte(&pPage->aData[pPage->hdrOffset+6]); return SQLITE_OK; } #endif /* ** Return the pager associated with a BTree. This routine is used for ** testing and debugging only. |
︙ | ︙ | |||
3402 3403 3404 3405 3406 3407 3408 | int iPage, /* Page number for first page in the list */ int N, /* Expected number of pages in the list */ char *zContext /* Context for error messages */ ){ int i; char zMsg[100]; while( N-- > 0 ){ | | < | | | | 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 | int iPage, /* Page number for first page in the list */ int N, /* Expected number of pages in the list */ char *zContext /* Context for error messages */ ){ int i; char zMsg[100]; while( N-- > 0 ){ unsigned char *pOvfl; if( iPage<1 ){ sprintf(zMsg, "%d pages missing from overflow list", N+1); checkAppendMsg(pCheck, zContext, zMsg); break; } if( checkRef(pCheck, iPage, zContext) ) break; if( sqlitepager_get(pCheck->pPager, (Pgno)iPage, (void**)&pOvfl) ){ sprintf(zMsg, "failed to get page %d", iPage); checkAppendMsg(pCheck, zContext, zMsg); break; } if( isFreeList ){ int n = get4byte(&pOvfl[4]); for(i=0; i<n; i++){ checkRef(pCheck, get4byte(&pOvfl[8+i*4]), zContext); } N -= n; } iPage = get4byte(pOvfl); sqlitepager_unref(pOvfl); } } /* ** Return negative if zKey1<zKey2. ** Return zero if zKey1==zKey2. |
︙ | ︙ | |||
3488 3489 3490 3491 3492 3493 3494 | /* Check that the page exists */ cur.pBt = pBt = pCheck->pBt; if( iPage==0 ) return 0; if( checkRef(pCheck, iPage, zParentContext) ) return 0; sprintf(zContext, "On tree page %d: ", iPage); | | | > > | 3480 3481 3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492 3493 3494 3495 3496 3497 3498 3499 3500 3501 3502 3503 3504 3505 3506 | /* Check that the page exists */ cur.pBt = pBt = pCheck->pBt; if( iPage==0 ) return 0; if( checkRef(pCheck, iPage, zParentContext) ) return 0; sprintf(zContext, "On tree page %d: ", iPage); if( (rc = getPage(pBt, (Pgno)iPage, &pPage))!=0 ){ sprintf(zMsg, "unable to get the page. error code=%d", rc); checkAppendMsg(pCheck, zContext, zMsg); return 0; } if( (rc = initPage(pPage, pParent))!=0 ){ sprintf(zMsg, "initPage() returns error code %d", rc); checkAppendMsg(pCheck, zContext, zMsg); sqlitepager_unref(pPage); return 0; } #if 0 /* Check out all the cells. */ depth = 0; if( zLowerBound ){ zKey1 = sqliteMalloc( nLower+1 ); memcpy(zKey1, zLowerBound, nLower); |
︙ | ︙ | |||
3580 3581 3582 3583 3584 3585 3586 | }else if( hit[i]>1 ){ sprintf(zMsg, "Multiple uses for byte %d of page %d", i, iPage); checkAppendMsg(pCheck, zMsg, 0); break; } } | < < < < < < < < | | 3574 3575 3576 3577 3578 3579 3580 3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 | }else if( hit[i]>1 ){ sprintf(zMsg, "Multiple uses for byte %d of page %d", i, iPage); checkAppendMsg(pCheck, zMsg, 0); break; } } #endif releasePage(pPage); return depth; } /* ** This routine does a complete check of the given BTree file. aRoot[] is ** an array of pages numbers were each page number is the root page of ** a table. nRoot is the number of entries in aRoot. |
︙ | ︙ |