/ Check-in [91acd87e]
Login

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

Overview
Comment:Back out changes allowing writes to tables that have open cursors. (CVS 2133)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:91acd87e52509a8f78894d0f4b625b54376cac21
User & Date: danielk1977 2004-11-22 10:02:10
Context
2004-11-22
10:02
Back out changes allowing writes to tables that have open cursors. (CVS 2134) check-in: af635cab user: danielk1977 tags: trunk
10:02
Back out changes allowing writes to tables that have open cursors. (CVS 2133) check-in: 91acd87e user: danielk1977 tags: trunk
08:43
Modify test suite to work when SQLITE_OMIT_VIEW is defined. (CVS 2132) check-in: 711e8d76 user: danielk1977 tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
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
....
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
....
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
....
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
....
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
....
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
....
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
....
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
....
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
....
3652
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
....
3900
3901
3902
3903
3904
3905
3906










3907
3908
3909
3910
3911
3912
3913
....
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
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979
3980
3981
3982
3983
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
4011
4012
4013
4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029
4030
4031
4032
4033
4034
4035
4036
4037
4038
4039
4040
4041
4042
4043
4044
4045
4046
4047
....
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
4212
4213
4214
4215
4216
4217
4218
4219
4220
4221
4222
4223
4224
4225
4226
4227
4228
4229
4230
4231
4232
4233
4234
4235
4236
....
4253
4254
4255
4256
4257
4258
4259
4260
4261
4262
4263
4264
4265
4266
4267
....
4280
4281
4282
4283
4284
4285
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300
4301
4302
4303
4304
4305
4306
4307
4308
....
4327
4328
4329
4330
4331
4332
4333








4334
4335








4336
4337
4338
4339
4340
4341
4342
....
4353
4354
4355
4356
4357
4358
4359
4360
4361
4362
4363
4364
4365
4366
4367
....
4405
4406
4407
4408
4409
4410
4411
4412
4413
4414
4415
4416
4417
4418
4419
4420
4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435



4436
4437
4438
4439
4440
4441
4442
....
4444
4445
4446
4447
4448
4449
4450
4451
4452
4453
4454
4455
4456
4457
4458
4459
....
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
4623
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
4634
4635
4636
4637
4638
4639
4640
4641
4642
4643

4644
4645
4646
4647
4648
4649
4650
** 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.222 2004/11/22 05:26:27 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.
*/
................................................................................
  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);
................................................................................
  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;
................................................................................
  u8 *apDiv[NB];               /* Divider cells in pParent */
  int cntNew[NB+2];            /* Index in aCell[] of cell after i-th page */
  int szNew[NB+2];             /* Combined size of cells place on i-th page */
  u8 **apCell;                 /* All cells begin balanced */
  int *szCell;                 /* Local size of all cells in apCell[] */
  u8 *aCopy[NB];               /* Space for holding data of apCopy[] */
  u8 *aSpace;                  /* Space to hold copies of dividers cells */
  BtCursor *pCur;

  /* 
  ** Find the parent page.
  */
  assert( pPage->isInit );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
................................................................................
      rc = allocatePage(pBt, &pNew, &pgnoNew[i], pgnoNew[i-1], 0);
      if( rc ) goto balance_cleanup;
      apNew[i] = pNew;
    }
    nNew++;
    zeroPage(pNew, pageFlags);
  }











  /*
  ** Put the new pages in accending order.  This helps to
  ** keep entries in the disk file in order so that a scan
  ** of the table is a linear scan through the file.  That
  ** in turn helps the operating system to deliver pages
  ** from the disk more rapidly.
................................................................................
    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;
    Pgno pgno = pCur->pPage->pgno;

    /* If the cursor is not valid, do not do anything with it. */
    if( !pCur->isValid ) continue;

    /* If the cursor pointed to one of the cells moved around during the
    ** balancing, then set variable iCell to the index of the cell in apCell.
    ** This is used by the block below to figure out where the cell was
    ** moved to, and adjust the cursor appropriately.
    **
    ** If the cursor points to the parent page, but the cell was not involved
    ** in the balance, then declare the cache of the cell-parse invalid, as a
    ** defragmentation may of occured during  the balance. Also, if the index
    ** of the cell is greater than that of the divider cells, then it may
    ** need to be adjusted (in case there are now more or less divider cells
    ** than there were before the balancing).
    */
    for(i=0; iCell<0 && i<nOld; i++){
      if( pgno==apCopy[i]->pgno ){
        iCell = nCellCnt + pCur->idx;
        break;
      }
      nCellCnt += (apCopy[i]->nCell + apCopy[i]->nOverflow) + (leafData?0:1);
    }
    if( pgno==pParent->pgno ){
      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 is greater than or equal to zero, then pCur points at a
    ** cell that was moved around during the balance. Figure out where
    ** the cell was moved to and adjust pCur to match.
    */
    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]. */
        idxNew = iCell-(x>0?cntNew[x-1]:0)-((leafData||x==0)?0:1);
        pgnoNew = apNew[x]->pgno;
      }

      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 = freePage(apOld[i]);
    if( rc ) goto balance_cleanup;
    releasePage(apOld[i]);
    apOld[i] = 0;
  }

  /*
  ** Evenly distribute the data in apCell[] across the new pages.
  ** Insert divider cells into pParent as necessary.
  */
  j = 0;
  for(i=0; i<nNew; i++){
    MemPage *pNew = apNew[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);
................................................................................
  Pgno pgnoChild;     /* Page number of the new child page */
  Btree *pBt;         /* The BTree */
  int usableSize;     /* Total usable size of a page */
  u8 *data;           /* Content of the parent page */
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int brk;            /* Offset to content of first cell in parent */
  BtCursor *pCur;

  assert( pPage->pParent==0 );
  assert( pPage->nOverflow>0 );
  pBt = pPage->pBt;
  rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0);
  if( rc ) return rc;
  assert( sqlite3pager_iswriteable(pChild->aData) );
