/ Check-in [6ad5fc8e]
Login

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

Overview
Comment:Allow btree cursors to persist through BtreeDelete() calls. (CVS 2103)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 6ad5fc8e1a119b750a82fc1426704164a2042d57
User & Date: danielk1977 2004-11-16 04:57:24
Context
2004-11-16
15:50
Perform deletes in a single pass. (CVS 2104) check-in: a2e1c35b user: danielk1977 tags: trunk
04:57
Allow btree cursors to persist through BtreeDelete() calls. (CVS 2103) check-in: 6ad5fc8e user: danielk1977 tags: trunk
2004-11-15
23:42
Fix a typo in the header comment to the MakeRecord opcode so that the documentation generator will actually see the opcode description. Ticket #1001. (CVS 2102) check-in: 33c9b647 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
...
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
....
2100
2101
2102
2103
2104
2105
2106

2107
2108
2109
2110
2111
2112
2113
....
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
....
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
....
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
....
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
....
2533
2534
2535
2536
2537
2538
2539

2540
2541
2542
2543
2544
2545
2546
....
2769
2770
2771
2772
2773
2774
2775










2776
2777
2778
2779
2780
2781
2782
....
2818
2819
2820
2821
2822
2823
2824










2825
2826
2827
2828
2829
2830
2831
....
3902
3903
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
3925
3926
3927
3928
3929
3930
3931
3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
3944
3945
3946
3947
3948
3949
3950
3951
3952
3953
3954
3955
3956
3957
3958
3959
3960
3961
3962
3963
3964
3965
3966
3967
3968
3969
....
3984
3985
3986
3987
3988
3989
3990
3991
3992
3993
3994
3995
3996
3997
3998
3999
4000
4001
4002
4003

4004
4005
4006
4007
4008
4009
4010
....
4015
4016
4017
4018
4019
4020
4021

4022
4023
4024
4025
4026
4027
4028
....
4171
4172
4173
4174
4175
4176
4177

4178
4179
4180
4181
4182
4183
4184
4185













4186
4187
4188
4189
4190
4191

4192
4193
4194
4195
4196
4197
4198
4199









4200
4201
4202
4203
4204
4205
4206
....
4296
4297
4298
4299
4300
4301
4302
4303
4304
4305
4306
4307
4308
4309
4310
4311
4312
4313
4314
4315
4316
4317
4318
4319
4320
4321
4322
4323
4324
4325
4326
....
4414
4415
4416
4417
4418
4419
4420
4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
....
4432
4433
4434
4435
4436
4437
4438


4439
4440
4441
4442
4443
4444
4445
....
4453
4454
4455
4456
4457
4458
4459
4460







































4461
4462
4463
4464
4465
4466
4467
4468
4469
4470
4471
4472
4473
4474
4475
4476
4477

4478
4479
4480
4481
4482
4483
4484






4485
4486
4487
4488
4489
4490
4491
4492
4493
4494
4495
4496






4497
4498
4499
4500
4501
4502



4503
4504
4505
4506
























4507
4508
4509
4510










4511
4512
4513
4514
4515
4516
4517














4518
4519
4520



4521
4522
4523
4524
4525
4526
4527
** 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.217 2004/11/13 13:19:56 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.
................................................................................
  u16 nSize;     /* Size of the cell content on the main b-tree page */
};

/*
** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.










*/
struct BtCursor {
  Btree *pBt;               /* The Btree to which this cursor belongs */
  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
  int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
  void *pArg;               /* First arg to xCompare() */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */
  u8 isValid;               /* TRUE if points to a valid entry */
  u8 status;                /* Set to SQLITE_ABORT if cursors is invalidated */

};

/*
** Forward declaration
*/
static int checkReadLocks(Btree*,Pgno,BtCursor*);

................................................................................
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur;
  }
  pCur->pPrev = 0;
  pBt->pCursor = pCur;
  pCur->isValid = 0;
  pCur->status = SQLITE_OK;

  *ppCur = pCur;
  return SQLITE_OK;

create_cursor_exception:
  if( pCur ){
    releasePage(pCur->pPage);
    sqliteFree(pCur);
................................................................................
** the key for the current entry.  If the cursor is not pointing
** to a valid entry, *pSize is set to 0. 
**
** For a table with the INTKEY flag set, this routine returns the key
** itself, not the number of bytes in the key.
*/
int sqlite3BtreeKeySize(BtCursor *pCur, i64 *pSize){
  if( !pCur->isValid ){
    *pSize = 0;
  }else{
    getCellInfo(pCur);
    *pSize = pCur->info.nKey;
  }
  return SQLITE_OK;
}
................................................................................
** Set *pSize to the number of bytes of data in the entry the
** cursor currently points to.  Always return SQLITE_OK.
** Failure is not possible.  If the cursor is not currently
** pointing to an entry (which can happen, for example, if
** the database is empty) then *pSize is set to 0.
*/
int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
  if( !pCur->isValid ){
    /* Not pointing at a valid entry - set *pSize to 0. */
    *pSize = 0;
  }else{
    getCellInfo(pCur);
    *pSize = pCur->info.nData;
  }
  return SQLITE_OK;
................................................................................
** begins at "offset".
**
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  if( pCur->isValid==0 ){
    return pCur->status;
  }
  assert( pCur->pPage!=0 );
  assert( pCur->pPage->intKey==0 );
  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  return getPayload(pCur, offset, amt, (unsigned char*)pBuf, 0);
}
................................................................................
** begins at "offset".
**
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeData(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  if( !pCur->isValid ){
    return pCur->status ? pCur->status : SQLITE_INTERNAL;
  }
  assert( pCur->pPage!=0 );
  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  return getPayload(pCur, offset, amt, pBuf, 1);
}

