- set->page_no = page_no;
-
- // obtain access lock using lock chaining
-
- if( page_no > ROOT_page )
- if( bt_lockpage(bt, page_no, BtLockAccess) )
- return 0;
-
- if( prevpage )
- if( bt_unlockpage(bt, prevpage, prevmode) )
- return 0;
-
- // obtain read lock using lock chaining
-
- if( bt_lockpage(bt, page_no, mode) )
- return 0;
-
- if( page_no > ROOT_page )
- if( bt_unlockpage(bt, page_no, BtLockAccess) )
- return 0;
-
- // map/obtain page contents
-
- if( bt_mappage (bt, &set->page, page_no) )
- return 0;
-
- // re-read and re-lock root after determining actual level of root
-
- if( set->page->lvl != drill) {
- if ( page_no != ROOT_page )
- return bt->err = BTERR_struct, 0;
-
- drill = set->page->lvl;
-
- if( lock == BtLockWrite && drill == lvl )
- if( bt_unlockpage(bt, page_no, mode) )
- return 0;
- else
- continue;
- }
-
- prevpage = page_no;
- prevmode = mode;
-
- // find key on page at this level
- // and descend to requested level
-
- if( slot = bt_findslot (set, key, len) ) {
- if( drill == lvl )
- return bt->posted = posted, slot;
-
- if( slot > set->page->cnt )
- return bt->err = BTERR_struct, 0;
-
- // if drilling down, find next active key
-
- while( slotptr(set->page, slot)->dead )
- if( slot++ < set->page->cnt )
- continue;
- else
- return bt->err = BTERR_struct, 0;
-
- page_no = bt_getid(slotptr(set->page, slot)->id);
- posted = 1;
- drill--;
- continue;
- }
-
- // or slide right into next page
- // (slide left from deleted page)
-
- page_no = bt_getid(set->page->right);
- posted = 0;
-
- } while( page_no );
-
- // return error on end of right chain
-
- bt->err = BTERR_struct;
- return 0; // return error
-}
-
-// drill down fixing fence values for left sibling tree
-// starting with current left page in bt->temp
-// call with bt->temp write locked
-// return with all pages unlocked.
-
-BTERR bt_fixfences (BtDb *bt, uid page_no, unsigned char *newfence)
-{
-unsigned char oldfence[256];
-uid prevpage = 0;
-int chk;
-
- memcpy (oldfence, bt->temp->fence, 256);
-
- // start at left page of btree and drill down
- // to update their fence values
-
- do {
- // obtain access lock using lock chaining
-
- if( prevpage ) {
- if( bt_lockpage(bt, page_no, BtLockAccess) )
- return 0;
-
- if( bt_unlockpage(bt, prevpage, BtLockWrite) )
- return 0;
-
- // obtain parent/fence key maintenance lock
-
- if( bt_lockpage(bt, page_no, BtLockParent) )
- return 0;
-
- // obtain write lock using lock chaining
-
- if( bt_lockpage(bt, page_no, BtLockWrite) )
- return 0;
-
- if( bt_unlockpage(bt, page_no, BtLockAccess) )
- return 0;
-
- // map/obtain page contents
-
- if( bt_mappage (bt, &bt->temp, page_no) )
- return 0;
- }
-
- chk = keycmp ((BtKey)bt->temp->fence, oldfence + 1, *oldfence);
- prevpage = page_no;
-
- if( chk < 0 ) {
- page_no = bt_getid (bt->temp->right);
- continue;
- }
-
- if( chk > 0 )
- return bt->err = BTERR_struct;
-
- memcpy (bt->temp->fence, newfence, 256);
-
- if( bt_update (bt, bt->temp, page_no) )
- return bt->err;
-
- // return when we reach a leaf page
-
- if( !bt->temp->lvl ) {
- if( bt_unlockpage (bt, page_no, BtLockWrite) )
- return bt->err;
- return bt_unlockpage (bt, page_no, BtLockParent);
- }
-
- page_no = bt_getid(slotptr(bt->temp, bt->temp->cnt)->id);
-
- } while( page_no );
-
- // return error on end of right chain
-
- bt->err = BTERR_struct;
- return 0; // return error
-}
-
-// return page to free list
-// page must be delete & write locked
-
-BTERR bt_freepage (BtDb *bt, BtPage page, uid page_no)
-{
- // lock & map allocation page
-
- if( bt_lockpage (bt, ALLOC_page, BtLockWrite) )
- return bt->err;
-
- if( bt_mappage (bt, &bt->alloc, ALLOC_page) )
- return bt->err;
-
- // store chain in second right
- bt_putid(page->right, bt_getid(bt->alloc[1].right));
- bt_putid(bt->alloc[1].right, page_no);
-
- if( bt_update(bt, bt->alloc, ALLOC_page) )
- return bt->err;
- if( bt_update(bt, page, page_no) )
- return bt->err;
-
- // unlock page zero
-
- if( bt_unlockpage(bt, ALLOC_page, BtLockWrite) )
- return bt->err;
-
- // remove write lock on deleted node
-
- if( bt_unlockpage(bt, page_no, BtLockWrite) )
- return bt->err;
-
- return bt_unlockpage (bt, page_no, BtLockDelete);
-}
-
-// remove the root level by promoting its only child
-
-BTERR bt_removeroot (BtDb *bt, BtPage root, BtPage child, uid page_no)
-{
-uid next = 0;
-
- do {
- if( next ) {
- if( bt_lockpage (bt, next, BtLockDelete) )
- return bt->err;
- if( bt_lockpage (bt, next, BtLockWrite) )
- return bt->err;
-
- if( bt_mappage (bt, &child, next) )
- return bt->err;
-
- page_no = next;
- }
-
- memcpy (root, child, bt->page_size);
- next = bt_getid (slotptr(child, child->cnt)->id);
-
- if( bt_freepage (bt, child, page_no) )
- return bt->err;
- } while( root->lvl > 1 && root->cnt == 1 );
-
- if( bt_update (bt, root, ROOT_page) )
- return bt->err;
-
- return bt_unlockpage (bt, ROOT_page, BtLockWrite);
-}
-
-// pull right page over ourselves in simple merge
-
-BTERR bt_mergeright (BtDb *bt, uid page_no, BtPageSet *parent, uint slot)
-{
-uid right;
-uint idx;