/ Check-in [cb1ffabf]
Login

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

Overview
Comment:Critical bugs fixed in btree.c. Incompatible file format change. Unrelated comment fix in select.c (CVS 1530)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: cb1ffabf86996ab20dfffcb5f133fa9a9b56bbe2
User & Date: drh 2004-06-05 00:01:45
Context
2004-06-05
08:04
Ensure blob values survive the ".dump" command of the shell. (CVS 1531) check-in: e82eb722 user: danielk1977 tags: trunk
00:01
Critical bugs fixed in btree.c. Incompatible file format change. Unrelated comment fix in select.c (CVS 1530) check-in: cb1ffabf user: drh tags: trunk
2004-06-04
10:38
Defer the exclusive db lock until the pager cache is flushed to disk. 41 tests now fail. (CVS 1528) check-in: d2f69e5e user: danielk1977 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
...
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
...
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
....
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
....
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100

3101
3102
3103
3104
3105
3106
3107
....
3719
3720
3721
3722
3723
3724
3725

3726
3727
3728
3729
3730




3731
3732
3733
3734
3735
3736
3737
....
3797
3798
3799
3800
3801
3802
3803

3804
3805
3806
3807
3808
3809
3810
....
4243
4244
4245
4246
4247
4248
4249
4250
4251
** 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.157 2004/06/04 06:22:01 danielk1977 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.
................................................................................
  u8 intKey;           /* True if intkey flag is set */
  u8 leaf;             /* True if leaf flag is set */
  u8 zeroData;         /* True if table stores keys only */
  u8 leafData;         /* True if tables stores data on leaves only */
  u8 hasData;          /* True if this page stores data */
  u8 hdrOffset;        /* 100 for page 1.  0 otherwise */
  u8 childPtrSize;     /* 0 if leaf==1.  4 if leaf==0 */
  u8 maxLocal;         /* Copy of Btree.maxLocal or Btree.maxLeaf */
  u8 minLocal;         /* Copy of Btree.minLocal or Btree.minLeaf */
  u16 cellOffset;      /* Index in aData of first cell pointer */
  u16 idxParent;       /* Index in parent of this node */
  u16 nFree;           /* Number of free bytes on the page */
  u16 nCell;           /* Number of cells on this page, local and ovfl */
  struct _OvflCell {   /* Cells that will not fit on aData[] */
    u8 *pCell;           /* Pointers to the body of the overflow cell */
    u16 idx;             /* Insert this cell before idx-th non-overflow cell */
  } aOvfl[3];
  struct Btree *pBt;   /* Pointer back to BTree structure */
  u8 *aData;           /* Pointer back to the start of the page */
  Pgno pgno;           /* Page number for this page */
  MemPage *pParent;    /* The parent of this page.  NULL for root */
};

/*
................................................................................
  MemPage *pPage1;      /* First page of the database */
  u8 inTrans;           /* True if a transaction is in progress */
  u8 inStmt;            /* True if we are in a statement subtransaction */
  u8 readOnly;          /* True if the underlying file is readonly */
  u8 maxEmbedFrac;      /* Maximum payload as % of total page size */
  u8 minEmbedFrac;      /* Minimum payload as % of total page size */
  u8 minLeafFrac;       /* Minimum leaf payload as % of total page size */
  int pageSize;         /* Total number of bytes on a page */
  int usableSize;       /* Number of usable bytes on each page */
  int maxLocal;         /* Maximum local payload in non-LEAFDATA tables */
  int minLocal;         /* Minimum local payload in non-LEAFDATA tables */
  int maxLeaf;          /* Maximum local payload in a LEAFDATA table */
  int minLeaf;          /* Minimum local payload in a LEAFDATA table */
};
typedef Btree Bt;

................................................................................
  int usableSpace;             /* Bytes in pPage beyond the header */
  int pageFlags;               /* Value of pPage->aData[0] */
  int subtotal;                /* Subtotal of bytes in cells on one page */
  int iSpace = 0;              /* First unused byte of aSpace[] */
  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 */
  int cntNew[NB+1];            /* Index in aCell[] 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[] */
  u8 aSpace[MX_PAGE_SIZE*4];   /* Space to copies of divider cells */

  /* 
  ** Find the parent page.
  */
  assert( pPage->isInit );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
