/ Check-in [0eee3b5c]
Login

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

Overview
Comment:Changes to btree for the new file format are mostly complete. Still need to test and debug. (CVS 1311)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:0eee3b5cd400e9548437632ec1dfe625a3fca9cf
User & Date: drh 2004-05-02 21:12:19
Context
2004-05-03
19:49
Incremental btree.c changes. (CVS 1312) check-in: fdc629db user: drh tags: trunk
2004-05-02
21:12
Changes to btree for the new file format are mostly complete. Still need to test and debug. (CVS 1311) check-in: 0eee3b5c user: drh tags: trunk
2004-04-29
14:42
Sync all version 3 changes. (CVS 1309) check-in: 51892d6c 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
...
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
...
190
191
192
193
194
195
196

197
198
199
200
201
202
203
...
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
...
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
...
531
532
533
534
535
536
537




















538
539
540
541
542
543
544
...
596
597
598
599
600
601
602















603
604
605
606
607
608
609
...
618
619
620
621
622
623
624


625

626
627
628
629
630
631

632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
...
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
...
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
...
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
....
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
....
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
....
1408
1409
1410
1411
1412
1413
1414
1415






1416
1417
1418
1419
1420
1421
1422
....
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
....
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
....
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094

2095
2096
2097
2098
2099
2100
2101
2102
2103
2104

2105

2106
2107
2108
2109
2110
2111
2112
2113
2114
2115





2116
2117
2118
2119
2120
2121
2122
....
2149
2150
2151
2152
2153
2154
2155
2156
2157

2158
2159
2160
2161

2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174


2175
2176
2177
2178
2179
2180
2181
2182
2183



2184
2185

2186
2187

2188
2189
2190
2191
2192
2193
2194
....
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209


2210
2211
2212
2213
2214
2215
2216
2217
2218
....
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235

2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260

2261
2262

2263
2264
2265
2266
2267

2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279






2280
2281

2282
2283


2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
....
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353

2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367

2368
2369
2370
2371
2372
2373
2374
2375
2376
2377

2378
2379
2380
2381
2382
2383

2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
....
2403
2404
2405
2406
2407
2408
2409

2410

2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422







2423

2424




2425
2426
2427


2428
2429
2430
2431
2432
2433
2434
2435

2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
....
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487

2488
2489
2490
2491
2492
2493
2494
2495

2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
....
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527

2528
2529

2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571



2572
2573
2574
2575
2576
2577
2578







2579
2580

2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594







2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608

2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633


2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
....
2694
2695
2696
2697
2698
2699
2700


2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714




2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
....
2798
2799
2800
2801
2802
2803
2804
2805



2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817

2818
2819
2820
2821
2822
2823
2824
....
2829
2830
2831
2832
2833
2834
2835

2836
2837
2838
2839
2840
2841
2842
2843






2844
2845
2846

2847
2848

2849
2850
2851

2852
2853
2854
2855
2856

2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
....
2895
2896
2897
2898
2899
2900
2901
2902
2903


2904
2905

2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950

2951
2952
2953
2954
2955
2956
2957
....
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988





2989
2990
2991
2992
2993
2994

2995
2996
2997
2998
2999
3000
3001
3002
3003
3004



3005
3006
3007
3008
3009
3010
3011

3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
....
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180

3181

3182
3183
3184
3185
3186
3187

3188
3189
3190
3191
3192
3193
3194
3195
3196
3197

3198
3199
3200
3201

3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
....
3220
3221
3222
3223
3224
3225
3226

3227
3228
3229

3230
3231
3232
3233

3234
3235


3236
3237




3238
3239






3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257

3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
3270
3271
3272


3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
3290
3291
3292
....
3305
3306
3307
3308
3309
3310
3311

3312
3313
3314
3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
....
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418
3419
3420
3421
3422
3423
3424
3425

3426
3427
3428
3429
3430
3431
3432
3433
3434
3435
3436
....
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
3500
3501
3502
3503
3504
3505


3506
3507
3508
3509
3510
3511
3512
....
3580
3581
3582
3583
3584
3585
3586
3587
3588
3589
3590
3591
3592
3593
3594
3595
3596
3597
3598
3599
3600
3601
3602
3603
3604
** 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.106 2004/04/29 14:42:46 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
**      *     zero or more pages numbers of leaves
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include <assert.h>






























/* Forward declarations */
typedef struct MemPage MemPage;

/*
** This is a magic string that appears at the beginning of every
** SQLite database in order to identify the file as a real database.
**                                  0123456789 123456 */
static const char zMagicHeader[] = "SQLite version 3";

/*
** Page type flags

*/
#define PTF_LEAF      0x01
#define PTF_ZERODATA  0x02
#define PTF_INTKEY    0x04


/*
** As each page of the file is loaded into memory, an instance of the following
** structure is appended and initialized to zero.  This structure stores
** information about the page that is decoded from the raw file page.
** The extra two entries in apCell[] are an allowance for this situation.
**
** The pParent field points back to the parent page.  This allows us to
** walk up the BTree from any leaf to the root.  Care must be taken to
** unref() the parent page pointer when this page is no longer referenced.
** The pageDestructor() routine handles that chore.
*/
struct MemPage {
................................................................................
  u8 zeroData;                   /* True if zero data flag is set */
  u8 hdrOffset;                  /* 100 for page 1.  0 otherwise */
  Pgno pgno;                     /* Page number for this page */
  MemPage *pParent;              /* The parent of this page.  NULL for root */
  int idxParent;                 /* Index in pParent->aCell[] of this node */
  int nFree;                     /* Number of free bytes on the page */
  int nCell;                     /* Number of entries on this page */

  unsigned char **aCell;         /* Pointer to start of each cell */
};

/*
** The in-memory image of a disk page has the auxiliary information appended
** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
** that extra information.
................................................................................
  int size;
  unsigned char *data;
#ifndef NDEBUG
  int cnt = 0;
#endif

  data = pPage->aData;
  assert( sqlitepager_iswriteable(data) );
  assert( pPage->pBt );
  if( nByte<4 ) nByte = 4;
  if( pPage->nFree<nByte || pPage->isOverfull ) return 0;
  hdr = pPage->hdrOffset;
  if( data[hdr+5]>=252 ){
    defragmentPage(pPage);
  }
................................................................................
  int addr, pbegin, pend;
#ifndef NDEBUG
  int tsize = 0;          /* Total size of all freeblocks */
#endif
  unsigned char *data = pPage->aData;

  assert( pPage->pBt!=0 );
  assert( sqlitepager_iswriteable(data) );
  assert( start>=pPage->hdrOffset+6+(pPage->leaf?0:4) );
  assert( end<=pPage->pBt->pageSize );
  if( size<4 ) size = 4;

  /* Add the space back into the linked list of freeblocks */
  addr = pPage->hdrOffset + 1;
  while( (pbegin = get2byte(&data[addr]))<start && pbegin>0 ){
................................................................................

#if 0
/*
** The following is the default comparison function for (non-integer)
** keys in the btrees.  This function returns negative, zero, or
** positive if the first key is less than, equal to, or greater than
** the second.




















**
*/
static int keyComp(
  void *userData,
  int nKey1, const unsigned char *aKey1, 
  int nKey2, const unsigned char *aKey2,
){
................................................................................
  }
  return 0;

bad_key:
  return 1;
}
#endif
















/*
** Initialize the auxiliary information for a disk block.
**
** The pParent parameter must be a pointer to the MemPage which
** is the parent of the page being initialized.  The root of a
** BTree has no parent and so for that page, pParent==NULL.
................................................................................
  MemPage *pPage,        /* The page to be initialized */
  MemPage *pParent       /* The parent.  Might be NULL */
){
  int c, pc, i, hdr;
  int sumCell = 0;       /* Total size of all cells */

  assert( pPage->pBt!=0 );


  assert( pPage->aData == &((unsigned char*)pPage)[pPage->pBt->pageSize] );

  if( pPage->pParent ){
    assert( pPage->pParent==pParent );
    return SQLITE_OK;
  }
  if( pParent ){
    pPage->pParent = pParent;

    sqlitepager_ref(pParent->aData);
  }
  if( pPage->isInit ) return SQLITE_OK;
  pPage->nCell = 0;
  assert( sqlitepager_pagenumber(pPage->aData)==pPage->pgno );
  pPage->hdrOffset = hdr = pgnoThis==1 ? 100 : 0;
  c = pPage->aData[pPage->hdrOffset];
  pPage->intKey = (c & PTF_INTKEY)!=0;
  pPage->zeroData = (c & PTF_ZERODATA)!=0;
  pPage->leaf = (c & PTF_INTKEY)!=0;

  /* Initialize the cell count and cell pointers */
  pc = get2byte(&data[hdr+3]);
  while( pc>0 ){
    if( pc>=pBt->pageSize ) return SQLITE_CORRUPT;
    if( pPage->nCell>pBt->pageSize ) return SQLITE_CORRUPT;
    pPage->nCell++;
    pc = get2byte(&data[pc]);
  }
  pPage->aCell = sqlite_malloc( sizeof(pPage->aCell[0])*pPage->nCell );
  if( pPage->aCell==0 ){
    return SQLITE_NOMEM;
  }
  pc = get2byte(&data[hdr+3]);
  for(i=0; pc>0; i++){
    pPage->aCell[i] = &data[pc];
    pc = get2byte(&data[pc]);
    sumCell += cellSize(pPage, &data[pc]);
................................................................................
*/
static void zeroPage(MemPage *pPage, int flags){
  unsigned char *data = pPage->aData;
  Btree *pBt = pPage->pBt;
  int hdr = pPage->hdrOffset;
  int first;

  assert( sqlitepager_iswriteable(data) );
  memset(&data[hdr], 0, pBt->pageSize - hdr);
  data[hdr] = flags;
  first = hdr + 6 + 4*((flags&0x01)!=0);
  put2byte(&data[hdr+1], first);
  put2byte(&data[first+2], pBt->pageSize - first);
  sqliteFree(pPage->aCell);
  pPage->aCell = 0;
................................................................................
  return SQLITE_OK;
}

/*
** Release a MemPage.  This should be called once for each prior
** call to getPage.
*/
static int releasePage(MemPage *pPage){
  if( pPage ){
    assert( pPage->aData );
    assert( pPage->pBt );
    assert( &pPage->aData[pPage->pBt->pageSize]==(unsigned char*)pPage );
    sqlitepager_unref(pPage->aData);
  }
}
................................................................................
    *ppBtree = 0;
    return rc;
  }
  sqlitepager_set_destructor(pBt->pPager, pageDestructor);
  pBt->pCursor = 0;
  pBt->page1 = 0;
  pBt->readOnly = sqlitepager_isreadonly(pBt->pPager);
  pBt->pageSize = SQLITE_PAGE_SIZE;
  pBt->maxLocal = (SQLITE_PAGE_SIZE-10)/4-12;
  *ppBtree = pBt;
  return SQLITE_OK;
}

/*
** Close an open database and invalidate all cursors.
*/
................................................................................
  int rc;
  BtCursor *pCur, *pRing;

  if( pBt->readOnly && wrFlag ){
    *ppCur = 0;
    return SQLITE_READONLY;
  }
  if( pBt->page1==0 ){
    rc = lockBtree(pBt);
    if( rc!=SQLITE_OK ){
      *ppCur = 0;
      return rc;
    }
  }
  pCur = sqliteMalloc( sizeof(*pCur) );
  if( pCur==0 ){
    rc = SQLITE_NOMEM;
    goto create_cursor_exception;
  }
  pCur->pgnoRoot = (Pgno)iTable;
  rc = getPage(pBt, pCur->pgnoRoot, (void**)&pCur->pPage);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }
  rc = initPage(pCur->pPage, 0);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }
................................................................................
}

/*
** Set *pSize to the size of the buffer needed to hold the value of
** 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, u64 *pSize){
  MemPage *pPage;

  pPage = pCur->pPage;
  assert( pPage!=0 );
................................................................................
** If pCur is not pointing to a valid entry return 0.
**
** The pointer returned is ephemeral.  The key may move
** or be destroyed on the next call to any Btree routine.
**
** This routine is used to do quick key comparisons in the
** common case where the entire key fits in the payload area
** of a cell and does not overflow onto secondary pages.






*/
void *sqlite3BtreeKeyFetch(BtCursor *pCur){
  unsigned char *aPayload;
  MemPage *pPage;
  Btree *pBt;
  u64 nData, nKey;

................................................................................
  pCur->pPage = pRoot;
  pCur->idx = 0;
  if( pRoot->nCell==0 && !pRoot->leaf ){
    Pgno subpage;
    assert( pRoot->pgno==1 );
    subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+6]);
    assert( subpage>0 );
    rc = movetoChild(pCur, subpage);
  }
  return rc;
}

