-// 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.