37 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid[] =
"@(#)bt_delete.c 8.13 (Berkeley) 7/28/94";
41 #include <sys/types.h>
47 #include "../include/db.h"
50 static int __bt_bdelete __P((
BTREE *,
const DBT *));
51 static int __bt_curdel __P((
BTREE *,
const DBT *,
PAGE *, u_int));
52 static int __bt_pdelete __P((
BTREE *,
PAGE *));
53 static int __bt_relink __P((
BTREE *,
PAGE *));
63 __bt_delete(dbp, key, flags)
76 if (t->bt_pinned != NULL) {
77 mpool_put(t->bt_mp, t->bt_pinned, 0);
82 if (F_ISSET(t, B_RDONLY)) {
89 status = __bt_bdelete(t, key);
97 if (F_ISSET(c, CURS_INIT)) {
98 if (F_ISSET(c, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE))
100 if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
107 if (NEXTINDEX(h) == 1)
108 if (__bt_stkacq(t, &h, &t->bt_cursor))
111 status = __bt_dleaf(t, NULL, h, c->pg.index);
113 if (NEXTINDEX(h) == 0 && status == RET_SUCCESS) {
114 if (__bt_pdelete(t, h))
118 h, status == RET_SUCCESS ? MPOOL_DIRTY : 0);
126 if (status == RET_SUCCESS)
127 F_SET(t, B_MODIFIED);
144 __bt_stkacq(t, hp, c)
155 recno_t nextpg, prevpg;
163 mpool_put(t->bt_mp, h, 0);
164 if ((e = __bt_search(t, &c->key, &exact)) == NULL)
169 if (h->pgno == c->pg.pgno)
178 while (h->pgno != c->pg.pgno) {
179 if ((nextpg = h->nextpg) == P_INVALID)
181 mpool_put(t->bt_mp, h, 0);
184 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
186 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
190 if (parent->index != NEXTINDEX(h) - 1) {
191 idx = parent->index + 1;
192 BT_PUSH(t, h->pgno, idx);
195 mpool_put(t->bt_mp, h, 0);
201 bi = GETBINTERNAL(h, idx);
206 mpool_put(t->bt_mp, h, 0);
209 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
213 mpool_put(t->bt_mp, h, 0);
214 if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL)
218 if (h->pgno == c->pg.pgno)
222 mpool_put(t->bt_mp, h, 0);
223 if ((e = __bt_search(t, &c->key, &exact)) == NULL)
233 while (h->pgno != c->pg.pgno) {
234 if ((prevpg = h->prevpg) == P_INVALID)
236 mpool_put(t->bt_mp, h, 0);
239 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
241 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
245 if (parent->index != 0) {
246 idx = parent->index - 1;
247 BT_PUSH(t, h->pgno, idx);
250 mpool_put(t->bt_mp, h, 0);
256 bi = GETBINTERNAL(h, idx);
260 mpool_put(t->bt_mp, h, 0);
263 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
266 idx = NEXTINDEX(h) - 1;
267 BT_PUSH(t, pgno, idx);
269 mpool_put(t->bt_mp, h, 0);
270 if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL)
275 ret: mpool_put(t->bt_mp, h, 0);
276 return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL);
297 int deleted, exact, redo;
302 loop:
if ((e = __bt_search(t, key, &exact)) == NULL)
303 return (deleted ? RET_SUCCESS : RET_ERROR);
305 mpool_put(t->bt_mp, e->page, 0);
306 return (deleted ? RET_SUCCESS : RET_SPECIAL);
317 if (__bt_dleaf(t, key, h, e->index)) {
318 mpool_put(t->bt_mp, h, 0);
321 if (F_ISSET(t, B_NODUPS)) {
322 if (NEXTINDEX(h) == 0) {
323 if (__bt_pdelete(t, h))
326 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
327 return (RET_SUCCESS);
330 }
while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);
333 if (e->index == NEXTINDEX(h))
337 while (e->index-- > 0) {
338 if (__bt_cmp(t, key, e) != 0)
340 if (__bt_dleaf(t, key, h, e->index) == RET_ERROR) {
341 mpool_put(t->bt_mp, h, 0);
349 if (NEXTINDEX(h) == 0) {
350 if (__bt_pdelete(t, h))
356 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
360 return (RET_SUCCESS);
385 indx_t cnt, idx, *ip, offset;
401 while ((parent = BT_POP(t)) != NULL) {
403 if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
407 bi = GETBINTERNAL(pg, idx);
410 if (bi->flags & P_BIGKEY &&
411 __ovfl_delete(t, bi->bytes) == RET_ERROR) {
412 mpool_put(t->bt_mp, pg, 0);
421 if (NEXTINDEX(pg) == 1) {
422 if (pg->pgno == P_ROOT) {
423 pg->lower = BTDATAOFF;
424 pg->upper = t->bt_psize;
427 if (__bt_relink(t, pg) || __bt_free(t, pg))
433 nksize = NBINTERNAL(bi->ksize);
434 from = (
char *)pg + pg->upper;
435 memmove(from + nksize, from, (
char *)bi - from);
439 offset = pg->linp[idx];
440 for (cnt = idx, ip = &pg->linp[0]; cnt--; ++ip)
443 for (cnt = NEXTINDEX(pg) - idx; --cnt; ++ip)
444 ip[0] = ip[1] < offset ? ip[1] + nksize : ip[1];
445 pg->lower -=
sizeof(indx_t);
448 mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
453 if (h->pgno == P_ROOT) {
454 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
455 return (RET_SUCCESS);
457 return (__bt_relink(t, h) || __bt_free(t, h));
474 __bt_dleaf(t, key, h, idx)
481 indx_t cnt, *ip, offset;
487 if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
488 !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
489 t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index == idx &&
490 __bt_curdel(t, key, h, idx))
494 to = bl = GETBLEAF(h, idx);
495 if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR)
497 if (bl->flags & P_BIGDATA &&
498 __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR)
503 from = (
char *)h + h->upper;
504 memmove(from + nbytes, from, (
char *)to - from);
508 offset = h->linp[idx];
509 for (cnt = idx, ip = &h->linp[0]; cnt--; ++ip)
512 for (cnt = NEXTINDEX(h) - idx; --cnt; ++ip)
513 ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
514 h->lower -=
sizeof(indx_t);
517 if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
518 !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
519 t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index > idx)
520 --t->bt_cursor.pg.index;
522 return (RET_SUCCESS);
539 __bt_curdel(t, key, h, idx)
555 F_CLR(c, CURS_AFTER | CURS_BEFORE | CURS_ACQUIRE);
558 if (!F_ISSET(t, B_NODUPS)) {
567 if ((status = __bt_ret(t, &e,
568 &c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS)
577 if (__bt_cmp(t, key, &e) == 0) {
578 F_SET(c, CURS_BEFORE);
583 if (idx < NEXTINDEX(h) - 1) {
586 if (__bt_cmp(t, key, &e) == 0) {
587 F_SET(c, CURS_AFTER);
592 if (idx == 0 && h->prevpg != P_INVALID) {
593 if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
596 e.index = NEXTINDEX(pg) - 1;
597 if (__bt_cmp(t, key, &e) == 0) {
598 F_SET(c, CURS_BEFORE);
601 mpool_put(t->bt_mp, pg, 0);
604 if (idx == NEXTINDEX(h) - 1 && h->nextpg != P_INVALID) {
605 if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
609 if (__bt_cmp(t, key, &e) == 0) {
610 F_SET(c, CURS_AFTER);
611 dup1: mpool_put(t->bt_mp, pg, 0);
612 dup2: c->pg.pgno = e.page->pgno;
613 c->pg.index = e.index;
614 return (RET_SUCCESS);
616 mpool_put(t->bt_mp, pg, 0);
621 if (curcopy || (status =
622 __bt_ret(t, &e, &c->key, &c->key, NULL, NULL, 1)) == RET_SUCCESS) {
623 F_SET(c, CURS_ACQUIRE);
624 return (RET_SUCCESS);
644 if (h->nextpg != P_INVALID) {
645 if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
647 pg->prevpg = h->prevpg;
648 mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
650 if (h->prevpg != P_INVALID) {
651 if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
653 pg->nextpg = h->nextpg;
654 mpool_put(t->bt_mp, pg, MPOOL_DIRTY);