/ Check-in [6b9b298b]
Login
Overview
Comment:More tests and bug fixes in btree.c (CVS 229)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:6b9b298b2846146b95d7df7f423867976bafa390
User & Date: drh 2001-06-25 02:11:07
Context
2001-06-28
01:54
Got a lot of BTree tests working. Still lots more needed. (CVS 230) check-in: 9cfeeb58 user: drh tags: trunk
2001-06-25
02:11
More tests and bug fixes in btree.c (CVS 229) check-in: 6b9b298b user: drh tags: trunk
2001-06-24
20:39
The first test file for BTree added. Simple insert and delete tests pass. There is still a lot of work to be done, though. (CVS 228) check-in: 85f015c9 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
...
137
138
139
140
141
142
143

144
145
146
147
148
149
150
151
...
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
...
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381



382
383
384
385
386
387
388
...
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
...
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
...
906
907
908
909
910
911
912

913
914
915

916

917
918
919
920
921
922
923
....
1263
1264
1265
1266
1267
1268
1269

1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
....
1290
1291
1292
1293
1294
1295
1296

1297
1298
1299
1300
1301
1302
1303
....
1307
1308
1309
1310
1311
1312
1313

1314
1315
1316
1317
1318
1319
1320
....
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
....
1473
1474
1475
1476
1477
1478
1479

1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
....
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023

2024
2025


2026




2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
....
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058

2059
2060
2061

2062

2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074

2075
2076
2077
2078
2079
2080
2081
2082
....
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
....
2112
2113
2114
2115
2116
2117
2118

2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129



2130
2131
2132
2133
2134
2135
2136
....
2140
2141
2142
2143
2144
2145
2146

2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159









2160
2161


2162
2163

















2164
2165
2166
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.14 2001/06/24 20:39:41 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.
................................................................................
** for additional information.)  Page 0 does not exist and a page
** number of 0 is used to mean "no such page".
*/
struct PageOne {
  char zMagic[MAGIC_SIZE]; /* String that identifies the file as a database */
  int iMagic;              /* Integer to verify correct byte order */
  Pgno freeList;           /* First free page in a list of all free pages */

  int aMeta[SQLITE_N_BTREE_META];  /* User defined integers */
};

/*
** Each database page has a header that is an instance of this
** structure.
**
** PageHdr.firstFree is 0 if there is no free space on this page.
................................................................................
** The maximum amount of payload (in bytes) that can be stored locally for
** a database entry.  If the entry contains more data than this, the
** extra goes onto overflow pages.
**
** This number is chosen so that at least 4 cells will fit on every page.
*/
#define MX_LOCAL_PAYLOAD \
  ((SQLITE_PAGE_SIZE-sizeof(PageHdr))/4-(sizeof(CellHdr)+sizeof(Pgno)))

/*
** Data on a database page is stored as a linked list of Cell structures.
** Both the key and the data are stored in aPayload[].  The key always comes
** first.  The aPayload[] field grows as necessary to hold the key and data,
** up to a maximum of MX_LOCAL_PAYLOAD bytes.  If the size of the key and
** data combined exceeds MX_LOCAL_PAYLOAD bytes, then Cell.ovfl is the
................................................................................
  FreeBlk *pFBlk;
  char newPage[SQLITE_PAGE_SIZE];

  pc = sizeof(PageHdr);
  pPage->u.hdr.firstCell = pc;
  memcpy(newPage, pPage->u.aDisk, pc);
  for(i=0; i<pPage->nCell; i++){
    Cell *pCell = (Cell*)&pPage->apCell[i];

    /* This routine should never be called on an overfull page.  The
    ** following asserts verify that constraint. */
    assert( Addr(pCell) > Addr(pPage) );
    assert( Addr(pCell) < Addr(pPage) + SQLITE_PAGE_SIZE );

    n = cellSize(pCell);
    pCell->h.iNext = i<pPage->nCell-1 ? pc + n : 0;
    memcpy(&newPage[pc], pCell, n);
    pPage->apCell[i] = (Cell*)&pPage->u.aDisk[pc];
    pc += n;
  }
  assert( pPage->nFree==SQLITE_PAGE_SIZE-pc );
  memcpy(pPage->u.aDisk, newPage, pc);



  pFBlk = (FreeBlk*)&pPage->u.aDisk[pc];
  pFBlk->iSize = SQLITE_PAGE_SIZE - pc;
  pFBlk->iNext = 0;
  pPage->u.hdr.firstFree = pc;
  memset(&pFBlk[1], 0, SQLITE_PAGE_SIZE - pc - sizeof(FreeBlk));
}

................................................................................
    sqlitepager_unref(pBt->page1);
    pBt->page1 = 0;
    pBt->inTrans = 0;
  }
}

/*
** Commit the transaction currently in progress.  All cursors
** must be closed before this routine is called.
*/
int sqliteBtreeCommit(Btree *pBt){
  int rc;
  if( pBt->pCursor!=0 || pBt->inTrans==0 ) return SQLITE_ERROR;
  rc = sqlitepager_commit(pBt->pPager);
  pBt->inTrans = 0;
  unlockBtree(pBt);
  return rc;
}