................................................................................
    assert( pRoot->pgno==1 );
    subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+8]);
    assert( subpage>0 );
    pCur->isValid = 1;
    rc = moveToChild(pCur, subpage);
  }
  pCur->isValid = pCur->pPage->nCell>0;

  return rc;
}

/*
** Move the cursor down to the left-most leaf entry beneath the
** entry to which it is currently pointing.
*/
................................................................................
  assert( pRes!=0 );
  if( pCur->isValid==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }
  assert( pPage->isInit );
  assert( pCur->idx<pPage->nCell );










  pCur->idx++;
  pCur->info.nSize = 0;
  if( pCur->idx>=pPage->nCell ){
    if( !pPage->leaf ){
      rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+8]));
      if( rc ) return rc;
      rc = moveToLeftmost(pCur);
................................................................................
  int rc;
  Pgno pgno;
  MemPage *pPage;
  if( pCur->isValid==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }










  pPage = pCur->pPage;
  assert( pPage->isInit );
  assert( pCur->idx>=0 );
  if( !pPage->leaf ){
    pgno = get4byte( findCell(pPage, pCur->idx) );
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
................................................................................
    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));

#if 0
  /* The following block shows how cells migrated during the balance op. */
  if( sqlite3_btree_trace ){
    char zBuf[200];
    char *zCsr = zBuf;
    int a, b, c=0, d=0;
    *zCsr = '\0';
    for(a=0; a<nOld; a++){
      int nOldCells = apCopy[a]->nCell+apCopy[a]->nOverflow;
      for(b=0; b<(nOldCells+((a!=nOld-1&&!leafData)?1:0)); b++){
        int x = 0;
        Pgno iNewPage;
        Pgno iOldPage;
        int iNewIndex;
        int iOldIndex;

        if( b<nOldCells ){
          iOldPage = pgnoOld[a];
          iOldIndex = b;
        }else{
          iOldPage = pParent->pgno;
          iOldIndex = idxDiv[a];
        }

        while( cntNew[x]<=c ) x++;
        if( x>0 && c==cntNew[x-1] && !leafData ){
          iNewPage = pParent->pgno;
          iNewIndex = nxDiv + a;
        }else{
          assert( x<nNew );
          iNewPage = pgnoNew[x];
          iNewIndex = c-(x>0?cntNew[x-1]:0)-(leafData?0:1);
        }

        if( (&zBuf[sizeof(zBuf)])-zCsr > 100 && 
            (1 || iOldPage!=iNewPage || iOldIndex!=iNewIndex) ){
          zCsr += sprintf(zCsr, " %d.%d->%d.%d", iOldPage, iOldIndex,
              iNewPage, iNewIndex);
        }
        c++;
        if( (d==0 && strlen(zBuf)>35) || strlen(zBuf)>60 ){
          TRACE(("%s%s\n", d==0?"BALANCE: Cell migration:":"", zBuf));
          zCsr = zBuf;
          d = 1;
        }
      }
    }
    assert( c==nCell );
    if( zCsr!=zBuf ){
      TRACE(("%s%s\n", d==0?"BALANCE: Cell migration":"", zBuf));
    }
  }
#endif

  /* If there are other cursors that refer to one of the pages involved
  ** in the balancing, then adjust these cursors so that they still
  ** point to the same cells.
  */
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    int nCellCnt = 0;
    int iCell = -1;
................................................................................
      assert( !leafData );
      assert( iCell==-1 );
      if( pCur->idx>=nxDiv && pCur->idx<(nxDiv+nOld-1) ){
        for(i=0; i<=(pCur->idx-nxDiv); i++){
          iCell += (apCopy[i]->nCell + apCopy[i]->nOverflow + 1);
        }
      }
      if( pCur->idx>=(nxDiv+nOld) ){
        TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
            pCur, pgno, pCur->idx, pgno, pCur->idx+(nNew-nOld)));
        pCur->idx += (nNew-nOld);
        pCur->info.nSize = 0;
      }
    }

    if( iCell>=0 ){
      int idxNew;
      Pgno pgnoNew;
      int x = 0;


      while( cntNew[x]<=iCell ) x++;
      if( x>0 && !leafData && cntNew[x-1]==iCell ){
        /* The cell that pCur points to is a divider cell in pParent. */
        pgnoNew = pParent->pgno;
        idxNew = nxDiv + x-1;
      }else{
        /* The cell that pCur points to is on page apNew[x]. */
................................................................................
      TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
          pCur, pgno, pCur->idx, pgnoNew, idxNew));

      pCur->idx = idxNew;
      releasePage(pCur->pPage);
      rc = getPage(pBt, pgnoNew, &pCur->pPage);
      assert( rc==SQLITE_OK );

      pCur->info.nSize = 0;
    }
  }

  /* Free any old pages that were not reused as new pages.
  */
  for(i=nNew; i<nOld; i++){
................................................................................
      rc = initPage(pChild, pPage);
      if( rc ) goto end_shallow_balance;
      assert( pChild->nOverflow==0 );
      if( pChild->nFree>=100 ){
        /* The child information will fit on the root page, so do the
        ** copy */
        int i;

        zeroPage(pPage, pChild->aData[0]);
        for(i=0; i<pChild->nCell; i++){
          apCell[i] = findCell(pChild,i);
          szCell[i] = cellSizePtr(pChild, apCell[i]);
        }
        assemblePage(pPage, pChild->nCell, apCell, szCell);
        freePage(pChild);
        TRACE(("BALANCE: child %d transfer to page 1\n", pChild->pgno));













      }else{
        /* The child has more information that will fit on the root.
        ** The tree is already balanced.  Do nothing. */
        TRACE(("BALANCE: child %d will not fit on page 1\n", pChild->pgno));
      }
    }else{

      memcpy(pPage->aData, pChild->aData, pPage->pBt->usableSize);
      pPage->isInit = 0;
      pPage->pParent = 0;
      rc = initPage(pPage, 0);
      assert( rc==SQLITE_OK );
      freePage(pChild);
      TRACE(("BALANCE: transfer child %d into root %d\n",
              pChild->pgno, pPage->pgno));









    }
    rc = reparentChildPages(pPage);
    if( rc!=SQLITE_OK ) goto end_shallow_balance;
    releasePage(pChild);
  }