................................................................................
  if( pChild->nOverflow ){
    pChild->nFree = 0;
  }
  assert( pChild->nCell==pPage->nCell );
  zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
  put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild);
  TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, 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==pPage ){
      TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
          pCur, pPage->pgno, pCur->idx, pChild->pgno, pCur->idx));
      releasePage(pCur->pPage);
      rc = getPage(pBt, pChild->pgno,  &pCur->pPage);
      assert( rc==SQLITE_OK );
    }
  }

  rc = balance_nonroot(pChild);
  releasePage(pChild);
  return rc;
}

/*
** Decide if the page pPage needs to be balanced.  If balancing is
................................................................................

/*
** 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){








  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
** define what table the record should be inserted into.  The cursor
................................................................................
  int rc;
  int loc;
  int szNew;
  MemPage *pPage;
  Btree *pBt = pCur->pBt;
  unsigned char *oldCell;
  unsigned char *newCell = 0;
  BtCursor *pCur2;

  if( pCur->status ){
    return pCur->status;  /* A rollback destroyed this cursor */
  }
  if( pBt->inTrans!=TRANS_WRITE ){
    /* Must start a transaction before doing an insert */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
................................................................................
    assert( pPage->leaf );
    pCur->idx++;
    pCur->info.nSize = 0;
  }else{
    assert( pPage->leaf );
  }
  rc = insertCell(pPage, pCur->idx, newCell, szNew, 0);
  pCur->isValid = 1;

  /* If there are other cursors pointing at this page with a BtCursor.idx
  ** field greater than or equal to 'i', then the cell they refer to
  ** has been modified or moved within the page. Fix the cursor.
  */
  for(pCur2=pPage->pBt->pCursor; pCur2; pCur2 = pCur2->pNext){
    if( pCur2->pPage==pPage ){
      if( pCur2->idx>=pCur->idx && pCur!=pCur2 && loc!=0 ){
	/* The cell pointed to by pCur2 was shifted one to the right on it's
	** page by this Insert(). 
        */
        TRACE(("INSERT: 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;
    }
  }

  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 */
................................................................................
  }
  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;

    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,%d replace "
        "from leaf %d,%d\n", pCur->pgnoRoot, pPage->pgno, idx, 
        leafCur.pPage->pgno, leafCur.idx));

    /* 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().
    **
    ** Also, any cursors that point to the internal page have their
    ** cached parses invalidated, as the insertCell() above may have 
    ** caused a defragmation.
    */
    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;
      }
      if( pCur2->pPage==pPage ){
        pCur2->info.nSize = 0;
      }
    }

    /* 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, 
            leafCur.pPage->pgno,pCur2->idx,leafCur.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.
**







|







 







<
<
<
<
<
<
<
<
<
<













<







 







<







 







|







 







|







 







|







 







|







 







<







 







<
<
<
<
<
<
<
<
<







 







<
<
<
<
<
<
<
<
<







 







<







 







>
>
>
>
>
>
>
>
>
>







 







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







 







<








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






<








<
<
<
<
<
<
<
<
<







 







<







 







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







 







>
>
>
>
>
>
>
>


>
>
>
>
>
>
>
>







 







<







 







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




>
>
>







 







<
<







 







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




|











|
<




>


<
<
<
<
<
<

>




|


|
|
|
<
<
<
<
<
<
<
|




|
<
<
<
|
|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<


|

<
<
<
<
<
<
<
<
<
<



|
|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<


<
<
<
>







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
....
2110
2111
2112
2113
2114
2115
2116

2117
2118
2119
2120
2121
2122
2123
....
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
....
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
....
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
....
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
....
2543
2544
2545
2546
2547
2548
2549

2550
2551
2552
2553
2554
2555
2556
....
2780
2781
2782
2783
2784
2785
2786









2787
2788
2789
2790
2791
2792
2793
....
2830
2831
2832
2833
2834
2835
2836









2837
2838
2839
2840
2841
2842
2843
....
3621
3622
3623
3624
3625
3626
3627

3628
3629
3630
3631
3632
3633
3634
....
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
....
3923
3924
3925
3926
3927
3928
3929

























































































3930
3931
3932
3933
3934
3935
3936
....
4066
4067
4068
4069
4070
4071
4072

4073
4074
4075
4076
4077
4078
4079
4080













4081
4082
4083
4084
4085
4086

4087
4088
4089
4090
4091
4092
4093
4094









4095
4096
4097
4098
4099
4100
4101
....
4118
4119
4120
4121
4122
4123
4124

4125
4126
4127
4128
4129
4130
4131
....
4144
4145
4146
4147
4148
4149
4150















4151
4152
4153
4154
4155
4156
4157
....
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
....
4218
4219
4220
4221
4222
4223
4224

4225
4226
4227
4228
4229
4230
4231
....
4269
4270
4271
4272
4273
4274
4275




















4276
4277
4278
4279
4280
4281
4282
4283
4284
4285
4286
4287
4288
4289
....
4291
4292
4293
4294
4295
4296
4297


4298
4299
4300
4301
4302
4303
4304
....
4313
4314
4315
4316
4317
4318
4319







































4320
4321
4322
4323
4324
4325
4326
4327
4328
4329
4330
4331
4332
4333
4334
4335
4336

4337
4338
4339
4340
4341
4342
4343






4344
4345
4346
4347
4348
4349
4350
4351
4352
4353
4354
4355







4356
4357
4358
4359
4360
4361



4362
4363
4364































4365
4366
4367
4368










4369
4370
4371
4372
4373
4374














4375
4376



4377
4378
4379
4380
4381
4382
4383
4384
** 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.223 2004/11/22 10:02:10 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 ){
    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.
*/
................................................................................
  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);
