/ Check-in [2d64cba3]
Login

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

Overview
Comment:More bug fixes in btree.c. (CVS 1323)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 2d64cba38c0f5fffa18cb30c4c448278837de49d
User & Date: drh 2004-05-08 02:03:23
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: 8af6474c user: danielk1977 tags: trunk
02:03
More bug fixes in btree.c. (CVS 1323) check-in: 2d64cba3 user: drh tags: trunk
2004-05-07
23:50
More bug fixes in btree.c. (CVS 1322) check-in: a80939ef user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
....
2063
2064
2065
2066
2067
2068
2069

2070


2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
....
2191
2192
2193
2194
2195
2196
2197

2198
2199
2200
2201
2202
2203
2204
....
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
** 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.112 2004/05/07 23:50:57 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.
................................................................................
    }
    nextPage = get4byte(aPayload);
    if( offset<ovflSize ){
      int a = amt;
      if( a + offset > ovflSize ){
        a = ovflSize - offset;
      }
      memcpy(pBuf, &aPayload[offset], a);
      offset = 0;
      amt -= a;
      pBuf += a;
    }else{
      offset -= ovflSize;
    }
    sqlite3pager_unref(aPayload);
................................................................................
          if( d2<dist ) closest = i;
        }
      }else{
        closest = 0;
      }
      put4byte(&aData[4], n-1);
      *pPgno = get4byte(&aData[8+closest*4]);

      memcpy(&aData[8+closest*4], &aData[4+closest*n], 4);


      rc = getPage(pBt, *pPgno, ppPage);
      releasePage(pTrunk);
      if( rc==SQLITE_OK ){
        sqlite3pager_dont_rollback(*ppPage);
        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;
................................................................................
  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. */
................................................................................
  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;
    }
    if( pOvfl && (spaceLeft==0 || nPayload==0) ){
      releasePage(pOvfl);
    }
  }

  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.







|







 







|







 







>
|
>
>



|







 







>







 







>




>
>











>






<
<
|
<
>







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
....
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
....
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
....
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
** 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.
................................................................................
    }
    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);
................................................................................
          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;
................................................................................
  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. */
................................................................................
  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
16
17
18
19
20
21
22
23
....
1014
1015
1016
1017
1018
1019
1020



















1021
1022
1023
1024
1025
1026
1027
....
1053
1054
1055
1056
1057
1058
1059

1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
**    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.28 2004/05/07 23:50:57 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  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;
................................................................................
     { "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;
}







|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







>










9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
....
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
....
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
**    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>
................................................................................
  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;
................................................................................
     { "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.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
637
638
639
640
641
642
643
644
645

646
647
648
649
650
651
652
653
654
655
656
657
...
667
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
...
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
...
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
...
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
#    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.17 2004/05/07 23:50:58 drh Exp $


set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Basic functionality.  Open and close a database.
#
................................................................................
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 2030 $data
} {}
do_test btree-8.6 {
  btree_move_to 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
................................................................................
} $::data
do_test btree-8.10 {
  btree_begin_transaction $::b1
  btree_delete $::c1
} {}
do_test btree-8.11 {
  lindex [btree_get_meta $::b1] 0
} {}

# 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_drop_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_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_key $::c1
} ${keyprefix}3
do_test btree-8.15 {
  btree_move_to $::c1 ${::keyprefix}2
  btree_data $::c1
} {2}
do_test btree-8.16 {
................................................................................
  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
} {4}
do_test btree-8.24 {
  lindex [btree_pager_stats $::b1] 1
} {2}
#btree_pager_ref_dump $::b1

# Check page splitting logic
#
................................................................................
  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
} {3}

# 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
................................................................................

# 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_drop_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 {







|







 







|

>




|







 







|







|





>








>







 







|







 







|







 







|







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
...
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
...
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
...
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
...
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
#    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.
#
................................................................................
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
................................................................................
} $::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 {
................................................................................
  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
#
................................................................................
  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
................................................................................

# 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 {