end_shallow_balance:
  sqliteFree(apCell);
................................................................................

/*
** This routine checks all cursors that point to table pgnoRoot.
** If any of those cursors other than pExclude were opened with 
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
** cursors that point to pgnoRoot were opened with wrFlag==1
** then this routine returns SQLITE_OK.
**
** In addition to checking for read-locks (where a read-lock 
** means a cursor opened with wrFlag==0) this routine also moves
** all cursors other than pExclude so that they are pointing to the 
** first Cell on root page.  This is necessary because an insert 
** or delete might change the number of cells on a page or delete
** a page entirely and we do not want to leave any cursors 
** pointing to non-existant pages or cells.
*/
static int checkReadLocks(Btree *pBt, Pgno pgnoRoot, BtCursor *pExclude){
  BtCursor *p;
  for(p=pBt->pCursor; p; p=p->pNext){
    if( p->pgnoRoot!=pgnoRoot || p==pExclude ) continue;
    if( p->wrFlag==0 ) return SQLITE_LOCKED;
    if( p->pPage->pgno!=p->pgnoRoot ){
/*      moveToRoot(p); */
    }
  }
  return SQLITE_OK;
}

/*
** Insert a new record into the BTree.  The key is given by (pKey,nKey)
** and the data is given by (pData,nData).  The cursor is used only to
................................................................................
    }
  }

  if( rc!=SQLITE_OK ) goto end_insert;
  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  if( rc==SQLITE_OK ){
  /*  moveToRoot(pCur); */
  }
end_insert:
  sqliteFree(newCell);
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor
................................................................................
*/
int sqlite3BtreeDelete(BtCursor *pCur){
  MemPage *pPage = pCur->pPage;
  unsigned char *pCell;
  int rc;
  Pgno pgnoChild = 0;
  Btree *pBt = pCur->pBt;



  assert( pPage->isInit );
  if( pCur->status ){
    return pCur->status;  /* A rollback destroyed this cursor */
  }
  if( pBt->inTrans!=TRANS_WRITE ){
    /* Must start a transaction before doing a delete */
................................................................................
    return SQLITE_PERM;   /* Did not open this cursor for writing */
  }
  if( checkReadLocks(pBt, pCur->pgnoRoot, pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlite3pager_write(pPage->aData);
  if( rc ) return rc;








































  /* Locate the cell within it's page and leave pCell pointing to the
  ** data. The clearCell() call frees any overflow pages associated with the
  ** cell. The cell itself is still intact.
  */
  pCell = findCell(pPage, pCur->idx);
  if( !pPage->leaf ){
    pgnoChild = get4byte(pCell);
  }
  clearCell(pPage, pCell);

  if( !pPage->leaf ){
    /*
    ** The entry we are about to delete is not a leaf so if we do not
    ** do something we will leave a hole on an internal page.
    ** We have to fill the hole by moving in a cell from a leaf.  The
    ** next Cell after the one to be deleted is guaranteed to exist and
    ** to be a leaf so we can use it.

    */
    BtCursor leafCur;
    unsigned char *pNext;
    int szNext;
    int notUsed;
    unsigned char *tempCell;
    assert( !pPage->leafData );






    getTempCursor(pCur, &leafCur);
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc!=SQLITE_OK ){
      if( rc!=SQLITE_NOMEM ){
        rc = SQLITE_CORRUPT;  /* bkpt-CORRUPT */
      }
      return rc;
    }
    rc = sqlite3pager_write(leafCur.pPage->aData);
    if( rc ) return rc;
    TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno));






    dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
    pNext = findCell(leafCur.pPage, leafCur.idx);
    szNext = cellSizePtr(leafCur.pPage, pNext);
    assert( MX_CELL_SIZE(pBt)>=szNext+4 );
    tempCell = sqliteMallocRaw( MX_CELL_SIZE(pBt) );
    if( tempCell==0 ) return SQLITE_NOMEM;



    rc = insertCell(pPage, pCur->idx, pNext-4, szNext+4, tempCell);
    if( rc!=SQLITE_OK ) return rc;
    put4byte(findOverflowCell(pPage, pCur->idx), pgnoChild);
    pCur->isValid = 0;
























    rc = balance(pPage);
    sqliteFree(tempCell);
    if( rc ) return rc;
    dropCell(leafCur.pPage, leafCur.idx, szNext);










    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno));
    dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
    pCur->isValid = 0;














    rc = balance(pPage);
  }
  moveToRoot(pCur);



  return rc;
}

