SQLite4
Check-in [f4df828793bf8266c3887ff17a9993210ebb3aa4]
Not logged in

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

Overview
SHA1 Hash:f4df828793bf8266c3887ff17a9993210ebb3aa4
Date: 2013-10-08 17:38:49
User: dan
Comment:Fix another bug in b-tree rebalancing.
Tags And Properties
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/bt_main.c

301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
....
1287
1288
1289
1290
1291
1292
1293

1294
1295
1296
1297
1298
1299
1300
....
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
....
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
      fprintf(f, "%02X", (int)pCell[j]);
    }
    if( btFlags(aData, nData) & BT_PGFLAGS_INTERNAL ){
      fprintf(f, "  child=%d ", (int)btGetU32(&pCell[j]));
    }
    fprintf(f, "\n");
  }


}

static int printPgToStderr(BtPage *pPg){
  printPage(stderr, sqlite4BtPagePgno(pPg), sqlite4BtPageData(pPg), 1024);
  return 0;
}
#endif
................................................................................
#endif

 rebalance_out:
  for(iPg=0; iPg<array_size(ctx.apPg); iPg++){
    sqlite4BtPageRelease(ctx.apPg[iPg]);
  }
  btFreeBuffer(pDb, ctx.pTmp);

  return rc;
}

static int btExtendTree(bt_cursor *pCsr){
  bt_db * const pDb = pCsr->pDb;
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  int rc;                         /* Return code */
................................................................................
    rc = sqlite4BtPageWrite(pLeaf);
    if( rc==SQLITE4_OK ){
      aData = sqlite4BtPageData(pLeaf);

      /* Make space within the cell pointer array */
      if( iCell!=nCell ){
        u8 *aFrom = btCellPtrFind(aData, pgsz, nCell-1);
        u8 *aTo = btCellPtrFind(aData, pgsz, nCell);
        memmove(aTo, aFrom, (nCell-iCell) * 2);
      }

      for(i=0; i<nKV; i++){
        /* Write the cell pointer */
        btPutU16(btCellPtrFind(aData, pgsz, iCell+i), iWrite);
      
................................................................................
      }
      if( rc==SQLITE4_OK ){
        u8 *a = sqlite4BtPageData(pChild);
        memcpy(aData, a, pgsz);
        rc = sqlite4BtPageTrim(pChild);
      }
    }
  }else if( nCell==0 || (nFree<(pgsz/3) && bLeaf==0) ){
    rc = btBalance(pCsr, bLeaf, 0, 0);
  }
  return rc;
}

/*
** Insert a new key/value pair or replace an existing one.







<
<







 







>







 







|







 







|







301
302
303
304
305
306
307


308
309
310
311
312
313
314
....
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
....
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
....
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
      fprintf(f, "%02X", (int)pCell[j]);
    }
    if( btFlags(aData, nData) & BT_PGFLAGS_INTERNAL ){
      fprintf(f, "  child=%d ", (int)btGetU32(&pCell[j]));
    }
    fprintf(f, "\n");
  }


}

static int printPgToStderr(BtPage *pPg){
  printPage(stderr, sqlite4BtPagePgno(pPg), sqlite4BtPageData(pPg), 1024);
  return 0;
}
#endif
................................................................................
#endif

 rebalance_out:
  for(iPg=0; iPg<array_size(ctx.apPg); iPg++){
    sqlite4BtPageRelease(ctx.apPg[iPg]);
  }
  btFreeBuffer(pDb, ctx.pTmp);
  sqlite4_free(pDb->pEnv, ctx.anCellSz);
  return rc;
}

static int btExtendTree(bt_cursor *pCsr){
  bt_db * const pDb = pCsr->pDb;
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  int rc;                         /* Return code */
................................................................................
    rc = sqlite4BtPageWrite(pLeaf);
    if( rc==SQLITE4_OK ){
      aData = sqlite4BtPageData(pLeaf);

      /* Make space within the cell pointer array */
      if( iCell!=nCell ){
        u8 *aFrom = btCellPtrFind(aData, pgsz, nCell-1);
        u8 *aTo = btCellPtrFind(aData, pgsz, nCell-1+nKV);
        memmove(aTo, aFrom, (nCell-iCell) * 2);
      }

      for(i=0; i<nKV; i++){
        /* Write the cell pointer */
        btPutU16(btCellPtrFind(aData, pgsz, iCell+i), iWrite);
      
................................................................................
      }
      if( rc==SQLITE4_OK ){
        u8 *a = sqlite4BtPageData(pChild);
        memcpy(aData, a, pgsz);
        rc = sqlite4BtPageTrim(pChild);
      }
    }
  }else if( nCell==0 || (nFree>(2*pgsz/3) && bLeaf==0) ){
    rc = btBalance(pCsr, bLeaf, 0, 0);
  }
  return rc;
}

