Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | More bug fixes in btree.c. (CVS 1323) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
2d64cba38c0f5fffa18cb30c4c448278 |
User & Date: | drh 2004-05-08 02:03:23.000 |
Context
2004-05-08
| ||
08:23 | Change lots of internal symbols from sqliteXXX to sqlite3XXX so that the library links again. It doesn't work yet, due to changes in the btree layer calling convention. (CVS 1324) (check-in: 8af6474c49 user: danielk1977 tags: trunk) | |
02:03 | More bug fixes in btree.c. (CVS 1323) (check-in: 2d64cba38c user: drh tags: trunk) | |
2004-05-07
| ||
23:50 | More bug fixes in btree.c. (CVS 1322) (check-in: a80939ef71 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.113 2004/05/08 02:03:23 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. |
︙ | ︙ | |||
1447 1448 1449 1450 1451 1452 1453 | } nextPage = get4byte(aPayload); if( offset<ovflSize ){ int a = amt; if( a + offset > ovflSize ){ a = ovflSize - offset; } | | | 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 | } nextPage = get4byte(aPayload); if( offset<ovflSize ){ int a = amt; if( a + offset > ovflSize ){ a = ovflSize - offset; } memcpy(pBuf, &aPayload[offset+4], a); offset = 0; amt -= a; pBuf += a; }else{ offset -= ovflSize; } sqlite3pager_unref(aPayload); |
︙ | ︙ | |||
2063 2064 2065 2066 2067 2068 2069 | if( d2<dist ) closest = i; } }else{ closest = 0; } put4byte(&aData[4], n-1); *pPgno = get4byte(&aData[8+closest*4]); | > | > > | | 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 | if( d2<dist ) closest = i; } }else{ closest = 0; } put4byte(&aData[4], n-1); *pPgno = get4byte(&aData[8+closest*4]); if( closest<k-1 ){ memcpy(&aData[8+closest*4], &aData[4+k*4], 4); } put4byte(&pTrunk->aData[4], k-1); rc = getPage(pBt, *pPgno, ppPage); releasePage(pTrunk); if( rc==SQLITE_OK ){ sqlite3pager_dont_rollback((*ppPage)->aData); rc = sqlite3pager_write((*ppPage)->aData); } } }else{ /* There are no pages on the freelist, so create a new page at the ** end of the file */ *pPgno = sqlite3pager_pagecount(pBt->pPager) + 1; |
︙ | ︙ | |||
2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 | int *pnSize /* Write cell size here */ ){ int nPayload; const void *pSrc; int nSrc, n, rc; int spaceLeft; MemPage *pOvfl = 0; unsigned char *pPrior; unsigned char *pPayload; Btree *pBt = pPage->pBt; Pgno pgnoOvfl = 0; int nHeader; /* Fill in the header. */ | > | 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 | int *pnSize /* Write cell size here */ ){ int nPayload; const void *pSrc; int nSrc, n, rc; int spaceLeft; MemPage *pOvfl = 0; MemPage *pToRelease = 0; unsigned char *pPrior; unsigned char *pPayload; Btree *pBt = pPage->pBt; Pgno pgnoOvfl = 0; int nHeader; /* Fill in the header. */ |
︙ | ︙ | |||
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 | pPayload = &pCell[nHeader]; pPrior = &pPayload[pBt->maxLocal]; while( nPayload>0 ){ if( spaceLeft==0 ){ rc = allocatePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl); if( rc ){ clearCell(pPage, pCell); return rc; } put4byte(pPrior, pgnoOvfl); pPrior = pOvfl->aData; put4byte(pPrior, 0); pPayload = &pOvfl->aData[4]; spaceLeft = pBt->pageSize - 4; } n = nPayload; if( n>spaceLeft ) n = spaceLeft; if( n>nSrc ) n = nSrc; memcpy(pPayload, pSrc, n); nPayload -= n; pPayload += n; nSrc -= n; spaceLeft -= n; if( nSrc==0 ){ nSrc = nData; pSrc = pData; } | > > > > < < | < > | 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 | pPayload = &pCell[nHeader]; pPrior = &pPayload[pBt->maxLocal]; while( nPayload>0 ){ if( spaceLeft==0 ){ rc = allocatePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl); if( rc ){ releasePage(pToRelease); clearCell(pPage, pCell); return rc; } put4byte(pPrior, pgnoOvfl); releasePage(pToRelease); pToRelease = pOvfl; pPrior = pOvfl->aData; put4byte(pPrior, 0); pPayload = &pOvfl->aData[4]; spaceLeft = pBt->pageSize - 4; } n = nPayload; if( n>spaceLeft ) n = spaceLeft; if( n>nSrc ) n = nSrc; memcpy(pPayload, pSrc, n); nPayload -= n; pPayload += n; pSrc += n; nSrc -= n; spaceLeft -= n; if( nSrc==0 ){ nSrc = nData; pSrc = pData; } } releasePage(pToRelease); return SQLITE_OK; } /* ** 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. |
︙ | ︙ |
Changes to src/test3.c.
︙ | ︙ | |||
9 10 11 12 13 14 15 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** 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. ** | | | 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** 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.29 2004/05/08 02:03:23 drh Exp $ */ #include "sqliteInt.h" #include "pager.h" #include "btree.h" #include "tcl.h" #include <stdlib.h> #include <string.h> |
︙ | ︙ | |||
1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 | 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){ static struct { char *zName; | > > > > > > > > > > > > > > > > > > > | 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 | 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; } /* ** The command is provided for the purpose of setting breakpoints. ** in regression test scripts. ** ** By setting a GDB breakpoint on this procedure and executing the ** btree_breakpoint command in a test script, we can stop GDB at ** the point in the script where the btree_breakpoint command is ** inserted. This is useful for debugging. */ static int btree_breakpoint( void *NotUsed, Tcl_Interp *interp, /* The TCL interpreter that invoked this command */ int argc, /* Number of arguments */ const char **argv /* Text of each argument */ ){ return TCL_OK; } /* ** Register commands with the TCL interpreter. */ int Sqlitetest3_Init(Tcl_Interp *interp){ static struct { char *zName; |
︙ | ︙ | |||
1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 | { "btree_key", (Tcl_CmdProc*)btree_key }, { "btree_data", (Tcl_CmdProc*)btree_data }, { "btree_payload_size", (Tcl_CmdProc*)btree_payload_size }, { "btree_first", (Tcl_CmdProc*)btree_first }, { "btree_last", (Tcl_CmdProc*)btree_last }, { "btree_cursor_dump", (Tcl_CmdProc*)btree_cursor_dump }, { "btree_integrity_check", (Tcl_CmdProc*)btree_integrity_check }, }; int i; for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){ Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0); } Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable, TCL_LINK_INT); return TCL_OK; } | > | 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 | { "btree_key", (Tcl_CmdProc*)btree_key }, { "btree_data", (Tcl_CmdProc*)btree_data }, { "btree_payload_size", (Tcl_CmdProc*)btree_payload_size }, { "btree_first", (Tcl_CmdProc*)btree_first }, { "btree_last", (Tcl_CmdProc*)btree_last }, { "btree_cursor_dump", (Tcl_CmdProc*)btree_cursor_dump }, { "btree_integrity_check", (Tcl_CmdProc*)btree_integrity_check }, { "btree_breakpoint", (Tcl_CmdProc*)btree_breakpoint }, }; int i; for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){ Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0); } Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable, TCL_LINK_INT); return TCL_OK; } |
Changes to test/btree.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 script is btree database backend # | | | 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 script is btree database backend # # $Id: btree.test,v 1.18 2004/05/08 02:03:23 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Basic functionality. Open and close a database. # |
︙ | ︙ | |||
637 638 639 640 641 642 643 | 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 { | | > | | 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 | 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} append data END set ::data $data btree_insert $::c1 2030 $data } {} do_test btree-8.6 { btree_move_to $::c1 2030 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 |
︙ | ︙ | |||
667 668 669 670 671 672 673 | } $::data do_test btree-8.10 { btree_begin_transaction $::b1 btree_delete $::c1 } {} do_test btree-8.11 { lindex [btree_get_meta $::b1] 0 | | | > > | 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 | } $::data do_test btree-8.10 { btree_begin_transaction $::b1 btree_delete $::c1 } {} do_test btree-8.11 { lindex [btree_get_meta $::b1] 0 } {4} # Now check out keys on overflow pages. # do_test btree-8.12 { set ::keyprefix "This is a long prefix to a key " while {[string length $::keyprefix]<256} {append ::keyprefix $::keyprefix} btree_close_cursor $::c1 btree_clear_table $::b1 2 lindex [btree_get_meta $::b1] 0 } {4} do_test btree-8.12.1 { set ::c1 [btree_cursor $::b1 2 1] btree_insert $::c1 ${::keyprefix}1 1 btree_first $::c1 btree_data $::c1 } {1} do_test btree-8.13 { btree_key $::c1 } ${keyprefix}1 do_test btree-8.14 { btree_insert $::c1 ${::keyprefix}2 2 btree_insert $::c1 ${::keyprefix}3 3 btree_last $::c1 btree_key $::c1 } ${keyprefix}3 do_test btree-8.15 { btree_move_to $::c1 ${::keyprefix}2 btree_data $::c1 } {2} do_test btree-8.16 { |
︙ | ︙ | |||
728 729 730 731 732 733 734 | lindex [btree_pager_stats $::b1] 1 } {2} do_test btree-8.23 { btree_close_cursor $::c1 btree_drop_table $::b1 2 set ::c1 [btree_cursor $::b1 2 1] lindex [btree_get_meta $::b1] 0 | | | 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 | lindex [btree_pager_stats $::b1] 1 } {2} do_test btree-8.23 { btree_close_cursor $::c1 btree_drop_table $::b1 2 set ::c1 [btree_cursor $::b1 2 1] lindex [btree_get_meta $::b1] 0 } {5} do_test btree-8.24 { lindex [btree_pager_stats $::b1] 1 } {2} #btree_pager_ref_dump $::b1 # Check page splitting logic # |
︙ | ︙ | |||
774 775 776 777 778 779 780 | do_test btree-9.3.$i.2 [subst { btree_move_to $::c1 [format %03d $i] string range \[btree_data $::c1\] 0 10 }] "*** [format %03d $i] ***" } do_test btree-9.4.1 { lindex [btree_pager_stats $::b1] 1 | | | 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 | do_test btree-9.3.$i.2 [subst { btree_move_to $::c1 [format %03d $i] string range \[btree_data $::c1\] 0 10 }] "*** [format %03d $i] ***" } do_test btree-9.4.1 { lindex [btree_pager_stats $::b1] 1 } {2} # Check the page joining logic. # #btree_page_dump $::b1 2 #btree_pager_ref_dump $::b1 do_test btree-9.4.2 { btree_move_to $::c1 005 |
︙ | ︙ | |||
812 813 814 815 816 817 818 | # Create a tree of depth two. That is, there is a single divider entry # on the root pages and two leaf pages. Then delete the divider entry # see what happens. # do_test btree-10.1 { btree_begin_transaction $::b1 | | | 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 | # Create a tree of depth two. That is, there is a single divider entry # on the root pages and two leaf pages. Then delete the divider entry # see what happens. # do_test btree-10.1 { btree_begin_transaction $::b1 btree_clear_table $::b1 2 lindex [btree_pager_stats $::b1] 1 } {1} do_test btree-10.2 { set ::c1 [btree_cursor $::b1 2 1] lindex [btree_pager_stats $::b1] 1 } {2} do_test btree-10.3 { |
︙ | ︙ |