/*
................................................................................
    if( a+offset>MX_LOCAL_PAYLOAD ){
      a = MX_LOCAL_PAYLOAD - offset;
    }
    memcpy(zBuf, &aPayload[offset], a);
    if( a==amt ){
      return SQLITE_OK;
    }
    offset += a;
    zBuf += a;
    amt -= a;
  }
  if( amt>0 ){
    nextPage = pCur->pPage->apCell[pCur->idx]->ovfl;
  }
  while( amt>0 && nextPage ){
................................................................................
    nextPage = pOvfl->iNext;
    if( offset<OVERFLOW_SIZE ){
      int a = amt;
      if( a + offset > OVERFLOW_SIZE ){
        a = OVERFLOW_SIZE - offset;
      }
      memcpy(zBuf, &pOvfl->aPayload[offset], a);

      amt -= a;
      zBuf += a;
    }

    offset -= OVERFLOW_SIZE;

    sqlitepager_unref(pOvfl);
  }
  return amt==0 ? SQLITE_OK : SQLITE_CORRUPT;
}

/*
** Read part of the key associated with cursor pCur.  A total
................................................................................
    if( rc ) return rc;
    rc = sqlitepager_write(pOvfl);
    if( rc ){
      sqlitepager_unref(pOvfl);
      return rc;
    }
    pPage1->freeList = pOvfl->iNext;

    *ppPage = (MemPage*)pOvfl;
  }else{
    *pPgno = sqlitepager_pagecount(pBt->pPager);
    rc = sqlitepager_get(pBt->pPager, *pPgno, (void**)ppPage);
    if( rc ) return rc;
    rc = sqlitepager_write(*ppPage);
  }
  return rc;
}

................................................................................
  int rc;
  int needOvflUnref = 0;

  if( pgno==0 ){
    assert( pOvfl!=0 );
    pgno = sqlitepager_pagenumber(pOvfl);
  }

  rc = sqlitepager_write(pPage1);
  if( rc ){
    return rc;
  }
  if( pOvfl==0 ){
    assert( pgno>0 );
    rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pOvfl);
................................................................................
  rc = sqlitepager_write(pOvfl);
  if( rc ){
    if( needOvflUnref ) sqlitepager_unref(pOvfl);
    return rc;
  }
  pOvfl->iNext = pPage1->freeList;
  pPage1->freeList = pgno;

  memset(pOvfl->aPayload, 0, OVERFLOW_SIZE);
  ((MemPage*)pPage)->isInit = 0;
  assert( ((MemPage*)pPage)->pParent==0 );
  rc = sqlitepager_unref(pOvfl);
  return rc;
}

................................................................................
  while( ovfl ){
    rc = sqlitepager_get(pPager, ovfl, (void**)&pOvfl);
    if( rc ) return rc;
    nextOvfl = pOvfl->iNext;
    rc = freePage(pBt, pOvfl, ovfl);
    if( rc ) return rc;
    ovfl = nextOvfl;
    sqlitepager_unref(pOvfl);
  }
  return SQLITE_OK;
}

/*
** Create a new cell from key and data.  Overflow pages are allocated as
** necessary and linked to this cell.  
................................................................................
** routine will be called soon after this routine in order to rebuild 
** the linked list.
*/
static void insertCell(MemPage *pPage, int i, Cell *pCell, int sz){
  int idx, j;
  assert( i>=0 && i<=pPage->nCell );
  assert( sz==cellSize(pCell) );

  for(j=pPage->nCell; j>i; j--){
    pPage->apCell[j] = pPage->apCell[j-1];
  }
  pPage->nCell++;
  idx = allocateSpace(pPage, sz);
  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];
  }
................................................................................
  return SQLITE_OK;
}

/*
** Erase the given database page and all its children.  Return
** the page to the freelist.
*/
static int clearDatabasePage(Btree *pBt, Pgno pgno){
  MemPage *pPage;
  int rc;
  Cell *pCell;
  int idx;

  rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pPage);
  if( rc ) return rc;
  idx = pPage->u.hdr.firstCell;
  while( idx>0 ){
    pCell = (Cell*)&pPage->u.aDisk[idx];
    idx = pCell->h.iNext;
    if( pCell->h.leftChild ){
      rc = clearDatabasePage(pBt, pCell->h.leftChild);
      if( rc ) return rc;
    }
    rc = clearCell(pBt, pCell);
    if( rc ) return rc;
  }

  rc = clearDatabasePage(pBt, pPage->u.hdr.rightChild);
  if( rc ) return rc;


  return freePage(pBt, pPage, pgno);




}

/*
** Delete all information from a single table in the database.
*/
int sqliteBtreeClearTable(Btree *pBt, int iTable){
  int rc;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  rc = clearDatabasePage(pBt, (Pgno)iTable);
  if( rc ){
    sqliteBtreeRollback(pBt);
  }
  return rc;
}