/*
** Move the cursor down to the left-most leaf entry beneath the
** entry to which it is currently pointing.
................................................................................
    if( rc ) return rc;
    sqlitepager_unref(pOvfl->aData);
  }
  return SQLITE_OK;
}

/*
** Compute the number of bytes required by a cell header.  If the *pHeader
** argument is not NULL, fill it in with the bytes of the header.
*/
static int makeCellHeader(
  MemPage *pPage,          /* The page that will contain the cell */
  u64 nKey,                /* Size of key, or the key value if intKey */
  int nData,               /* Size of data.  Ignored for zerodata */
  unsigned char *pHeader   /* Write header bytes here */
){
................................................................................
/*
** Fill in the payload section of a cell into the space provided.  If
** the payload will not completely fit in the cell, allocate additional
** overflow pages and fill them in.
*/
static int fillInCell(
  MemPage *pPage,                /* The page that contains the cell */
  unsigned char *pCell,          /* Pointer to start of payload area */
  int nHeader,                   /* Number of bytes in the cell header */
  const void *pKey, u64 nKey,    /* The key */
  const void *pData,int nData    /* The data */

){
  int nPayload;
  const void *pSrc;
  int nSrc, nSrc2;
  int spaceLeft;
  MemPage *pOvfl = 0;
  unsigned char *pPrior;
  unsigned char *pPayload;
  Btree *pBt = pPage->pBt;
  Pgno pgnoOvfl = 0;



  nPayload = nData;
  if( pPage->intKey ){
    pSrc = pData;
    nSrc = nData;
    nSrc2 = 0;
  }else{
    nPayload += nKey;
    pSrc = pKey;
    nSrc = nKey;
  }





  spaceLeft = pBt->maxLocal;
  pPayload = &pCell[nHeader];
  pPrior = &pPayload[pBt->maxLocal];

  while( nPayload>0 ){
    if( spaceLeft==0 ){
      rc =  allocatePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl);
................................................................................
}

/*
** Change the MemPage.pParent pointer on the page whose number is
** given in the second argument so that MemPage.pParent holds the
** pointer in the third argument.
*/
static void reparentPage(Pager *pPager, Pgno pgno, MemPage *pNewParent,int idx){
  MemPage *pThis;


  if( pgno==0 ) return;
  assert( pPager!=0 );
  pThis = sqlitepager_lookup(pPager, pgno);

  if( pThis && pThis->isInit ){
    if( pThis->pParent!=pNewParent ){
      if( pThis->pParent ) sqlitepager_unref(pThis->pParent);
      pThis->pParent = pNewParent;
      if( pNewParent ) sqlitepager_ref(pNewParent);
    }
    pThis->idxParent = idx;
    sqlitepager_unref(pThis);
  }
}

/*
** Reparent all children of the given page to be the given page.


** In other words, for every child of pPage, invoke reparentPage()
** to make sure that each child knows that pPage is its parent.
**
** This routine gets called after you memcpy() one page into
** another.
*/
static void reparentChildPages(Btree *pBt, MemPage *pPage){
  int i;
  Pager *pPager = pBt->pPager;



  for(i=0; i<pPage->nCell; i++){
    reparentPage(pPager, SWAB32(pBt, pPage->apCell[i]->h.leftChild), pPage, i);

  }
  reparentPage(pPager, SWAB32(pBt, pPage->u.hdr.rightChild), pPage, i);

  pPage->idxShift = 0;
}

/*
** Remove the i-th cell from pPage.  This routine effects pPage only.
** The cell content is not freed or deallocated.  It is assumed that
** the cell content has been copied someplace else.  This routine just
................................................................................
** "sz" must be the number of bytes in the cell.
**
** Do not bother maintaining the integrity of the linked list of Cells.
** Only the pPage->apCell[] array is important.  The relinkCellList() 
** routine will be called soon after this routine in order to rebuild 
** the linked list.
*/
static void dropCell(Btree *pBt, MemPage *pPage, int idx, int sz){
  int j;
  assert( idx>=0 && idx<pPage->nCell );
  assert( sz==cellSize(pBt, pPage->apCell[idx]) );
  assert( sqlitepager_iswriteable(pPage) );
  freeSpace(pBt, pPage, Addr(pPage->apCell[idx]) - Addr(pPage), sz);


  for(j=idx; j<pPage->nCell-1; j++){
    pPage->apCell[j] = pPage->apCell[j+1];
  }
  pPage->nCell--;
  pPage->idxShift = 1;
}

/*
** Insert a new cell on pPage at cell index "i".  pCell points to the
................................................................................
** and set pPage->isOverfull.  
**
** Do not bother maintaining the integrity of the linked list of Cells.
** Only the pPage->apCell[] array is important.  The relinkCellList() 
** routine will be called soon after this routine in order to rebuild 
** the linked list.
*/
static void insertCell(Btree *pBt, MemPage *pPage, int i, Cell *pCell, int sz){
  int idx, j;
  assert( i>=0 && i<=pPage->nCell );
  assert( sz==cellSize(pBt, pCell) );
  assert( sqlitepager_iswriteable(pPage) );
  idx = allocateSpace(pBt, pPage, sz);

  for(j=pPage->nCell; j>i; j--){
    pPage->apCell[j] = pPage->apCell[j-1];
  }
  pPage->nCell++;
  if( idx<=0 ){
    pPage->isOverfull = 1;
    pPage->apCell[i] = pCell;
  }else{
    memcpy(&pPage->u.aDisk[idx], pCell, sz);
    pPage->apCell[i] = (Cell*)&pPage->u.aDisk[idx];
  }
  pPage->idxShift = 1;
}

/*
** Rebuild the linked list of cells on a page so that the cells
** occur in the order specified by the pPage->apCell[] array.  
** Invoke this routine once to repair damage after one or more
** invocations of either insertCell() or dropCell().
*/
static void relinkCellList(Btree *pBt, MemPage *pPage){
  int i;
  u16 *pIdx;
  assert( sqlitepager_iswriteable(pPage) );
  pIdx = &pPage->u.hdr.firstCell;

  for(i=0; i<pPage->nCell; i++){
    int idx = Addr(pPage->apCell[i]) - Addr(pPage);

    assert( idx>0 && idx<SQLITE_USABLE_SIZE );
    *pIdx = SWAB16(pBt, idx);
    pIdx = &pPage->apCell[i]->h.iNext;
  }
  *pIdx = 0;

}

/*
** Make a copy of the contents of pFrom into pTo.  The pFrom->apCell[]
** pointers that point into pFrom->u.aDisk[] must be adjusted to point
** into pTo->u.aDisk[] instead.  But some pFrom->apCell[] entries might
** not point to pFrom->u.aDisk[].  Those are unchanged.
*/
static void copyPage(MemPage *pTo, MemPage *pFrom){
  uptr from, to;
  int i;
  memcpy(pTo->u.aDisk, pFrom->u.aDisk, SQLITE_USABLE_SIZE);






  pTo->pParent = 0;
  pTo->isInit = 1;

  pTo->nCell = pFrom->nCell;
  pTo->nFree = pFrom->nFree;


  pTo->isOverfull = pFrom->isOverfull;
  to = Addr(pTo);
  from = Addr(pFrom);
  for(i=0; i<pTo->nCell; i++){
    uptr x = Addr(pFrom->apCell[i]);
    if( x>from && x<from+SQLITE_USABLE_SIZE ){
      *((uptr*)&pTo->apCell[i]) = x + to - from;
    }else{
      pTo->apCell[i] = pFrom->apCell[i];
    }
  }
}

/*
** The following parameters determine how many adjacent pages get involved
** in a balancing operation.  NN is the number of neighbors on either side
................................................................................
** The number of siblings of pPage might be increased or decreased by
** one in an effort to keep pages between 66% and 100% full. The root page
** is special and is allowed to be less than 66% full. If pPage is 
** the root page, then the depth of the tree might be increased
** or decreased by one, as necessary, to keep the root page from being
** overfull or empty.
**
** This routine calls relinkCellList() on its input page regardless of
** whether or not it does any real balancing.  Client routines will typically
** invoke insertCell() or dropCell() before calling this routine, so we
** need to call relinkCellList() to clean up the mess that those other
** routines left behind.
**
** pCur is left pointing to the same cell as when this routine was called
** even if that cell gets moved to a different page.  pCur may be NULL.
** Set the pCur parameter to NULL if you do not care about keeping track
** of a cell as that will save this routine the work of keeping track of it.
**
** Note that when this routine is called, some of the Cells on pPage
** might not actually be stored in pPage->u.aDisk[].  This can happen
** if the page is overfull.  Part of the job of this routine is to
** make sure all Cells for pPage once again fit in pPage->u.aDisk[].
**
** In the course of balancing the siblings of pPage, the parent of pPage
** might become overfull or underfull.  If that happens, then this routine
** is called recursively on the parent.
**
** If this routine fails for any reason, it might leave the database
** in a corrupted state.  So if this routine fails, the database should
** be rolled back.
*/
static int balance(Btree *pBt, MemPage *pPage, BtCursor *pCur){
  MemPage *pParent;            /* The parent of pPage */

  int nCell;                   /* Number of cells in apCell[] */
  int nOld;                    /* Number of pages in apOld[] */
  int nNew;                    /* Number of pages in apNew[] */
  int nDiv;                    /* Number of cells in apDiv[] */
  int i, j, k;                 /* Loop counters */
  int idx;                     /* Index of pPage in pParent->apCell[] */
  int nxDiv;                   /* Next divider slot in pParent->apCell[] */
  int rc;                      /* The return code */
  int iCur;                    /* apCell[iCur] is the cell of the cursor */
  MemPage *pOldCurPage;        /* The cursor originally points to this page */
  int subtotal;                /* Subtotal of bytes in cells on one page */
  MemPage *extraUnref = 0;     /* A page that needs to be unref-ed */
  MemPage *apOld[NB];          /* pPage and up to two siblings */
  Pgno pgnoOld[NB];            /* Page numbers for each page in apOld[] */

  MemPage *apNew[NB+1];        /* pPage and up to NB siblings after balancing */
  Pgno pgnoNew[NB+1];          /* Page numbers for each page in apNew[] */
  int idxDiv[NB];              /* Indices of divider cells in pParent */
  Cell *apDiv[NB];             /* Divider cells in pParent */
  Cell aTemp[NB];              /* Temporary holding area for apDiv[] */
  int cntNew[NB+1];            /* Index in apCell[] of cell after i-th page */
  int szNew[NB+1];             /* Combined size of cells place on i-th page */
  MemPage aOld[NB];            /* Temporary copies of pPage and its siblings */
  Cell *apCell[(MX_CELL+2)*NB]; /* All cells from pages being balanced */
  int szCell[(MX_CELL+2)*NB];  /* Local size of all cells */


  /* 
  ** Return without doing any work if pPage is neither overfull nor
  ** underfull.
  */
  assert( sqlitepager_iswriteable(pPage) );

  if( !pPage->isOverfull && pPage->nFree<SQLITE_USABLE_SIZE/2 
        && pPage->nCell>=2){
    relinkCellList(pBt, pPage);
    return SQLITE_OK;
  }

  /*
  ** Find the parent of the page to be balanceed.
  ** If there is no parent, it means this page is the root page and
  ** special rules apply.
  */
  pParent = pPage->pParent;
  if( pParent==0 ){
    Pgno pgnoChild;
    MemPage *pChild;
    assert( pPage->isInit );
    if( pPage->nCell==0 ){
................................................................................
        relinkCellList(pPage);
      }else{
        /* The root page is empty but has one child.  Transfer the
        ** information from that one child into the root page if it 
        ** will fit.  This reduces the depth of the BTree by one.
        **
        ** If the root page is page 1, it has less space available than

        ** the child, so it might not be able to hold all of the information

        ** in the child.  If this is the case, then do not do the transfer.
        ** Leave page 1 empty except for the right-pointer to the child page.
        ** The child page becomes the virtual root of the tree.
        */
        pgnoChild = get4byte(pPage->aData[pPage->hdrOffset+6]);
        assert( pgnoChild>0 && pgnoChild<=sqlit3pager_pagecount(pBt->pPager) );
        rc = getPage(pBt, pgnoChild, &pChild);
        if( rc ) return rc;
        if( pPage->pgno==1 ){
          rc = initPage(pChild);
          if( rc ) return rc;
          if( pChild->nFree>=100 ){







          }

        }else{




          memcpy(pPage, pChild, SQLITE_USABLE_SIZE);
          pPage->isInit = 0;
          rc = initPage(pBt, pPage, sqlitepager_pagenumber(pPage), 0);


          assert( rc==SQLITE_OK );
          reparentChildPages(pBt, pPage);
        if( pCur && pCur->pPage==pChild ){
          sqlitepager_unref(pChild);
          pCur->pPage = pPage;
          sqlitepager_ref(pPage);
        }
        freePage(pBt, pChild, pgnoChild);

        sqlitepager_unref(pChild);
      }else{
        relinkCellList(pBt, pPage);
      }
      return SQLITE_OK;
    }
    if( !pPage->isOverfull ){
      /* It is OK for the root page to be less than half full.
      */
      relinkCellList(pBt, pPage);
................................................................................
    ** If we get to here, it means the root page is overfull.
    ** When this happens, Create a new child page and copy the
    ** contents of the root into the child.  Then make the root
    ** page an empty page with rightChild pointing to the new
    ** child.  Then fall thru to the code below which will cause
    ** the overfull child page to be split.
    */
    rc = sqlitepager_write(pPage);
    if( rc ) return rc;
    rc = allocatePage(pBt, &pChild, &pgnoChild, sqlitepager_pagenumber(pPage));
    if( rc ) return rc;
    assert( sqlitepager_iswriteable(pChild) );
    copyPage(pChild, pPage);
    pChild->pParent = pPage;
    pChild->idxParent = 0;
    sqlitepager_ref(pPage);
    pChild->isOverfull = 1;
    if( pCur && pCur->pPage==pPage ){
      sqlitepager_unref(pPage);
      pCur->pPage = pChild;
    }else{
      extraUnref = pChild;
    }
    zeroPage(pBt, pPage);
    pPage->u.hdr.rightChild = SWAB32(pBt, pgnoChild);
    pParent = pPage;
    pPage = pChild;
  }
  rc = sqlitepager_write(pParent);
  if( rc ) return rc;
  assert( pParent->isInit );
  
  /*
  ** Find the Cell in the parent page whose h.leftChild points back
  ** to pPage.  The "idx" variable is the index of that cell.  If pPage
  ** is the rightmost child of pParent then set idx to pParent->nCell 
  */
  if( pParent->idxShift ){
    Pgno pgno, swabPgno;

    pgno = sqlitepager_pagenumber(pPage);
    swabPgno = SWAB32(pBt, pgno);
    for(idx=0; idx<pParent->nCell; idx++){
      if( pParent->apCell[idx]->h.leftChild==swabPgno ){
        break;
      }
    }
    assert( idx<pParent->nCell || pParent->u.hdr.rightChild==swabPgno );

  }else{
    idx = pPage->idxParent;
  }

  /*
  ** Initialize variables so that it will be safe to jump
  ** directly to balance_cleanup at any moment.
  */
  nOld = nNew = 0;
  sqlitepager_ref(pParent);

  /*
  ** Find sibling pages to pPage and the Cells in pParent that divide
  ** the siblings.  An attempt is made to find NN siblings on either
  ** side of pPage.  More siblings are taken from one side, however, if
  ** pPage there are fewer than NN siblings on the other side.  If pParent
  ** has NB or fewer children then all children of pParent are taken.
  */
  nxDiv = idx - NN;
  if( nxDiv + NB > pParent->nCell ){
................................................................................
  if( nxDiv<0 ){
    nxDiv = 0;
  }
  nDiv = 0;
  for(i=0, k=nxDiv; i<NB; i++, k++){
    if( k<pParent->nCell ){
      idxDiv[i] = k;
      apDiv[i] = pParent->apCell[k];
      nDiv++;
      pgnoOld[i] = SWAB32(pBt, apDiv[i]->h.leftChild);

    }else if( k==pParent->nCell ){
      pgnoOld[i] = SWAB32(pBt, pParent->u.hdr.rightChild);

    }else{
      break;
    }
    rc = sqlitepager_get(pBt->pPager, pgnoOld[i], (void**)&apOld[i]);
    if( rc ) goto balance_cleanup;
    rc = initPage(pBt, apOld[i], pgnoOld[i], pParent);
    if( rc ) goto balance_cleanup;
    apOld[i]->idxParent = k;
    nOld++;
  }

  /*
  ** Set iCur to be the index in apCell[] of the cell that the cursor
  ** is pointing to.  We will need this later on in order to keep the
  ** cursor pointing at the same cell.  If pCur points to a page that
  ** has no involvement with this rebalancing, then set iCur to a large
  ** number so that the iCur==j tests always fail in the main cell
  ** distribution loop below.
  */
  if( pCur ){
    iCur = 0;
    for(i=0; i<nOld; i++){
      if( pCur->pPage==apOld[i] ){
        iCur += pCur->idx;
        break;
      }
      iCur += apOld[i]->nCell;
      if( i<nOld-1 && pCur->pPage==pParent && pCur->idx==idxDiv[i] ){
        break;
      }
      iCur++;
    }
    pOldCurPage = pCur->pPage;
  }

  /*
  ** Make copies of the content of pPage and its siblings into aOld[].
  ** The rest of this function will use data from the copies rather
  ** that the original pages since the original pages will be in the
  ** process of being overwritten.
  */
  for(i=0; i<nOld; i++){



    copyPage(&aOld[i], apOld[i]);
  }

  /*
  ** Load pointers to all cells on sibling pages and the divider cells
  ** into the local apCell[] array.  Make copies of the divider cells
  ** into aTemp[] and remove the the divider Cells from pParent.







  */
  nCell = 0;

  for(i=0; i<nOld; i++){
    MemPage *pOld = &aOld[i];
    for(j=0; j<pOld->nCell; j++){
      apCell[nCell] = pOld->apCell[j];
      szCell[nCell] = cellSize(pBt, apCell[nCell]);
      nCell++;
    }
    if( i<nOld-1 ){
      szCell[nCell] = cellSize(pBt, apDiv[i]);
      memcpy(&aTemp[i], apDiv[i], szCell[nCell]);
      apCell[nCell] = &aTemp[i];
      dropCell(pBt, pParent, nxDiv, szCell[nCell]);
      assert( SWAB32(pBt, apCell[nCell]->h.leftChild)==pgnoOld[i] );
      apCell[nCell]->h.leftChild = pOld->u.hdr.rightChild;







      nCell++;
    }
  }

  /*
  ** Figure out the number of pages needed to hold all nCell cells.
  ** Store this number in "k".  Also compute szNew[] which is the total
  ** size of all cells on the i-th page and cntNew[] which is the index
  ** in apCell[] of the cell that divides path i from path i+1.  
  ** cntNew[k] should equal nCell.
  **
  ** This little patch of code is critical for keeping the tree
  ** balanced. 
  */

  for(subtotal=k=i=0; i<nCell; i++){
    subtotal += szCell[i];
    if( subtotal > USABLE_SPACE ){
      szNew[k] = subtotal - szCell[i];
      cntNew[k] = i;
      subtotal = 0;
      k++;
    }
  }
  szNew[k] = subtotal;
  cntNew[k] = nCell;
  k++;
  for(i=k-1; i>0; i--){
    while( szNew[i]<USABLE_SPACE/2 ){
      cntNew[i-1]--;
      assert( cntNew[i-1]>0 );
      szNew[i] += szCell[cntNew[i-1]];
      szNew[i-1] -= szCell[cntNew[i-1]-1];
    }
  }
  assert( cntNew[0]>0 );

  /*
  ** Allocate k new pages.  Reuse old pages where possible.
  */


  for(i=0; i<k; i++){
    if( i<nOld ){
      apNew[i] = apOld[i];
      pgnoNew[i] = pgnoOld[i];
      apOld[i] = 0;
      sqlitepager_write(apNew[i]);
    }else{
      rc = allocatePage(pBt, &apNew[i], &pgnoNew[i], pgnoNew[i-1]);
      if( rc ) goto balance_cleanup;
    }
    nNew++;
    zeroPage(pBt, apNew[i]);
    apNew[i]->isInit = 1;
  }

  /* Free any old pages that were not reused as new pages.
  */
  while( i<nOld ){
    rc = freePage(pBt, apOld[i], pgnoOld[i]);
    if( rc ) goto balance_cleanup;
    sqlitepager_unref(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
................................................................................
  /*
  ** 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];


    while( j<cntNew[i] ){
      assert( pNew->nFree>=szCell[j] );
      if( pCur && iCur==j ){ pCur->pPage = pNew; pCur->idx = pNew->nCell; }
      insertCell(pBt, pNew, pNew->nCell, apCell[j], szCell[j]);
      j++;
    }
    assert( pNew->nCell>0 );
    assert( !pNew->isOverfull );
    relinkCellList(pBt, pNew);
    if( i<nNew-1 && j<nCell ){
      pNew->u.hdr.rightChild = apCell[j]->h.leftChild;
      apCell[j]->h.leftChild = SWAB32(pBt, pgnoNew[i]);
      if( pCur && iCur==j ){ pCur->pPage = pParent; pCur->idx = nxDiv; }
      insertCell(pBt, pParent, nxDiv, apCell[j], szCell[j]);




      j++;
      nxDiv++;
    }
  }
  assert( j==nCell );
  apNew[nNew-1]->u.hdr.rightChild = aOld[nOld-1].u.hdr.rightChild;
  if( nxDiv==pParent->nCell ){
    pParent->u.hdr.rightChild = SWAB32(pBt, pgnoNew[nNew-1]);
  }else{
    pParent->apCell[nxDiv]->h.leftChild = SWAB32(pBt, pgnoNew[nNew-1]);
  }
  if( pCur ){
    if( j<=iCur && pCur->pPage==pParent && pCur->idx>idxDiv[nOld-1] ){
      assert( pCur->pPage==pOldCurPage );
      pCur->idx += nNew - nOld;
    }else{
      assert( pOldCurPage!=0 );
      sqlitepager_ref(pCur->pPage);
      sqlitepager_unref(pOldCurPage);
    }
  }

  /*
  ** Reparent children of all cells.
  */
  for(i=0; i<nNew; i++){
    reparentChildPages(pBt, apNew[i]);
  }
  reparentChildPages(pBt, pParent);

  /*
  ** balance the parent page.
  */
  rc = balance(pBt, pParent, pCur);

  /*
  ** Cleanup before returning.
  */
balance_cleanup:
  if( extraUnref ){
    sqlitepager_unref(extraUnref);
  }
  for(i=0; i<nOld; i++){
    if( apOld[i]!=0 && apOld[i]!=&aOld[i] ) sqlitepager_unref(apOld[i]);
  }
  for(i=0; i<nNew; i++){
    sqlitepager_unref(apNew[i]);
  }
  if( pCur && pCur->pPage==0 ){
    pCur->pPage = pParent;
    pCur->idx = 0;
  }else{
    sqlitepager_unref(pParent);
  }
  return rc;
}

/*
** This routine checks all cursors that point to the same table
** as pCur points to.  If any of those cursors were opened with
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
................................................................................
  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 database the record should be inserted into.  The cursor
** is left pointing at the new record.



*/
int sqlite3BtreeInsert(
  BtCursor *pCur,                /* Insert data into the table of this cursor */
  const void *pKey, int nKey,    /* The key of the new record */
  const void *pData, int nData   /* The data of the new record */
){
  Cell newCell;
  int rc;
  int loc;
  int szNew;
  MemPage *pPage;
  Btree *pBt = pCur->pBt;


  if( pCur->pPage==0 ){
    return SQLITE_ABORT;  /* A rollback destroyed this cursor */
  }
  if( !pBt->inTrans || nKey+nData==0 ){
    /* Must start a transaction before doing an insert */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
................................................................................
  }
  if( checkReadLocks(pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc);
  if( rc ) return rc;
  pPage = pCur->pPage;

  assert( pPage->isInit );
  rc = sqlitepager_write(pPage);
  if( rc ) return rc;
  rc = fillInCell(pBt, &newCell, pKey, nKey, pData, nData);
  if( rc ) return rc;
  szNew = cellSize(pBt, &newCell);
  if( loc==0 ){
    newCell.h.leftChild = pPage->apCell[pCur->idx]->h.leftChild;






    rc = clearCell(pBt, pPage->apCell[pCur->idx]);
    if( rc ) return rc;
    dropCell(pBt, pPage, pCur->idx, cellSize(pBt, pPage->apCell[pCur->idx]));

  }else if( loc<0 && pPage->nCell>0 ){
    assert( pPage->u.hdr.rightChild==0 );  /* Must be a leaf page */

    pCur->idx++;
  }else{
    assert( pPage->u.hdr.rightChild==0 );  /* Must be a leaf page */

  }
  insertCell(pBt, pPage, pCur->idx, &newCell, szNew);
  rc = balance(pCur->pBt, pPage, pCur);
  /* sqliteBtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */

  pCur->eSkip = SKIP_INVALID;
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.
**
** The cursor is left pointing at either the next or the previous
** entry.  If the cursor is left pointing to the next entry, then 
** the pCur->eSkip flag is set to SKIP_NEXT which forces the next call to 
** sqliteBtreeNext() to be a no-op.  That way, you can always call
** sqliteBtreeNext() after a delete and the cursor will be left
** pointing to the first entry after the deleted entry.  Similarly,
** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to
** the entry prior to the deleted entry so that a subsequent call to
** sqliteBtreePrevious() will always leave the cursor pointing at the
** entry immediately before the one that was deleted.
*/
int sqlite3BtreeDelete(BtCursor *pCur){
  MemPage *pPage = pCur->pPage;
  Cell *pCell;
  int rc;
  Pgno pgnoChild;
  Btree *pBt = pCur->pBt;

  assert( pPage->isInit );
  if( pCur->pPage==0 ){
    return SQLITE_ABORT;  /* A rollback destroyed this cursor */
................................................................................
    return SQLITE_PERM;   /* Did not open this cursor for writing */
  }
  if( checkReadLocks(pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlitepager_write(pPage);
  if( rc ) return rc;
  pCell = pPage->apCell[pCur->idx];
  pgnoChild = SWAB32(pBt, pCell->h.leftChild);


  clearCell(pBt, pCell);
  if( pgnoChild ){

    /*
    ** 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;
    Cell *pNext;
    int szNext;
    int notUsed;
    getTempCursor(pCur, &leafCur);
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc!=SQLITE_OK ){
      if( rc!=SQLITE_NOMEM ) rc = SQLITE_CORRUPT;
      return rc;
    }
    rc = sqlitepager_write(leafCur.pPage);
    if( rc ) return rc;
    dropCell(pBt, pPage, pCur->idx, cellSize(pBt, pCell));
    pNext = leafCur.pPage->apCell[leafCur.idx];
    szNext = cellSize(pBt, pNext);
    pNext->h.leftChild = SWAB32(pBt, pgnoChild);
    insertCell(pBt, pPage, pCur->idx, pNext, szNext);
    rc = balance(pBt, pPage, pCur);
    if( rc ) return rc;
    pCur->eSkip = SKIP_NEXT;
    dropCell(pBt, leafCur.pPage, leafCur.idx, szNext);
    rc = balance(pBt, leafCur.pPage, pCur);
    releaseTempCursor(&leafCur);
  }else{
    dropCell(pBt, pPage, pCur->idx, cellSize(pBt, pCell));
    if( pCur->idx>=pPage->nCell ){
      pCur->idx = pPage->nCell-1;
      if( pCur->idx<0 ){ 
        pCur->idx = 0;
        pCur->eSkip = SKIP_NEXT;
      }else{
        pCur->eSkip = SKIP_PREV;
      }
    }else{
      pCur->eSkip = SKIP_NEXT;
    }
    rc = balance(pBt, pPage, pCur);
  }

  return rc;
}

/*
** Create a new BTree table.  Write into *piTable the page
** number for the root page of the new table.
**
................................................................................
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  if( pBt->readOnly ){
    return SQLITE_READONLY;
  }
  rc = allocatePage(pBt, &pRoot, &pgnoRoot, 0);
  if( rc ) return rc;
  assert( sqlitepager_iswriteable(pRoot) );
  zeroPage(pBt, pRoot);
  sqlitepager_unref(pRoot);
  *piTable = (int)pgnoRoot;
  return SQLITE_OK;
}

/*
** Erase the given database page and all its children.  Return
** the page to the freelist.
*/
static int clearDatabasePage(Btree *pBt, Pgno pgno, int freePageFlag){





  MemPage *pPage;
  int rc;
  Cell *pCell;
  int idx;

  rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pPage);

  if( rc ) return rc;
  rc = sqlitepager_write(pPage);
  if( rc ) return rc;
  rc = initPage(pBt, pPage, pgno, 0);
  if( rc ) return rc;
  idx = SWAB16(pBt, pPage->u.hdr.firstCell);
  while( idx>0 ){
    pCell = (Cell*)&pPage->u.aDisk[idx];
    idx = SWAB16(pBt, pCell->h.iNext);
    if( pCell->h.leftChild ){



      rc = clearDatabasePage(pBt, SWAB32(pBt, pCell->h.leftChild), 1);
      if( rc ) return rc;
    }
    rc = clearCell(pBt, pCell);
    if( rc ) return rc;
  }
  if( pPage->u.hdr.rightChild ){

    rc = clearDatabasePage(pBt, SWAB32(pBt, pPage->u.hdr.rightChild), 1);
    if( rc ) return rc;
  }
  if( freePageFlag ){
    rc = freePage(pBt, pPage, pgno);
  }else{
    zeroPage(pBt, pPage);
  }
  sqlitepager_unref(pPage);
  return rc;
}

/*
** Delete all information from a single table in the database.
*/
int sqlite3BtreeClearTable(Btree *pBt, int iTable){
................................................................................
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    if( pCur->pgnoRoot==(Pgno)iTable ){
      return SQLITE_LOCKED;  /* Cannot drop a table that has a cursor */
    }
  }
  rc = sqlitepager_get(pBt->pPager, (Pgno)iTable, (void**)&pPage);
  if( rc ) return rc;
  rc = sqlite3BtreeClearTable(pBt, iTable);
  if( rc ) return rc;
  if( iTable>2 ){
    rc = freePage(pBt, pPage, iTable);
  }else{
    zeroPage(pBt, pPage);
  }
  sqlitepager_unref(pPage);
  return rc;  
}

#if 0 /* UNTESTED */
/*
** Copy all cell data from one database file into another.
** pages back the freelist.
*/
static int copyCell(Btree *pBtFrom, BTree *pBtTo, Cell *pCell){
  Pager *pFromPager = pBtFrom->pPager;
  OverflowPage *pOvfl;
  Pgno ovfl, nextOvfl;
  Pgno *pPrev;
  int rc = SQLITE_OK;
  MemPage *pNew, *pPrevPg;
  Pgno new;

  if( NKEY(pBtTo, pCell->h) + NDATA(pBtTo, pCell->h) <= MX_LOCAL_PAYLOAD ){
    return SQLITE_OK;
  }
  pPrev = &pCell->ovfl;
  pPrevPg = 0;
  ovfl = SWAB32(pBtTo, pCell->ovfl);
  while( ovfl && rc==SQLITE_OK ){
    rc = sqlitepager_get(pFromPager, ovfl, (void**)&pOvfl);
    if( rc ) return rc;
    nextOvfl = SWAB32(pBtFrom, pOvfl->iNext);
    rc = allocatePage(pBtTo, &pNew, &new, 0);
    if( rc==SQLITE_OK ){
      rc = sqlitepager_write(pNew);
      if( rc==SQLITE_OK ){
        memcpy(pNew, pOvfl, SQLITE_USABLE_SIZE);
        *pPrev = SWAB32(pBtTo, new);
        if( pPrevPg ){
          sqlitepager_unref(pPrevPg);
        }
        pPrev = &pOvfl->iNext;
        pPrevPg = pNew;
      }
    }
    sqlitepager_unref(pOvfl);
    ovfl = nextOvfl;
  }
  if( pPrevPg ){
    sqlitepager_unref(pPrevPg);
  }
  return rc;
}
#endif


#if 0 /* UNTESTED */
/*
** Copy a page of data from one database over to another.
*/
static int copyDatabasePage(
  Btree *pBtFrom,
  Pgno pgnoFrom,
  Btree *pBtTo,
  Pgno *pTo
){
  MemPage *pPageFrom, *pPage;
  Pgno to;
  int rc;
  Cell *pCell;
  int idx;

  rc = sqlitepager_get(pBtFrom->pPager, pgno, (void**)&pPageFrom);
  if( rc ) return rc;
  rc = allocatePage(pBt, &pPage, pTo, 0);
  if( rc==SQLITE_OK ){
    rc = sqlitepager_write(pPage);
  }
  if( rc==SQLITE_OK ){
    memcpy(pPage, pPageFrom, SQLITE_USABLE_SIZE);
    idx = SWAB16(pBt, pPage->u.hdr.firstCell);
    while( idx>0 ){
      pCell = (Cell*)&pPage->u.aDisk[idx];
      idx = SWAB16(pBt, pCell->h.iNext);
      if( pCell->h.leftChild ){
        Pgno newChld;
        rc = copyDatabasePage(pBtFrom, SWAB32(pBtFrom, pCell->h.leftChild),
                              pBtTo, &newChld);
        if( rc ) return rc;
        pCell->h.leftChild = SWAB32(pBtFrom, newChld);
      }
      rc = copyCell(pBtFrom, pBtTo, pCell);
      if( rc ) return rc;
    }
    if( pPage->u.hdr.rightChild ){
      Pgno newChld;
      rc = copyDatabasePage(pBtFrom, SWAB32(pBtFrom, pPage->u.hdr.rightChild), 
                            pBtTo, &newChld);
      if( rc ) return rc;
      pPage->u.hdr.rightChild = SWAB32(pBtTo, newChild);
    }
  }
  sqlitepager_unref(pPage);
  return rc;
}
#endif

/*
** Read the meta-information out of a database file.
*/
int sqlite3BtreeGetMeta(Btree *pBt, int idx, u32 *pMeta){
  int rc;
  int i;



  rc = sqlitepager_get(pBt->pPager, 1, (void**)&pP1);
  if( rc ) return rc;
  aMeta[0] = SWAB32(pBt, pP1->nFree);
  for(i=0; i<sizeof(pP1->aMeta)/sizeof(pP1->aMeta[0]); i++){
    aMeta[i+1] = SWAB32(pBt, pP1->aMeta[i]);
  }

  sqlitepager_unref(pP1);
  return SQLITE_OK;
}

/*
** Write meta-information back into the database.
*/
int sqlite3BtreeUpdateMeta(Btree *pBt, int idx, u32 iMeta){
  PageOne *pP1;
  int rc, i;

  if( !pBt->inTrans ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  pP1 = pBt->page1;

  rc = sqlitepager_write(pP1);
  if( rc ) return rc;   
  for(i=0; i<sizeof(pP1->aMeta)/sizeof(pP1->aMeta[0]); i++){
    pP1->aMeta[i] = SWAB32(pBt, aMeta[i+1]);
  }
  return SQLITE_OK;
}

/******************************************************************************
** The complete implementation of the BTree subsystem is above this line.
** All the code the follows is for testing and troubleshooting the BTree
** subsystem.  None of the code that follows is used during normal operation.
................................................................................
#ifdef SQLITE_TEST
static int fileBtreePageDump(Btree *pBt, int pgno, int recursive){
  int rc;
  MemPage *pPage;
  int i, j;
  int nFree;
  u16 idx;

  char range[20];
  unsigned char payload[20];
  rc = sqlitepager_get(pBt->pPager, (Pgno)pgno, (void**)&pPage);

  if( rc ){
    return rc;
  }
  if( recursive ) printf("PAGE %d:\n", pgno);

  i = 0;
  idx = SWAB16(pBt, pPage->u.hdr.firstCell);


  while( idx>0 && idx<=SQLITE_USABLE_SIZE-MIN_CELL_SIZE ){
    Cell *pCell = (Cell*)&pPage->u.aDisk[idx];




    int sz = cellSize(pBt, pCell);
    sprintf(range,"%d..%d", idx, idx+sz-1);






    sz = NKEY(pBt, pCell->h) + NDATA(pBt, pCell->h);
    if( sz>sizeof(payload)-1 ) sz = sizeof(payload)-1;
    memcpy(payload, pCell->aPayload, sz);
    for(j=0; j<sz; j++){
      if( payload[j]<0x20 || payload[j]>0x7f ) payload[j] = '.';
    }
    payload[sz] = 0;
    printf(
      "cell %2d: i=%-10s chld=%-4d nk=%-4d nd=%-4d payload=%s\n",
      i, range, (int)pCell->h.leftChild, 
      NKEY(pBt, pCell->h), NDATA(pBt, pCell->h),
      payload
    );
    if( pPage->isInit && pPage->apCell[i]!=pCell ){
      printf("**** apCell[%d] does not match on prior entry ****\n", i);
    }
    i++;
    idx = SWAB16(pBt, pCell->h.iNext);

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


    i++;
  }
  if( idx!=0 ){
    printf("ERROR: next freeblock index out of range: %d\n", idx);
  }
  if( recursive && pPage->u.hdr.rightChild!=0 ){
    idx = SWAB16(pBt, pPage->u.hdr.firstCell);
    while( idx>0 && idx<SQLITE_USABLE_SIZE-MIN_CELL_SIZE ){
      Cell *pCell = (Cell*)&pPage->u.aDisk[idx];
      fileBtreePageDump(pBt, SWAB32(pBt, pCell->h.leftChild), 1);
      idx = SWAB16(pBt, pCell->h.iNext);
    }
    fileBtreePageDump(pBt, SWAB32(pBt, pPage->u.hdr.rightChild), 1);
  }
  sqlitepager_unref(pPage);
  return SQLITE_OK;
}
#endif

#ifdef SQLITE_TEST
................................................................................
**
** This routine is used for testing and debugging only.
*/
static int fileBtreeCursorDump(BtCursor *pCur, int *aResult){
  int cnt, idx;
  MemPage *pPage = pCur->pPage;
  Btree *pBt = pCur->pBt;

  aResult[0] = sqlitepager_pagenumber(pPage);
  aResult[1] = pCur->idx;
  aResult[2] = pPage->nCell;
  if( pCur->idx>=0 && pCur->idx<pPage->nCell ){
    aResult[3] = cellSize(pBt, pPage->apCell[pCur->idx]);
    aResult[6] = SWAB32(pBt, pPage->apCell[pCur->idx]->h.leftChild);
  }else{
    aResult[3] = 0;
    aResult[6] = 0;
  }
  aResult[4] = pPage->nFree;
  cnt = 0;
  idx = SWAB16(pBt, pPage->u.hdr.firstFree);
  while( idx>0 && idx<SQLITE_USABLE_SIZE ){
    cnt++;
    idx = SWAB16(pBt, ((FreeBlk*)&pPage->u.aDisk[idx])->iNext);
  }
  aResult[5] = cnt;
  aResult[7] = SWAB32(pBt, pPage->u.hdr.rightChild);
  return SQLITE_OK;
}
#endif

/*
** Return the pager associated with a BTree.  This routine is used for
** testing and debugging only.
................................................................................
  int iPage,            /* Page number for first page in the list */
  int N,                /* Expected number of pages in the list */
  char *zContext        /* Context for error messages */
){
  int i;
  char zMsg[100];
  while( N-- > 0 ){
    OverflowPage *pOvfl;
    if( iPage<1 ){
      sprintf(zMsg, "%d pages missing from overflow list", N+1);
      checkAppendMsg(pCheck, zContext, zMsg);
      break;
    }
    if( checkRef(pCheck, iPage, zContext) ) break;
    if( sqlitepager_get(pCheck->pPager, (Pgno)iPage, (void**)&pOvfl) ){
      sprintf(zMsg, "failed to get page %d", iPage);
      checkAppendMsg(pCheck, zContext, zMsg);
      break;
    }
    if( isFreeList ){
      FreelistInfo *pInfo = (FreelistInfo*)pOvfl->aPayload;
      int n = SWAB32(pCheck->pBt, pInfo->nFree);
      for(i=0; i<n; i++){
        checkRef(pCheck, SWAB32(pCheck->pBt, pInfo->aFree[i]), zContext);

      }
      N -= n;
    }
    iPage = SWAB32(pCheck->pBt, pOvfl->iNext);
    sqlitepager_unref(pOvfl);
  }
}

/*
** Return negative if zKey1<zKey2.
** Return zero if zKey1==zKey2.
................................................................................

  /* Check that the page exists
  */
  cur.pBt = pBt = pCheck->pBt;
  if( iPage==0 ) return 0;
  if( checkRef(pCheck, iPage, zParentContext) ) return 0;
  sprintf(zContext, "On tree page %d: ", iPage);
  if( (rc = sqlitepager_get(pCheck->pPager, (Pgno)iPage, (void**)&pPage))!=0 ){
    sprintf(zMsg, "unable to get the page. error code=%d", rc);
    checkAppendMsg(pCheck, zContext, zMsg);
    return 0;
  }
  if( (rc = initPage(pBt, pPage, (Pgno)iPage, pParent))!=0 ){
    sprintf(zMsg, "initPage() returns error code %d", rc);
    checkAppendMsg(pCheck, zContext, zMsg);
    sqlitepager_unref(pPage);
    return 0;
  }



  /* Check out all the cells.
  */
  depth = 0;
  if( zLowerBound ){
    zKey1 = sqliteMalloc( nLower+1 );
    memcpy(zKey1, zLowerBound, nLower);
................................................................................
    }else if( hit[i]>1 ){
      sprintf(zMsg, "Multiple uses for byte %d of page %d", i, iPage);
      checkAppendMsg(pCheck, zMsg, 0);
      break;
    }
  }

  /* Check that free space is kept to a minimum
  */
#if 0
  if( pParent && pParent->nCell>2 && pPage->nFree>3*SQLITE_USABLE_SIZE/4 ){
    sprintf(zMsg, "free space (%d) greater than max (%d)", pPage->nFree,
       SQLITE_USABLE_SIZE/3);
    checkAppendMsg(pCheck, zContext, zMsg);
  }
#endif

  sqlitepager_unref(pPage);
  return depth;
}

/*
** This routine does a complete check of the given BTree file.  aRoot[] is
** an array of pages numbers were each page number is the root page of
** a table.  nRoot is the number of entries in aRoot.







|







 







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










|
>




>





<







 







>







 







|







 







|







 







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







 







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







 







>
>

>
|
|
<
<
<
|
>


<
|
<
|
|


|









|
<







 







|







 







|







 







|
|







 







|












|







 







|







 







|
>
>
>
>
>
>







 







|







 







|
|







 







|
<

|
>










>

>










>
>
>
>
>







 







|

>


|
|
>


|

|


|




|
>
>






|

|
>
>
>

<
>

<
>







 







|


|
|
|
>
>

|







 







|



|

>

|




|

|
|






|



|
|
<
|
<
>

|
>
|
|
<

<
>



|
|
|
|




|
>
>
>
>
>
>


>

|
>
>

|
|

|
|
|

|







 







|





<
<
<
<
<

|

|









|

>











<


>



|
|


<
|

>





|
>
|
<
|




|
|
<







 







>
|
>
|
|
|






|


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

<
>
>

<
<
|
<
<

<
>
|

|







 







<
<
|

|



|

|
|
<
<
<
<
<
<



|




|





>
|
<

|



|
>









|


|







 







|

|
>

<
>



|

|





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







>
>
>
|






>
>
>
>
>
>
>


>

|

|
|



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








|





>


|










|











>
>











|






|

|







 







>
>


<





|

|
|
|
|
>
>
>
>





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






|

|




|





<
<
<

|


|

<
<
<
<
|
<







 







|
>
>
>



|


<





>







 







>



|

|

|
>
>
>
>
>
>
|

<
>

<
>


<
>

|
|


>





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



|







 







|
|
>
>
|
<
>








|










|
|
|
|
|
|

<
|
|


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

>







 







|










|
>
>
>
>
>


|
|

<
>

|

|

<
<
<
<
<
>
>
>
|


|


<
>
|



|

|

|







 







|



|




|



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

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

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





>

>


<
<
<
<
>








|

>



|
>

|
<
|
<







 







>


<
>



|
>

<
>
>
|
<
>
>
>
>
|

>
>
>
>
>
>









|
<
<

|
|


<
>




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





|
|

|
|
|

|







 







>




|
|






|


|


|







 







|












|
<

<
>



|







 







|




|





>
>







 







<
<
<
<
<
<
<
<


|







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
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
...
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
...
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
...
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
...
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
...
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
...
684
685
686
687
688
689
690
691
692
693
694
695
696



697
698
699
700

701

702
703
704
705
706
707
708
709
710
711
712
713
714
715
716

717
718
719
720
721
722
723
...
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
...
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
...
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
....
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
....
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
....
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
....
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
....
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
....
2154
2155
2156
2157
2158
2159
2160
2161

2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
....
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268

2269
2270

2271
2272
2273
2274
2275
2276
2277
2278
....
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
....
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344

2345

2346
2347
2348
2349
2350
2351

2352

2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
....
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428





2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455

2456
2457
2458
2459
2460
2461
2462
2463
2464
2465

2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476

2477
2478
2479
2480
2481
2482
2483

2484
2485
2486
2487
2488
2489
2490
....
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530

2531
2532
2533


2534


2535

2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
....
2550
2551
2552
2553
2554
2555
2556


2557
2558
2559
2560
2561
2562
2563
2564
2565
2566






2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582

2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
....
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623

2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
























2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
....
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796

2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826





2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845



2846
2847
2848
2849
2850
2851




2852

2853
2854
2855
2856
2857
2858
2859
....
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898

2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
....
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939

2940
2941

2942
2943
2944

2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957

2958









2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
....
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991

2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018

3019
3020
3021
3022
3023











3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
....
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074

3075
3076
3077
3078
3079
3080





3081
3082
3083
3084
3085
3086
3087
3088
3089

3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
....
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154













3155



































3156


















































3157
3158
3159
3160
3161
3162
3163
3164
3165
3166




3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185

3186

3187
3188
3189
3190
3191
3192
3193
....
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209

3210
3211
3212
3213
3214
3215
3216

3217
3218
3219

3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241


3242
3243
3244
3245
3246

3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
....
3297
3298
3299
3300
3301
3302
3303
3304
3305
3306
3307
3308
3309
3310
3311
3312
3313
3314
3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
3327
3328
3329
3330
....
3395
3396
3397
3398
3399
3400
3401
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415

3416

3417
3418
3419
3420
3421
3422
3423
3424
3425
3426
3427
3428
....
3480
3481
3482
3483
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
3500
3501
3502
3503
3504
3505
3506
....
3574
3575
3576
3577
3578
3579
3580








3581
3582
3583
3584
3585
3586
3587
3588
3589
3590
** 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.107 2004/05/02 21:12:19 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
**      *     zero or more pages numbers of leaves
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include <assert.h>


/* Maximum page size.  The upper bound on this value is 65536 (a limit
** imposed by the 2-byte offset at the beginning of each cell.)  The
** maximum page size determines the amount of stack space allocated
** by many of the routines in this module.  On embedded architectures
** or any machine where memory and especially stack memory is limited,
** one may wish to chose a smaller value for the maximum page size.
*/
#ifndef MX_PAGE_SIZE
# define MX_PAGE_SIZE 1024
#endif

/* Individual entries or "cells" are limited in size so that at least
** this many cells will fit on one page.  Changing this value will result
** in an incompatible database.
*/
#define MN_CELLS_PER_PAGE 4

/* The following value is the maximum cell size assuming a maximum page
** size give above.
*/
#define MX_CELL_SIZE  ((MX_PAGE_SIZE-10)/MN_CELLS_PER_PAGE)

/* The maximum number of cells on a single page of the database.  This
** assumes a minimum cell size of 3 bytes.  Such small cells will be
** exceedingly rare, but they are possible.
*/
#define MX_CELL ((MX_PAGE_SIZE-10)/3)

/* Forward declarations */
typedef struct MemPage MemPage;

/*
** This is a magic string that appears at the beginning of every
** SQLite database in order to identify the file as a real database.
**                                  0123456789 123456 */
static const char zMagicHeader[] = "SQLite version 3";

/*
** Page type flags.  An ORed combination of these flags appear as the
** first byte of every BTree page.
*/
#define PTF_LEAF      0x01
#define PTF_ZERODATA  0x02
#define PTF_INTKEY    0x04
/* Idea for the future:  PTF_LEAFDATA */

/*
** As each page of the file is loaded into memory, an instance of the following
** structure is appended and initialized to zero.  This structure stores
** information about the page that is decoded from the raw file page.

**
** The pParent field points back to the parent page.  This allows us to
** walk up the BTree from any leaf to the root.  Care must be taken to
** unref() the parent page pointer when this page is no longer referenced.
** The pageDestructor() routine handles that chore.
*/
struct MemPage {
................................................................................
  u8 zeroData;                   /* True if zero data flag is set */
  u8 hdrOffset;                  /* 100 for page 1.  0 otherwise */
  Pgno pgno;                     /* Page number for this page */
  MemPage *pParent;              /* The parent of this page.  NULL for root */
  int idxParent;                 /* Index in pParent->aCell[] of this node */
  int nFree;                     /* Number of free bytes on the page */
  int nCell;                     /* Number of entries on this page */
  int nCellAlloc;                /* Number of slots allocated in aCell[] */
  unsigned char **aCell;         /* Pointer to start of each cell */
};

/*
** The in-memory image of a disk page has the auxiliary information appended
** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
** that extra information.
................................................................................
  int size;
  unsigned char *data;
#ifndef NDEBUG
  int cnt = 0;
#endif

  data = pPage->aData;
  assert( sqlitepager_iswriteable(data->aData) );
  assert( pPage->pBt );
  if( nByte<4 ) nByte = 4;
  if( pPage->nFree<nByte || pPage->isOverfull ) return 0;
  hdr = pPage->hdrOffset;
  if( data[hdr+5]>=252 ){
    defragmentPage(pPage);
  }
................................................................................
  int addr, pbegin, pend;
#ifndef NDEBUG
  int tsize = 0;          /* Total size of all freeblocks */
#endif
  unsigned char *data = pPage->aData;

  assert( pPage->pBt!=0 );
  assert( sqlitepager_iswriteable(data->aData) );
  assert( start>=pPage->hdrOffset+6+(pPage->leaf?0:4) );
  assert( end<=pPage->pBt->pageSize );
  if( size<4 ) size = 4;

  /* Add the space back into the linked list of freeblocks */
  addr = pPage->hdrOffset + 1;
  while( (pbegin = get2byte(&data[addr]))<start && pbegin>0 ){
................................................................................

#if 0
/*
** The following is the default comparison function for (non-integer)
** keys in the btrees.  This function returns negative, zero, or
** positive if the first key is less than, equal to, or greater than
** the second.
**
** The key consists of multiple fields.  Each field begins with a variable
** length integer which determines the field type and the number of bytes
** of key data to follow for that field.
**
**   initial varint     bytes to follow    type
**   --------------     ---------------    ---------------
**      0                     0            NULL
**      1                     1            signed integer
**      2                     2            signed integer
**      3                     4            signed integer
**      4                     8            signed integer
**      5                     8            IEEE float
**     6..12                               reserved for expansion
**    N>=12 and even       (N-12)/2        BLOB
**    N>=13 and odd        (N-13)/2        text
**
** For a particular database, text is always either UTF-8, UTF-16BE, or
** UTF-16LE.  Which of these three formats to use is determined by one
** of the meta values in the file header.
**
*/
static int keyComp(
  void *userData,
  int nKey1, const unsigned char *aKey1, 
  int nKey2, const unsigned char *aKey2,
){
................................................................................
  }
  return 0;

bad_key:
  return 1;
}
#endif

/*
** Resize the aCell[] array of the given page so that it is able to
** hold at least nNewSz entries.
**
** Return SQLITE_OK or SQLITE_NOMEM.
*/
static int resizeCellArray(MemPage *pPage, int nNewSz){
  if( pPage->nCellAlloc<nNewSize ){
    pPage->aCell = sqliteRealloc(pPage->aCell, nNewSz*sizeof(pPage->aCell[0]) );
    if( sqlite_malloc_failed ) return SQLITE_NOMEM;
    pPage->nCellAlloc = nNewSize;
  }
  return SQLITE_OK;
}

/*
** Initialize the auxiliary information for a disk block.
**
** The pParent parameter must be a pointer to the MemPage which
** is the parent of the page being initialized.  The root of a
** BTree has no parent and so for that page, pParent==NULL.
................................................................................
  MemPage *pPage,        /* The page to be initialized */
  MemPage *pParent       /* The parent.  Might be NULL */
){
  int c, pc, i, hdr;
  int sumCell = 0;       /* Total size of all cells */

  assert( pPage->pBt!=0 );
  assert( pParent==0 || pParent->pBt==pPage->pBt );
  assert( pPage->pgno==sqlitepager_pagenumber(pPage->aData) );
  assert( pPage->aData == &((unsigned char*)pPage)[pPage->pBt->pageSize] );
  assert( pPage->isInit==0 || pPage->pParent==pParent );
  if( pPage->isInit ) return SQLITE_OK;
  assert( pPage->pParent==0 );



  pPage->pParent = pParent;
  if( pParent ){
    sqlitepager_ref(pParent->aData);
  }

  pPage->nCell = pPage->nCellAlloc = 0;

  pPage->hdrOffset = hdr = pPage->pgno==1 ? 100 : 0;
  c = pPage->aData[hdr];
  pPage->intKey = (c & PTF_INTKEY)!=0;
  pPage->zeroData = (c & PTF_ZERODATA)!=0;
  pPage->leaf = (c & PTF_LEAF)!=0;

  /* Initialize the cell count and cell pointers */
  pc = get2byte(&data[hdr+3]);
  while( pc>0 ){
    if( pc>=pBt->pageSize ) return SQLITE_CORRUPT;
    if( pPage->nCell>pBt->pageSize ) return SQLITE_CORRUPT;
    pPage->nCell++;
    pc = get2byte(&data[pc]);
  }
  if( resizeCellArray(pPage, pPage->nCell) ){

    return SQLITE_NOMEM;
  }
  pc = get2byte(&data[hdr+3]);
  for(i=0; pc>0; i++){
    pPage->aCell[i] = &data[pc];
    pc = get2byte(&data[pc]);
    sumCell += cellSize(pPage, &data[pc]);
................................................................................
*/
static void zeroPage(MemPage *pPage, int flags){
  unsigned char *data = pPage->aData;
  Btree *pBt = pPage->pBt;
  int hdr = pPage->hdrOffset;
  int first;

  assert( sqlitepager_iswriteable(data->aData) );
  memset(&data[hdr], 0, pBt->pageSize - hdr);
  data[hdr] = flags;
  first = hdr + 6 + 4*((flags&0x01)!=0);
  put2byte(&data[hdr+1], first);
  put2byte(&data[first+2], pBt->pageSize - first);
  sqliteFree(pPage->aCell);
  pPage->aCell = 0;
................................................................................
  return SQLITE_OK;
}

/*
** Release a MemPage.  This should be called once for each prior
** call to getPage.
*/
static void releasePage(MemPage *pPage){
  if( pPage ){
    assert( pPage->aData );
    assert( pPage->pBt );
    assert( &pPage->aData[pPage->pBt->pageSize]==(unsigned char*)pPage );
    sqlitepager_unref(pPage->aData);
  }
}
................................................................................
    *ppBtree = 0;
    return rc;
  }
  sqlitepager_set_destructor(pBt->pPager, pageDestructor);
  pBt->pCursor = 0;
  pBt->page1 = 0;
  pBt->readOnly = sqlitepager_isreadonly(pBt->pPager);
  pBt->pageSize = SQLITE_PAGE_SIZE;  /* FIX ME - read from header */
  pBt->maxLocal = (pBt->pageSize-10)/4-12;
  *ppBtree = pBt;
  return SQLITE_OK;
}

/*
** Close an open database and invalidate all cursors.
*/
................................................................................
  int rc;
  BtCursor *pCur, *pRing;

  if( pBt->readOnly && wrFlag ){
    *ppCur = 0;
    return SQLITE_READONLY;
  }
  if( pBt->pPage1==0 ){
    rc = lockBtree(pBt);
    if( rc!=SQLITE_OK ){
      *ppCur = 0;
      return rc;
    }
  }
  pCur = sqliteMalloc( sizeof(*pCur) );
  if( pCur==0 ){
    rc = SQLITE_NOMEM;
    goto create_cursor_exception;
  }
  pCur->pgnoRoot = (Pgno)iTable;
  rc = getPage(pBt, pCur->pgnoRoot, &pCur->pPage);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }
  rc = initPage(pCur->pPage, 0);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }
................................................................................
}

/*
** Set *pSize to the size of the buffer needed to hold the value of
** 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, u64 *pSize){
  MemPage *pPage;

  pPage = pCur->pPage;
  assert( pPage!=0 );
................................................................................
** If pCur is not pointing to a valid entry return 0.
**
** The pointer returned is ephemeral.  The key may move
** or be destroyed on the next call to any Btree routine.
**
** This routine is used to do quick key comparisons in the
** common case where the entire key fits in the payload area
** of a cell and does not overflow onto secondary pages.  If
** this routine returns 0 for a valid cursor, the caller will
** need to allocate a buffer big enough to hold the whole key
** then use sqlite3BtreeKey() to copy the key value into the
** buffer.  That is substantially slower.  But fortunately,
** most keys are small enough to fit in the payload area so
** the slower method is rarely needed.
*/
void *sqlite3BtreeKeyFetch(BtCursor *pCur){
  unsigned char *aPayload;
  MemPage *pPage;
  Btree *pBt;
  u64 nData, nKey;

................................................................................
  pCur->pPage = pRoot;
  pCur->idx = 0;
  if( pRoot->nCell==0 && !pRoot->leaf ){
    Pgno subpage;
    assert( pRoot->pgno==1 );
    subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+6]);
    assert( subpage>0 );
    rc = moveToChild(pCur, subpage);
  }
  return rc;
}

/*
** Move the cursor down to the left-most leaf entry beneath the
** entry to which it is currently pointing.
................................................................................
    if( rc ) return rc;
    sqlitepager_unref(pOvfl->aData);
  }
  return SQLITE_OK;
}

/*
** Compute the number of bytes required by a cell header.  Fill in
** the nData and nKey values of the header that pHeader points to.
*/
static int makeCellHeader(
  MemPage *pPage,          /* The page that will contain the cell */
  u64 nKey,                /* Size of key, or the key value if intKey */
  int nData,               /* Size of data.  Ignored for zerodata */
  unsigned char *pHeader   /* Write header bytes here */
){
................................................................................
/*
** Fill in the payload section of a cell into the space provided.  If
** the payload will not completely fit in the cell, allocate additional
** overflow pages and fill them in.
*/
static int fillInCell(
  MemPage *pPage,                /* The page that contains the cell */
  unsigned char *pCell,          /* Complete text of the cell */

  const void *pKey, u64 nKey,    /* The key */
  const void *pData,int nData,   /* The data */
  int *pnSize                    /* Write cell size here */
){
  int nPayload;
  const void *pSrc;
  int nSrc, nSrc2;
  int spaceLeft;
  MemPage *pOvfl = 0;
  unsigned char *pPrior;
  unsigned char *pPayload;
  Btree *pBt = pPage->pBt;
  Pgno pgnoOvfl = 0;
  int nHeader;

  nHeader = makeCellHeader(pPage, pCell, nKey, nData);
  nPayload = nData;
  if( pPage->intKey ){
    pSrc = pData;
    nSrc = nData;
    nSrc2 = 0;
  }else{
    nPayload += nKey;
    pSrc = pKey;
    nSrc = nKey;
  }
  if( nPayload>pBt->maxLocal ){
    *pnSize = nHeader + pBt->maxLocal + 4;
  }else{
    *pnSize = nHeader + nPayload;
  }
  spaceLeft = pBt->maxLocal;
  pPayload = &pCell[nHeader];
  pPrior = &pPayload[pBt->maxLocal];

  while( nPayload>0 ){
    if( spaceLeft==0 ){
      rc =  allocatePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl);
................................................................................
}

/*
** Change the MemPage.pParent pointer on the page whose number is
** given in the second argument so that MemPage.pParent holds the
** pointer in the third argument.
*/
static void reparentPage(Btree *pBt, Pgno pgno, MemPage *pNewParent, int idx){
  MemPage *pThis;
  unsigned char *aData;

  if( pgno==0 ) return;
  assert( pBt->pPager!=0 );
  aData = sqlitepager_lookup(pBt->pPager, pgno);
  pThis = (MemPage)&aData[pBt->pageSize];
  if( pThis && pThis->isInit ){
    if( pThis->pParent!=pNewParent ){
      if( pThis->pParent ) sqlitepager_unref(pThis->pParent->aData);
      pThis->pParent = pNewParent;
      if( pNewParent ) sqlitepager_ref(pNewParent->aData);
    }
    pThis->idxParent = idx;
    sqlitepager_unref(aData);
  }
}

/*
** Change the pParent pointer of all children of pPage to point back
** to pPage.
**
** In other words, for every child of pPage, invoke reparentPage()
** to make sure that each child knows that pPage is its parent.
**
** This routine gets called after you memcpy() one page into
** another.
*/
static void reparentChildPages(MemPage *pPage){
  int i;
  Btree *pBt;

  if( pPage->left ) return;
  pBt = pPage->pBt;
  for(i=0; i<pPage->nCell; i++){

    reparentPage(pBt, get4byte(&pPage->aCell[i][2]), pPage, i);
  }

  reparentPage(pBt, get4byte(&pPage->aData[pPage->hdrOffset+6]), pPage, i);
  pPage->idxShift = 0;
}

/*
** Remove the i-th cell from pPage.  This routine effects pPage only.
** The cell content is not freed or deallocated.  It is assumed that
** the cell content has been copied someplace else.  This routine just
................................................................................
** "sz" must be the number of bytes in the cell.
**
** Do not bother maintaining the integrity of the linked list of Cells.
** Only the pPage->apCell[] array is important.  The relinkCellList() 
** routine will be called soon after this routine in order to rebuild 
** the linked list.
*/
static void dropCell(MemPage *pPage, int idx, int sz){
  int j;
  assert( idx>=0 && idx<pPage->nCell );
  assert( sz==cellSize(pPage, pPage->aCell[idx]) );
  assert( sqlitepager_iswriteable(pPage->aData) );
  assert( pPage->aCell[idx]>=pPage->aData );
  assert( pPage->aCell[idx]<&pPage->aData[pPage->pBt->pageSize-sz] );
  freeSpace(pPage, idx, sz);
  for(j=idx; j<pPage->nCell-1; j++){
    pPage->aCell[j] = pPage->aCell[j+1];
  }
  pPage->nCell--;
  pPage->idxShift = 1;
}

/*
** Insert a new cell on pPage at cell index "i".  pCell points to the
................................................................................
** and set pPage->isOverfull.  
**
** Do not bother maintaining the integrity of the linked list of Cells.
** Only the pPage->apCell[] array is important.  The relinkCellList() 
** routine will be called soon after this routine in order to rebuild 
** the linked list.
*/
static void insertCell(MemPage *pPage, int i, unsigned char *pCell, int sz){
  int idx, j;
  assert( i>=0 && i<=pPage->nCell );
  assert( sz==cellSize(pBt, pCell) );
  assert( sqlitepager_iswriteable(pPage->aData) );
  idx = allocateSpace(pBt, pPage, sz);
  resizeCellArray(pPage, pPage->nCell+1);
  for(j=pPage->nCell; j>i; j--){
    pPage->aCell[j] = pPage->aCell[j-1];
  }
  pPage->nCell++;
  if( idx<=0 ){
    pPage->isOverfull = 1;
    pPage->aCell[i] = pCell;
  }else{
    memcpy(&pPage->aData[idx], pCell, sz);
    pPage->aCell[i] = &pPage->aData[idx];
  }
  pPage->idxShift = 1;
}

/*
** Rebuild the linked list of cells on a page so that the cells
** occur in the order specified by the pPage->aCell[] array.  
** Invoke this routine once to repair damage after one or more
** invocations of either insertCell() or dropCell().
*/
static void relinkCellList(MemPage *pPage){
  int i, idxFrom;

  assert( sqlitepager_iswriteable(pPage->aData) );

  idxFrom = pPage->hdrOffset+3;
  for(i=0; i<pPage->nCell; i++){
    int idx = Addr(pPage->aCell[i]) - Addr(pPage);
    assert( idx>pPage->hdrOffset && idx<pPage->pBt->pageSize );
    put2byte(&pPage->aData[idxFrom], idx);
    idxFrom = idx;

  }

  put2byte(&pPage->aData[idxFrom], 0);
}

/*
** Make a copy of the contents of pFrom into pTo.  The pFrom->aCell[]
** pointers that point into pFrom->aData[] must be adjusted to point
** into pTo->aData[] instead.  But some pFrom->aCell[] entries might
** not point to pFrom->aData[].  Those are unchanged.
*/
static void copyPage(MemPage *pTo, MemPage *pFrom){
  uptr from, to;
  int i;
  int pageSize;
  int ofst;

  assert( pTo->hdrOffset==0 );
  ofst = pFrom->hdrOffset;
  pageSize = pTo->pBt->pageSize;
  memcpy(pTo->aData, &pFrom->aData[ofst], pageSize - ofst);
  pTo->pParent = 0;
  pTo->isInit = 1;
  resizeCellArray(pTo, pFrom->nCell);
  pTo->nCell = pFrom->nCell;
  pTo->nFree = pFrom->nFree + ofst;
  assert( pTo->aData[5]<155 );
  pTo->aData[5] += ofst;
  pTo->isOverfull = pFrom->isOverfull;
  to = Addr(pTo->aData);
  from = Addr(pFrom->aData);
  for(i=0; i<pTo->nCell; i++){
    uptr x = Addr(pFrom->aCell[i]);
    if( x>from && x<from+pageSize ){
      *((uptr*)&pTo->aCell[i]) = x + to - from;
    }else{
      pTo->aCell[i] = pFrom->aCell[i];
    }
  }
}

/*
** The following parameters determine how many adjacent pages get involved
** in a balancing operation.  NN is the number of neighbors on either side
................................................................................
** The number of siblings of pPage might be increased or decreased by
** one in an effort to keep pages between 66% and 100% full. The root page
** is special and is allowed to be less than 66% full. If pPage is 
** the root page, then the depth of the tree might be increased
** or decreased by one, as necessary, to keep the root page from being
** overfull or empty.
**
** This routine alwyas calls relinkCellList() on its input page regardless of
** whether or not it does any real balancing.  Client routines will typically
** invoke insertCell() or dropCell() before calling this routine, so we
** need to call relinkCellList() to clean up the mess that those other
** routines left behind.
**





** Note that when this routine is called, some of the Cells on pPage
** might not actually be stored in pPage->aData[].  This can happen
** if the page is overfull.  Part of the job of this routine is to
** make sure all Cells for pPage once again fit in pPage->aData[].
**
** In the course of balancing the siblings of pPage, the parent of pPage
** might become overfull or underfull.  If that happens, then this routine
** is called recursively on the parent.
**
** If this routine fails for any reason, it might leave the database
** in a corrupted state.  So if this routine fails, the database should
** be rolled back.
*/
static int balance(MemPage *pPage){
  MemPage *pParent;            /* The parent of pPage */
  Btree *pBt;                  /* The whole database */
  int nCell;                   /* Number of cells in apCell[] */
  int nOld;                    /* Number of pages in apOld[] */
  int nNew;                    /* Number of pages in apNew[] */
  int nDiv;                    /* Number of cells in apDiv[] */
  int i, j, k;                 /* Loop counters */
  int idx;                     /* Index of pPage in pParent->apCell[] */
  int nxDiv;                   /* Next divider slot in pParent->apCell[] */
  int rc;                      /* The return code */
  int iCur;                    /* apCell[iCur] is the cell of the cursor */
  MemPage *pOldCurPage;        /* The cursor originally points to this page */
  int subtotal;                /* Subtotal of bytes in cells on one page */

  MemPage *apOld[NB];          /* pPage and up to two siblings */
  Pgno pgnoOld[NB];            /* Page numbers for each page in apOld[] */
  MemPage *apCopy[NB];         /* Private copies of apOld[] pages */
  MemPage *apNew[NB+1];        /* pPage and up to NB siblings after balancing */
  Pgno pgnoNew[NB+1];          /* Page numbers for each page in apNew[] */
  int idxDiv[NB];              /* Indices of divider cells in pParent */
  u8 *apDiv[NB];               /* Divider cells in pParent */
  u8 aTemp[NB][MX_CELL_SIZE];  /* Temporary holding area for apDiv[] */
  int cntNew[NB+1];            /* Index in apCell[] of cell after i-th page */
  int szNew[NB+1];             /* Combined size of cells place on i-th page */

  u8 *apCell[(MX_CELL+2)*NB];  /* All cells from pages being balanced */
  int szCell[(MX_CELL+2)*NB];  /* Local size of all cells */
  u8 aCopy[NB][MX_PAGE_SIZE+sizeof(MemPage)];  /* Space for apCopy[] */

  /* 
  ** Return without doing any work if pPage is neither overfull nor
  ** underfull.
  */
  assert( sqlitepager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
  if( !pPage->isOverfull && pPage->nFree<pBt->pageSize/2 && pPage->nCell>=2){

    relinkCellList(pPage);
    return SQLITE_OK;
  }

  /*
  ** Find the parent of the page to be balanced.  If there is no parent,
  ** it means this page is the root page and special rules apply.

  */
  pParent = pPage->pParent;
  if( pParent==0 ){
    Pgno pgnoChild;
    MemPage *pChild;
    assert( pPage->isInit );
    if( pPage->nCell==0 ){
................................................................................
        relinkCellList(pPage);
      }else{
        /* The root page is empty but has one child.  Transfer the
        ** information from that one child into the root page if it 
        ** will fit.  This reduces the depth of the BTree by one.
        **
        ** If the root page is page 1, it has less space available than
        ** its child (due to the 100 byte header that occurs at the beginning
        ** of the database fle), so it might not be able to hold all of the 
        ** information currently contained in the child.  If this is the 
        ** case, then do not do the transfer.  Leave page 1 empty except
        ** for the right-pointer to the child page.  The child page becomes
        ** the virtual root of the tree.
        */
        pgnoChild = get4byte(pPage->aData[pPage->hdrOffset+6]);
        assert( pgnoChild>0 && pgnoChild<=sqlit3pager_pagecount(pBt->pPager) );
        rc = getPage(pBt, pgnoChild, &pChild);
        if( rc ) return rc;
        if( pPage->pgno==1 ){
          rc = initPage(pChild, pPage);
          if( rc ) return rc;
          if( pChild->nFree>=100 ){
            /* The child information will fit on the root page, so do the
            ** copy */
            zeroPage(pPage, pChild->aData[0]);
            resizeCellArray(pPage, pChild->nCell);
            for(i=0; i<pChild->nCell; i++){
              insertCell(pPage, i, pChild->aCell[i], 
                        cellSize(pChild, pChild->aCell[i]));
            }
            freePage(pChild);
          }else{
            /* The child has more information that will fit on the root.
            ** The tree is already balanced.  Do nothing. */
          }
        }else{
          memcpy(pPage, pChild, pBt->pageSize);
          pPage->isInit = 0;

          pPage->pParent = 0;
          rc = initPage(pPage, 0);
          assert( rc==SQLITE_OK );


          freePage(pChild);


        }

        reparentChildPages(pPage);
        releasePage(pChild);
      }else{
        relinkCellList(pPage);
      }
      return SQLITE_OK;
    }
    if( !pPage->isOverfull ){
      /* It is OK for the root page to be less than half full.
      */
      relinkCellList(pBt, pPage);
................................................................................
    ** If we get to here, it means the root page is overfull.
    ** When this happens, Create a new child page and copy the
    ** contents of the root into the child.  Then make the root
    ** page an empty page with rightChild pointing to the new
    ** child.  Then fall thru to the code below which will cause
    ** the overfull child page to be split.
    */


    rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno);
    if( rc ) return rc;
    assert( sqlitepager_iswriteable(pChild->aData) );
    copyPage(pChild, pPage);
    pChild->pParent = pPage;
    pChild->idxParent = 0;
    sqlitepager_ref(pPage->aData);
    pChild->isOverfull = 1;
    zeroPage(pPage, pPage->aData[pPage->hdrOffset] & ~PTF_LEAF);
    put4byte(&pPage->aData[pPage->hdrOffset+6], pChild->pgno);






    pParent = pPage;
    pPage = pChild;
  }
  rc = sqlitepager_write(pParent->aData);
  if( rc ) return rc;
  assert( pParent->isInit );
  
  /*
  ** Find the cell in the parent page whose left child points back
  ** to pPage.  The "idx" variable is the index of that cell.  If pPage
  ** is the rightmost child of pParent then set idx to pParent->nCell 
  */
  if( pParent->idxShift ){
    Pgno pgno, swabPgno;
    pgno = pPage->pgno;
    assert( pgno==sqlitepager_pagenumber(pPage->aData) );

    for(idx=0; idx<pParent->nCell; idx++){
      if( get4byte(pParent->aCell[idx][2])==pgno ){
        break;
      }
    }
    assert( idx<pParent->nCell
             || get4byte(&pParent->aData[pParent->hdrOffset+6])==pgno );
  }else{
    idx = pPage->idxParent;
  }

  /*
  ** Initialize variables so that it will be safe to jump
  ** directly to balance_cleanup at any moment.
  */
  nOld = nNew = 0;
  sqlitepager_ref(pParent->aData);

  /*
  ** Find sibling pages to pPage and the cells in pParent that divide
  ** the siblings.  An attempt is made to find NN siblings on either
  ** side of pPage.  More siblings are taken from one side, however, if
  ** pPage there are fewer than NN siblings on the other side.  If pParent
  ** has NB or fewer children then all children of pParent are taken.
  */
  nxDiv = idx - NN;
  if( nxDiv + NB > pParent->nCell ){
................................................................................
  if( nxDiv<0 ){
    nxDiv = 0;
  }
  nDiv = 0;
  for(i=0, k=nxDiv; i<NB; i++, k++){
    if( k<pParent->nCell ){
      idxDiv[i] = k;
      apDiv[i] = pParent->aCell[k];
      nDiv++;
      assert( !pParent->left );
      pgnoOld[i] = get4byte(&apDev[i][2]);
    }else if( k==pParent->nCell ){

      pgnoOld[i] = get4byte(&pParent->aData[pParent->hdrOffset+6]);
    }else{
      break;
    }
    rc = getPage(pBt, pgnoOld[i], &apOld[i]);
    if( rc ) goto balance_cleanup;
    rc = initPage(apOld[i], pParent);
    if( rc ) goto balance_cleanup;
    apOld[i]->idxParent = k;
    nOld++;
  }

























  /*
  ** Make copies of the content of pPage and its siblings into aOld[].
  ** The rest of this function will use data from the copies rather
  ** that the original pages since the original pages will be in the
  ** process of being overwritten.
  */
  for(i=0; i<nOld; i++){
    apCopy[i] = (MemPage*)&aCopy[i+1][-sizeof(MemPage)];
    memset(apCopy[i], 0, sizeof(MemPage));
    apCopy[i]->aData = &((u8*)apCopy)[-pBt->pageSize];
    copyPage(apCopy[i], apOld[i]);
  }

  /*
  ** Load pointers to all cells on sibling pages and the divider cells
  ** into the local apCell[] array.  Make copies of the divider cells
  ** into aTemp[] and remove the the divider Cells from pParent.
  **
  ** If the siblings are on leaf pages, then the child pointers of the
  ** divider cells are stripped from the cells before they are copied
  ** into aTemp[].  In this wall, all cells in apCell[] are without
  ** child pointers.  If siblings are not leaves, then all cell in
  ** apCell[] include child pointers.  Either way, all cells in apCell[]
  ** are alike.
  */
  nCell = 0;
  leafCorrection = pPage->leaf*4;
  for(i=0; i<nOld; i++){
    MemPage *pOld = apCopy[i];
    for(j=0; j<pOld->nCell; j++){
      apCell[nCell] = pOld->aCell[j];
      szCell[nCell] = cellSize(pOld, apCell[nCell]);
      nCell++;
    }
    if( i<nOld-1 ){
      szCell[nCell] = cellSize(pParent, apDiv[i]) - leafCorrection;
      memcpy(aTemp[i], apDiv[i], szCell[nCell] + leafCorrection);
      apCell[nCell] = &aTemp[i][leafCorrection];
      dropCell(pParent, nxDiv, szCell[nCell]);
      assert( get4byte(&apCell[nCell][2])==pgnoOld[i] );
      if( !pOld->leaf ){
        assert( leafCorrection==0 );
        /* The right pointer of the child page pOld becomes the left
        ** pointer of the divider cell */
        memcpy(&apCell[nCell][2], &pOld->aData[pOld->hdrOffset+6], 4);
      }else{
        assert( leafCorrection==4 );
      }
      nCell++;
    }
  }

  /*
  ** Figure out the number of pages needed to hold all nCell cells.
  ** Store this number in "k".  Also compute szNew[] which is the total
  ** size of all cells on the i-th page and cntNew[] which is the index
  ** in apCell[] of the cell that divides page i from page i+1.  
  ** cntNew[k] should equal nCell.
  **
  ** This little patch of code is critical for keeping the tree
  ** balanced. 
  */
  usableSpace = pBt->pageSize - 10 + leafCorrection;
  for(subtotal=k=i=0; i<nCell; i++){
    subtotal += szCell[i];
    if( subtotal > usableSpace ){
      szNew[k] = subtotal - szCell[i];
      cntNew[k] = i;
      subtotal = 0;
      k++;
    }
  }
  szNew[k] = subtotal;
  cntNew[k] = nCell;
  k++;
  for(i=k-1; i>0; i--){
    while( szNew[i]<usableSpace/2 ){
      cntNew[i-1]--;
      assert( cntNew[i-1]>0 );
      szNew[i] += szCell[cntNew[i-1]];
      szNew[i-1] -= szCell[cntNew[i-1]-1];
    }
  }
  assert( cntNew[0]>0 );

  /*
  ** Allocate k new pages.  Reuse old pages where possible.
  */
  assert( pPage->pgno>1 );
  pageFlags = pPage->aData[0];
  for(i=0; i<k; i++){
    if( i<nOld ){
      apNew[i] = apOld[i];
      pgnoNew[i] = pgnoOld[i];
      apOld[i] = 0;
      sqlitepager_write(apNew[i]);
    }else{
      rc = allocatePage(pBt, &apNew[i], &pgnoNew[i], pgnoNew[i-1]);
      if( rc ) goto balance_cleanup;
    }
    nNew++;
    zeroPage(apNew[i], pageFlags);
    apNew[i]->isInit = 1;
  }

  /* Free any old pages that were not reused as new pages.
  */
  while( i<nOld ){
    rc = freePage(apOld[i]);
    if( rc ) goto balance_cleanup;
    sqlitepager_unref(apOld[i]->aData);
    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
................................................................................
  /*
  ** 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];
    assert( pNew->pgno==pgnoNew[i] );
    resizeCellArray(pNew, cntNew[i] - j);
    while( j<cntNew[i] ){
      assert( pNew->nFree>=szCell[j] );

      insertCell(pBt, pNew, pNew->nCell, apCell[j], szCell[j]);
      j++;
    }
    assert( pNew->nCell>0 );
    assert( !pNew->isOverfull );
    relinkCellList(pNew);
    if( i<nNew-1 && j<nCell ){
      u8 *pCell = apCell[j];
      if( !pNew->leaf ){
        memcpy(&pNew->aData[6], &apCell[j][2], 4);
      }else{
        pCell -= 4;
      }
      insertCell(pParent, nxDiv, pCell, szCell[j]+leafCorrection);
      put4byte(&pParent->aCell[nxDiv][2], pNew->pgno);
      j++;
      nxDiv++;
    }
  }
  assert( j==nCell );
  if( (pageFlags & PTF_LEAF)==0 ){
    memcpy(&apNew[nNew-1]->aData[6], &apCopy[nOld-1]->aData[6], 4);
  }
  if( nxDiv==pParent->nCell ){
    /* Right-most sibling is the right-most child of pParent */
    put4byte(&pParent->aData[pParent->hdrOffset+6], pgnoNew[nNew-1]);
  }else{
    /* Right-most sibling is the left child of the first entry in pParent
    ** past the right-most divider entry */
    put4byte(&pParent->apCell[nxDiv][2], pgnoNew[nNew-1]);





  }

  /*
  ** Reparent children of all cells.
  */
  for(i=0; i<nNew; i++){
    reparentChildPages(apNew[i]);
  }
  reparentChildPages(pParent);

  /*
  ** balance the parent page.
  */
  rc = balance(pParent);

  /*
  ** Cleanup before returning.
  */
balance_cleanup:



  for(i=0; i<nOld; i++){
    if( apOld[i]!=0 ) sqlitepager_unref(apOld[i]->aData);
  }
  for(i=0; i<nNew; i++){
    sqlitepager_unref(apNew[i]->aData);
  }




  sqlitepager_unref(pParent->aData);

  return rc;
}

/*
** This routine checks all cursors that point to the same table
** as pCur points to.  If any of those cursors were opened with
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
................................................................................
  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 database the record should be inserted into.  The cursor
** is left pointing at a random location.
**
** For an INTKEY table, only the nKey value of the key is used.  pKey is
** ignored.  For a ZERODATA table, the pData and nData are both ignored.
*/
int sqlite3BtreeInsert(
  BtCursor *pCur,                /* Insert data into the table of this cursor */
  const void *pKey, u64 nKey,    /* The key of the new record */
  const void *pData, int nData   /* The data of the new record */
){

  int rc;
  int loc;
  int szNew;
  MemPage *pPage;
  Btree *pBt = pCur->pBt;
  unsigned char newCell[MX_CELL_SIZE], *oldCell;

  if( pCur->pPage==0 ){
    return SQLITE_ABORT;  /* A rollback destroyed this cursor */
  }
  if( !pBt->inTrans || nKey+nData==0 ){
    /* Must start a transaction before doing an insert */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
................................................................................
  }
  if( checkReadLocks(pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc);
  if( rc ) return rc;
  pPage = pCur->pPage;
  assert( nData==0 || pPage->zeroData!=0 );
  assert( pPage->isInit );
  rc = sqlitepager_write(pPage);
  if( rc ) return rc;
  rc = fillInCell(pPage, &newCell, pKey, nKey, pData, nData, &szNew);
  if( rc ) return rc;
  assert( szNew==cellSize(pPage, newCell) );
  if( loc==0 ){
    int szOld
    assert( pCur->idx>=0 && pCur->idx<pPage->nPage );
    oldCell = pPage->aCell[pCur->idx];
    if( !pPage->leaf ){
      memcpy(&newCell[2], &oldCell[2], 4);
    }
    szOld = cellSize(pPage, oldCell);
    rc = clearCell(pPage, oldCell);
    if( rc ) return rc;

    dropCell(pPage, pCur->idx, szOld);
  }else if( loc<0 && pPage->nCell>0 ){

    assert( pPage->leaf );
    pCur->idx++;
  }else{

    assert( pPage->leaf );
  }
  insertCell(pPage, pCur->idx, &newCell, szNew);
  rc = balance(pPage);
  /* sqliteBtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  moveToRoot(pCur);
  pCur->eSkip = SKIP_INVALID;
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor

** is left pointing at a random location.









*/
int sqlite3BtreeDelete(BtCursor *pCur){
  MemPage *pPage = pCur->pPage;
  unsigned char *pCell;
  int rc;
  Pgno pgnoChild;
  Btree *pBt = pCur->pBt;

  assert( pPage->isInit );
  if( pCur->pPage==0 ){
    return SQLITE_ABORT;  /* A rollback destroyed this cursor */
................................................................................
    return SQLITE_PERM;   /* Did not open this cursor for writing */
  }
  if( checkReadLocks(pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlitepager_write(pPage);
  if( rc ) return rc;
  pCell = pPage->aCell[pCur->idx];
  if( !pPage->leaf ){
    pgnoChild = get4byte(&pCell[2]);
  }
  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;
    getTempCursor(pCur, &leafCur);
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc!=SQLITE_OK ){
      if( rc!=SQLITE_NOMEM ) rc = SQLITE_CORRUPT;
      return rc;
    }
    rc = sqlitepager_write(leafCur.pPage);
    if( rc ) return rc;
    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));
    pNext = leafCur.pPage->aCell[leafCur.idx];
    szNext = cellSize(leafCur.pPage, pNext);
    insertCell(pPage, pCur->idx, &pNext[-4], szNext+4);
    put4byte(&pNext[-2], pgnoChild);
    rc = balance(pPage);
    if( rc ) return rc;

    dropCell(leafCur.pPage, leafCur.idx, szNext);
    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);
  }else{
    dropCell(pPage, pCur->idx, cellSize(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.
**
................................................................................
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  if( pBt->readOnly ){
    return SQLITE_READONLY;
  }
  rc = allocatePage(pBt, &pRoot, &pgnoRoot, 0);
  if( rc ) return rc;
  assert( sqlitepager_iswriteable(pRoot->aData) );
  zeroPage(pBt, pRoot);
  sqlitepager_unref(pRoot);
  *piTable = (int)pgnoRoot;
  return SQLITE_OK;
}

/*
** Erase the given database page and all its children.  Return
** the page to the freelist.
*/
static int clearDatabasePage(
  Btree *pBt,           /* The BTree that contains the table */
  Pgno pgno,            /* Page number to clear */
  MemPage *pParent,     /* Parent page.  NULL for the root */
  int freePageFlag      /* Deallocate page if true */
){
  MemPage *pPage;
  int rc;
  unsigned char *pCell;
  int i;


  rc = getPage(pBt, pgno, &pPage);
  if( rc ) return rc;
  rc = sqlitepager_write(pPage->aData);
  if( rc ) return rc;
  rc = initPage(pPage, pParent);
  if( rc ) return rc;





  for(i=0; i<pPage->nCell; i++){
    pCell = pPage->aCell[i];
    if( !pPage->leaf ){
      rc = clearDatabasePage(pBt, get4byte(&pCell[2]), 1);
      if( rc ) return rc;
    }
    rc = clearCell(pPage, pCell);
    if( rc ) return rc;
  }

  if( !pPage->left ){
    rc = clearDatabasePage(pBt, get4byte(&pPage->aData[6]), 1);
    if( rc ) return rc;
  }
  if( freePageFlag ){
    rc = freePage(pPage);
  }else{
    zeroPage(pPage, pPage->aData[0]);
  }
  releasePage(pPage);
  return rc;
}

/*
** Delete all information from a single table in the database.
*/
int sqlite3BtreeClearTable(Btree *pBt, int iTable){
................................................................................
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    if( pCur->pgnoRoot==(Pgno)iTable ){
      return SQLITE_LOCKED;  /* Cannot drop a table that has a cursor */
    }
  }
  rc = getPage(pBt, (Pgno)iTable, pPage);
  if( rc ) return rc;
  rc = sqlite3BtreeClearTable(pBt, iTable);
  if( rc ) return rc;
  if( iTable>1 ){
    rc = freePage(pBt, pPage, iTable);
  }else{
    zeroPage(pBt, pPage);
  }
  releasePage(pPage);
  return rc;  
}


















































/*


















































** Read the meta-information out of a database file.
*/
int sqlite3BtreeGetMeta(Btree *pBt, int idx, u32 *pMeta){
  int rc;
  int i;
  unsigned char *pP1;

  assert( idx>=0 && idx<15 );
  rc = sqlitepager_get(pBt->pPager, 1, (void**)&pP1);
  if( rc ) return rc;




  *pMeta = get4byte(&pP1[40 + idx*4]);
  sqlitepager_unref(pP1);
  return SQLITE_OK;
}

/*
** Write meta-information back into the database.
*/
int sqlite3BtreeUpdateMeta(Btree *pBt, int idx, u32 iMeta){
  unsigned char *pP1;
  int rc, i;
  assert( idx>=0 && idx<15 );
  if( !pBt->inTrans ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  rc = sqlitepager_get(pBt->pPager, 1, (void**)&pP1);
  if( rc ) return rc;
  rc = sqlitepager_write(pP1);
  if( rc ) return rc;

  put4byte(&pP1[40 + idx*4], iMeta);

  return SQLITE_OK;
}

/******************************************************************************
** The complete implementation of the BTree subsystem is above this line.
** All the code the follows is for testing and troubleshooting the BTree
** subsystem.  None of the code that follows is used during normal operation.
................................................................................
#ifdef SQLITE_TEST
static int fileBtreePageDump(Btree *pBt, int pgno, int recursive){
  int rc;
  MemPage *pPage;
  int i, j;
  int nFree;
  u16 idx;
  int hdrOffset;
  char range[20];
  unsigned char payload[20];

  rc = getPage(pBt, (Pgno)pgno, &pPage);
  if( rc ){
    return rc;
  }
  printf("PAGE %d:  flags=0x%02x  frag=%d\n", pgno, pPage->aData[0],
    pPage->aData[5]);
  i = 0;

  hdrOffset = pgno==1 ? 100 : 0;
  idx = get2byte(&pPage->aData[hdrOffset+3]);
  while( idx>0 && idx<=pBt->pageSize ){

    u64 nData, nKey;
    int nHeader;
    Pgno child;
    unsigned char *pCell = &pPage->aData[idx];
    int sz = cellSize(pPage, pCell);
    sprintf(range,"%d..%d", idx, idx+sz-1);
    parseCellHeader(pPage, pCell, &nData, &nKey, &nHeader);
    if( pPage->leaf ){
      child = 0;
    }else{
      child = get4byte(&pCell[2]);
    }
    sz = NKEY(pBt, pCell->h) + NDATA(pBt, pCell->h);
    if( sz>sizeof(payload)-1 ) sz = sizeof(payload)-1;
    memcpy(payload, pCell->aPayload, sz);
    for(j=0; j<sz; j++){
      if( payload[j]<0x20 || payload[j]>0x7f ) payload[j] = '.';
    }
    payload[sz] = 0;
    printf(
      "cell %2d: i=%-10s chld=%-4d nk=%-4d nd=%-4d payload=%s\n",
      i, range, child, (int)nKey, (int)nData, payload


    );
    if( pPage->isInit && pPage->aCell[i]!=pCell ){
      printf("**** aCell[%d] does not match on prior entry ****\n", i);
    }
    i++;

    idx = get2byte(pCell);
  }
  if( idx!=0 ){
    printf("ERROR: next cell index out of range: %d\n", idx);
  }
  if( !pPage->leaf ){
    printf("right_child: %d\n", get4byte(&pPage->aData[6]));
  }
  nFree = 0;
  i = 0;
  idx = get2byte(&pPage->aData[hdrOffset+1]);
  while( idx>0 && idx<SQLITE_USABLE_SIZE ){
    int sz = get2byte(&pPage->aData[idx+2]);
    sprintf(range,"%d..%d", idx, idx+sz-1);
    nFree += sz;
    printf("freeblock %2d: i=%-10s size=%-4d total=%d\n",
       i, range, sz, nFree);
    idx = get2byte(&pPage->aData[idx]);
    i++;
  }
  if( idx!=0 ){
    printf("ERROR: next freeblock index out of range: %d\n", idx);
  }
  if( recursive && !pPage->left ){
    idx = get2byte(&pPage->aData[hdrOffset+3]);
    while( idx>0 && idx<SQLITE_USABLE_SIZE-MIN_CELL_SIZE ){
      unsigned char *pCell = &pPage->aData[idx];
      fileBtreePageDump(pBt, get4byte(&pPage->aData[idx+2]), 1);
      idx = get2byte(&pPage->aData[idx]);
    }
    fileBtreePageDump(pBt, get4byte(&pPage->aData[hdrOffset+6]), 1);
  }
  sqlitepager_unref(pPage);
  return SQLITE_OK;
}
#endif

#ifdef SQLITE_TEST
................................................................................
**
** This routine is used for testing and debugging only.
*/
static int fileBtreeCursorDump(BtCursor *pCur, int *aResult){
  int cnt, idx;
  MemPage *pPage = pCur->pPage;
  Btree *pBt = pCur->pBt;
  assert( pPage->isInit );
  aResult[0] = sqlitepager_pagenumber(pPage);
  aResult[1] = pCur->idx;
  aResult[2] = pPage->nCell;
  if( pCur->idx>=0 && pCur->idx<pPage->nCell ){
    aResult[3] = cellSize(pPage, pPage->aCell[pCur->idx]);
    aResult[6] = pPage->leaf ? 0 : get4byte(&pPage->aCell[pCur->idx][2]);
  }else{
    aResult[3] = 0;
    aResult[6] = 0;
  }
  aResult[4] = pPage->nFree;
  cnt = 0;
  idx = get2byte(&pPage->aData[pPage->hdrOffset+1]);
  while( idx>0 && idx<SQLITE_USABLE_SIZE ){
    cnt++;
    idx = get2byte(&pPage->aData[idx]);
  }
  aResult[5] = cnt;
  aResult[7] = pPage->leaf ? 0 : get4byte(&pPage->aData[pPage->hdrOffset+6]);
  return SQLITE_OK;
}
#endif

/*
** Return the pager associated with a BTree.  This routine is used for
** testing and debugging only.
................................................................................
  int iPage,            /* Page number for first page in the list */
  int N,                /* Expected number of pages in the list */
  char *zContext        /* Context for error messages */
){
  int i;
  char zMsg[100];
  while( N-- > 0 ){
    unsigned char *pOvfl;
    if( iPage<1 ){
      sprintf(zMsg, "%d pages missing from overflow list", N+1);
      checkAppendMsg(pCheck, zContext, zMsg);
      break;
    }
    if( checkRef(pCheck, iPage, zContext) ) break;
    if( sqlitepager_get(pCheck->pPager, (Pgno)iPage, (void**)&pOvfl) ){
      sprintf(zMsg, "failed to get page %d", iPage);
      checkAppendMsg(pCheck, zContext, zMsg);
      break;
    }
    if( isFreeList ){
      int n = get4byte(&pOvfl[4]);

      for(i=0; i<n; i++){

        checkRef(pCheck, get4byte(&pOvfl[8+i*4]), zContext);
      }
      N -= n;
    }
    iPage = get4byte(pOvfl);
    sqlitepager_unref(pOvfl);
  }
}

/*
** Return negative if zKey1<zKey2.
** Return zero if zKey1==zKey2.
................................................................................

  /* Check that the page exists
  */
  cur.pBt = pBt = pCheck->pBt;
  if( iPage==0 ) return 0;
  if( checkRef(pCheck, iPage, zParentContext) ) return 0;
  sprintf(zContext, "On tree page %d: ", iPage);
  if( (rc = getPage(pBt, (Pgno)iPage, &pPage))!=0 ){
    sprintf(zMsg, "unable to get the page. error code=%d", rc);
    checkAppendMsg(pCheck, zContext, zMsg);
    return 0;
  }
  if( (rc = initPage(pPage, pParent))!=0 ){
    sprintf(zMsg, "initPage() returns error code %d", rc);
    checkAppendMsg(pCheck, zContext, zMsg);
    sqlitepager_unref(pPage);
    return 0;
  }

#if 0

  /* Check out all the cells.
  */
  depth = 0;
  if( zLowerBound ){
    zKey1 = sqliteMalloc( nLower+1 );
    memcpy(zKey1, zLowerBound, nLower);
................................................................................
    }else if( hit[i]>1 ){
      sprintf(zMsg, "Multiple uses for byte %d of page %d", i, iPage);
      checkAppendMsg(pCheck, zMsg, 0);
      break;
    }
  }









#endif

  releasePage(pPage);
  return depth;
}

/*
** This routine does a complete check of the given BTree file.  aRoot[] is
** an array of pages numbers were each page number is the root page of
** a table.  nRoot is the number of entries in aRoot.