................................................................................
  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;
................................................................................
  u8 *apDiv[NB];               /* Divider cells in pParent */
  int cntNew[NB+2];            /* Index in aCell[] of cell after i-th page */
  int szNew[NB+2];             /* Combined size of cells place on i-th page */
  u8 **apCell;                 /* All cells begin balanced */
  int *szCell;                 /* Local size of all cells in apCell[] */
  u8 *aCopy[NB];               /* Space for holding data of apCopy[] */
  u8 *aSpace;                  /* Space to hold copies of dividers cells */


  /* 
  ** Find the parent page.
  */
  assert( pPage->isInit );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
................................................................................
      rc = allocatePage(pBt, &pNew, &pgnoNew[i], pgnoNew[i-1], 0);
      if( rc ) goto balance_cleanup;
      apNew[i] = pNew;
    }
    nNew++;
    zeroPage(pNew, pageFlags);
  }

  /* Free any old pages that were not reused as new pages.
  */
  while( i<nOld ){
    rc = freePage(apOld[i]);
    if( rc ) goto balance_cleanup;
    releasePage(apOld[i]);
    apOld[i] = 0;
    i++;
  }

  /*
  ** Put the new pages in accending order.  This helps to
  ** keep entries in the disk file in order so that a scan
  ** of the table is a linear scan through the file.  That
  ** in turn helps the operating system to deliver pages
  ** from the disk more rapidly.
................................................................................
    nOld>=3 ? pgnoOld[2] : 0,
    pgnoNew[0], szNew[0],
    nNew>=2 ? pgnoNew[1] : 0, nNew>=2 ? szNew[1] : 0,
    nNew>=3 ? pgnoNew[2] : 0, nNew>=3 ? szNew[2] : 0,
    nNew>=4 ? pgnoNew[3] : 0, nNew>=4 ? szNew[3] : 0,
    nNew>=5 ? pgnoNew[4] : 0, nNew>=5 ? szNew[4] : 0));


























































































  /*
  ** Evenly distribute the data in apCell[] across the new pages.
  ** Insert divider cells into pParent as necessary.
  */
  j = 0;
  for(i=0; i<nNew; i++){
    MemPage *pNew = apNew[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);
................................................................................
  Pgno pgnoChild;     /* Page number of the new child page */
  Btree *pBt;         /* The BTree */
  int usableSize;     /* Total usable size of a page */
  u8 *data;           /* Content of the parent page */
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int brk;            /* Offset to content of first cell in parent */


  assert( pPage->pParent==0 );
  assert( pPage->nOverflow>0 );
  pBt = pPage->pBt;
  rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0);
  if( rc ) return rc;
  assert( sqlite3pager_iswriteable(pChild->aData) );
