Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Optimizations to the BTree module for a modest speed improvement. (CVS 810) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
39902a70417475225956704a03749351 |
User & Date: | drh 2003-01-04 16:48:09.000 |
Context
2003-01-04
| ||
18:53 | Another optimization to the btree logic. (CVS 811) (check-in: 03d2067361 user: drh tags: trunk) | |
16:48 | Optimizations to the BTree module for a modest speed improvement. (CVS 810) (check-in: 39902a7041 user: drh tags: trunk) | |
2003-01-03
| ||
02:04 | Allow the rollback journal to be empty except for its header. Ticket #212. (CVS 809) (check-in: 1ba41bc2af user: drh tags: trunk) | |
Changes
Changes to src/btree.c.
1 2 3 4 5 6 7 8 9 10 11 | /* ** 2001 September 15 ** ** The author disclaims copyright to this source code. In place of ** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /* ** 2001 September 15 ** ** The author disclaims copyright to this source code. In place of ** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** $Id: btree.c,v 1.77 2003/01/04 16:48:09 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. |
︙ | ︙ | |||
315 316 317 318 319 320 321 | ** The pageDestructor() routine handles that chore. */ struct MemPage { union { char aDisk[SQLITE_PAGE_SIZE]; /* Page data stored on disk */ PageHdr hdr; /* Overlay page header */ } u; | | > > > < | 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 | ** The pageDestructor() routine handles that chore. */ struct MemPage { union { char aDisk[SQLITE_PAGE_SIZE]; /* Page data stored on disk */ PageHdr hdr; /* Overlay page header */ } u; u8 isInit; /* True if auxiliary data is initialized */ u8 idxShift; /* True if apCell[] indices have changed */ u8 isOverfull; /* Some apCell[] points outside u.aDisk[] */ MemPage *pParent; /* The parent of this page. NULL for root */ int idxParent; /* Index in pParent->apCell[] of this node */ int nFree; /* Number of free bytes in u.aDisk[] */ int nCell; /* Number of entries on this page */ Cell *apCell[MX_CELL+2]; /* All data entires in sorted order */ }; /* ** 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. |
︙ | ︙ | |||
1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 | MemPage *pNewPage; Btree *pBt = pCur->pBt; rc = sqlitepager_get(pBt->pPager, newPgno, (void**)&pNewPage); if( rc ) return rc; rc = initPage(pBt, pNewPage, newPgno, pCur->pPage); if( rc ) return rc; sqlitepager_unref(pCur->pPage); pCur->pPage = pNewPage; pCur->idx = 0; return SQLITE_OK; } /* ** Move the cursor up to the parent page. ** ** pCur->idx is set to the cell index that contains the pointer ** to the page we are coming from. If we are coming from the ** right-most child page then pCur->idx is set to one more than ** the largest cell index. */ static int moveToParent(BtCursor *pCur){ Pgno oldPgno; MemPage *pParent; | > > > > > > | > > > > > > > > > > > > > > > > > > > > > > | | | | | | > | 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 | MemPage *pNewPage; Btree *pBt = pCur->pBt; rc = sqlitepager_get(pBt->pPager, newPgno, (void**)&pNewPage); if( rc ) return rc; rc = initPage(pBt, pNewPage, newPgno, pCur->pPage); if( rc ) return rc; assert( pCur->idx>=pCur->pPage->nCell || pCur->pPage->apCell[pCur->idx]->h.leftChild==SWAB32(pBt,newPgno) ); assert( pCur->idx<pCur->pPage->nCell || pCur->pPage->u.hdr.rightChild==SWAB32(pBt,newPgno) ); pNewPage->idxParent = pCur->idx; pCur->pPage->idxShift = 0; sqlitepager_unref(pCur->pPage); pCur->pPage = pNewPage; pCur->idx = 0; return SQLITE_OK; } /* ** Move the cursor up to the parent page. ** ** pCur->idx is set to the cell index that contains the pointer ** to the page we are coming from. If we are coming from the ** right-most child page then pCur->idx is set to one more than ** the largest cell index. */ static int moveToParent(BtCursor *pCur){ Pgno oldPgno; MemPage *pParent; int idxParent; pParent = pCur->pPage->pParent; if( pParent==0 ) return SQLITE_INTERNAL; idxParent = pCur->pPage->idxParent; oldPgno = sqlitepager_pagenumber(pCur->pPage); sqlitepager_ref(pParent); sqlitepager_unref(pCur->pPage); pCur->pPage = pParent; assert( pParent->idxShift==0 ); if( pParent->idxShift==0 ){ pCur->idx = idxParent; #ifndef NDEBUG /* Verify that pCur->idx is the correct index to point back to the child ** page we just came from */ oldPgno = SWAB32(pCur->pBt, oldPgno); if( pCur->idx<pParent->nCell ){ assert( pParent->apCell[idxParent]->h.leftChild==oldPgno ); }else{ assert( pParent->u.hdr.rightChild==oldPgno ); } #endif }else{ /* The MemPage.idxShift flag indicates that cell indices might have ** changed since idxParent was set and hence idxParent might be out ** of date. So recompute the parent cell index by scanning all cells ** and locating the one that points to the child we just came from. */ int i; pCur->idx = pParent->nCell; oldPgno = SWAB32(pCur->pBt, oldPgno); for(i=0; i<pParent->nCell; i++){ if( pParent->apCell[i]->h.leftChild==oldPgno ){ pCur->idx = i; break; } } } return SQLITE_OK; } /* ** Move the cursor to the root page |
︙ | ︙ | |||
1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 | ** finds the right-most entry beneath the *page*. */ static int moveToRightmost(BtCursor *pCur){ Pgno pgno; int rc; while( (pgno = pCur->pPage->u.hdr.rightChild)!=0 ){ rc = moveToChild(pCur, SWAB32(pCur->pBt, pgno)); if( rc ) return rc; } pCur->idx = pCur->pPage->nCell - 1; return SQLITE_OK; } | > | 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 | ** finds the right-most entry beneath the *page*. */ static int moveToRightmost(BtCursor *pCur){ Pgno pgno; int rc; while( (pgno = pCur->pPage->u.hdr.rightChild)!=0 ){ pCur->idx = pCur->pPage->nCell; rc = moveToChild(pCur, SWAB32(pCur->pBt, pgno)); if( rc ) return rc; } pCur->idx = pCur->pPage->nCell - 1; return SQLITE_OK; } |
︙ | ︙ | |||
1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 | chldPg = pPage->apCell[lwr]->h.leftChild; } if( chldPg==0 ){ pCur->iMatch = c; if( pRes ) *pRes = c; return SQLITE_OK; } rc = moveToChild(pCur, SWAB32(pCur->pBt, chldPg)); if( rc ) return rc; } /* NOT REACHED */ } /* | > | 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 | chldPg = pPage->apCell[lwr]->h.leftChild; } if( chldPg==0 ){ pCur->iMatch = c; if( pRes ) *pRes = c; return SQLITE_OK; } pCur->idx = lwr; rc = moveToChild(pCur, SWAB32(pCur->pBt, chldPg)); if( rc ) return rc; } /* NOT REACHED */ } /* |
︙ | ︙ | |||
1883 1884 1885 1886 1887 1888 1889 | } /* ** 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. */ | | > | | > | 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 | } /* ** 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(Pager *pPager, Pgno pgno, MemPage *pNewParent,int idx){ MemPage *pThis; if( pgno==0 ) return; assert( pPager!=0 ); pThis = sqlitepager_lookup(pPager, pgno); if( pThis && pThis->isInit ){ if( pThis->pParent!=pNewParent ){ if( pThis->pParent ) sqlitepager_unref(pThis->pParent); pThis->pParent = pNewParent; if( pNewParent ) sqlitepager_ref(pNewParent); } pThis->idxParent = idx; sqlitepager_unref(pThis); } } /* ** Reparent all children of the given page to be the given page. ** 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(Btree *pBt, MemPage *pPage){ int i; Pager *pPager = pBt->pPager; for(i=0; i<pPage->nCell; i++){ reparentPage(pPager, SWAB32(pBt, pPage->apCell[i]->h.leftChild), pPage, i); } reparentPage(pPager, SWAB32(pBt, pPage->u.hdr.rightChild), 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. |
︙ | ︙ | |||
1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 | assert( sz==cellSize(pBt, pPage->apCell[idx]) ); assert( sqlitepager_iswriteable(pPage) ); freeSpace(pBt, pPage, Addr(pPage->apCell[idx]) - Addr(pPage), sz); for(j=idx; j<pPage->nCell-1; j++){ pPage->apCell[j] = pPage->apCell[j+1]; } pPage->nCell--; } /* ** 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 | > | 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 | assert( sz==cellSize(pBt, pPage->apCell[idx]) ); assert( sqlitepager_iswriteable(pPage) ); freeSpace(pBt, pPage, Addr(pPage->apCell[idx]) - Addr(pPage), sz); for(j=idx; j<pPage->nCell-1; j++){ pPage->apCell[j] = pPage->apCell[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 |
︙ | ︙ | |||
1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 | 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]; } } /* ** Rebuild the linked list of cells on a page so that the cells ** occur in the order specified by the pPage->apCell[] array. ** Invoke this routine once to repair damage after one or more ** invocations of either insertCell() or dropCell(). | > | 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 | 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]; } pPage->idxShift = 1; } /* ** Rebuild the linked list of cells on a page so that the cells ** occur in the order specified by the pPage->apCell[] array. ** Invoke this routine once to repair damage after one or more ** invocations of either insertCell() or dropCell(). |
︙ | ︙ | |||
2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 | rc = sqlitepager_write(pPage); if( rc ) return rc; rc = allocatePage(pBt, &pChild, &pgnoChild, sqlitepager_pagenumber(pPage)); if( rc ) return rc; assert( sqlitepager_iswriteable(pChild) ); copyPage(pChild, pPage); pChild->pParent = pPage; sqlitepager_ref(pPage); pChild->isOverfull = 1; if( pCur && pCur->pPage==pPage ){ sqlitepager_unref(pPage); pCur->pPage = pChild; }else{ extraUnref = pChild; | > | 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 | rc = sqlitepager_write(pPage); if( rc ) return rc; rc = allocatePage(pBt, &pChild, &pgnoChild, sqlitepager_pagenumber(pPage)); if( rc ) return rc; assert( sqlitepager_iswriteable(pChild) ); copyPage(pChild, pPage); pChild->pParent = pPage; pChild->idxParent = pChild->nCell; sqlitepager_ref(pPage); pChild->isOverfull = 1; if( pCur && pCur->pPage==pPage ){ sqlitepager_unref(pPage); pCur->pPage = pChild; }else{ extraUnref = pChild; |
︙ | ︙ | |||
2191 2192 2193 2194 2195 2196 2197 | idx = i; break; } } if( idx<0 && pParent->u.hdr.rightChild==swabPgno ){ idx = pParent->nCell; } | | | < | 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 | idx = i; break; } } if( idx<0 && pParent->u.hdr.rightChild==swabPgno ){ idx = pParent->nCell; } assert( idx>=0 ); /* assert( pParent->idxShift || 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); |
︙ | ︙ | |||
2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 | }else{ break; } rc = sqlitepager_get(pBt->pPager, pgnoOld[i], (void**)&apOld[i]); if( rc ) goto balance_cleanup; rc = initPage(pBt, apOld[i], pgnoOld[i], pParent); if( rc ) goto balance_cleanup; nOld++; } /* ** Set iCur to be the index in apCell[] of the cell that the cursor ** is pointing to. We will need this later on in order to keep the ** cursor pointing at the same cell. If pCur points to a page that | > | 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 | }else{ break; } rc = sqlitepager_get(pBt->pPager, pgnoOld[i], (void**)&apOld[i]); if( rc ) goto balance_cleanup; rc = initPage(pBt, apOld[i], pgnoOld[i], pParent); if( rc ) goto balance_cleanup; apOld[i]->idxParent = k; nOld++; } /* ** Set iCur to be the index in apCell[] of the cell that the cursor ** is pointing to. We will need this later on in order to keep the ** cursor pointing at the same cell. If pCur points to a page that |
︙ | ︙ |
Changes to test/table.test.
1 2 3 4 5 6 7 8 9 10 11 12 13 | # 2001 September 15 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing the CREATE TABLE statement. # | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # 2001 September 15 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing the CREATE TABLE statement. # # $Id: table.test,v 1.21 2003/01/04 16:48:10 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Create a basic table and verify it is added to sqlite_master # do_test table-1.1 { |
︙ | ︙ | |||
213 214 215 216 217 218 219 | # Drop the even numbered tables # set r {} for {set i 1} {$i<=100} {incr i 2} { lappend r [format test%03d $i] } | < > | 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 | # Drop the even numbered tables # set r {} for {set i 1} {$i<=100} {incr i 2} { lappend r [format test%03d $i] } do_test table-4.2 { for {set i 2} {$i<=100} {incr i 2} { # if {$i==38} {execsql {pragma vdbe_trace=on}} set sql "DROP TABLE [format TEST%03d $i]" execsql $sql } execsql {SELECT name FROM sqlite_master WHERE type!='meta' ORDER BY name} } $r #exit |
︙ | ︙ |