/*
................................................................................
int sqliteBtreeDropTable(Btree *pBt, int iTable){
  int rc;
  MemPage *pPage;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  rc = sqlitepager_get(pBt->pPager, (Pgno)iTable, (void**)&pPage);
  if( rc==SQLITE_OK ){
    rc = sqliteBtreeClearTable(pBt, iTable);
  }

  if( rc==SQLITE_OK && iTable!=2 ){
    rc = freePage(pBt, pPage, (Pgno)iTable);
  }

  sqlitepager_unref(pPage);

  return rc;  
}

/*
** Read the meta-information out of a database file.
*/
int sqliteBtreeGetMeta(Btree *pBt, int *aMeta){
  PageOne *pP1;
  int rc;

  rc = sqlitepager_get(pBt->pPager, 1, (void**)&pP1);
  if( rc ) return rc;

  memcpy(aMeta, pP1->aMeta, sizeof(pP1->aMeta));
  sqlitepager_unref(pP1);
  return SQLITE_OK;
}

/*
** Write meta-information back into the database.
*/
................................................................................
  PageOne *pP1;
  int rc;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  pP1 = pBt->page1;
  rc = sqlitepager_write(pP1);
  if( rc ) return rc;
  memcpy(pP1->aMeta, aMeta, sizeof(pP1->aMeta));
  return SQLITE_OK;
}

#ifdef SQLITE_TEST
/*
** Print a disassembly of the given page on standard output.  This routine
** is used for debugging and testing only.
................................................................................
  }
  i = 0;
  idx = pPage->u.hdr.firstCell;
  while( idx>0 && idx<=SQLITE_PAGE_SIZE-MIN_CELL_SIZE ){
    Cell *pCell = (Cell*)&pPage->u.aDisk[idx];
    int sz = cellSize(pCell);
    sprintf(range,"%d..%d", idx, idx+sz-1);

    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=%-3d nd=%-3d payload=%s\n",
      i, range, (int)pCell->h.leftChild, pCell->h.nKey, pCell->h.nData,
      pCell->aPayload
    );



    i++;
    idx = pCell->h.iNext;
  }
  if( idx!=0 ){
    printf("ERROR: next cell index out of range: %d\n", idx);
  }
  printf("right_child: %d\n", pPage->u.hdr.rightChild);
................................................................................
  while( idx>0 && idx<SQLITE_PAGE_SIZE ){
    FreeBlk *p = (FreeBlk*)&pPage->u.aDisk[idx];
    sprintf(range,"%d..%d", idx, idx+p->iSize-1);
    nFree += p->iSize;
    printf("freeblock %2d: i=%-10s size=%-4d total=%d\n",
       i, range, p->iSize, nFree);
    idx = p->iNext;

  }
  if( idx!=0 ){
    printf("ERROR: next freeblock index out of range: %d\n", idx);
  }
  sqlitepager_unref(pPage);
  return SQLITE_OK;
}
#endif

#ifdef SQLITE_TEST
/*
** Put the page number and index of a cursor into aResult[0] and aResult[1]
** This routine is used for debugging and testing only.









*/
int sqliteBtreeCursorDump(BtCursor *pCur, int *aResult){


  aResult[0] = sqlitepager_pagenumber(pCur->pPage);
  aResult[1] = pCur->idx;

















  return SQLITE_OK;
}
#endif







|







 







>
|







 







|







 







|







|






>
>
>







 







|
<



|







 







|







 







>


<
>
|
>







 







>


|







 







>







 







>







 







<







 







>




<







 







|












|





>
|
|
>
>
|
>
>
>
>










|







 







|
|
<
>
|
|
|
>
|
>












>
|







 







|
|







 







>









|

>
>
>







 







>











|
|
>
>
>
>
>
>
>
>
>


>
>
|

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



17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
...
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
...
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
...
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
...
729
730
731
732
733
734
735
736

737
738
739
740
741
742
743
744
745
746
747
...
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
...
909
910
911
912
913
914
915
916
917
918

919
920
921
922
923
924
925
926
927
928
....
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
....
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
....
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
....
1344
1345
1346
1347
1348
1349
1350

1351
1352
1353
1354
1355
1356
1357
....
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491

1492
1493
1494
1495
1496
1497
1498
....
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
....
2063
2064
2065
2066
2067
2068
2069
2070
2071

2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
....
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
....
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
....
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
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.15 2001/06/25 02:11:07 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.
................................................................................
** for additional information.)  Page 0 does not exist and a page
** number of 0 is used to mean "no such page".
*/
struct PageOne {
  char zMagic[MAGIC_SIZE]; /* String that identifies the file as a database */
  int iMagic;              /* Integer to verify correct byte order */
  Pgno freeList;           /* First free page in a list of all free pages */
  int nFree;               /* Number of pages on the free list */
  int aMeta[SQLITE_N_BTREE_META-1];  /* User defined integers */
};