................................................................................
      pT = apNew[i];
      pgnoNew[i] = pgnoNew[minI];
      apNew[i] = apNew[minI];
      pgnoNew[minI] = t;
      apNew[minI] = pT;
    }
  }
  TRACE(("BALANCE: old: %d %d %d  new: %d(%d) %d(%d) %d(%d) %d(%d)\n",
    pgnoOld[0], 
    nOld>=2 ? pgnoOld[1] : 0,
    nOld>=3 ? pgnoOld[2] : 0,
    pgnoNew[0], szNew[0],
    nNew>=2 ? pgnoNew[1] : 0, nNew>=2 ? szNew[1] : 0,
    nNew>=3 ? pgnoNew[2] : 0, nNew>=3 ? szNew[2] : 0,
    nNew>=4 ? pgnoNew[3] : 0, nNew>=4 ? szNew[3] : 0));



  /*
  ** Evenly distribute the data in apCell[] across the new pages.
  ** Insert divider cells into pParent as necessary.
  */
  j = 0;
................................................................................
  int rc;
  MemPage *pPage;
  int i, j, c;
  int nFree;
  u16 idx;
  int hdr;
  int nCell;

  unsigned char *data;
  char range[20];
  unsigned char payload[20];

  rc = getPage(pBt, (Pgno)pgno, &pPage);




  if( rc ){
    return rc;
  }
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  c = data[hdr];
  pPage->intKey = (c & (PTF_INTKEY|PTF_LEAFDATA))!=0;
................................................................................
    for(i=0; i<nCell; i++){
      unsigned char *pCell = findCell(pPage, i);
      sqlite3BtreePageDump(pBt, get4byte(pCell), 1);
      idx = get2byte(pCell);
    }
    sqlite3BtreePageDump(pBt, get4byte(&data[hdr+8]), 1);
  }

  sqlite3pager_unref(data);
  fflush(stdout);
  return SQLITE_OK;
}
#endif

#ifdef SQLITE_TEST
................................................................................
*/
int sqlite3BtreeSync(Btree *pBt, const char *zMaster){
  if( pBt->inTrans==TRANS_WRITE ){
    return sqlite3pager_sync(pBt->pPager, zMaster);
  }
  return SQLITE_OK;
}









|







 







|
|







|







 







|
|







 







|
|


|
|



|







 







|






|
>







 







>





>
>
>
>







 







>







 







<
<
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
...
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
....
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
....
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
....
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
3736
3737
3738
3739
3740
3741
3742
3743
....
3803
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817
....
4250
4251
4252
4253
4254
4255
4256


** 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.158 2004/06/05 00:01:45 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.
................................................................................
  u8 intKey;           /* True if intkey flag is set */
  u8 leaf;             /* True if leaf flag is set */
  u8 zeroData;         /* True if table stores keys only */
  u8 leafData;         /* True if tables stores data on leaves only */
  u8 hasData;          /* True if this page stores data */
  u8 hdrOffset;        /* 100 for page 1.  0 otherwise */
  u8 childPtrSize;     /* 0 if leaf==1.  4 if leaf==0 */
  u16 maxLocal;        /* Copy of Btree.maxLocal or Btree.maxLeaf */
  u16 minLocal;        /* Copy of Btree.minLocal or Btree.minLeaf */
  u16 cellOffset;      /* Index in aData of first cell pointer */
  u16 idxParent;       /* Index in parent of this node */
  u16 nFree;           /* Number of free bytes on the page */
  u16 nCell;           /* Number of cells on this page, local and ovfl */
  struct _OvflCell {   /* Cells that will not fit on aData[] */
    u8 *pCell;           /* Pointers to the body of the overflow cell */
    u16 idx;             /* Insert this cell before idx-th non-overflow cell */
  } aOvfl[5];
  struct Btree *pBt;   /* Pointer back to BTree structure */
  u8 *aData;           /* Pointer back to the start of the page */
  Pgno pgno;           /* Page number for this page */
  MemPage *pParent;    /* The parent of this page.  NULL for root */
};