/*
** Create a new BTree table.  Write into *piTable the page
** number for the root page of the new table.
**







|







 







>
>
>
>
>
>
>
>
>
>













>







 







>







 







|







 







|







 







|







 







|







 







>







 







>
>
>
>
>
>
>
>
>
>







 







>
>
>
>
>
>
>
>
>
>







 







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







|












>







 







>







 







>








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






>








>
>
>
>
>
>
>
>
>







 







<
<
<
<
<
<
<
<






<
<
<







 







<
<
<







 







>
>







 








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




|











|
>







>
>
>
>
>
>

<




|


|


>
>
>
>
>
>
|




|
>
>
>
|
|
|
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>


|

>
>
>
>
>
>
>
>
>
>



|
|
|
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>


<
>
>
>







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
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
....
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
....
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
....
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
....
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
....
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
....
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
....
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
....
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
....
3935
3936
3937
3938
3939
3940
3941






















































3942
3943
3944
3945
3946
3947
3948
....
3963
3964
3965
3966
3967
3968
3969
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979
3980
3981
3982
3983
3984
3985
3986
3987
3988
3989
3990
....
3995
3996
3997
3998
3999
4000
4001
4002
4003
4004
4005
4006
4007
4008
4009
....
4152
4153
4154
4155
4156
4157
4158
4159
4160
4161
4162
4163
4164
4165
4166
4167
4168
4169
4170
4171
4172
4173
4174
4175
4176
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
4190
4191
4192
4193
4194
4195
4196
4197
4198
4199
4200
4201
4202
4203
4204
4205
4206
4207
4208
4209
4210
4211
....
4301
4302
4303
4304
4305
4306
4307








4308
4309
4310
4311
4312
4313



4314
4315
4316
4317
4318
4319
4320
....
4408
4409
4410
4411
4412
4413
4414



4415
4416
4417
4418
4419
4420
4421
....
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435
4436
4437
4438
....
4446
4447
4448
4449
4450
4451
4452
4453
4454
4455
4456
4457
4458
4459
4460
4461
4462
4463
4464
4465
4466
4467
4468
4469
4470
4471
4472
4473
4474
4475
4476
4477
4478
4479
4480
4481
4482
4483
4484
4485
4486
4487
4488
4489
4490
4491
4492
4493
4494
4495
4496
4497
4498
4499
4500
4501
4502
4503
4504
4505
4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
4524

4525
4526
4527
4528
4529
4530
4531
4532
4533
4534
4535
4536
4537
4538
4539
4540
4541
4542
4543
4544
4545
4546
4547
4548
4549
4550
4551
4552

4553
4554
4555
4556
4557
4558
4559
4560
4561
4562
4563
4564
4565
4566
4567
4568
4569
4570
4571
4572
4573
4574
4575
4576
4577
4578
4579
4580
4581
4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
4592
4593
4594
4595
4596

4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612

4613
4614
4615
4616
4617
4618
4619
4620
4621
4622
** 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.218 2004/11/16 04:57:24 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.
................................................................................
  u16 nSize;     /* Size of the cell content on the main b-tree page */
};

/*
** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.
**
** Normally, the BtCursor.delShift variable is 0. If non-zero, this
** indicates that the entry to which the cursor logically points 
** was deleted (by a BtreeDelete() call). If this is the case, the
** BtreeKeySize() and BtreeDataSize() calls both return 0. 

** If BtCursor.delShift is +1, then do not move the cursor for a 
** BtreeNext() operation (it was already advanced when the entry the
** cursor logically points to was deleted). If BtCursor.delShift is
** -1, then ignore the next BtreePrevious() call.
*/
struct BtCursor {
  Btree *pBt;               /* The Btree to which this cursor belongs */
  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
  int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
  void *pArg;               /* First arg to xCompare() */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */
  u8 isValid;               /* TRUE if points to a valid entry */
  u8 status;                /* Set to SQLITE_ABORT if cursors is invalidated */
  int delShift;             /* See above. */
};

/*
** Forward declaration
*/
static int checkReadLocks(Btree*,Pgno,BtCursor*);

................................................................................
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur;
  }
  pCur->pPrev = 0;
  pBt->pCursor = pCur;
  pCur->isValid = 0;
  pCur->status = SQLITE_OK;
  pCur->delShift = 0;
  *ppCur = pCur;
  return SQLITE_OK;

create_cursor_exception:
  if( pCur ){
    releasePage(pCur->pPage);
    sqliteFree(pCur);
................................................................................
** the key for the current entry.  If the cursor is not pointing
** to a valid entry, *pSize is set to 0. 
**
** For a table with the INTKEY flag set, this routine returns the key
** itself, not the number of bytes in the key.
*/
int sqlite3BtreeKeySize(BtCursor *pCur, i64 *pSize){
  if( !pCur->isValid || pCur->delShift ){
    *pSize = 0;
  }else{
    getCellInfo(pCur);
    *pSize = pCur->info.nKey;
  }
  return SQLITE_OK;
}
................................................................................
** Set *pSize to the number of bytes of data in the entry the
** cursor currently points to.  Always return SQLITE_OK.
** Failure is not possible.  If the cursor is not currently
** pointing to an entry (which can happen, for example, if
** the database is empty) then *pSize is set to 0.
*/
int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
  if( !pCur->isValid || pCur->delShift ){
    /* Not pointing at a valid entry - set *pSize to 0. */
    *pSize = 0;
  }else{
    getCellInfo(pCur);
    *pSize = pCur->info.nData;
  }
  return SQLITE_OK;
................................................................................
** begins at "offset".
**
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  if( !pCur->isValid || pCur->delShift ){
    return pCur->status;
  }
  assert( pCur->pPage!=0 );
  assert( pCur->pPage->intKey==0 );
  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  return getPayload(pCur, offset, amt, (unsigned char*)pBuf, 0);
}
................................................................................
** begins at "offset".
**
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeData(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  if( !pCur->isValid || pCur->delShift ){
    return pCur->status ? pCur->status : SQLITE_INTERNAL;
  }
  assert( pCur->pPage!=0 );
  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  return getPayload(pCur, offset, amt, pBuf, 1);
}

................................................................................
    assert( pRoot->pgno==1 );
    subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+8]);
    assert( subpage>0 );
    pCur->isValid = 1;
    rc = moveToChild(pCur, subpage);
  }
  pCur->isValid = pCur->pPage->nCell>0;
  pCur->delShift = 0;
  return rc;
}