/*
** Each database page has a header that is an instance of this
** structure.
**
** PageHdr.firstFree is 0 if there is no free space on this page.
................................................................................
** The maximum amount of payload (in bytes) that can be stored locally for
** a database entry.  If the entry contains more data than this, the
** extra goes onto overflow pages.
**
** This number is chosen so that at least 4 cells will fit on every page.
*/
#define MX_LOCAL_PAYLOAD \
  (((SQLITE_PAGE_SIZE-sizeof(PageHdr))/4-(sizeof(CellHdr)+sizeof(Pgno)))&~3)

/*
** Data on a database page is stored as a linked list of Cell structures.
** Both the key and the data are stored in aPayload[].  The key always comes
** first.  The aPayload[] field grows as necessary to hold the key and data,
** up to a maximum of MX_LOCAL_PAYLOAD bytes.  If the size of the key and
** data combined exceeds MX_LOCAL_PAYLOAD bytes, then Cell.ovfl is the
................................................................................
  FreeBlk *pFBlk;
  char newPage[SQLITE_PAGE_SIZE];

  pc = sizeof(PageHdr);
  pPage->u.hdr.firstCell = pc;
  memcpy(newPage, pPage->u.aDisk, pc);
  for(i=0; i<pPage->nCell; i++){
    Cell *pCell = pPage->apCell[i];

    /* This routine should never be called on an overfull page.  The
    ** following asserts verify that constraint. */
    assert( Addr(pCell) > Addr(pPage) );
    assert( Addr(pCell) < Addr(pPage) + SQLITE_PAGE_SIZE );

    n = cellSize(pCell);
    pCell->h.iNext = pc + n;
    memcpy(&newPage[pc], pCell, n);
    pPage->apCell[i] = (Cell*)&pPage->u.aDisk[pc];
    pc += n;
  }
  assert( pPage->nFree==SQLITE_PAGE_SIZE-pc );
  memcpy(pPage->u.aDisk, newPage, pc);
  if( pPage->nCell>0 ){
    pPage->apCell[pPage->nCell-1]->h.iNext = 0;
  }
  pFBlk = (FreeBlk*)&pPage->u.aDisk[pc];
  pFBlk->iSize = SQLITE_PAGE_SIZE - pc;
  pFBlk->iNext = 0;
  pPage->u.hdr.firstFree = pc;
  memset(&pFBlk[1], 0, SQLITE_PAGE_SIZE - pc - sizeof(FreeBlk));
}

................................................................................
    sqlitepager_unref(pBt->page1);
    pBt->page1 = 0;
    pBt->inTrans = 0;
  }
}

/*
** Commit the transaction currently in progress.

*/
int sqliteBtreeCommit(Btree *pBt){
  int rc;
  if( pBt->inTrans==0 ) return SQLITE_ERROR;
  rc = sqlitepager_commit(pBt->pPager);
  pBt->inTrans = 0;
  unlockBtree(pBt);
  return rc;
}

/*
................................................................................
    if( a+offset>MX_LOCAL_PAYLOAD ){
      a = MX_LOCAL_PAYLOAD - offset;
    }
    memcpy(zBuf, &aPayload[offset], a);
    if( a==amt ){
      return SQLITE_OK;
    }
    offset = 0;
    zBuf += a;
    amt -= a;
  }
  if( amt>0 ){
    nextPage = pCur->pPage->apCell[pCur->idx]->ovfl;
  }
  while( amt>0 && nextPage ){
................................................................................
    nextPage = pOvfl->iNext;
    if( offset<OVERFLOW_SIZE ){
      int a = amt;
      if( a + offset > OVERFLOW_SIZE ){
        a = OVERFLOW_SIZE - offset;
      }
      memcpy(zBuf, &pOvfl->aPayload[offset], a);
      offset = 0;
      amt -= a;
      zBuf += a;

    }else{
      offset -= OVERFLOW_SIZE;
    }
    sqlitepager_unref(pOvfl);
  }
  return amt==0 ? SQLITE_OK : SQLITE_CORRUPT;
}

/*
** Read part of the key associated with cursor pCur.  A total
................................................................................
    if( rc ) return rc;
    rc = sqlitepager_write(pOvfl);
    if( rc ){
      sqlitepager_unref(pOvfl);
      return rc;
    }
    pPage1->freeList = pOvfl->iNext;
    pPage1->nFree--;
    *ppPage = (MemPage*)pOvfl;
  }else{
    *pPgno = sqlitepager_pagecount(pBt->pPager) + 1;
    rc = sqlitepager_get(pBt->pPager, *pPgno, (void**)ppPage);
    if( rc ) return rc;
    rc = sqlitepager_write(*ppPage);
  }
  return rc;
}

................................................................................
  int rc;
  int needOvflUnref = 0;

  if( pgno==0 ){
    assert( pOvfl!=0 );
    pgno = sqlitepager_pagenumber(pOvfl);
  }
  assert( pgno>2 );
  rc = sqlitepager_write(pPage1);
  if( rc ){
    return rc;
  }
  if( pOvfl==0 ){
    assert( pgno>0 );
    rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pOvfl);
................................................................................
  rc = sqlitepager_write(pOvfl);
  if( rc ){
    if( needOvflUnref ) sqlitepager_unref(pOvfl);
    return rc;
  }
  pOvfl->iNext = pPage1->freeList;
  pPage1->freeList = pgno;
  pPage1->nFree++;
  memset(pOvfl->aPayload, 0, OVERFLOW_SIZE);
  ((MemPage*)pPage)->isInit = 0;
  assert( ((MemPage*)pPage)->pParent==0 );
  rc = sqlitepager_unref(pOvfl);
  return rc;
}

................................................................................
  while( ovfl ){
    rc = sqlitepager_get(pPager, ovfl, (void**)&pOvfl);
    if( rc ) return rc;
    nextOvfl = pOvfl->iNext;
    rc = freePage(pBt, pOvfl, ovfl);
    if( rc ) return rc;
    ovfl = nextOvfl;

  }
  return SQLITE_OK;
}

/*
** Create a new cell from key and data.  Overflow pages are allocated as
** necessary and linked to this cell.  
................................................................................
** routine will be called soon after this routine in order to rebuild 
** the linked list.
*/
static void insertCell(MemPage *pPage, int i, Cell *pCell, int sz){
  int idx, j;
  assert( i>=0 && i<=pPage->nCell );
  assert( sz==cellSize(pCell) );
  idx = allocateSpace(pPage, sz);
  for(j=pPage->nCell; j>i; j--){
    pPage->apCell[j] = pPage->apCell[j-1];
  }
  pPage->nCell++;

  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];
  }
