uint min; // next key offset
unsigned char bits:7; // page size in bits
unsigned char free:1; // page is on free list
- unsigned char lvl:5; // level of page
+ unsigned char lvl:6; // level of page
unsigned char kill:1; // page is being deleted
unsigned char dirty:1; // page is dirty
- unsigned char posted:1; // page is posted in parent
unsigned char right[BtId]; // page number to right
} *BtPage;
BTERR bt_splitpage (BtDb *bt)
{
uint cnt = 0, idx = 0, max, nxt = bt->page_size;
+unsigned char fencekey[256], rightkey[256];
uid page_no = bt->page_no, right;
-unsigned char fencekey[256];
BtPage page = bt->page;
uint lvl = page->lvl;
-uint prev;
BtKey key;
// split higher half of keys to bt->frame
slotptr(bt->frame, idx)->off = nxt;
}
+ // remember fence key for new right page
+
+ memcpy (rightkey, key, key->len + 1);
+
bt->frame->bits = bt->page_bits;
bt->frame->min = nxt;
bt->frame->cnt = idx;
memcpy (bt->frame, page, bt->page_size);
memset (page+1, 0, bt->page_size - sizeof(*page));
nxt = bt->page_size;
- page->posted = 0;
page->dirty = 0;
page->act = 0;
cnt = 0;
// remember fence key for smaller page
memcpy (fencekey, key, key->len + 1);
+
bt_putid(page->right, right);
page->min = nxt;
page->cnt = idx;
if( page_no == ROOT_page )
return bt_splitroot (bt, fencekey, right);
- // update left (containing) node
+ // lock right page
- if( bt_update(bt, page, page_no) )
+ if( bt_lockpage (bt, right, BtLockParent) )
return bt->err;
- right = 0;
-
- // insert new fences in parent pages
+ // update left (containing) node
- while( 1 ) {
- if( bt_lockpage (bt, page_no, BtLockParent) )
+ if( bt_update(bt, page, page_no) )
return bt->err;
- if( right )
- if( bt_mappage (bt, &bt->page, page_no) )
+ if( bt_lockpage (bt, page_no, BtLockParent) )
return bt->err;
- key = keyptr(bt->page, bt->page->cnt);
- memcpy (fencekey, key, key->len + 1);
- prev = bt->page->posted;
-
- if( right && prev ) {
- if( bt_unlockpage (bt, page_no, BtLockParent) )
- return bt->err;
- return bt_unlockpage (bt, page_no, BtLockWrite);
- }
-
- right = bt_getid (bt->page->right);
- bt->page->posted = 1;
+ // insert new fence for reformulated left block
- if( bt_update (bt, bt->page, page_no) )
+ if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, page_no, time(NULL)) )
return bt->err;
- if( bt_unlockpage (bt, page_no, BtLockWrite) )
- return bt->err;
-
- // insert new fence for reformulated left block
-
- if( !prev )
- if( bt_insertkey (bt, fencekey+1, *fencekey, lvl + 1, page_no, time(NULL)) )
- return bt->err;
+ // switch fence for right block of larger keys to new right page
- if( bt_unlockpage (bt, page_no, BtLockParent) )
+ if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right, time(NULL)) )
return bt->err;
- if( !(page_no = right) )
- break;
-
- if( bt_lockpage (bt, page_no, BtLockWrite) )
+ if( bt_unlockpage (bt, page_no, BtLockParent) )
return bt->err;
- }
- return 0;
+ return bt_unlockpage (bt, right, BtLockParent);
}
// Insert new key into the btree at requested level.
uint min; // next key offset
unsigned char bits:7; // page size in bits
unsigned char free:1; // page is on free list
- unsigned char lvl:5; // level of page
+ unsigned char lvl:6; // level of page
unsigned char kill:1; // page is being killed
unsigned char dirty:1; // page has deleted keys
- unsigned char posted:1; // page fence is posted
unsigned char right[BtId]; // page number to right
} *BtPage;
BTERR bt_splitpage (BtDb *bt, BtPageSet *set)
{
uint cnt = 0, idx = 0, max, nxt = bt->mgr->page_size;
-unsigned char fencekey[256];
+unsigned char fencekey[256], rightkey[256];
uint lvl = set->page->lvl;
+BtPageSet right[1];
uint prev;
-uid right;
BtKey key;
// split higher half of keys to bt->frame
slotptr(bt->frame, idx)->off = nxt;
}
+ // remember existing fence key for new page to the right
+
+ memcpy (rightkey, key, key->len + 1);
+
bt->frame->bits = bt->mgr->page_bits;
bt->frame->min = nxt;
bt->frame->cnt = idx;
// get new free page and write higher keys to it.
- if( !(right = bt_newpage(bt, bt->frame)) )
+ if( !(right->page_no = bt_newpage(bt, bt->frame)) )
return bt->err;
// update lower keys to continue in old page
memcpy (bt->frame, set->page, bt->mgr->page_size);
memset (set->page+1, 0, bt->mgr->page_size - sizeof(*set->page));
nxt = bt->mgr->page_size;
- set->page->posted = 0;
set->page->dirty = 0;
set->page->act = 0;
cnt = 0;
// remember fence key for smaller page
memcpy(fencekey, key, key->len + 1);
- bt_putid(set->page->right, right);
+
+ bt_putid(set->page->right, right->page_no);
set->page->min = nxt;
set->page->cnt = idx;
// if current page is the root page, split it
if( set->page_no == ROOT_page )
- return bt_splitroot (bt, set, fencekey, right);
-
- right = 0;
+ return bt_splitroot (bt, set, fencekey, right->page_no);
// insert new fences in their parent pages
- while( 1 ) {
- bt_lockpage (BtLockParent, set->latch);
-
- key = keyptr (set->page, set->page->cnt);
- memcpy (fencekey, key, key->len + 1);
- prev = set->page->posted;
-
- if( right && prev ) {
- bt_unlockpage (BtLockParent, set->latch);
- bt_unlockpage (BtLockWrite, set->latch);
- bt_unpinlatch (set->latch);
- bt_unpinpool (set->pool);
- return 0;
- }
-
- right = bt_getid (set->page->right);
- set->page->posted = 1;
-
- bt_unlockpage (BtLockWrite, set->latch);
-
- // insert new fence for reformulated left block of smaller keys
+ right->latch = bt_pinlatch (bt, right->page_no);
+ bt_lockpage (BtLockParent, right->latch);
- if( !prev )
- if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) )
- return bt->err;
+ bt_lockpage (BtLockParent, set->latch);
+ bt_unlockpage (BtLockWrite, set->latch);
- bt_unlockpage (BtLockParent, set->latch);
- bt_unpinlatch (set->latch);
- bt_unpinpool (set->pool);
+ // insert new fence for reformulated left block of smaller keys
- if( !(set->page_no = right) )
- break;
+ if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) )
+ return bt->err;
- set->latch = bt_pinlatch (bt, right);
+ // switch fence for right block of larger keys to new right page
- if( set->pool = bt_pinpool (bt, right) )
- set->page = bt_page (bt, set->pool, right);
- else
- return bt->err;
+ if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right->page_no, time(NULL)) )
+ return bt->err;
- bt_lockpage (BtLockWrite, set->latch);
- }
+ bt_unlockpage (BtLockParent, set->latch);
+ bt_unpinlatch (set->latch);
+ bt_unpinpool (set->pool);
+ bt_unlockpage (BtLockParent, right->latch);
+ bt_unpinlatch (right->latch);
return 0;
}
BTERR bt_splitpage (BtDb *bt, BtPageSet *set)
{
uint cnt = 0, idx = 0, max, nxt = bt->mgr->page_size;
-unsigned char fencekey[256];
+unsigned char fencekey[256], rightkey[256];
uint lvl = set->page->lvl;
+BtPageSet right[1];
uint prev;
-uid right;
BtKey key;
// split higher half of keys to bt->frame
slotptr(bt->frame, idx)->off = nxt;
}
+ // remember existing fence key for new page to the right
+
+ memcpy (rightkey, key, key->len + 1);
+
bt->frame->bits = bt->mgr->page_bits;
bt->frame->min = nxt;
bt->frame->cnt = idx;
// get new free page and write higher keys to it.
- if( !(right = bt_newpage(bt, bt->frame)) )
+ if( !(right->page_no = bt_newpage(bt, bt->frame)) )
return bt->err;
// update lower keys to continue in old page
memcpy (bt->frame, set->page, bt->mgr->page_size);
memset (set->page+1, 0, bt->mgr->page_size - sizeof(*set->page));
nxt = bt->mgr->page_size;
- set->page->posted = 0;
set->page->dirty = 0;
set->page->act = 0;
cnt = 0;
// remember fence key for smaller page
memcpy(fencekey, key, key->len + 1);
- bt_putid(set->page->right, right);
+
+ bt_putid(set->page->right, right->page_no);
set->page->min = nxt;
set->page->cnt = idx;
// if current page is the root page, split it
if( set->page_no == ROOT_page )
- return bt_splitroot (bt, set, fencekey, right);
-
- right = 0;
+ return bt_splitroot (bt, set, fencekey, right->page_no);
// insert new fences in their parent pages
- while( 1 ) {
- bt_lockpage (BtLockParent, set->latch);
-
- key = keyptr (set->page, set->page->cnt);
- memcpy (fencekey, key, key->len + 1);
- prev = set->page->posted;
-
- if( right && prev ) {
- bt_unlockpage (BtLockParent, set->latch);
- bt_unlockpage (BtLockWrite, set->latch);
- bt_unpinlatch (set->latch);
- bt_unpinpool (set->pool);
- return 0;
- }
-
- right = bt_getid (set->page->right);
- set->page->posted = 1;
-
- bt_unlockpage (BtLockWrite, set->latch);
-
- // insert new fence for reformulated left block of smaller keys
+ right->latch = bt_pinlatch (bt, right->page_no);
+ bt_lockpage (BtLockParent, right->latch);
- if( !prev )
- if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) )
- return bt->err;
+ bt_lockpage (BtLockParent, set->latch);
+ bt_unlockpage (BtLockWrite, set->latch);
- bt_unlockpage (BtLockParent, set->latch);
- bt_unpinlatch (set->latch);
- bt_unpinpool (set->pool);
+ // insert new fence for reformulated left block of smaller keys
- if( !(set->page_no = right) )
- break;
+ if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) )
+ return bt->err;
- set->latch = bt_pinlatch (bt, right);
+ // switch fence for right block of larger keys to new right page
- if( set->pool = bt_pinpool (bt, right) )
- set->page = bt_page (bt, set->pool, right);
- else
- return bt->err;
+ if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right->page_no, time(NULL)) )
+ return bt->err;
- bt_lockpage (BtLockWrite, set->latch);
- }
+ bt_unlockpage (BtLockParent, set->latch);
+ bt_unpinlatch (set->latch);
+ bt_unpinpool (set->pool);
+ bt_unlockpage (BtLockParent, right->latch);
+ bt_unpinlatch (right->latch);
return 0;
}
-
// Insert new key into the btree at given level.
BTERR bt_insertkey (BtDb *bt, unsigned char *key, uint len, uint lvl, uid id, uint tod)
BTERR bt_splitpage (BtDb *bt, BtPageSet *set)
{
uint cnt = 0, idx = 0, max, nxt = bt->mgr->page_size;
-unsigned char fencekey[256];
+unsigned char fencekey[256], rightkey[256];
uint lvl = set->page->lvl;
-uid right;
-BtKey key;
+BtPageSet right[1];
uint prev;
+BtKey key;
// split higher half of keys to bt->frame
slotptr(bt->frame, idx)->off = nxt;
}
+ // remember existing fence key for new page to the right
+
+ memcpy (rightkey, key, key->len + 1);
+
bt->frame->bits = bt->mgr->page_bits;
bt->frame->min = nxt;
bt->frame->cnt = idx;
// get new free page and write higher keys to it.
- if( !(right = bt_newpage(bt, bt->frame)) )
+ if( !(right->page_no = bt_newpage(bt, bt->frame)) )
return bt->err;
// update lower keys to continue in old page
memcpy (bt->frame, set->page, bt->mgr->page_size);
memset (set->page+1, 0, bt->mgr->page_size - sizeof(*set->page));
nxt = bt->mgr->page_size;
- set->page->posted = 0;
set->page->dirty = 0;
set->page->act = 0;
cnt = 0;
// remember fence key for smaller page
memcpy(fencekey, key, key->len + 1);
- bt_putid(set->page->right, right);
+
+ bt_putid(set->page->right, right->page_no);
set->page->min = nxt;
set->page->cnt = idx;
// if current page is the root page, split it
if( set->page_no == ROOT_page )
- return bt_splitroot (bt, set, fencekey, right);
-
- bt_unlockpage (BtLockWrite, set->latch);
- right = 0;
+ return bt_splitroot (bt, set, fencekey, right->page_no);
// insert new fences in their parent pages
- while( 1 ) {
- bt_lockpage (BtLockParent, set->latch);
- bt_lockpage (BtLockWrite, set->latch);
-
- key = keyptr (set->page, set->page->cnt);
- memcpy (fencekey, key, key->len + 1);
- prev = set->page->posted;
-
- if( right && prev ) {
- bt_unlockpage (BtLockParent, set->latch);
- bt_unlockpage (BtLockWrite, set->latch);
- bt_unpinlatch (set->latch);
- bt_unpinpool (set->pool);
- return 0;
- }
-
- right = bt_getid (set->page->right);
- set->page->posted = 1;
-
- bt_unlockpage (BtLockWrite, set->latch);
+ right->latch = bt_pinlatch (bt, right->page_no);
+ bt_lockpage (BtLockParent, right->latch);
- // insert new fence for reformulated left block of smaller keys
+ bt_lockpage (BtLockParent, set->latch);
+ bt_unlockpage (BtLockWrite, set->latch);
- if( !prev )
- if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) )
- return bt->err;
+ // insert new fence for reformulated left block of smaller keys
- bt_unlockpage (BtLockParent, set->latch);
- bt_unpinlatch (set->latch);
- bt_unpinpool (set->pool);
+ if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) )
+ return bt->err;
- if( !(set->page_no = right) )
- break;
+ // switch fence for right block of larger keys to new right page
- set->latch = bt_pinlatch (bt, right);
+ if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right->page_no, time(NULL)) )
+ return bt->err;
- if( set->pool = bt_pinpool (bt, right) )
- set->page = bt_page (bt, set->pool, right);
- else
- return bt->err;
- }
+ bt_unlockpage (BtLockParent, set->latch);
+ bt_unpinlatch (set->latch);
+ bt_unpinpool (set->pool);
+ bt_unlockpage (BtLockParent, right->latch);
+ bt_unpinlatch (right->latch);
return 0;
}
-
// Insert new key into the btree at given level.
BTERR bt_insertkey (BtDb *bt, unsigned char *key, uint len, uint lvl, uid id, uint tod)