/*
................................................................................
  MemPage *pPage1;      /* First page of the database */
  u8 inTrans;           /* True if a transaction is in progress */
  u8 inStmt;            /* True if we are in a statement subtransaction */
  u8 readOnly;          /* True if the underlying file is readonly */
  u8 maxEmbedFrac;      /* Maximum payload as % of total page size */
  u8 minEmbedFrac;      /* Minimum payload as % of total page size */
  u8 minLeafFrac;       /* Minimum leaf payload as % of total page size */
  u16 pageSize;         /* Total number of bytes on a page */
  u16 usableSize;       /* Number of usable bytes on each page */
  int maxLocal;         /* Maximum local payload in non-LEAFDATA tables */
  int minLocal;         /* Minimum local payload in non-LEAFDATA tables */
  int maxLeaf;          /* Maximum local payload in a LEAFDATA table */
  int minLeaf;          /* Minimum local payload in a LEAFDATA table */
};
typedef Btree Bt;

................................................................................
  int usableSpace;             /* Bytes in pPage beyond the header */
  int pageFlags;               /* Value of pPage->aData[0] */
  int subtotal;                /* Subtotal of bytes in cells on one page */
  int iSpace = 0;              /* First unused byte of aSpace[] */
  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+2];        /* pPage and up to NB siblings after balancing */
  Pgno pgnoNew[NB+2];          /* Page numbers for each page in apNew[] */
  int idxDiv[NB];              /* Indices of divider cells in pParent */
  u8 *apDiv[NB];               /* Divider cells in pParent */
  int cntNew[NB+2];            /* Index in aCell[] of cell after i-th page */
  int szNew[NB+2];             /* 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[] */
  u8 aSpace[MX_PAGE_SIZE*5];   /* Space to copies of divider cells */

  /* 
  ** Find the parent page.
  */
  assert( pPage->isInit );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
................................................................................
      pT = apNew[i];
      pgnoNew[i] = pgnoNew[minI];
      apNew[i] = apNew[minI];
      pgnoNew[minI] = t;
      apNew[minI] = pT;
    }
  }
  TRACE(("BALANCE: old: %d %d %d  new: %d(%d) %d(%d) %d(%d) %d(%d) %d(%d)\n",
    pgnoOld[0], 
    nOld>=2 ? pgnoOld[1] : 0,
    nOld>=3 ? pgnoOld[2] : 0,
    pgnoNew[0], szNew[0],
    nNew>=2 ? pgnoNew[1] : 0, nNew>=2 ? szNew[1] : 0,
    nNew>=3 ? pgnoNew[2] : 0, nNew>=3 ? szNew[2] : 0,
    nNew>=4 ? pgnoNew[3] : 0, nNew>=4 ? szNew[3] : 0,
    nNew>=5 ? pgnoNew[4] : 0, nNew>=5 ? szNew[4] : 0));


  /*
  ** Evenly distribute the data in apCell[] across the new pages.
  ** Insert divider cells into pParent as necessary.
  */
  j = 0;
................................................................................
  int rc;
  MemPage *pPage;
  int i, j, c;
  int nFree;
  u16 idx;
  int hdr;
  int nCell;
  int isInit;
  unsigned char *data;
  char range[20];
  unsigned char payload[20];

  rc = getPage(pBt, (Pgno)pgno, &pPage);
  isInit = pPage->isInit;
  if( pPage->isInit==0 ){
    initPage(pPage, 0);
  }
  if( rc ){
    return rc;
  }
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  c = data[hdr];
  pPage->intKey = (c & (PTF_INTKEY|PTF_LEAFDATA))!=0;
................................................................................
    for(i=0; i<nCell; i++){
      unsigned char *pCell = findCell(pPage, i);
      sqlite3BtreePageDump(pBt, get4byte(pCell), 1);
      idx = get2byte(pCell);
    }
    sqlite3BtreePageDump(pBt, get4byte(&data[hdr+8]), 1);
  }
  pPage->isInit = isInit;
  sqlite3pager_unref(data);
  fflush(stdout);
  return SQLITE_OK;
}
#endif