................................................................................
  if( pChild->nOverflow ){
    pChild->nFree = 0;
  }
  assert( pChild->nCell==pPage->nCell );
  zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
  put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild);
  TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, pChild->pgno));















  rc = balance_nonroot(pChild);
  releasePage(pChild);
  return rc;
}

/*
** Decide if the page pPage needs to be balanced.  If balancing is
................................................................................

/*
** 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
** define what table the record should be inserted into.  The cursor
................................................................................
  int rc;
  int loc;
  int szNew;
  MemPage *pPage;
  Btree *pBt = pCur->pBt;
  unsigned char *oldCell;
  unsigned char *newCell = 0;


  if( pCur->status ){
    return pCur->status;  /* A rollback destroyed this cursor */
  }
  if( pBt->inTrans!=TRANS_WRITE ){
    /* Must start a transaction before doing an insert */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
................................................................................
    assert( pPage->leaf );
    pCur->idx++;
    pCur->info.nSize = 0;
  }else{
    assert( pPage->leaf );
  }
  rc = insertCell(pPage, pCur->idx, newCell, szNew, 0);




















  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 */
................................................................................
  }
  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);































    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));














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

Changes to src/delete.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
59
60
61
62
63
64
65

66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
...
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
...
226
227
228
229
230
231
232
















233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250


251
252
253


254
255






256
257
258




259
260
261
262
263
264
265




266
267





268
269
270


271
272


273

274






275
276
277
278
279
280
281





282
283


284
285
286
287
288
289
290
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle DELETE FROM statements.
**
** $Id: delete.c,v 1.89 2004/11/16 15:50:20 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** Look up every table that is named in pSrc.  If any table is not found,
** add an error message to pParse->zErrMsg and return NULL.  If all tables
** are found, return a pointer to the last table.
................................................................................
  Table *pTab     /* The table to be opened */
){
  sqlite3VdbeAddOp(v, OP_Integer, pTab->iDb, 0);
  sqlite3VdbeAddOp(v, OP_OpenRead, iCur, pTab->tnum);
  VdbeComment((v, "# %s", pTab->zName));
  sqlite3VdbeAddOp(v, OP_SetNumColumns, iCur, pTab->nCol);
}