................................................................................
  return SQLITE_OK;
}

/*
** Erase the given database page and all its children.  Return
** the page to the freelist.
*/
static int clearDatabasePage(Btree *pBt, Pgno pgno, int freePageFlag){
  MemPage *pPage;
  int rc;
  Cell *pCell;
  int idx;

  rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pPage);
  if( rc ) return rc;
  idx = pPage->u.hdr.firstCell;
  while( idx>0 ){
    pCell = (Cell*)&pPage->u.aDisk[idx];
    idx = pCell->h.iNext;
    if( pCell->h.leftChild ){
      rc = clearDatabasePage(pBt, pCell->h.leftChild, 1);
      if( rc ) return rc;
    }
    rc = clearCell(pBt, pCell);
    if( rc ) return rc;
  }
  if( pPage->u.hdr.rightChild ){
    rc = clearDatabasePage(pBt, pPage->u.hdr.rightChild, 1);
    if( rc ) return rc;
  }
  if( freePageFlag ){
    rc = freePage(pBt, pPage, pgno);
  }else{
    zeroPage(pPage);
  }
  return rc;
}

/*
** Delete all information from a single table in the database.
*/
int sqliteBtreeClearTable(Btree *pBt, int iTable){
  int rc;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  rc = clearDatabasePage(pBt, (Pgno)iTable, 0);
  if( rc ){
    sqliteBtreeRollback(pBt);
  }
  return rc;
}

/*
................................................................................
int sqliteBtreeDropTable(Btree *pBt, int iTable){
  int rc;
  MemPage *pPage;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  rc = sqlitepager_get(pBt->pPager, (Pgno)iTable, (void**)&pPage);
  if( rc ) return rc;
  rc = sqliteBtreeClearTable(pBt, iTable);

  if( rc ) return rc;
  if( iTable>2 ){
    rc = freePage(pBt, pPage, iTable);
  }else{
    zeroPage(pPage);
    sqlitepager_unref(pPage);
  }
  return rc;  
}

/*
** Read the meta-information out of a database file.
*/
int sqliteBtreeGetMeta(Btree *pBt, int *aMeta){
  PageOne *pP1;
  int rc;

  rc = sqlitepager_get(pBt->pPager, 1, (void**)&pP1);
  if( rc ) return rc;
  aMeta[0] = pP1->nFree;
  memcpy(&aMeta[1], pP1->aMeta, sizeof(pP1->aMeta));
  sqlitepager_unref(pP1);
  return SQLITE_OK;
}

/*
** Write meta-information back into the database.
*/
................................................................................
  PageOne *pP1;
  int rc;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  pP1 = pBt->page1;
  rc = sqlitepager_write(pP1);
  if( rc ) return rc;	
  memcpy(pP1->aMeta, &aMeta[1], sizeof(pP1->aMeta));
  return SQLITE_OK;
}