/*
** Move the cursor down to the left-most leaf entry beneath the
** entry to which it is currently pointing.
*/
................................................................................
  assert( pRes!=0 );
  if( pCur->isValid==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }
  assert( pPage->isInit );
  assert( pCur->idx<pPage->nCell );

  /* If BtCursor.delShift is 1, the cursor has already been advanced. */
  if( pCur->delShift==1 ){
    *pRes = 0;
    pCur->delShift = 0;
    return SQLITE_OK;
  }else{
    pCur->delShift = 0;
  }

  pCur->idx++;
  pCur->info.nSize = 0;
  if( pCur->idx>=pPage->nCell ){
    if( !pPage->leaf ){
      rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+8]));
      if( rc ) return rc;
      rc = moveToLeftmost(pCur);
................................................................................
  int rc;
  Pgno pgno;
  MemPage *pPage;
  if( pCur->isValid==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }

  /* If BtCursor.delShift is -1, the cursor has already been advanced. */
  if( pCur->delShift==-1 ){
    *pRes = 0;
    pCur->delShift = 0;
    return SQLITE_OK;
  }else{
    pCur->delShift = 0;
  }

  pPage = pCur->pPage;
  assert( pPage->isInit );
  assert( pCur->idx>=0 );
  if( !pPage->leaf ){
    pgno = get4byte( findCell(pPage, pCur->idx) );
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
................................................................................
    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));























































  /* If there are other cursors that refer to one of the pages involved
  ** in the balancing, then adjust these cursors so that they still
  ** point to the same cells.
  */
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    int nCellCnt = 0;
    int iCell = -1;
................................................................................
      assert( !leafData );
      assert( iCell==-1 );
      if( pCur->idx>=nxDiv && pCur->idx<(nxDiv+nOld-1) ){
        for(i=0; i<=(pCur->idx-nxDiv); i++){
          iCell += (apCopy[i]->nCell + apCopy[i]->nOverflow + 1);
        }
      }
      if( pCur->idx>=(nxDiv+nOld-1) ){
        TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
            pCur, pgno, pCur->idx, pgno, pCur->idx+(nNew-nOld)));
        pCur->idx += (nNew-nOld);
        pCur->info.nSize = 0;
      }
    }

    if( iCell>=0 ){
      int idxNew;
      Pgno pgnoNew;
      int x = 0;

      assert( iCell<nCell );
      while( cntNew[x]<=iCell ) x++;
      if( x>0 && !leafData && cntNew[x-1]==iCell ){
        /* The cell that pCur points to is a divider cell in pParent. */
        pgnoNew = pParent->pgno;
        idxNew = nxDiv + x-1;
      }else{
        /* The cell that pCur points to is on page apNew[x]. */
................................................................................
      TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
          pCur, pgno, pCur->idx, pgnoNew, idxNew));

      pCur->idx = idxNew;
      releasePage(pCur->pPage);
      rc = getPage(pBt, pgnoNew, &pCur->pPage);
      assert( rc==SQLITE_OK );
      assert( pCur->pPage->isInit );
      pCur->info.nSize = 0;
    }
  }

  /* Free any old pages that were not reused as new pages.
  */
  for(i=nNew; i<nOld; i++){
................................................................................
      rc = initPage(pChild, pPage);
      if( rc ) goto end_shallow_balance;
      assert( pChild->nOverflow==0 );
      if( pChild->nFree>=100 ){
        /* The child information will fit on the root page, so do the
        ** copy */
        int i;
        BtCursor *pCur;
        zeroPage(pPage, pChild->aData[0]);
        for(i=0; i<pChild->nCell; i++){
          apCell[i] = findCell(pChild,i);
          szCell[i] = cellSizePtr(pChild, apCell[i]);
        }
        assemblePage(pPage, pChild->nCell, apCell, szCell);
        freePage(pChild);
        TRACE(("BALANCE: child %d transfer to page 1\n", pChild->pgno));
        /* If there were cursors pointing at this page, point them at the 
        ** new page instead. Decrement the reference count for the old 
        ** page and increment it for the new one.
        */
        for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
          if( pCur->pPage==pChild ){
            TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
                pCur, pPage->pgno, pCur->idx, pPage->pgno, pCur->idx));
            releasePage(pCur->pPage);
            rc = getPage(pBt, 1,  &pCur->pPage);
            assert( rc==SQLITE_OK );
          }
        }
      }else{
        /* The child has more information that will fit on the root.
        ** The tree is already balanced.  Do nothing. */
        TRACE(("BALANCE: child %d will not fit on page 1\n", pChild->pgno));
      }
    }else{
      BtCursor *pCur;
      memcpy(pPage->aData, pChild->aData, pPage->pBt->usableSize);
      pPage->isInit = 0;
      pPage->pParent = 0;
      rc = initPage(pPage, 0);
      assert( rc==SQLITE_OK );
      freePage(pChild);
      TRACE(("BALANCE: transfer child %d into root %d\n",
              pChild->pgno, pPage->pgno));
      for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
        if( pCur->pPage==pChild ){
          TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
              pCur, pChild->pgno, pCur->idx, pPage->pgno, pCur->idx));
          releasePage(pCur->pPage);
          rc = getPage(pBt, pPage->pgno,  &pCur->pPage);
          assert( rc==SQLITE_OK );
        }
      }
    }
    rc = reparentChildPages(pPage);
    if( rc!=SQLITE_OK ) goto end_shallow_balance;
    releasePage(pChild);
  }
end_shallow_balance:
  sqliteFree(apCell);
................................................................................

