Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Fix another bug in b-tree rebalancing. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
f4df828793bf8266c3887ff17a999321 |
| User & Date: | dan 2013-10-08 17:38:49 |
Context
|
2013-10-08
| ||
| 20:37 | Add hooks to run the "lsmtest" tree-structure tests and performance comparisons on the btree module. check-in: 8140c0abef user: dan tags: trunk | |
| 17:38 | Fix another bug in b-tree rebalancing. check-in: f4df828793 user: dan tags: trunk | |
|
2013-10-07
| ||
| 20:43 | Further progress on b-tree module. check-in: 51c2c9358d user: dan tags: trunk | |
Changes
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
|