#ifdef SQLITE_TEST
/*
** Print a disassembly of the given page on standard output.  This routine
** is used for debugging and testing only.
................................................................................
  }
  i = 0;
  idx = pPage->u.hdr.firstCell;
  while( idx>0 && idx<=SQLITE_PAGE_SIZE-MIN_CELL_SIZE ){
    Cell *pCell = (Cell*)&pPage->u.aDisk[idx];
    int sz = cellSize(pCell);
    sprintf(range,"%d..%d", idx, idx+sz-1);
    sz = pCell->h.nKey + pCell->h.nData;
    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=%-3d nd=%-3d payload=%s\n",
      i, range, (int)pCell->h.leftChild, pCell->h.nKey, pCell->h.nData,
      payload
    );
    if( pPage->apCell[i]!=pCell ){
      printf("**** apCell[%d] does not match on prior entry ****\n", i);
    }
    i++;
    idx = pCell->h.iNext;
  }
  if( idx!=0 ){
    printf("ERROR: next cell index out of range: %d\n", idx);
  }
  printf("right_child: %d\n", pPage->u.hdr.rightChild);
................................................................................
  while( idx>0 && idx<SQLITE_PAGE_SIZE ){
    FreeBlk *p = (FreeBlk*)&pPage->u.aDisk[idx];
    sprintf(range,"%d..%d", idx, idx+p->iSize-1);
    nFree += p->iSize;
    printf("freeblock %2d: i=%-10s size=%-4d total=%d\n",
       i, range, p->iSize, nFree);
    idx = p->iNext;
    i++;
  }
  if( idx!=0 ){
    printf("ERROR: next freeblock index out of range: %d\n", idx);
  }
  sqlitepager_unref(pPage);
  return SQLITE_OK;
}
#endif

#ifdef SQLITE_TEST
/*
** Fill aResult[] with information about the entry and page that the
** cursor is pointing to.
** 
**   aResult[0] =  The page number
**   aResult[1] =  The entry number
**   aResult[2] =  Total number of entries on this page
**   aResult[3] =  Size of this entry
**   aResult[4] =  Number of free bytes on this page
**   aResult[5] =  Number of free blocks on the page
**   aResult[6] =  Page number of the left child of this entry
**   aResult[7] =  Page number of the right child for the whole page
*/
int sqliteBtreeCursorDump(BtCursor *pCur, int *aResult){
  int cnt, idx;
  MemPage *pPage = pCur->pPage;
  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->apCell[pCur->idx]);
    aResult[6] = pPage->apCell[pCur->idx]->h.leftChild;
  }else{
    aResult[3] = 0;
    aResult[6] = 0;
  }
  aResult[4] = pPage->nFree;
  cnt = 0;
  idx = pPage->u.hdr.firstFree;
  while( idx>0 && idx<SQLITE_PAGE_SIZE ){
    cnt++;
    idx = ((FreeBlk*)&pPage->u.aDisk[idx])->iNext;
  }
  aResult[5] = cnt;
  aResult[7] = pPage->u.hdr.rightChild;
  return SQLITE_OK;
}
#endif

Changes to src/btree.h.