/*
** This routine checks all cursors that point to table pgnoRoot.
** If any of those cursors other than pExclude were opened with 
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
** cursors that point to pgnoRoot were opened with wrFlag==1
** then this routine returns SQLITE_OK.








*/
static int checkReadLocks(Btree *pBt, Pgno pgnoRoot, BtCursor *pExclude){
  BtCursor *p;
  for(p=pBt->pCursor; p; p=p->pNext){
    if( p->pgnoRoot!=pgnoRoot || p==pExclude ) continue;
    if( p->wrFlag==0 ) return SQLITE_LOCKED;



  }
  return SQLITE_OK;
}

/*
** Insert a new record into the BTree.  The key is given by (pKey,nKey)
** and the data is given by (pData,nData).  The cursor is used only to
................................................................................
    }
  }

  if( rc!=SQLITE_OK ) goto end_insert;
  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */



end_insert:
  sqliteFree(newCell);
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor
................................................................................
*/
int sqlite3BtreeDelete(BtCursor *pCur){
  MemPage *pPage = pCur->pPage;
  unsigned char *pCell;
  int rc;
  Pgno pgnoChild = 0;
  Btree *pBt = pCur->pBt;
  int idx;                /* Index of the cell to delete */
  BtCursor *pCur2;        /* Iterator variable for the pBt.pCursor link-list */

  assert( pPage->isInit );
  if( pCur->status ){
    return pCur->status;  /* A rollback destroyed this cursor */
  }
  if( pBt->inTrans!=TRANS_WRITE ){
    /* Must start a transaction before doing a delete */
................................................................................
    return SQLITE_PERM;   /* Did not open this cursor for writing */
  }
  if( checkReadLocks(pBt, pCur->pgnoRoot, pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlite3pager_write(pPage->aData);
  if( rc ) return rc;

  /* Set index to the index in pPage that contains the cell to delete. Also
  ** increment the reference count for pPage. This allows us to move the
  ** cursor pCur before the delete takes place.
  */
  idx = pCur->idx;
  rc = getPage(pBt, pPage->pgno, &pPage);
  if( rc ) return rc;
  assert( pPage==pCur->pPage );

  /* If there are any cursors that point to the cell being deleted, 
  ** move them to the next or previous entry in the table. It is preferable
  ** to move the cursor to the 'next' location, rather than the 'previous'
  ** one, as most table scans are done in the forward direction (also, code
  ** below depends on this). If neither entry exists, declare the cursor
  ** invalid.
  */ 
  for(pCur2=pBt->pCursor; pCur2; pCur2 = pCur2->pNext){
    if( pCur2->pPage==pPage && pCur2->idx==idx && pCur2->isValid ){
      int res;
      pCur2->delShift = 0;
      rc = sqlite3BtreeNext(pCur2, &res);
      if( rc ) goto delete_out;
      if( res ){
        /* If the next tree entry cannot be found, then the cursor must
        ** already point to the last table entry. So point it to the
        ** second last by calling BtreeLast(), BtreePrevious().
        */
        rc = sqlite3BtreeLast(pCur2, &res);
        if( rc ) goto delete_out;
        assert( res==0 );
        rc = sqlite3BtreePrevious(pCur2, &res);
        if( rc ) goto delete_out;
        pCur2->delShift = -1;
      }else{
        pCur2->delShift = 1;
      }
    }
  }

  /* Locate the cell within it's page and leave pCell pointing to the
  ** data. The clearCell() call frees any overflow pages associated with the
  ** cell. The cell itself is still intact.
  */
  pCell = findCell(pPage, idx);
  if( !pPage->leaf ){
    pgnoChild = get4byte(pCell);
  }
  clearCell(pPage, pCell);

  if( !pPage->leaf ){
    /*
    ** The entry we are about to delete is not a leaf so if we do not
    ** do something we will leave a hole on an internal page.
    ** We have to fill the hole by moving in a cell from a leaf.  The
    ** next Cell after the one to be deleted is guaranteed to exist and
    ** to be a leaf so we can use it. Conveniantly, pCur now points
    ** at this cell (because it was advanced above).
    */
    BtCursor leafCur;
    unsigned char *pNext;
    int szNext;
    int notUsed;
    unsigned char *tempCell;
    assert( !pPage->leafData );

    /* Make a copy of *pCur in leafCur. leafCur now points to the cell 
    ** that will be moved into the space left by the cell being deleted.
    */
    assert( pCur->delShift==1 );
    assert( pCur->isValid );
    getTempCursor(pCur, &leafCur);

    if( rc!=SQLITE_OK ){
      if( rc!=SQLITE_NOMEM ){
        rc = SQLITE_CORRUPT;  /* bkpt-CORRUPT */
      }
      goto delete_out;
    }
    rc = sqlite3pager_write(leafCur.pPage->aData);
    if( rc ) goto delete_out;
    TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno));

    /* Drop the cell from the internal page. Make a copy of the cell from
    ** the leaf page into memory obtained from malloc(). Insert it into
    ** the internal page, at the position vacated by the delete. There
    ** are now two copies of the leaf-cell in the tree.
    */
    dropCell(pPage, idx, cellSizePtr(pPage, pCell));
    pNext = findCell(leafCur.pPage, leafCur.idx);
    szNext = cellSizePtr(leafCur.pPage, pNext);
    assert( MX_CELL_SIZE(pBt)>=szNext+4 );
    tempCell = sqliteMallocRaw( MX_CELL_SIZE(pBt) );
    if( tempCell==0 ){
       rc = SQLITE_NOMEM;
       goto delete_out;
    }
    rc = insertCell(pPage, idx, pNext-4, szNext+4, tempCell);
    if( rc!=SQLITE_OK ) goto delete_out;
    put4byte(findOverflowCell(pPage, idx), pgnoChild);

    pPage->idxShift = 0;

    /* If there are any cursors that point to the leaf-cell, move them
    ** so that they point at internal cell. This is easiest done by
    ** calling BtreePrevious().
    */
    for(pCur2=pBt->pCursor; pCur2; pCur2 = pCur2->pNext){
      if( pCur2->pPage==leafCur.pPage && pCur2->idx==leafCur.idx ){
        int res;
        int delShiftSave = pCur2->delShift; 
        assert( leafCur.idx==0 );
        pCur2->delShift = 0;
        rc = sqlite3BtreePrevious(pCur2, &res);
        if( rc ) goto delete_out;
        assert( res==0 );
        assert( pCur2->pPage==pPage );
        assert( pCur2->idx==idx );
        pCur2->delShift = delShiftSave;
      }
    }

    /* Balance the internal page. Free the memory allocated for the 
    ** copy of the leaf cell. Then delete the cell from the leaf page.
    */
    rc = balance(pPage);
    sqliteFree(tempCell);
    if( rc ) goto delete_out;
    dropCell(leafCur.pPage, leafCur.idx, szNext);

    for(pCur2=pBt->pCursor; pCur2; pCur2 = pCur2->pNext){
      if( pCur2->pPage==leafCur.pPage && pCur2->idx>leafCur.idx ){
        TRACE(("DELETE: Cursor %p migrates from %d,%d to %d,%d\n", 
            pCur2, pPage->pgno, pCur2->idx, pPage->pgno, pCur2->idx-1));
        pCur2->idx--;
        pCur2->info.nSize = 0;
      }
    }

    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete %d from leaf %d\n",
       pCur->pgnoRoot, idx, pPage->pgno));
    dropCell(pPage, idx, cellSizePtr(pPage, pCell));


    /* If there were cursors pointing to cells on pPage with index values
    ** greater than idx, decrement the index values now.
    */
    for(pCur2=pBt->pCursor; pCur2; pCur2 = pCur2->pNext){
      assert( !pCur2->isValid || pCur2->pPage!=pPage || pCur2->idx!=idx );
      if( pCur2->pPage==pPage && pCur2->idx>idx ){
        TRACE(("DELETE: Cursor %p migrates from %d,%d to %d,%d\n", 
            pCur2, pPage->pgno, pCur2->idx, pPage->pgno, pCur2->idx-1));
        pCur2->idx--;
        pCur2->info.nSize = 0;
      }
    }

    rc = balance(pPage);
  }


