+
+ child->page_no = next;
+ }
+
+ memcpy (root->page, child->page, bt->mgr->page_size);
+ next = bt_getid (slotptr(child->page, child->page->cnt)->id);
+ bt_freepage (bt, child);
+ } while( root->page->lvl > 1 && root->page->cnt == 1 );
+
+ bt_unlockpage (BtLockWrite, root->latch);
+ bt_unpinlatch (root->latch);
+ bt_unpinpool (root->pool);
+ return 0;
+}
+
+// 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->mgr->page_size);
+ bt_unlockpage (BtLockParent, right->latch);
+
+ bt_freepage (bt, right);
+
+ // 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);
+
+ bt_unlockpage (BtLockWrite, parent->latch);
+ bt_unlockpage (BtLockDelete, set->latch);
+ bt_unlockpage (BtLockWrite, set->latch);
+ bt_unpinlatch (parent->latch);
+ bt_unpinpool (parent->pool);
+ bt_unpinlatch (set->latch);
+ bt_unpinpool (set->pool);
+ return 0;
+}
+
+// remove both child and parent from the btree
+// from the fence position in the parent
+// call with both pages locked for writing
+
+BTERR bt_removeparent (BtDb *bt, BtPageSet *child, BtPageSet *parent, BtPageSet *right, BtPageSet *rparent, uint lvl)
+{
+unsigned char pagefence[256];
+uint idx;
+
+ // pull right sibling over ourselves and unlock
+
+ memcpy (child->page, right->page, bt->mgr->page_size);
+
+ bt_unlockpage (BtLockWrite, child->latch);
+ bt_unpinlatch (child->latch);
+ bt_unpinpool (child->pool);
+
+ // install ourselves into right link of old right page
+
+ bt_putid (right->page->right, child->page_no);
+ right->page->goright = 1; // tell bt_loadpage to go right to us
+ right->page->kill = 1;
+
+ bt_unlockpage (BtLockWrite, right->latch);
+
+ // remove our slot from our parent
+ // signal to move right
+
+ parent->page->goright = 1; // tell bt_loadpage to go right to rparent
+ parent->page->kill = 1;
+ parent->page->act--;
+
+ // redirect right page pointer in right parent to us
+
+ for( idx = 0; idx++ < rparent->page->cnt; )
+ if( !slotptr(rparent->page, idx)->dead )
+ break;
+
+ if( bt_getid (slotptr(rparent->page, idx)->id) != right->page_no )
+ return bt->err = BTERR_struct;
+
+ 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
+
+retry:
+ if( !(slot = bt_loadpage (bt, parent, pagefence+1, *pagefence, lvl+1, BtLockWrite)) )
+ return bt->err;
+
+ // 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
+ goto retry;