/*
** Insert a new key/value pair or replace an existing one.

Changes to test/simple3.test

87
88
89
90
91
92
93

94
95
96





















97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114




115

116
117
118
119
120
121
122
123



124
125

126
127
128
129
130

131
132
133
134
135
136
137
138



139
140
141
142
143


144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
  INSERT INTO t1 VALUES(6, $val);
}

do_execsql_test 2.5 { 
  SELECT a, length(b) FROM t1 
} {1 200  3 200  4 200  5 200  6 200}


#--------------------------------------------------------------------------
# Insert many rows in sequence.
#





















do_test 3.0 {
  catch { db close }
  forcedelete test.db
  sqlite4 db file:test.db?kv=bt
} {}

do_execsql_test 3.1 {
  CREATE TABLE t1(a PRIMARY KEY, b);
}

for {set i 0} {$i < 100} {incr i} {
  lappend rows $i
  do_execsql_test 3.2.$i {
    INSERT INTO t1 VALUES($i, randomblob(200));
    SELECT a FROM t1 ORDER BY a;
  } $rows
}
set nInitial 100






if 1 {
for {set i 0} {$i < 100} {incr i} {
  if {[set_test_counter errors]} break
  do_test 3.3.$i {
    for {set j 0} {$j < 1000} {incr j} {
      set pk [expr 100 + $i*1000 + $j]
      execsql { INSERT INTO t1 VALUES($pk, randomblob(200)) }
    }



    execsql { SELECT count(*) FROM t1 } 
  } [expr ($i+1)*1000 + 100]

}
set nInitial 100100
}

do_test 3.4 {

  for {set i 0} {$i < $nInitial} {incr i} {
    set res [execsql {SELECT count(*) FROM t1 WHERE a = $i}]
    if {$res!="1"} { error "res = $res for i=$i" }
  }
} {}

#--------------------------------------------------------------------------
# Remove many rows in sequence.



#
for {set i 0} {$i < 100} {incr i} {
if {$i == 5} breakpoint
  do_execsql_test 4.1.$i {
    DELETE FROM t1 WHERE a = $i;


    SELECT count(*) FROM t1;
  } [expr $nInitial - 1 - $i]
  if {[set_test_counter errors]} break
}

for {set i 100} {$i < $nInitial} {incr i 1000} {
  if {[set_test_counter errors]} break
  do_test 4.2.$i {
    for {set j 0} {$j < 1000} {incr j} {
      execsql { DELETE FROM t1 WHERE a = ($i + $j) }
    }
    execsql { SELECT count(*) FROM t1 }
  } [expr $nInitial - $i - 1000]
}

finish_test








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










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




87
88
89
90
91
92
93
94
95

96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129




130

131
132
133
134
135
136
137
138





139
140
141
142
143

144
145

146
147
148
149
150
151
152
153
154
155


156
157
158
159



160
161
162
163
164

165
166








167
168
169
170
  INSERT INTO t1 VALUES(6, $val);
}

do_execsql_test 2.5 { 
  SELECT a, length(b) FROM t1 
} {1 200  3 200  4 200  5 200  6 200}


#-------------------------------------------------------------------------


proc lshuffle {list} {
  set nVal [llength $list]
  for {set i 0} {$i < $nVal} {incr i} {
    set i2 [expr int(rand()*$nVal)]
    set tmp [lindex $list $i]
    lset list $i [lindex $list $i2]
    lset list $i2 $tmp
  }
  return $list
}

proc K {a} { set a }

proc int_list {nVal} {
  set ret [list]
  for {set i 0} {$i < $nVal} {incr i} {
    lappend ret $i
  }
  return $ret
}

do_test 3.0 {
  catch { db close }
  forcedelete test.db
  sqlite4 db file:test.db?kv=bt
} {}

do_execsql_test 3.1 {
  CREATE TABLE t1(a PRIMARY KEY, b);
}

set nRow 100000
set nStep [expr $nRow / 50]






foreach {tn shuffle_proc} {
  1 K
  2 lshuffle
} {
  
  set iRow 0
  foreach k [$shuffle_proc [int_list $nRow]] {
    incr iRow





    
    execsql { INSERT INTO t1 VALUES($k, randomblob(100)); }
    if {0==($iRow % $nStep)} {
      do_execsql_test 4.$tn.1.$iRow {
        SELECT count(*) FROM t1;

      } $iRow
    }

  }
  
  do_test 4.$tn.2 {
    set nInitial [db one {SELECT count(*) FROM t1}]
    for {set i 0} {$i < $nRow} {incr i} {
      set res [execsql {SELECT count(*) FROM t1 WHERE a = $i}]
      if {$res!="1"} { error "res = $res for i=$i" }
    }
  } {}
  


  set iRow 0
  foreach k [$shuffle_proc [int_list $nRow]] {
    incr iRow
    



    execsql { DELETE FROM t1 WHERE a = $k }
    if {0==($iRow % $nStep)} {
      do_execsql_test 4.$tn.3.$iRow {
        SELECT count(*) FROM t1;
      } [expr $nRow - $iRow]

    }
  }








}

finish_test