/*
** Process a DELETE FROM statement.
*/
void sqlite3DeleteFrom(
  Parse *pParse,         /* The parser context */
  SrcList *pTabList,     /* The table from which we should delete things */
  Expr *pWhere           /* The WHERE clause.  May be null */
){
  Vdbe *v;               /* The virtual database engine */
  Table *pTab;           /* The table from which records will be deleted */
  const char *zDb;       /* Name of database holding pTab */
  int addr = 0;          /* A couple addresses of generated code */
  int i;                 /* Loop counter */
  WhereInfo *pWInfo;     /* Information about the WHERE clause */
  Index *pIdx;           /* For looping over indices of the table */
  int iCur;              /* VDBE Cursor number for pTab */
  sqlite3 *db;           /* Main database structure */
  AuthContext sContext;  /* Authorization context */
  int oldIdx = -1;       /* Cursor for the OLD table of AFTER triggers */
................................................................................

  /* Allocate a cursor used to store the old.* data for a trigger.
  */
  if( row_triggers_exist ){ 
    oldIdx = pParse->nTab++;
  }

  /* Resolve the column names in all the expressions. Allocate cursors
  ** for the table and indices first, in case an expression needs to use
  ** a cursor (e.g. an IN() expression).
  */
  assert( pTabList->nSrc==1 );
  iCur = pTabList->a[0].iCursor = pParse->nTab++;
  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
    pParse->nTab++;
  }
  if( sqlite3ExprResolveAndCheck(pParse, pTabList, 0, pWhere, 0, 0) ){
    goto delete_from_cleanup;
  }

  /* Start the view context
  */
  if( isView ){
................................................................................
  else{
    /* Ensure all required collation sequences are available. */
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      if( sqlite3CheckIndexCollSeq(pParse, pIdx) ){
        goto delete_from_cleanup;
      }
    }

















    /* Open the pseudo-table used to store OLD if there are triggers.
    */
    if( row_triggers_exist ){
      sqlite3VdbeAddOp(v, OP_OpenPseudo, oldIdx, 0);
      sqlite3VdbeAddOp(v, OP_SetNumColumns, oldIdx, pTab->nCol);
    }

    /* Open cursors for the table and indices we are deleting from. */
    if( !isView ){
      sqlite3OpenTableAndIndices(pParse, pTab, iCur, OP_OpenWrite);
    }

    /* Begin the database scan
    */
    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 0, isView?0:iCur);
    if( pWInfo==0 ) goto delete_from_cleanup;
    addr = pWInfo->iContinue;



    /* If row-triggers exist, copy the record being deleted into the
    ** oldIdx psuedo-table. Then invoke the BEFORE triggers.


    */
    if( row_triggers_exist ){






      sqlite3VdbeAddOp(v, OP_Recno, iCur, 0);
      sqlite3VdbeAddOp(v, OP_RowData, iCur, 0);
      sqlite3VdbeAddOp(v, OP_PutIntKey, oldIdx, 0);




      (void)sqlite3CodeRowTrigger(pParse, TK_DELETE, 0, TK_BEFORE, pTab, -1, 
          oldIdx, (pParse->trigStack)?pParse->trigStack->orconf:OE_Default,
	  addr);
    }

    /* Delete the row. Increment the callback value if the count-rows flag 
    ** is set. 




    */
    if( db->flags & SQLITE_CountRows ){





      sqlite3VdbeAddOp(v, OP_AddImm, 1, 0);
    }
    sqlite3VdbeAddOp(v, OP_Recno, iCur, 0);


    sqlite3GenerateRowDelete(db, v, pTab, iCur, pParse->nested==0);



    /* Code the AFTER triggers.  */

    if( row_triggers_exist ){






      (void)sqlite3CodeRowTrigger(pParse, TK_DELETE, 0, TK_AFTER, pTab, -1, 
          oldIdx, (pParse->trigStack)?pParse->trigStack->orconf:OE_Default,
	  addr);
    }

    /* End the database scan loop and close indices. */
    sqlite3WhereEnd(pWInfo);





    for(i=1, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
      sqlite3VdbeAddOp(v, OP_Close, iCur + i, pIdx->tnum);


    }
  }

  /*
  ** Return the number of rows that were deleted. If this routine is 
  ** generating code because of a call to sqlite3NestedParse(), do not
  ** invoke the callback function.







|







 







>












|







 







|
<
<



<
<
<







 







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








|
|
|
<
<
<

<
<
<
>
>

<
<
>
>


>
>
>
>
>
>



>
>
>
>





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

>
>
>
>
>
>





|
|
>
>
>
>
>
|
|
>
>







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
...
146
147
148
149
150
151
152
153


154
155
156



157
158
159
160
161
162
163
...
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255



256



257
258
259


260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
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
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle DELETE FROM statements.
**
** $Id: delete.c,v 1.90 2004/11/22 10:02:10 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** Look up every table that is named in pSrc.  If any table is not found,
** add an error message to pParse->zErrMsg and return NULL.  If all tables
** are found, return a pointer to the last table.
................................................................................
  Table *pTab     /* The table to be opened */
){
  sqlite3VdbeAddOp(v, OP_Integer, pTab->iDb, 0);
  sqlite3VdbeAddOp(v, OP_OpenRead, iCur, pTab->tnum);
  VdbeComment((v, "# %s", pTab->zName));
  sqlite3VdbeAddOp(v, OP_SetNumColumns, iCur, pTab->nCol);
}


