-// allocate a new page and write page into it
-
-uid bt_newpage(BtDb *bt, BtPage page)
-{
-uid new_page;
-char *pmap;
-int reuse;
-
- // lock page zero
-
- if ( bt_lockpage(bt, ALLOC_page, BtLockWrite) )
- return 0;
-
- if( bt_mappage (bt, &bt->alloc, ALLOC_page) )
- return 0;
-
- // use empty chain first
- // else allocate empty page
-
- if( new_page = bt_getid(bt->alloc[1].right) ) {
- if( bt_mappage (bt, &bt->temp, new_page) )
- return 0; // don't unlock on error
- memcpy(bt->alloc[1].right, bt->temp->right, BtId);
- reuse = 1;
- } else {
- new_page = bt_getid(bt->alloc->right);
- bt_putid(bt->alloc->right, new_page+1);
- reuse = 0;
- }
-
- if( bt_update(bt, bt->alloc, ALLOC_page) )
- return 0; // don't unlock on error
-
- if( !bt->mapped_io ) {
- if( bt_update(bt, page, new_page) )
- return 0; //don't unlock on error
-
- // unlock page zero
-
- if ( bt_unlockpage(bt, ALLOC_page, BtLockWrite) )
- return 0;
-
- return new_page;
- }
-
-#ifdef unix
- if ( pwrite(bt->idx, page, bt->page_size, new_page << bt->page_bits) < bt->page_size )
- return bt->err = BTERR_wrt, 0;
-
- // if writing first page of hash block, zero last page in the block
-
- if ( !reuse && bt->hashmask > 0 && (new_page & bt->hashmask) == 0 )
- {
- // use temp buffer to write zeros
- memset(bt->zero, 0, bt->page_size);
- if ( pwrite(bt->idx,bt->zero, bt->page_size, (new_page | bt->hashmask) << bt->page_bits) < bt->page_size )
- return bt->err = BTERR_wrt, 0;
- }
-#else
- // bring new page into page-cache and copy page.
- // this will extend the file into the new pages.
-
- if( !(pmap = (char*)bt_hashpage(bt, new_page & ~bt->hashmask)) )
- return 0;
-
- memcpy(pmap+((new_page & bt->hashmask) << bt->page_bits), page, bt->page_size);
-#endif
-
- // unlock page zero
-
- if ( bt_unlockpage(bt, ALLOC_page, BtLockWrite) )
- return 0;
-
- return new_page;
-}
-
-// find slot in page for given key at a given level
-// return 0 if beyond fence value
-
-int bt_findslot (BtPageSet *set, unsigned char *key, uint len)
-{
-uint diff, higher = set->page->cnt, low = 1, slot;
-
- // make stopper key an infinite fence value
-
- if( bt_getid (set->page->right) )
- higher++;
-
- // low is the lowest candidate, higher is already
- // tested as .ge. the given key, loop ends when they meet
-
- while( diff = higher - low ) {
- slot = low + ( diff >> 1 );
- if( keycmp (keyptr(set->page, slot), key, len) < 0 )
- low = slot + 1;
- else
- higher = slot;
- }
-
- if( higher <= set->page->cnt )
- return higher;
-
- // if leaf page, compare against fence value
-
- // return zero if key is on right link page
- // or return slot beyond last key
-
- if( set->page->lvl || keycmp ((BtKey)set->page->fence, key, len) < 0 )
- return 0;
-
- return higher;
-}
-
-// find and load page at given level for given key
-// leave page rd or wr locked as requested
-
-int bt_loadpage (BtDb *bt, BtPageSet *set, unsigned char *key, uint len, uint lvl, uint lock)
-{
-uid page_no = ROOT_page, prevpage = 0;
-uint drill = 0xff, slot;
-uint mode, prevmode;
-
- // start at root of btree and drill down
-
- do {
- // determine lock mode of drill level
- mode = (lock == BtLockWrite) && (drill == lvl) ? BtLockWrite : BtLockRead;
-
- 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;
-
- // if page is being deleted and we should continue right
-
- if( set->page->kill && set->page->goright ) {
- page_no = bt_getid (set->page->right);
- continue;
- }
-
- // otherwise, wait for deleted node to clear
-
- if( set->page->kill ) {
- if( bt_unlockpage(bt, set->page_no, mode) )
- return bt->err;
- page_no = ROOT_page;
- prevpage = 0;
- drill = 0xff;
-#ifdef unix
- sched_yield();
-#else
- SwitchToThread();
-#endif
- continue;
- }
-
- // find key on page at this level
- // and descend to requested level
-
- if( slot = bt_findslot (set, key, len) ) {
- if( drill == lvl )
- return 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);
- drill--;
- continue;
- }
-
- // or slide right into next page
- // (slide left from deleted page)
-
- page_no = bt_getid(set->page->right);
-
- } 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
-
-// call with set write locked mapped to bt->temp
-// return with set unlocked & unpinned.
-
-BTERR bt_fixfences (BtDb *bt, BtPageSet *set, unsigned char *newfence)
-{
-unsigned char oldfence[256];
-BtPageSet next[1];
-uid right;
-int chk;
-
- next->page_no = bt_getid(slotptr(set->page, set->page->cnt)->id);
- memcpy (oldfence, set->page->fence, 256);
- next->page = bt->temp2;
- bt->temp2 = bt->temp;
- bt->temp = next->page;
-
- while( !set->page->kill && set->page->lvl ) {
- if( bt_lockpage (bt, next->page_no, BtLockParent) )
- return bt->err;
- if( bt_lockpage (bt, next->page_no, BtLockAccess) )
- return bt->err;
- if( bt_lockpage (bt, next->page_no, BtLockWrite) )
- return bt->err;
- if( bt_unlockpage (bt, next->page_no, BtLockAccess) )
- return bt->err;
-
- if( bt_mappage (bt, &next->page, next->page_no) )
- return bt->err;
-
- chk = keycmp ((BtKey)next->page->fence, oldfence + 1, *oldfence);
-
- if( chk < 0 ) {
- right = bt_getid (next->page->right);
- if( bt_unlockpage (bt, next->page_no, BtLockWrite) )
- return bt->err;
- if( bt_unlockpage (bt, next->page_no, BtLockParent) )
- return bt->err;
- next->page_no = right;
- continue;
- }
-
- if( chk > 0 )
- return bt->err = BTERR_struct;
-
- if( bt_fixfences (bt, next, newfence) )
- return bt->err;
-
- break;
- }
-
- set->page = bt->temp;
-
- if( bt_mappage (bt, &set->page, set->page_no) )
- return bt->err;
-
- memcpy (set->page->fence, newfence, 256);
-
- if( bt_update(bt, set->page, set->page_no) )
- return bt->err;
- if( bt_unlockpage (bt, set->page_no, BtLockWrite) )
- return bt->err;
- if( bt_unlockpage (bt, set->page_no, BtLockParent) )
- return bt->err;
- return 0;
-}
-
-
-// return page to free list
-// page must be delete & write locked
-
-BTERR bt_freepage (BtDb *bt, BtPageSet *set)
-{
- // 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(set->page->right, bt_getid(bt->alloc[1].right));
- bt_putid(bt->alloc[1].right, set->page_no);
- set->page->free = 1;
-
- if( bt_update(bt, bt->alloc, ALLOC_page) )
- return bt->err;
- if( bt_update(bt, set->page, set->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, set->page_no, BtLockWrite) )
- return bt->err;
-
- return bt_unlockpage (bt, set->page_no, BtLockDelete);
-}
-
-// remove the root level by promoting its only child
-
-BTERR bt_removeroot (BtDb *bt, BtPageSet *root, BtPageSet *child)
-{
-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->page, next) )
- return bt->err;
-
- child->page_no = next;
- }
-
- memcpy (root->page, child->page, bt->page_size);
- next = bt_getid (slotptr(child->page, child->page->cnt)->id);
-
- if( bt_freepage (bt, child) )
- return bt->err;
- } while( root->page->lvl > 1 && root->page->cnt == 1 );
-
- if( bt_update (bt, root->page, 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, BtPageSet *set, BtPageSet *parent, BtPageSet *right, uint slot, uint idx)
-{
- // install ourselves as child page
- // and delete ourselves from parent
-
- bt_putid (slotptr(parent->page, idx)->id, set->page_no);
- slotptr(parent->page, slot)->dead = 1;
- parent->page->act--;
-
- // collapse any empty slots
-
- while( idx = parent->page->cnt - 1 )
- if( slotptr(parent->page, idx)->dead ) {
- *slotptr(parent->page, idx) = *slotptr(parent->page, idx + 1);
- memset (slotptr(parent->page, parent->page->cnt--), 0, sizeof(BtSlot));
- } else
- break;
-
- memcpy (set->page, right->page, bt->page_size);
-
- if( bt_unlockpage (bt, right->page_no, BtLockParent) )
- return bt->err;
-
- if( bt_freepage (bt, right) )
- return bt->err;
-
- // do we need to remove a btree level?
- // (leave the first page of leaves alone)
-
- if( parent->page_no == ROOT_page && parent->page->cnt == 1 )
- if( set->page->lvl )
- return bt_removeroot (bt, parent, set);
-
- if( bt_update (bt, parent->page, parent->page_no) )
- return bt->err;
-
- if( bt_unlockpage (bt, parent->page_no, BtLockWrite) )
- return bt->err;
-
- if( bt_update (bt, set->page, set->page_no) )
- return bt->err;
-
- if( bt_unlockpage (bt, set->page_no, BtLockWrite) )
- return bt->err;
-
- if( bt_unlockpage (bt, set->page_no, BtLockDelete) )
- return bt->err;
-
- return 0;
-}
-
-// remove both child and parent from the btree
-// from the fence position in the parent