#ifdef SQLITE_TEST
................................................................................
*/
int sqlite3BtreeSync(Btree *pBt, const char *zMaster){
  if( pBt->inTrans==TRANS_WRITE ){
    return sqlite3pager_sync(pBt->pPager, zMaster);
  }
  return SQLITE_OK;
}


Changes to src/select.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.182 2004/05/29 11:24:50 danielk1977 Exp $
*/
#include "sqliteInt.h"


/*
** Allocate a new Select structure and return a pointer to that
** structure.
................................................................................
  pParse->nAgg = 0;
  pParse->useAgg = 0;
}

/*
** Insert code into "v" that will push the record on the top of the
** stack into the sorter.
**
** FIX ME:  Change this so that it uses the OP_MakeKey opcode
** instead of OP_SortMakeKey.  Delete the OP_SortMakeKey opcode.
** All columns should have affinity NONE.  Handle ASC versus
** DESC sort order by defining a list of comparison functions to
** be used by the OP_Sort opcode.
*/
static void pushOntoSorter(Parse *pParse, Vdbe *v, ExprList *pOrderBy){
  int i;
  for(i=0; i<pOrderBy->nExpr; i++){
    sqlite3ExprCode(pParse, pOrderBy->a[i].pExpr);
  }
  sqlite3VdbeAddOp(v, OP_MakeKey, pOrderBy->nExpr, 0);







|







 







<
<
<
<
<
<







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
306
307
308
309
310
311
312






313
314
315
316
317
318
319
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.183 2004/06/05 00:01:46 drh Exp $
*/
#include "sqliteInt.h"


/*
** Allocate a new Select structure and return a pointer to that
** structure.
................................................................................
  pParse->nAgg = 0;
  pParse->useAgg = 0;
}

/*
** Insert code into "v" that will push the record on the top of the
** stack into the sorter.






*/
static void pushOntoSorter(Parse *pParse, Vdbe *v, ExprList *pOrderBy){
  int i;
  for(i=0; i<pOrderBy->nExpr; i++){
    sqlite3ExprCode(pParse, pOrderBy->a[i].pExpr);
  }
  sqlite3VdbeAddOp(v, OP_MakeKey, pOrderBy->nExpr, 0);

Added test/btree7.test.





















































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# 2004 Jun 4	
#
# 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: btree7.test,v 1.1 2004/06/05 00:01:46 drh Exp $


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

# Stress the balance routine by trying to create situations where
# 3 neighboring nodes split into 5.
#
set bigdata _123456789    ;#  10
append bigdata $bigdata   ;#  20
append bigdata $bigdata   ;#  40
append bigdata $bigdata   ;#  80
append bigdata $bigdata   ;# 160
append bigdata $bigdata   ;# 320
append bigdata $bigdata   ;# 640
set data450 [string range $bigdata 0 449]
do_test btree7-1.1 {
  execsql "
    CREATE TABLE t1(x INTEGER PRIMARY KEY, y TEXT);
    INSERT INTO t1 VALUES(1, '$bigdata');
    INSERT INTO t1 VALUES(2, '$bigdata');
    INSERT INTO t1 VALUES(3, '$data450');
    INSERT INTO t1 VALUES(5, '$data450');
    INSERT INTO t1 VALUES(8, '$bigdata');
    INSERT INTO t1 VALUES(9, '$bigdata');
  "
} {}
#puts [execsql {select * from sqlite_master}]
#set bt [btree_open test.db 2000 0]
#btree_tree_dump $bt 2
do_test btree7-1.2 {
  execsql {PRAGMA integrity_check}
} {ok}
do_test btree7-1.3 {
  execsql "
    INSERT INTO t1 VALUES(4, '$bigdata');
  "
} {}
#btree_tree_dump $bt 2
do_test btree7-1.4 {
  execsql {PRAGMA integrity_check}
} {ok}

finish_test