#include <sys/types.h> #include <stdio.h> #include "btconf.h" #include "btree.h" #include "btintern.h" /* (C) Copyright, 1988, 1989 Marcus J. Ranum All rights reserved This software, its documentation, and supporting files are copyrighted material and may only be distributed in accordance with the terms listed in the COPYRIGHT document. $Log: btdelete.c,v $ * Revision 1.1 90/06/08 16:11:43 mjr * * * Revision 1.1 90/06/06 15:03:41 mjr * * * Revision 1.1 90/06/03 16:23:08 mjr * * * Revision 1.1 90/05/18 23:20:35 mjr * * * Revision 1.1 90/05/15 13:18:28 mjr * Initial revision * * Revision 1.1 90/05/05 15:04:33 mjr * Initial revision * * Revision 1.2 90/05/03 10:42:33 mjr * *** empty log message *** * * Revision 1.2 90/05/03 10:38:50 mjr * *** empty log message *** * */ #ifndef lint static char *rcsid = "$Header: /atreus/mjr/hacks/mud/btlib/RCS/btdelete.c,v 1.1 90/06/08 16:11:43 mjr Exp $"; #endif bt_delete(b,key,len) BT_INDEX *b; bt_chrp key; int len; { struct bt_cache *op; int staklev; off_t dpag; /* page to delete from */ int keyat; /* key # to delete */ off_t ptj; /* junk */ int sr; /* 90% of this code is straight from bt_insert(). the only */ /* difference is that we need to ensure an exact match at */ /* leaf level only, otherwise we just track our way up the */ /* tree, deleting keys. page concatenation and redistribution */ /* are not implemented, though if they are to be, they should */ /* fit fairly easily in this framework. good luck, deletes suck */ /* the usual consistency checks */ if(len > BT_MAXK(b)) { bt_errno(b) = BT_KTOOBIG; return(BT_ERR); } if(len <= 0) { bt_errno(b) = BT_ZEROKEY; return(BT_ERR); } if(bt_seekdown(b,key,len) == BT_ERR) return(BT_ERR); /* set current stack level */ staklev = b->sblk.levs - 1; dpag = b->stack[staklev].pg; if((op = bt_rpage(b,dpag)) == NULL) return(BT_ERR); /* locate first del point, check if not there */ /* there must not be anything to delete. error. */ sr = bt_srchpg(key,len,bt_dtype(b),b->cmpfn,&ptj,&keyat,op->p); if(sr == BT_NF) return(BT_NF); if(sr == BT_ERR) { bt_errno(b) = BT_PAGESRCH; return(BT_ERR); } /* this loop should be comfortably repeated until we perform a */ /* simple delete without emptying a page. if a page concatentation */ /* function is added, we would look until we no longer concatenate */ while(1) { /* oddball special case. if the page is root and */ /* there is no key left to delete, the tree is */ /* (by definition) empty, having only a high pointer */ /* left. so, the high pointer is dropped, and */ /* turned to BT_NULL, instantly converting root */ /* back to a leaf page. we then return. done */ if(dpag == b->sblk.root && KEYCNT(op->p) == 0) { HIPT(op->p) = BT_NULL; KEYLEN(op->p) = 0; op->flags = BT_CHE_DIRTY; if(bt_wpage(b,op) == BT_ERR) return(BT_ERR); b->sblk.levs = 1; if(bt_wsuper(b) == BT_ERR) return(BT_ERR); return(BT_OK); } /* if the page has more than one key OR is an index with */ /* one key, just drop one key from the page, do not free it */ /* also, if the page is the root page, do not do free it */ if(KEYCNT(op->p) > 1 || dpag == b->sblk.root || (KEYCNT(op->p) == 1 && HIPT(op->p) != BT_NULL)) { struct bt_cache *tp; /* temp copy page */ if((tp = bt_rpage(b,BT_NULL)) == NULL) return(BT_ERR); bt_delpg(keyat,op->p,tp->p); if(HIPT(op->p) == BT_NULL) { b->cpag = op->num; b->cky = keyat - 1; } /* swap the page numbers, invalidate the old, */ /* mark the new as dirty to force a write */ tp->num = op->num; tp->flags = BT_CHE_DIRTY; op->num = BT_NULL; if(bt_wpage(b,op) == BT_ERR || bt_wpage(b,tp) == BT_ERR) return(BT_ERR); /* mark all as well with tree */ bt_clearerr(b); return(BT_OK); } else { off_t savlft; off_t savrt; savlft = LSIB(op->p); savrt = RSIB(op->p); if(HIPT(op->p) == BT_NULL) { b->cpag = savlft; b->cky = -1; } if(savlft != BT_NULL) { if((op = bt_rpage(b,savlft)) == NULL) return(BT_ERR); if(HIPT(op->p) == BT_NULL) b->cky = KEYCNT(op->p) - 1; RSIB(op->p) = savrt; op->flags = BT_CHE_DIRTY; if(bt_wpage(b,op) == BT_ERR) return(BT_ERR); } if(savrt != BT_NULL) { if((op = bt_rpage(b,savrt)) == NULL) return(BT_ERR); LSIB(op->p) = savlft; op->flags = BT_CHE_DIRTY; if(bt_wpage(b,op) == BT_ERR) return(BT_ERR); } /* sibs are fixed, now free the page */ if(bt_freepage(b,dpag) == BT_ERR) return(BT_ERR); } /* still going, pop stack level */ staklev--; /* set key location for next delete */ keyat = b->stack[staklev].ky; dpag = b->stack[staklev].pg; /* allocate a scratch page and read the old */ if((op = bt_rpage(b,dpag)) == NULL) return(BT_ERR); } }