+ bt_putid (slotptr(rparent->page, idx)->id, child->page_no);
+ bt_unlockpage (BtLockWrite, rparent->latch);
+ bt_unpinlatch (rparent->latch);
+ bt_unpinpool (rparent->pool);
+
+ // free the right page
+
+ bt_lockpage (BtLockDelete, right->latch);
+ bt_lockpage (BtLockWrite, right->latch);
+ bt_freepage (bt, right);
+
+ // save parent page fence value
+
+ memcpy (pagefence, parent->page->fence, 256);
+ bt_unlockpage (BtLockWrite, parent->latch);
+
+ return bt_removepage (bt, parent, lvl, pagefence);
+}
+
+// remove page from btree
+// call with page unlocked
+// returns with page on free list
+
+BTERR bt_removepage (BtDb *bt, BtPageSet *set, uint lvl, unsigned char *pagefence)
+{
+BtPageSet parent[1], sibling[1], rparent[1];
+unsigned char newfence[256];
+uint slot, idx;
+BtKey ptr;
+
+ // load and lock our parent
+
+ while( 1 ) {
+ if( !(slot = bt_loadpage (bt, parent, pagefence+1, *pagefence, lvl+1, BtLockWrite)) )
+ return bt->err;
+
+ // do we show up in our parent yet?
+
+ if( set->page_no != bt_getid (slotptr (parent->page, slot)->id) ) {
+ bt_unlockpage (BtLockWrite, parent->latch);
+ bt_unpinlatch (parent->latch);
+ bt_unpinpool (parent->pool);
+#ifdef linux
+ sched_yield();
+#else
+ SwitchToThread();
+#endif
+ continue;
+ }
+
+ // can we do a simple merge entirely
+ // between siblings on the parent page?
+
+ if( slot < parent->page->cnt ) {
+ // find our right neighbor
+ // right must exist because the stopper prevents
+ // the rightmost page from deleting
+
+ for( idx = slot; idx++ < parent->page->cnt; )
+ if( !slotptr(parent->page, idx)->dead )
+ break;
+
+ sibling->page_no = bt_getid (slotptr (parent->page, idx)->id);
+
+ bt_lockpage (BtLockDelete, set->latch);
+ bt_lockpage (BtLockWrite, set->latch);
+
+ // merge right if sibling shows up in
+ // our parent and is not being killed
+
+ if( sibling->page_no == bt_getid (set->page->right) ) {
+ sibling->latch = bt_pinlatch (bt, sibling->page_no);
+ bt_lockpage (BtLockParent, sibling->latch);
+ bt_lockpage (BtLockDelete, sibling->latch);
+ bt_lockpage (BtLockWrite, sibling->latch);
+
+ if( sibling->pool = bt_pinpool (bt, sibling->page_no) )
+ sibling->page = bt_page (bt, sibling->pool, sibling->page_no);
+ else
+ return bt->err;
+
+ if( !sibling->page->kill )
+ return bt_mergeright(bt, set, parent, sibling, slot, idx);
+
+ // try again later
+
+ bt_unlockpage (BtLockWrite, sibling->latch);
+ bt_unlockpage (BtLockParent, sibling->latch);
+ bt_unlockpage (BtLockDelete, sibling->latch);
+ bt_unpinlatch (sibling->latch);
+ bt_unpinpool (sibling->pool);
+ }
+
+ bt_unlockpage (BtLockDelete, set->latch);
+ bt_unlockpage (BtLockWrite, set->latch);
+ bt_unlockpage (BtLockWrite, parent->latch);
+ bt_unpinlatch (parent->latch);
+ bt_unpinpool (parent->pool);
+#ifdef linux
+ sched_yield();
+#else
+ SwitchToThread();
+#endif
+ continue;
+ }
+
+ // find our left neighbor in our parent page
+
+ for( idx = slot; --idx; )
+ if( !slotptr(parent->page, idx)->dead )
+ break;
+
+ // if no left neighbor, delete ourselves and our parent
+
+ if( !idx ) {
+ bt_lockpage (BtLockAccess, set->latch);
+ bt_lockpage (BtLockWrite, set->latch);
+ bt_unlockpage (BtLockAccess, set->latch);
+
+ rparent->page_no = bt_getid (parent->page->right);
+ rparent->latch = bt_pinlatch (bt, rparent->page_no);
+
+ bt_lockpage (BtLockAccess, rparent->latch);
+ bt_lockpage (BtLockWrite, rparent->latch);
+ bt_unlockpage (BtLockAccess, rparent->latch);
+
+ if( rparent->pool = bt_pinpool (bt, rparent->page_no) )
+ rparent->page = bt_page (bt, rparent->pool, rparent->page_no);
+ else
+ return bt->err;
+
+ if( !rparent->page->kill ) {
+ sibling->page_no = bt_getid (set->page->right);
+ sibling->latch = bt_pinlatch (bt, sibling->page_no);
+
+ bt_lockpage (BtLockAccess, sibling->latch);
+ bt_lockpage (BtLockWrite, sibling->latch);
+ bt_unlockpage (BtLockAccess, sibling->latch);
+
+ if( sibling->pool = bt_pinpool (bt, sibling->page_no) )
+ sibling->page = bt_page (bt, sibling->pool, sibling->page_no);
+ else
+ return bt->err;
+
+ if( !sibling->page->kill )
+ return bt_removeparent (bt, set, parent, sibling, rparent, lvl+1);
+
+ // try again later
+
+ bt_unlockpage (BtLockWrite, sibling->latch);
+ bt_unpinlatch (sibling->latch);
+ bt_unpinpool (sibling->pool);
+ }
+
+ bt_unlockpage (BtLockWrite, set->latch);
+ bt_unlockpage (BtLockWrite, rparent->latch);
+ bt_unpinlatch (rparent->latch);
+ bt_unpinpool (rparent->pool);
+
+ bt_unlockpage (BtLockWrite, parent->latch);
+ bt_unpinlatch (parent->latch);
+ bt_unpinpool (parent->pool);
+#ifdef linux
+ sched_yield();
+#else
+ SwitchToThread();
+#endif
+ continue;
+ }
+
+ // redirect parent to our left sibling
+ // lock and map our left sibling's page
+
+ sibling->page_no = bt_getid (slotptr(parent->page, idx)->id);
+ sibling->latch = bt_pinlatch (bt, sibling->page_no);
+
+ // wait our turn on fence key maintenance
+
+ bt_lockpage(BtLockParent, sibling->latch);
+ bt_lockpage(BtLockAccess, sibling->latch);
+ bt_lockpage(BtLockWrite, sibling->latch);
+ bt_unlockpage(BtLockAccess, sibling->latch);
+
+ if( sibling->pool = bt_pinpool (bt, sibling->page_no) )
+ sibling->page = bt_page (bt, sibling->pool, sibling->page_no);