20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
..
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.
**
** @(#) $Id: btree.h,v 1.5 2001/06/22 19:15:00 drh Exp $
*/

typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

int sqliteBtreeOpen(const char *zFilename, int mode, Btree **ppBtree);
int sqliteBtreeClose(Btree*);
................................................................................
int sqliteBtreeNext(BtCursor*, int *pRes);
int sqliteBtreeKeySize(BtCursor*, int *pSize);
int sqliteBtreeKey(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeDataSize(BtCursor*, int *pSize);
int sqliteBtreeData(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeCloseCursor(BtCursor*);

#define SQLITE_N_BTREE_META 3
int sqliteBtreeGetMeta(Btree*, int*);
int sqliteBtreeUpdateMeta(Btree*, int*);


#ifdef SQLITE_TEST
int sqliteBtreePageDump(Btree*, int);
int sqliteBtreeCursorDump(BtCursor*, int*);
#endif







|







 







|








20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
..
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.
**
** @(#) $Id: btree.h,v 1.6 2001/06/25 02:11:07 drh Exp $
*/

typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

int sqliteBtreeOpen(const char *zFilename, int mode, Btree **ppBtree);
int sqliteBtreeClose(Btree*);
................................................................................
int sqliteBtreeNext(BtCursor*, int *pRes);
int sqliteBtreeKeySize(BtCursor*, int *pSize);
int sqliteBtreeKey(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeDataSize(BtCursor*, int *pSize);
int sqliteBtreeData(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeCloseCursor(BtCursor*);

#define SQLITE_N_BTREE_META 4
int sqliteBtreeGetMeta(Btree*, int*);
int sqliteBtreeUpdateMeta(Btree*, int*);


#ifdef SQLITE_TEST
int sqliteBtreePageDump(Btree*, int);
int sqliteBtreeCursorDump(BtCursor*, int*);
#endif

Changes to src/test3.c.

21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
...
606
607
608
609
610
611
612
613
614









615
616
617
618
619
620
621
622
623

624
625
626
627
628
629
630
631
632
633
634
635
636
637
638




639
640
641
642
643
644
645
646
**   http://www.hwaci.com/drh/
**
*************************************************************************
** 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.2 2001/06/22 19:15:01 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  free(zBuf);
  return SQLITE_OK;
}

/*
** Usage:   btree_cursor_dump ID
**
** Return two integers which are the page number and cell index for
** the given cursor.









*/
static int btree_cursor_dump(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  char **argv            /* Text of each argument */
){
  BtCursor *pCur;
  int rc;

  int aResult[2];
  char zBuf[50];

  if( argc!=2 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR;
  rc = sqliteBtreeCursorDump(pCur, aResult);
  if( rc ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  sprintf(zBuf,"%d %d",aResult[0], aResult[1]);




  Tcl_AppendResult(interp, zBuf, 0);
  return SQLITE_OK;
}

/*
** Register commands with the TCL interpreter.
*/
int Sqlitetest3_Init(Tcl_Interp *interp){







|







 







|
|
>
>
>
>
>
>
>
>
>









>
|
|












|
>
>
>
>
|







21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
...
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
**   http://www.hwaci.com/drh/
**
*************************************************************************
** 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.3 2001/06/25 02:11:07 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  free(zBuf);
  return SQLITE_OK;
}

/*
** Usage:   btree_cursor_dump ID
**
** Return eight integers containing information about the entry the
** cursor is pointing to:
**
**   aResult[0] =  The page number
**   aResult[1] =  The entry number
**   aResult[2] =  Total number of entries on this page
**   aResult[3] =  Size of this entry
**   aResult[4] =  Number of free bytes on this page
**   aResult[5] =  Number of free blocks on the page
**   aResult[6] =  Page number of the left child of this entry
**   aResult[7] =  Page number of the right child for the whole page
*/
static int btree_cursor_dump(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  char **argv            /* Text of each argument */
){
  BtCursor *pCur;
  int rc;
  int i, j;
  int aResult[8];
  char zBuf[400];

  if( argc!=2 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR;
  rc = sqliteBtreeCursorDump(pCur, aResult);
  if( rc ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  j = 0;
  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){

Changes to test/btree.test.

19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
...
283
284
285
286
287
288
289

















290
291

292
293
294
295
296
297
298
299
300
301
302
303
304

305


























306









307





308






























































































































































































309








310




311



312
313
314
315
#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree.test,v 1.1 2001/06/24 20:39:41 drh Exp $


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

if {$dbprefix!="memory:" && [info commands btree_open]!=""} {

................................................................................
  }
  set r   
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}

# Commit and make sure the delete is still there.
#
do_test btree-4.5 {

















  btree_close_cursor $::c1
  btree_commit $::b1

  set ::c1 [btree_cursor $::b1 2]
  btree_move_to $::c1 {}
  set r {}
  while 1 {
    set key [btree_key $::c1]
    if {$key==""} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}













































do_test btree-99.1 {






























































































































































































  btree_close $::b1








} {}









} ;# end if( not mem: and has pager_open command );

finish_test







|







 







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

|
>

<











>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

>
>
>
>
>
>
>
>
>
|
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

>
>
>
>
>
>
>
>

>
>
>
>

>
>
>




19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
...
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310

311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree.test,v 1.2 2001/06/25 02:11:07 drh Exp $


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

if {$dbprefix!="memory:" && [info commands btree_open]!=""} {

................................................................................
  }
  set r   
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}

# Commit and make sure the delete is still there.
#
do_test btree-4.5 {
  btree_commit $::b1
  btree_move_to $::c1 {}
  set r {}
  while 1 {
    set key [btree_key $::c1]
    if {$key==""} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}

# Completely close the database and reopen it.  Then check
# the data again.
#
do_test btree-4.6 {
  btree_close_cursor $::c1
  btree_close $::b1
  set ::b1 [btree_open test1.bt]
  set ::c1 [btree_cursor $::b1 2]

  set r {}
  while 1 {
    set key [btree_key $::c1]
    if {$key==""} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}

# Try to read and write meta data
#
do_test btree-5.1 {
  btree_get_meta $::b1
} {0 0 0 0}
do_test btree-5.2 {
  set rc [catch {btree_update_meta $::b1 1 2 3 4} msg]
  lappend rc $msg
} {1 SQLITE_ERROR}
do_test btree-5.3 {
  btree_begin_transaction $::b1
  set rc [catch {btree_update_meta $::b1 1 2 3 4} msg]
  lappend rc $msg
} {0 {}}
do_test btree-5.4 {
  btree_get_meta $::b1
} {0 2 3 4}
do_test btree-5.5 {
  btree_close_cursor $::c1
  btree_rollback $::b1
  btree_get_meta $::b1
} {0 0 0 0}
do_test btree-5.6 {
  btree_begin_transaction $::b1
  btree_update_meta $::b1 999 10 20 30
  btree_commit $::b1
  btree_get_meta $::b1
} {0 10 20 30}

proc select_all {cursor} {
  set r {}
  btree_move_to $cursor {}
  while 1 {
    set key [btree_key $cursor]
    if {$key==""} break
    lappend r $key
    lappend r [btree_data $cursor]
    btree_next $cursor
  }
  return $r
}

# Try to create a new table in the database file
#
do_test btree-6.1 {
  set rc [catch {btree_create_table $::b1} msg]
  lappend rc $msg
} {1 SQLITE_ERROR}
do_test btree-6.2 {
  btree_begin_transaction $::b1
  set ::t2 [btree_create_table $::b1]
} {3}
do_test btree-6.2.1 {
  set ::c2 [btree_cursor $::b1 $::t2]
  btree_insert $::c2 ten 10
  btree_key $::c2
} {ten}
do_test btree-6.3 {
  btree_commit $::b1
  set ::c1 [btree_cursor $::b1 2]
  select_all $::c1
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}
#btree_page_dump $::b1 3
do_test btree-6.4 {
  select_all $::c2
} {ten 10}

# Drop the new table, then create it again anew.
#
do_test btree-6.5 {
  btree_begin_transaction $::b1
} {}
do_test btree-6.6 {
  btree_close_cursor $::c2
} {}
do_test btree-6.7 {
  btree_drop_table $::b1 $::t2
} {}
do_test btree-6.7.1 {
  lindex [btree_get_meta $::b1] 0
} {1}
do_test btree-6.8 {
  set ::t2 [btree_create_table $::b1]
} {3}
do_test btree-6.8.1 {
  lindex [btree_get_meta $::b1] 0
} {0}
do_test btree-6.9 {
  set ::c2 [btree_cursor $::b1 $::t2]
  btree_move_to $::c2 {}
  btree_key $::c2
} {}

# If we drop table 2 it just clears the table.  Table 2 always exists.
#
do_test btree-6.10 {
  btree_close_cursor $::c1
  btree_drop_table $::b1 2
  set ::c1 [btree_cursor $::b1 2]
  btree_move_to $::c1 {}
  btree_key $::c1
} {}
do_test btree-6.11 {
  btree_commit $::b1
  select_all $::c1
} {}
do_test btree-6.12 {
  select_all $::c2
} {}

# Check to see that pages defragment properly.  To do this test we will
# 
#   1.  Fill the first page table 2 with data.
#   2.  Delete every other entry of table 2. 
#   3.  Insert a single entry that requires more contiguous
#       space than is available.
#
do_test btree-7.1 {
  btree_begin_transaction $::b1
} {}
do_test btree-7.2 {
  for {set i 0} {$i<36} {incr i} {
    set key [format %03d $i]
    set data "*** $key ***"
    btree_insert $::c1 $key $data
  }
  lrange [btree_cursor_dump $::c1] 4 5
} {8 1}
do_test btree-7.3 {
  btree_move_to $::c1 000
  while {[btree_key $::c1]!=""} {
    btree_delete $::c1
    btree_next $::c1
    btree_next $::c1
  }
  lrange [btree_cursor_dump $::c1] 4 5
} {512 19}
#btree_page_dump $::b1 2
do_test btree-7.4 {
  btree_insert $::c1 018 {*** 018 ***+++}
  btree_key $::c1
} {018}
do_test btree-7.5 {
  lrange [btree_cursor_dump $::c1] 4 5
} {480 1}
#btree_page_dump $::b1 2

# Delete an entry to make a hole of a known size, then immediately recreate
# that entry.  This tests the path into allocateSpace where the hole exactly
# matches the size of the desired space.
#
do_test btree-7.6 {
  btree_move_to $::c1 007
  btree_delete $::c1
  btree_move_to $::c1 011
  btree_delete $::c1
} {}
do_test btree-7.7 {
  lindex [btree_cursor_dump $::c1] 5
} {3}
#btree_page_dump $::b1 2
do_test btree-7.8 {
  btree_insert $::c1 007 {*** 007 ***}
  lindex [btree_cursor_dump $::c1] 5
} {2}
#btree_page_dump $::b1 2

# Make sure the freeSpace() routine properly coaleses adjacent memory blocks
#
do_test btree-7.9 {
  btree_move_to $::c1 013
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {536 2}
do_test btree-7.10 {
  btree_move_to $::c1 009
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {564 2}
do_test btree-7.11 {
  btree_move_to $::c1 018
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {596 2}
do_test btree-7.13 {
  btree_move_to $::c1 033
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {624 3}
do_test btree-7.14 {
  btree_move_to $::c1 035
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {652 2}
#btree_page_dump $::b1 2

# Check to see that both key and data on overflow pages work correctly.
#
do_test btree-8.1 {
  set data "*** This is a very long key "
  while {[string length $data]<256} {append data $data}
  set ::data $data
  btree_insert $::c1 020 $data
} {}
#btree_page_dump $::b1 2
do_test btree-8.2 {
  string length [btree_data $::c1]
} [string length $::data]
do_test btree-8.3 {
  btree_data $::c1
} $::data
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 020 $data
} {}
do_test btree-8.6 {
  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
  btree_data $::c1
} $::data
do_test btree-8.9 {
  btree_close_cursor $::c1
  btree_close $::b1
  set ::b1 [btree_open test1.bt]
  set ::c1 [btree_cursor $::b1 2]
  btree_move_to $::c1 020
  btree_data $::c1
} $::data
do_test btree-8.10 {
  btree_begin_transaction $::b1
  btree_delete $::c1
} {}
do_test btree-8.11 {
  lindex [btree_get_meta $::b1] 0
} [expr {int(([string length $::data]-238+1019)/1020)}]
puts [btree_get_meta $::b1]

do_test btree-99.1 {
  btree_close $::b1
} {}

} ;# end if( not mem: and has pager_open command );

finish_test