/*
** Process a DELETE FROM statement.
*/
void sqlite3DeleteFrom(
  Parse *pParse,         /* The parser context */
  SrcList *pTabList,     /* The table from which we should delete things */
  Expr *pWhere           /* The WHERE clause.  May be null */
){
  Vdbe *v;               /* The virtual database engine */
  Table *pTab;           /* The table from which records will be deleted */
  const char *zDb;       /* Name of database holding pTab */
  int end, addr = 0;     /* A couple addresses of generated code */
  int i;                 /* Loop counter */
  WhereInfo *pWInfo;     /* Information about the WHERE clause */
  Index *pIdx;           /* For looping over indices of the table */
  int iCur;              /* VDBE Cursor number for pTab */
  sqlite3 *db;           /* Main database structure */
  AuthContext sContext;  /* Authorization context */
  int oldIdx = -1;       /* Cursor for the OLD table of AFTER triggers */
................................................................................

  /* Allocate a cursor used to store the old.* data for a trigger.
  */
  if( row_triggers_exist ){ 
    oldIdx = pParse->nTab++;
  }

  /* Resolve the column names in all the expressions.


  */
  assert( pTabList->nSrc==1 );
  iCur = pTabList->a[0].iCursor = pParse->nTab++;



  if( sqlite3ExprResolveAndCheck(pParse, pTabList, 0, pWhere, 0, 0) ){
    goto delete_from_cleanup;
  }

  /* Start the view context
  */
  if( isView ){
................................................................................
  else{
    /* Ensure all required collation sequences are available. */
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      if( sqlite3CheckIndexCollSeq(pParse, pIdx) ){
        goto delete_from_cleanup;
      }
    }

    /* Begin the database scan
    */
    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 1, 0);
    if( pWInfo==0 ) goto delete_from_cleanup;

    /* Remember the key of every item to be deleted.
    */
    sqlite3VdbeAddOp(v, OP_ListWrite, 0, 0);
    if( db->flags & SQLITE_CountRows ){
      sqlite3VdbeAddOp(v, OP_AddImm, 1, 0);
    }

    /* End the database scan loop.
    */
    sqlite3WhereEnd(pWInfo);

    /* Open the pseudo-table used to store OLD if there are triggers.
    */
    if( row_triggers_exist ){
      sqlite3VdbeAddOp(v, OP_OpenPseudo, oldIdx, 0);
      sqlite3VdbeAddOp(v, OP_SetNumColumns, oldIdx, pTab->nCol);
    }

    /* Delete every item whose key was written to the list during the
    ** database scan.  We have to delete items after the scan is complete
    ** because deleting an item can change the scan order.



    */



    sqlite3VdbeAddOp(v, OP_ListRewind, 0, 0);
    end = sqlite3VdbeMakeLabel(v);



    /* This is the beginning of the delete loop when there are
    ** row triggers.
    */
    if( row_triggers_exist ){
      addr = sqlite3VdbeAddOp(v, OP_ListRead, 0, end);
      sqlite3VdbeAddOp(v, OP_Dup, 0, 0);
      if( !isView ){
        sqlite3OpenTableForReading(v, iCur, pTab);
      }
      sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
      sqlite3VdbeAddOp(v, OP_Recno, iCur, 0);
      sqlite3VdbeAddOp(v, OP_RowData, iCur, 0);
      sqlite3VdbeAddOp(v, OP_PutIntKey, oldIdx, 0);
      if( !isView ){
        sqlite3VdbeAddOp(v, OP_Close, iCur, 0);
      }

      (void)sqlite3CodeRowTrigger(pParse, TK_DELETE, 0, TK_BEFORE, pTab, -1, 
          oldIdx, (pParse->trigStack)?pParse->trigStack->orconf:OE_Default,
	  addr);
    }

    if( !isView ){
      /* Open cursors for the table we are deleting from and all its
      ** indices.  If there are row triggers, this happens inside the
      ** OP_ListRead loop because the cursor have to all be closed
      ** before the trigger fires.  If there are no row triggers, the
      ** cursors are opened only once on the outside the loop.
      */

      sqlite3OpenTableAndIndices(pParse, pTab, iCur, OP_OpenWrite);

      /* This is the beginning of the delete loop when there are no
      ** row triggers */
      if( !row_triggers_exist ){ 
        addr = sqlite3VdbeAddOp(v, OP_ListRead, 0, end);
      }


      /* Delete the row */
      sqlite3GenerateRowDelete(db, v, pTab, iCur, pParse->nested==0);
    }

    /* If there are row triggers, close all cursors then invoke
    ** the AFTER triggers
    */
    if( row_triggers_exist ){
      if( !isView ){
        for(i=1, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
          sqlite3VdbeAddOp(v, OP_Close, iCur + i, pIdx->tnum);
        }
        sqlite3VdbeAddOp(v, OP_Close, iCur, 0);
      }
      (void)sqlite3CodeRowTrigger(pParse, TK_DELETE, 0, TK_AFTER, pTab, -1, 
          oldIdx, (pParse->trigStack)?pParse->trigStack->orconf:OE_Default,
	  addr);
    }

    /* End of the delete loop */
    sqlite3VdbeAddOp(v, OP_Goto, 0, addr);
    sqlite3VdbeResolveLabel(v, end);
    sqlite3VdbeAddOp(v, OP_ListReset, 0, 0);

    /* Close the cursors after the loop if there are no row triggers */
    if( !row_triggers_exist ){
      for(i=1, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
        sqlite3VdbeAddOp(v, OP_Close, iCur + i, pIdx->tnum);
      }
      sqlite3VdbeAddOp(v, OP_Close, iCur, 0);
    }
  }

  /*
  ** Return the number of rows that were deleted. If this routine is 
  ** generating code because of a call to sqlite3NestedParse(), do not
  ** invoke the callback function.

Changes to src/select.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.214 2004/11/16 15:50:20 danielk1977 Exp $
*/
#include "sqliteInt.h"