delete_out:
  releasePage(pPage);
  return rc;
}

/*
** Create a new BTree table.  Write into *piTable the page
** number for the root page of the new table.
**

Changes to test/btree8.test.

5
6
7
8
9
10
11
12


13
14
15
16
17
18
19
20
21
..
51
52
53
54
55
56
57
58
59
60
61
62
63
64

65
66
67
68
69
70
71
..
73
74
75
76
77
78
79

























80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

95
96
97
98
99
100
101
...
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
...
120
121
122
123
124
125
126

127
128
129
130
131
132
133
134
135
136
137
138
139
140
141



















































142
143
144
145
146
147
148
149
150
151
#
#    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: btree8.test,v 1.1 2004/11/13 13:19:56 danielk1977 Exp $

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

# Use the SQL interface to create a couple of btree tables, one using
# the flags for an SQL table, the other an SQL index.
# 
................................................................................
    lappend csr_list $csr
    btree_key $csr
  } $key
  incr testnum 
}
btree_commit $::bt

# set btree_trace 1

# Now write more entries to the table (and overwriting the ones that exist).
# After each write, check that the cursors created above still point to the
# same entries.
btree_begin_transaction $::bt
set ::write_csr [btree_cursor $::bt $::tnum 1]

for {set i $testnum} {$i < 5000 && $nErr==0 } {incr i} {
  set datalen [expr int(rand()*20.0)]

  do_test btree8-1.$i.1 {
    btree_insert $::write_csr $i [string repeat x $datalen]
  } {}

................................................................................
  foreach csr $csr_list key $keys {
    incr testnum
    do_test btree8-1.$i.$testnum {
      btree_key $::csr
    } $key
  }
}

























btree_close_cursor $::write_csr
btree_commit $::bt
if {$::nErr>0} { puts $::csr_list }
foreach csr $csr_list {
  btree_close_cursor $csr
}
set csr_list [list]

# Transform the number $num into a string of length $len by repeating the
# string representation of the number as many times as necessary. Repeats
# are seperated by a '.' character. Eg:
#
# [num_to_string 456 10] -> "456.456.45"
#
proc num_to_string {num len} {

  return [string range [string repeat "$num." $len] 0 [expr $len-1]]
}

foreach key $keys {
  lappend skeys [num_to_string $key 20]
}

................................................................................
# the key is left pointing to it after the insert. Then save this cursor
# in the list $csr_list.
#
btree_begin_transaction $::bt
set testnum 0
foreach key $skeys {
  incr testnum 
  do_test btree-8-2.$testnum {
    set csr [btree_cursor $::bt $::inum 1]
    btree_insert $csr $key ""
    lappend csr_list $csr
    btree_key $csr
  } $key
}
btree_commit $::bt
................................................................................
# set btree_trace 1

# Now write more entries to the index (and overwrite the ones that exist).
# After each write, check that the cursors created above still point to the
# same entries.
btree_begin_transaction $::bt
set ::write_csr [btree_cursor $::bt $::inum 1]

for {set i $testnum} {$i < 5000 && $nErr==0 } {incr i} {
  set skey [num_to_string $i 20]

  do_test btree8-2.$i.1 {
    btree_insert $::write_csr $skey ""
  } {}

  set testnum 1
  foreach csr $csr_list key $skeys {
    incr testnum
    do_test btree8-2.$i.$testnum {
      btree_key $::csr
    } $key
  }
}



















































btree_close_cursor $::write_csr
btree_commit $::bt
if {$::nErr>0} { puts $::csr_list }
foreach csr $csr_list {
  btree_close_cursor $csr
}
set csr_list [list]

finish_test








|
>
>

|







 







<
<





>







 







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


|












>







 







|







 







>



|






|




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










5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
53
54
55
56
57
58
59


60
61
62
63
64
65
66
67
68
69
70
71
72
..
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
...
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
...
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#
#    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. Specifically,
# this file tests that existing cursors are correctly repositioned 
# when entries are inserted into or deleted from btrees.
#
# $Id: btree8.test,v 1.2 2004/11/16 04:57:25 danielk1977 Exp $

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

# Use the SQL interface to create a couple of btree tables, one using
# the flags for an SQL table, the other an SQL index.
# 
................................................................................
    lappend csr_list $csr
    btree_key $csr
  } $key
  incr testnum 
}
btree_commit $::bt



# Now write more entries to the table (and overwriting the ones that exist).
# After each write, check that the cursors created above still point to the
# same entries.
btree_begin_transaction $::bt
set ::write_csr [btree_cursor $::bt $::tnum 1]
set first_entry $testnum
for {set i $testnum} {$i < 5000 && $nErr==0 } {incr i} {
  set datalen [expr int(rand()*20.0)]

  do_test btree8-1.$i.1 {
    btree_insert $::write_csr $i [string repeat x $datalen]
  } {}

................................................................................
  foreach csr $csr_list key $keys {
    incr testnum
    do_test btree8-1.$i.$testnum {
      btree_key $::csr
    } $key
  }
}

# Now delete entries from the table.
btree_first $::write_csr
for {set i $first_entry} {$i < 5000 && $nErr==0 } {incr i} {

  do_test btree8-2.$i.1 {
    btree_key $::write_csr
  } $i
  do_test btree8-2.$i.2 {
    btree_delete $::write_csr
    btree_next $::write_csr
    expr 0
  } {0}
  set testnum 2
  foreach csr $csr_list key $keys {
    incr testnum
    if {$key <= $i } {
      set key 0
    }
    do_test btree8-2.$i.$testnum {
      btree_key $::csr
    } $key
  }
}

btree_close_cursor $::write_csr
btree_commit $::bt
if {$::nErr>0} { puts $::csr_list ; exit }
foreach csr $csr_list {
  btree_close_cursor $csr
}
set csr_list [list]

# Transform the number $num into a string of length $len by repeating the
# string representation of the number as many times as necessary. Repeats
# are seperated by a '.' character. Eg:
#
# [num_to_string 456 10] -> "456.456.45"
#
proc num_to_string {num len} {
  set num [format %.4d $num]
  return [string range [string repeat "$num." $len] 0 [expr $len-1]]
}

foreach key $keys {
  lappend skeys [num_to_string $key 20]
}

................................................................................
# the key is left pointing to it after the insert. Then save this cursor
# in the list $csr_list.
#
btree_begin_transaction $::bt
set testnum 0
foreach key $skeys {
  incr testnum 
  do_test btree-8-3.$testnum {
    set csr [btree_cursor $::bt $::inum 1]
    btree_insert $csr $key ""
    lappend csr_list $csr
    btree_key $csr
  } $key
}
btree_commit $::bt
................................................................................
# set btree_trace 1

# Now write more entries to the index (and overwrite the ones that exist).
# After each write, check that the cursors created above still point to the
# same entries.
btree_begin_transaction $::bt
set ::write_csr [btree_cursor $::bt $::inum 1]
set first_entry $testnum
for {set i $testnum} {$i < 5000 && $nErr==0 } {incr i} {
  set skey [num_to_string $i 20]

  do_test btree-8-3.$i.1 {
    btree_insert $::write_csr $skey ""
  } {}

  set testnum 1
  foreach csr $csr_list key $skeys {
    incr testnum
    do_test btree-8-3.$i.$testnum {
      btree_key $::csr
    } $key
  }
}
btree_commit $::bt
btree_begin_transaction $::bt

proc lremove {l key} {
  set idx [lsearch $l $key]
  return [concat [lrange $l 0 [expr $idx-1]] [lrange $l [expr $idx+1] end]]
}
proc K {x y} {set x}
proc lshuffle { list } {
    set n [llength $list]
    while {$n>0} {
        set j [expr {int(rand()*$n)}]
        lappend slist [lindex $list $j]
        set list [lreplace [K $list [set list {}]] $j $j]
        incr n -1
    }
    return $slist
}

# Now delete entries from the index. Do this in a random order, to try to
# ensure that internal and external nodes are deleted.
for {set i $first_entry} {$i < 5000} {incr i} {
  lappend delete_order $i
}
set delete_order [lshuffle $delete_order]

btree_first $::write_csr
foreach i $delete_order { 
  do_test btree8-4.$i.1 {
    btree_move_to $::write_csr [num_to_string $i 20]
    btree_key $::write_csr
  } [num_to_string $i 20]
  do_test btree8-4.$i.2 {
    btree_delete $::write_csr
  } {}

  set delete_order [lremove $delete_order $i]
  set testnum 2
  foreach csr $csr_list key $keys {
    incr testnum
    if { [lsearch $delete_order $key]==-1 } {
      set skey ""
    } else {
      set skey [num_to_string $key 20]
    }
    do_test btree8-4.$i.$testnum {
      btree_key $::csr
    } $skey
  }
}

btree_close_cursor $::write_csr
btree_commit $::bt
if {$::nErr>0} { puts $::csr_list }
foreach csr $csr_list {
  btree_close_cursor $csr
}
set csr_list [list]

finish_test