2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 4. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 #if defined(LIBC_SCCS) && !defined(lint)
34 static char sccsid[] = "@(#)bt_delete.c 8.13 (Berkeley) 7/28/94";
35 #endif /* LIBC_SCCS and not lint */
36 #include <sys/cdefs.h>
37 __FBSDID("$FreeBSD$");
39 #include <sys/types.h>
48 static int __bt_bdelete(BTREE *, const DBT *);
49 static int __bt_curdel(BTREE *, const DBT *, PAGE *, u_int);
50 static int __bt_pdelete(BTREE *, PAGE *);
51 static int __bt_relink(BTREE *, PAGE *);
52 static int __bt_stkacq(BTREE *, PAGE **, CURSOR *);
56 * Delete the item(s) referenced by a key.
58 * Return RET_SPECIAL if the key is not found.
61 __bt_delete(const DB *dbp, const DBT *key, u_int flags)
70 /* Toss any page pinned across calls. */
71 if (t->bt_pinned != NULL) {
72 mpool_put(t->bt_mp, t->bt_pinned, 0);
76 /* Check for change to a read-only tree. */
77 if (F_ISSET(t, B_RDONLY)) {
84 status = __bt_bdelete(t, key);
88 * If flags is R_CURSOR, delete the cursor. Must already
89 * have started a scan and not have already deleted it.
92 if (F_ISSET(c, CURS_INIT)) {
93 if (F_ISSET(c, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE))
95 if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
99 * If the page is about to be emptied, we'll need to
100 * delete it, which means we have to acquire a stack.
102 if (NEXTINDEX(h) == 1)
103 if (__bt_stkacq(t, &h, &t->bt_cursor))
106 status = __bt_dleaf(t, NULL, h, c->pg.index);
108 if (NEXTINDEX(h) == 0 && status == RET_SUCCESS) {
109 if (__bt_pdelete(t, h))
113 h, status == RET_SUCCESS ? MPOOL_DIRTY : 0);
121 if (status == RET_SUCCESS)
122 F_SET(t, B_MODIFIED);
128 * Acquire a stack so we can delete a cursor entry.
132 * hp: pointer to current, pinned PAGE pointer
133 * c: pointer to the cursor
136 * 0 on success, 1 on failure
139 __bt_stkacq(BTREE *t, PAGE **hp, CURSOR *c)
147 recno_t nextpg, prevpg;
151 * Find the first occurrence of the key in the tree. Toss the
152 * currently locked page so we don't hit an already-locked page.
155 mpool_put(t->bt_mp, h, 0);
156 if ((e = __bt_search(t, &c->key, &exact)) == NULL)
160 /* See if we got it in one shot. */
161 if (h->pgno == c->pg.pgno)
165 * Move right, looking for the page. At each move we have to move
166 * up the stack until we don't have to move to the next page. If
167 * we have to change pages at an internal level, we have to fix the
170 while (h->pgno != c->pg.pgno) {
171 if ((nextpg = h->nextpg) == P_INVALID)
173 mpool_put(t->bt_mp, h, 0);
175 /* Move up the stack. */
176 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
177 /* Get the parent page. */
178 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
181 /* Move to the next index. */
182 if (parent->index != NEXTINDEX(h) - 1) {
183 idx = parent->index + 1;
184 BT_PUSH(t, h->pgno, idx);
187 mpool_put(t->bt_mp, h, 0);
190 /* Restore the stack. */
192 /* Push the next level down onto the stack. */
193 bi = GETBINTERNAL(h, idx);
197 /* Lose the currently pinned page. */
198 mpool_put(t->bt_mp, h, 0);
200 /* Get the next level down. */
201 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
205 mpool_put(t->bt_mp, h, 0);
206 if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL)
210 if (h->pgno == c->pg.pgno)
213 /* Reacquire the original stack. */
214 mpool_put(t->bt_mp, h, 0);
215 if ((e = __bt_search(t, &c->key, &exact)) == NULL)
220 * Move left, looking for the page. At each move we have to move
221 * up the stack until we don't have to change pages to move to the
222 * next page. If we have to change pages at an internal level, we
223 * have to fix the stack back up.
225 while (h->pgno != c->pg.pgno) {
226 if ((prevpg = h->prevpg) == P_INVALID)
228 mpool_put(t->bt_mp, h, 0);
230 /* Move up the stack. */
231 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
232 /* Get the parent page. */
233 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
236 /* Move to the next index. */
237 if (parent->index != 0) {
238 idx = parent->index - 1;
239 BT_PUSH(t, h->pgno, idx);
242 mpool_put(t->bt_mp, h, 0);
245 /* Restore the stack. */
247 /* Push the next level down onto the stack. */
248 bi = GETBINTERNAL(h, idx);
251 /* Lose the currently pinned page. */
252 mpool_put(t->bt_mp, h, 0);
254 /* Get the next level down. */
255 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
258 idx = NEXTINDEX(h) - 1;
259 BT_PUSH(t, pgno, idx);
261 mpool_put(t->bt_mp, h, 0);
262 if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL)
267 ret: mpool_put(t->bt_mp, h, 0);
268 return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL);
273 * Delete all key/data pairs matching the specified key.
280 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
283 __bt_bdelete(BTREE *t, const DBT *key)
287 int deleted, exact, redo;
291 /* Find any matching record; __bt_search pins the page. */
292 loop: if ((e = __bt_search(t, key, &exact)) == NULL)
293 return (deleted ? RET_SUCCESS : RET_ERROR);
295 mpool_put(t->bt_mp, e->page, 0);
296 return (deleted ? RET_SUCCESS : RET_SPECIAL);
300 * Delete forward, then delete backward, from the found key. If
301 * there are duplicates and we reach either side of the page, do
302 * the key search again, so that we get them all.
307 if (__bt_dleaf(t, key, h, e->index)) {
308 mpool_put(t->bt_mp, h, 0);
311 if (F_ISSET(t, B_NODUPS)) {
312 if (NEXTINDEX(h) == 0) {
313 if (__bt_pdelete(t, h))
316 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
317 return (RET_SUCCESS);
320 } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);
322 /* Check for right-hand edge of the page. */
323 if (e->index == NEXTINDEX(h))
326 /* Delete from the key to the beginning of the page. */
327 while (e->index-- > 0) {
328 if (__bt_cmp(t, key, e) != 0)
330 if (__bt_dleaf(t, key, h, e->index) == RET_ERROR) {
331 mpool_put(t->bt_mp, h, 0);
338 /* Check for an empty page. */
339 if (NEXTINDEX(h) == 0) {
340 if (__bt_pdelete(t, h))
346 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
350 return (RET_SUCCESS);
355 * Delete a single page from the tree.
362 * RET_SUCCESS, RET_ERROR.
365 * mpool_put's the page
368 __bt_pdelete(BTREE *t, PAGE *h)
373 indx_t cnt, idx, *ip, offset;
378 * Walk the parent page stack -- a LIFO stack of the pages that were
379 * traversed when we searched for the page where the delete occurred.
380 * Each stack entry is a page number and a page index offset. The
381 * offset is for the page traversed on the search. We've just deleted
382 * a page, so we have to delete the key from the parent page.
384 * If the delete from the parent page makes it empty, this process may
385 * continue all the way up the tree. We stop if we reach the root page
386 * (which is never deleted, it's just not worth the effort) or if the
387 * delete does not empty the page.
389 while ((parent = BT_POP(t)) != NULL) {
390 /* Get the parent page. */
391 if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
395 bi = GETBINTERNAL(pg, idx);
397 /* Free any overflow pages. */
398 if (bi->flags & P_BIGKEY &&
399 __ovfl_delete(t, bi->bytes) == RET_ERROR) {
400 mpool_put(t->bt_mp, pg, 0);
405 * Free the parent if it has only the one key and it's not the
406 * root page. If it's the rootpage, turn it back into an empty
409 if (NEXTINDEX(pg) == 1) {
410 if (pg->pgno == P_ROOT) {
411 pg->lower = BTDATAOFF;
412 pg->upper = t->bt_psize;
415 if (__bt_relink(t, pg) || __bt_free(t, pg))
420 /* Pack remaining key items at the end of the page. */
421 nksize = NBINTERNAL(bi->ksize);
422 from = (char *)pg + pg->upper;
423 memmove(from + nksize, from, (char *)bi - from);
426 /* Adjust indices' offsets, shift the indices down. */
427 offset = pg->linp[idx];
428 for (cnt = idx, ip = &pg->linp[0]; cnt--; ++ip)
431 for (cnt = NEXTINDEX(pg) - idx; --cnt; ++ip)
432 ip[0] = ip[1] < offset ? ip[1] + nksize : ip[1];
433 pg->lower -= sizeof(indx_t);
436 mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
440 /* Free the leaf page, as long as it wasn't the root. */
441 if (h->pgno == P_ROOT) {
442 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
443 return (RET_SUCCESS);
445 return (__bt_relink(t, h) || __bt_free(t, h));
450 * Delete a single record from a leaf page.
454 * key: referenced key
456 * idx: index on page to delete
459 * RET_SUCCESS, RET_ERROR.
462 __bt_dleaf(BTREE *t, const DBT *key, PAGE *h, u_int idx)
465 indx_t cnt, *ip, offset;
470 /* If this record is referenced by the cursor, delete the cursor. */
471 if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
472 !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
473 t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index == idx &&
474 __bt_curdel(t, key, h, idx))
477 /* If the entry uses overflow pages, make them available for reuse. */
478 to = bl = GETBLEAF(h, idx);
479 if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR)
481 if (bl->flags & P_BIGDATA &&
482 __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR)
485 /* Pack the remaining key/data items at the end of the page. */
487 from = (char *)h + h->upper;
488 memmove(from + nbytes, from, (char *)to - from);
491 /* Adjust the indices' offsets, shift the indices down. */
492 offset = h->linp[idx];
493 for (cnt = idx, ip = &h->linp[0]; cnt--; ++ip)
496 for (cnt = NEXTINDEX(h) - idx; --cnt; ++ip)
497 ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
498 h->lower -= sizeof(indx_t);
500 /* If the cursor is on this page, adjust it as necessary. */
501 if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
502 !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
503 t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index > idx)
504 --t->bt_cursor.pg.index;
506 return (RET_SUCCESS);
515 * key: referenced key (or NULL)
517 * idx: index on page to delete
520 * RET_SUCCESS, RET_ERROR.
523 __bt_curdel(BTREE *t, const DBT *key, PAGE *h, u_int idx)
531 * If there are duplicates, move forward or backward to one.
532 * Otherwise, copy the key into the cursor area.
535 F_CLR(c, CURS_AFTER | CURS_BEFORE | CURS_ACQUIRE);
538 if (!F_ISSET(t, B_NODUPS)) {
540 * We're going to have to do comparisons. If we weren't
541 * provided a copy of the key, i.e. the user is deleting
542 * the current cursor position, get one.
547 if ((status = __bt_ret(t, &e,
548 &c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS)
553 /* Check previous key, if not at the beginning of the page. */
557 if (__bt_cmp(t, key, &e) == 0) {
558 F_SET(c, CURS_BEFORE);
562 /* Check next key, if not at the end of the page. */
563 if (idx < NEXTINDEX(h) - 1) {
566 if (__bt_cmp(t, key, &e) == 0) {
567 F_SET(c, CURS_AFTER);
571 /* Check previous key if at the beginning of the page. */
572 if (idx == 0 && h->prevpg != P_INVALID) {
573 if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
576 e.index = NEXTINDEX(pg) - 1;
577 if (__bt_cmp(t, key, &e) == 0) {
578 F_SET(c, CURS_BEFORE);
581 mpool_put(t->bt_mp, pg, 0);
583 /* Check next key if at the end of the page. */
584 if (idx == NEXTINDEX(h) - 1 && h->nextpg != P_INVALID) {
585 if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
589 if (__bt_cmp(t, key, &e) == 0) {
590 F_SET(c, CURS_AFTER);
591 dup1: mpool_put(t->bt_mp, pg, 0);
592 dup2: c->pg.pgno = e.page->pgno;
593 c->pg.index = e.index;
594 return (RET_SUCCESS);
596 mpool_put(t->bt_mp, pg, 0);
601 if (curcopy || (status =
602 __bt_ret(t, &e, &c->key, &c->key, NULL, NULL, 1)) == RET_SUCCESS) {
603 F_SET(c, CURS_ACQUIRE);
604 return (RET_SUCCESS);
611 * Link around a deleted page.
615 * h: page to be deleted
618 __bt_relink(BTREE *t, PAGE *h)
622 if (h->nextpg != P_INVALID) {
623 if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
625 pg->prevpg = h->prevpg;
626 mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
628 if (h->prevpg != P_INVALID) {
629 if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
631 pg->nextpg = h->nextpg;
632 mpool_put(t->bt_mp, pg, MPOOL_DIRTY);