/*
** Allocate a new Select structure and return a pointer to that
** structure.
................................................................................
  }else{
    distinct = -1;
  }

  /* Begin the database scan
  */
  pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 
                            pGroupBy ? 0 : &pOrderBy, -1);
  if( pWInfo==0 ) goto select_end;

  /* Use the standard inner loop if we are not dealing with
  ** aggregates
  */
  if( !isAgg ){
    if( selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, distinct, eDest,







|







 







|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.215 2004/11/22 10:02:11 danielk1977 Exp $
*/
#include "sqliteInt.h"


/*
** Allocate a new Select structure and return a pointer to that
** structure.
................................................................................
  }else{
    distinct = -1;
  }

  /* Begin the database scan
  */
  pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 
                            pGroupBy ? 0 : &pOrderBy);
  if( pWInfo==0 ) goto select_end;

  /* Use the standard inner loop if we are not dealing with
  ** aggregates
  */
  if( !isAgg ){
    if( selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, distinct, eDest,

Changes to src/sqliteInt.h.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
**    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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.341 2004/11/20 19:18:01 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** These #defines should enable >2GB file support on Posix if the
** underlying operating system supports it.  If the OS lacks
................................................................................
Select *sqlite3SelectNew(ExprList*,SrcList*,Expr*,ExprList*,Expr*,ExprList*,
                        int,int,int);
void sqlite3SelectDelete(Select*);
void sqlite3SelectUnbind(Select*);
Table *sqlite3SrcListLookup(Parse*, SrcList*);
int sqlite3IsReadOnly(Parse*, Table*, int);
void sqlite3OpenTableForReading(Vdbe*, int iCur, Table*);
void sqlite3OpenTable(Vdbe*, int iCur, Table*, int);
void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
WhereInfo *sqlite3WhereBegin(Parse*, SrcList*, Expr*, int, ExprList**, int);
void sqlite3WhereEnd(WhereInfo*);
void sqlite3ExprCode(Parse*, Expr*);
int sqlite3ExprCodeExprList(Parse*, ExprList*);
void sqlite3ExprIfTrue(Parse*, Expr*, int, int);
void sqlite3ExprIfFalse(Parse*, Expr*, int, int);
void sqlite3NextedParse(Parse*, const char*, ...);
Table *sqlite3FindTable(sqlite3*,const char*, const char*);







|







 







<


|







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1310
1311
1312
1313
1314
1315
1316

1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
**    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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.342 2004/11/22 10:02:11 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** These #defines should enable >2GB file support on Posix if the
** underlying operating system supports it.  If the OS lacks
................................................................................
Select *sqlite3SelectNew(ExprList*,SrcList*,Expr*,ExprList*,Expr*,ExprList*,
                        int,int,int);
void sqlite3SelectDelete(Select*);
void sqlite3SelectUnbind(Select*);
Table *sqlite3SrcListLookup(Parse*, SrcList*);
int sqlite3IsReadOnly(Parse*, Table*, int);
void sqlite3OpenTableForReading(Vdbe*, int iCur, Table*);

void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
WhereInfo *sqlite3WhereBegin(Parse*, SrcList*, Expr*, int, ExprList**);
void sqlite3WhereEnd(WhereInfo*);
void sqlite3ExprCode(Parse*, Expr*);
int sqlite3ExprCodeExprList(Parse*, ExprList*);
void sqlite3ExprIfTrue(Parse*, Expr*, int, int);
void sqlite3ExprIfFalse(Parse*, Expr*, int, int);
void sqlite3NextedParse(Parse*, const char*, ...);
Table *sqlite3FindTable(sqlite3*,const char*, const char*);

Changes to src/update.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle UPDATE statements.
**
** $Id: update.c,v 1.95 2004/11/16 15:50:20 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** Process an UPDATE statement.
**
**   UPDATE OR IGNORE table_wxyz SET a=b, c=d WHERE e<5 AND f NOT NULL;
................................................................................
    pView = sqlite3SelectDup(pTab->pSelect);
    sqlite3Select(pParse, pView, SRT_TempTable, iCur, 0, 0, 0, 0);
    sqlite3SelectDelete(pView);
  }

  /* Begin the database scan
  */
  pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 1, 0, -1);
  if( pWInfo==0 ) goto update_cleanup;

  /* Remember the index of every item to be updated.
  */
  sqlite3VdbeAddOp(v, OP_ListWrite, 0, 0);

  /* End the database scan loop.







|







 







|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle UPDATE statements.
**
** $Id: update.c,v 1.96 2004/11/22 10:02:11 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** Process an UPDATE statement.
**
**   UPDATE OR IGNORE table_wxyz SET a=b, c=d WHERE e<5 AND f NOT NULL;
................................................................................
    pView = sqlite3SelectDup(pTab->pSelect);
    sqlite3Select(pParse, pView, SRT_TempTable, iCur, 0, 0, 0, 0);
    sqlite3SelectDelete(pView);
  }

  /* Begin the database scan
  */
  pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 1, 0);
  if( pWInfo==0 ) goto update_cleanup;

  /* Remember the index of every item to be updated.
  */
  sqlite3VdbeAddOp(v, OP_ListWrite, 0, 0);

  /* End the database scan loop.

Changes to src/where.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
...
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.
**
** $Id: where.c,v 1.117 2004/11/16 15:50:20 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.
................................................................................
** one.
*/
WhereInfo *sqlite3WhereBegin(
  Parse *pParse,        /* The parser context */
  SrcList *pTabList,    /* A list of all tables to be scanned */
  Expr *pWhere,         /* The WHERE clause */
  int pushKey,          /* If TRUE, leave the table key on the stack */
  ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
  int iTabCur           /* Cursor for pTabList->aSrc[0] */
){
  int i;                     /* Loop counter */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  int brk, cont = 0;         /* Addresses used during code generation */
  int nExpr;           /* Number of subexpressions in the WHERE clause */
  int loopMask;        /* One bit set for each outer loop */
................................................................................
  sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  for(i=0; i<pTabList->nSrc; i++){
    Table *pTab;
    Index *pIx;

    pTab = pTabList->a[i].pTab;
    if( pTab->isTransient || pTab->pSelect ) continue;
    if( i>0 || iTabCur<0 ){
      sqlite3OpenTableForReading(v, pTabList->a[i].iCursor, pTab);
    }
    sqlite3CodeVerifySchema(pParse, pTab->iDb);
    if( (pIx = pWInfo->a[i].pIdx)!=0 ){
      sqlite3VdbeAddOp(v, OP_Integer, pIx->iDb, 0);
      sqlite3VdbeOp3(v, OP_OpenRead, pWInfo->a[i].iCur, pIx->tnum,
                     (char*)&pIx->keyInfo, P3_KEYINFO);
    }
  }







|







 







|
<







 







<
|
<







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
477
478
479
480
481
482
483
484

485
486
487
488
489
490
491
...
773
774
775
776
777
778
779

780

781
782
783
784
785
786
787
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.
**
** $Id: where.c,v 1.118 2004/11/22 10:02:20 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.
................................................................................
** one.
*/
WhereInfo *sqlite3WhereBegin(
  Parse *pParse,        /* The parser context */
  SrcList *pTabList,    /* A list of all tables to be scanned */
  Expr *pWhere,         /* The WHERE clause */
  int pushKey,          /* If TRUE, leave the table key on the stack */
  ExprList **ppOrderBy  /* An ORDER BY clause, or NULL */

){
  int i;                     /* Loop counter */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  int brk, cont = 0;         /* Addresses used during code generation */
  int nExpr;           /* Number of subexpressions in the WHERE clause */
  int loopMask;        /* One bit set for each outer loop */
................................................................................
  sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  for(i=0; i<pTabList->nSrc; i++){
    Table *pTab;
    Index *pIx;

    pTab = pTabList->a[i].pTab;
    if( pTab->isTransient || pTab->pSelect ) continue;

    sqlite3OpenTableForReading(v, pTabList->a[i].iCursor, pTab);

    sqlite3CodeVerifySchema(pParse, pTab->iDb);
    if( (pIx = pWInfo->a[i].pIdx)!=0 ){
      sqlite3VdbeAddOp(v, OP_Integer, pIx->iDb, 0);
      sqlite3VdbeOp3(v, OP_OpenRead, pWInfo->a[i].iCur, pIx->tnum,
                     (char*)&pIx->keyInfo, P3_KEYINFO);
    }
  }