/* ![[previous]](../icons/n_left.png)
![[next]](../icons/n_right.png)
![[first]](../icons/first.png)
![[last]](../icons/last.png)
![[top]](../icons/n_top.png)
![[bottom]](../icons/bottom.png)
![[index]](../icons/index.png)
![[help]](../icons/help.png)
*/
This source file includes following definitions.
- __bt_delete
- __bt_stkacq
- __bt_bdelete
- __bt_pdelete
- __bt_dleaf
- __bt_curdel
- __bt_relink
1 /*-
2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Mike Olson.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
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 * 3. 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.
19 *
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
30 * SUCH DAMAGE.
31 */
32
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
37 #ifdef HAVE_CONFIG_H
38 #include <config.h>
39 #endif
40 #include <sys/types.h>
41
42 #include <errno.h>
43 #include <stdio.h>
44 #ifdef HAVE_STRING_H
45 #include <string.h>
46 #else
47 #include <strings.h>
48 #endif
49
50 #include "db.h"
51 #include "btree.h"
52
53 static int __bt_bdelete(BTREE *, const DBT *);
54 static int __bt_curdel(BTREE *, const DBT *, PAGE *, u_int);
55 static int __bt_pdelete(BTREE *, PAGE *);
56 static int __bt_relink(BTREE *, PAGE *);
57 static int __bt_stkacq(BTREE *, PAGE **, CURSOR *);
58
59 /**
60 * __bt_delete
61 * Delete the item(s) referenced by a @a key.
62 *
63 * @return #RET_SPECIAL if the key is not found.
64 */
65 int
66 __bt_delete(dbp, key, flags)
67 const DB *dbp;
68 const DBT *key;
69 u_int flags;
70 {
71 BTREE *t;
72 CURSOR *c;
73 PAGE *h;
74 int status;
75
76 t = dbp->internal;
77
78 /* Toss any page pinned across calls. */
79 if (t->bt_pinned != NULL) {
80 mpool_put(t->bt_mp, t->bt_pinned, 0);
81 t->bt_pinned = NULL;
82 }
83
84 /* Check for change to a read-only tree. */
85 if (F_ISSET(t, B_RDONLY)) {
86 errno = EPERM;
87 return (RET_ERROR);
88 }
89
90 switch (flags) {
91 case 0:
92 status = __bt_bdelete(t, key);
93 break;
94 case R_CURSOR:
95 /*
96 * If flags is R_CURSOR, delete the cursor. Must already
97 * have started a scan and not have already deleted it.
98 */
99 c = &t->bt_cursor;
100 if (F_ISSET(c, CURS_INIT)) {
101 if (F_ISSET(c, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE))
102 return (RET_SPECIAL);
103 if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
104 return (RET_ERROR);
105
106 /*
107 * If the page is about to be emptied, we'll need to
108 * delete it, which means we have to acquire a stack.
109 */
110 if (NEXTINDEX(h) == 1)
111 if (__bt_stkacq(t, &h, &t->bt_cursor))
112 return (RET_ERROR);
113
114 status = __bt_dleaf(t, NULL, h, c->pg.index);
115
116 if (NEXTINDEX(h) == 0 && status == RET_SUCCESS) {
117 if (__bt_pdelete(t, h))
118 return (RET_ERROR);
119 } else
120 mpool_put(t->bt_mp,
121 h, status == RET_SUCCESS ? MPOOL_DIRTY : 0);
122 break;
123 }
124 /* FALLTHROUGH */
125 default:
126 errno = EINVAL;
127 return (RET_ERROR);
128 }
129 if (status == RET_SUCCESS)
130 F_SET(t, B_MODIFIED);
131 return (status);
132 }
133
134 /**
135 * __bt_stkacq --
136 * Acquire a stack so we can delete a cursor entry.
137 *
138 * @param t tree
139 * @param hp pointer to current, pinned #PAGE pointer
140 * @param c pointer to the cursor
141 *
142 * @return 0 on success, 1 on failure
143 */
144 static int
145 __bt_stkacq(t, hp, c)
146 BTREE *t;
147 PAGE **hp;
148 CURSOR *c;
149 {
150 BINTERNAL *bi;
151 EPG *e;
152 EPGNO *parent;
153 PAGE *h;
154 indx_t index = 0;
155 pgno_t pgno;
156 recno_t nextpg, prevpg;
157 int exact, level;
158
159 /*
160 * Find the first occurrence of the key in the tree. Toss the
161 * currently locked page so we don't hit an already-locked page.
162 */
163 h = *hp;
164 mpool_put(t->bt_mp, h, 0);
165 if ((e = __bt_search(t, &c->key, &exact)) == NULL)
166 return (1);
167 h = e->page;
168
169 /* See if we got it in one shot. */
170 if (h->pgno == c->pg.pgno)
171 goto ret;
172
173 /*
174 * Move right, looking for the page. At each move we have to move
175 * up the stack until we don't have to move to the next page. If
176 * we have to change pages at an internal level, we have to fix the
177 * stack back up.
178 */
179 while (h->pgno != c->pg.pgno) {
180 if ((nextpg = h->nextpg) == P_INVALID)
181 break;
182 mpool_put(t->bt_mp, h, 0);
183
184 /* Move up the stack. */
185 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
186 /* Get the parent page. */
187 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
188 return (1);
189
190 /* Move to the next index. */
191 if (parent->index != NEXTINDEX(h) - 1) {
192 index = parent->index + 1;
193 BT_PUSH(t, h->pgno, index);
194 break;
195 }
196 mpool_put(t->bt_mp, h, 0);
197 }
198
199 /* Restore the stack. */
200 while (level--) {
201 /* Push the next level down onto the stack. */
202 bi = GETBINTERNAL(h, index);
203 pgno = bi->pgno;
204 BT_PUSH(t, pgno, 0);
205
206 /* Lose the currently pinned page. */
207 mpool_put(t->bt_mp, h, 0);
208
209 /* Get the next level down. */
210 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
211 return (1);
212 index = 0;
213 }
214 mpool_put(t->bt_mp, h, 0);
215 if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL)
216 return (1);
217 }
218
219 if (h->pgno == c->pg.pgno)
220 goto ret;
221
222 /* Reacquire the original stack. */
223 mpool_put(t->bt_mp, h, 0);
224 if ((e = __bt_search(t, &c->key, &exact)) == NULL)
225 return (1);
226 h = e->page;
227
228 /*
229 * Move left, looking for the page. At each move we have to move
230 * up the stack until we don't have to change pages to move to the
231 * next page. If we have to change pages at an internal level, we
232 * have to fix the stack back up.
233 */
234 while (h->pgno != c->pg.pgno) {
235 if ((prevpg = h->prevpg) == P_INVALID)
236 break;
237 mpool_put(t->bt_mp, h, 0);
238
239 /* Move up the stack. */
240 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
241 /* Get the parent page. */
242 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
243 return (1);
244
245 /* Move to the next index. */
246 if (parent->index != 0) {
247 index = parent->index - 1;
248 BT_PUSH(t, h->pgno, index);
249 break;
250 }
251 mpool_put(t->bt_mp, h, 0);
252 }
253
254 /* Restore the stack. */
255 while (level--) {
256 /* Push the next level down onto the stack. */
257 bi = GETBINTERNAL(h, index);
258 pgno = bi->pgno;
259
260 /* Lose the currently pinned page. */
261 mpool_put(t->bt_mp, h, 0);
262
263 /* Get the next level down. */
264 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
265 return (1);
266
267 index = NEXTINDEX(h) - 1;
268 BT_PUSH(t, pgno, index);
269 }
270 mpool_put(t->bt_mp, h, 0);
271 if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL)
272 return (1);
273 }
274
275
276 ret: mpool_put(t->bt_mp, h, 0);
277 return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL);
278 }
279
280 /**
281 * __bt_bdelete --
282 * Delete all key/data pairs matching the specified @a key.
283 *
284 * @param t tree
285 * @param key key to delete
286 *
287 * @return #RET_ERROR, #RET_SUCCESS and #RET_SPECIAL if the key not found.
288 */
289 static int
290 __bt_bdelete(t, key)
291 BTREE *t;
292 const DBT *key;
293 {
294 EPG *e;
295 PAGE *h;
296 int deleted, exact, redo;
297
298 deleted = 0;
299
300 /* Find any matching record; __bt_search pins the page. */
301 loop: if ((e = __bt_search(t, key, &exact)) == NULL)
302 return (deleted ? RET_SUCCESS : RET_ERROR);
303 if (!exact) {
304 mpool_put(t->bt_mp, e->page, 0);
305 return (deleted ? RET_SUCCESS : RET_SPECIAL);
306 }
307
308 /*
309 * Delete forward, then delete backward, from the found key. If
310 * there are duplicates and we reach either side of the page, do
311 * the key search again, so that we get them all.
312 */
313 redo = 0;
314 h = e->page;
315 do {
316 if (__bt_dleaf(t, key, h, e->index)) {
317 mpool_put(t->bt_mp, h, 0);
318 return (RET_ERROR);
319 }
320 if (F_ISSET(t, B_NODUPS)) {
321 if (NEXTINDEX(h) == 0) {
322 if (__bt_pdelete(t, h))
323 return (RET_ERROR);
324 } else
325 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
326 return (RET_SUCCESS);
327 }
328 deleted = 1;
329 } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);
330
331 /* Check for right-hand edge of the page. */
332 if (e->index == NEXTINDEX(h))
333 redo = 1;
334
335 /* Delete from the key to the beginning of the page. */
336 while (e->index-- > 0) {
337 if (__bt_cmp(t, key, e) != 0)
338 break;
339 if (__bt_dleaf(t, key, h, e->index) == RET_ERROR) {
340 mpool_put(t->bt_mp, h, 0);
341 return (RET_ERROR);
342 }
343 if (e->index == 0)
344 redo = 1;
345 }
346
347 /* Check for an empty page. */
348 if (NEXTINDEX(h) == 0) {
349 if (__bt_pdelete(t, h))
350 return (RET_ERROR);
351 goto loop;
352 }
353
354 /* Put the page. */
355 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
356
357 if (redo)
358 goto loop;
359 return (RET_SUCCESS);
360 }
361
362 /**
363 * __bt_pdelete --
364 * Delete a single page from the tree.
365 *
366 * @param t tree
367 * @param h leaf page
368 *
369 * @return #RET_SUCCESS, #RET_ERROR.
370 *
371 * @par Side-effects:
372 * #mpool_put's the page
373 */
374 static int
375 __bt_pdelete(t, h)
376 BTREE *t;
377 PAGE *h;
378 {
379 BINTERNAL *bi;
380 PAGE *pg;
381 EPGNO *parent;
382 indx_t cnt, index, *ip, offset;
383 u_int32_t nksize;
384 char *from;
385
386 /*
387 * Walk the parent page stack -- a LIFO stack of the pages that were
388 * traversed when we searched for the page where the delete occurred.
389 * Each stack entry is a page number and a page index offset. The
390 * offset is for the page traversed on the search. We've just deleted
391 * a page, so we have to delete the key from the parent page.
392 *
393 * If the delete from the parent page makes it empty, this process may
394 * continue all the way up the tree. We stop if we reach the root page
395 * (which is never deleted, it's just not worth the effort) or if the
396 * delete does not empty the page.
397 */
398 while ((parent = BT_POP(t)) != NULL) {
399 /* Get the parent page. */
400 if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
401 return (RET_ERROR);
402
403 index = parent->index;
404 bi = GETBINTERNAL(pg, index);
405
406 /* Free any overflow pages. */
407 if (bi->flags & P_BIGKEY &&
408 __ovfl_delete(t, bi->bytes) == RET_ERROR) {
409 mpool_put(t->bt_mp, pg, 0);
410 return (RET_ERROR);
411 }
412
413 /*
414 * Free the parent if it has only the one key and it's not the
415 * root page. If it's the rootpage, turn it back into an empty
416 * leaf page.
417 */
418 if (NEXTINDEX(pg) == 1)
419 if (pg->pgno == P_ROOT) {
420 pg->lower = BTDATAOFF;
421 pg->upper = t->bt_psize;
422 pg->flags = P_BLEAF;
423 } else {
424 if (__bt_relink(t, pg) || __bt_free(t, pg))
425 return (RET_ERROR);
426 continue;
427 }
428 else {
429 /* Pack remaining key items at the end of the page. */
430 nksize = NBINTERNAL(bi->ksize);
431 from = (char *)pg + pg->upper;
432 memmove(from + nksize, from, (char *)bi - from);
433 pg->upper += nksize;
434
435 /* Adjust indices' offsets, shift the indices down. */
436 offset = pg->linp[index];
437 for (cnt = index, ip = &pg->linp[0]; cnt--; ++ip)
438 if (ip[0] < offset)
439 ip[0] += nksize;
440 for (cnt = NEXTINDEX(pg) - index; --cnt; ++ip)
441 ip[0] = ip[1] < offset ? ip[1] + nksize : ip[1];
442 pg->lower -= sizeof(indx_t);
443 }
444
445 mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
446 break;
447 }
448
449 /* Free the leaf page, as long as it wasn't the root. */
450 if (h->pgno == P_ROOT) {
451 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
452 return (RET_SUCCESS);
453 }
454 return (__bt_relink(t, h) || __bt_free(t, h));
455 }
456
457 /**
458 * __bt_dleaf --
459 * Delete a single record from a leaf page.
460 *
461 * @param t tree
462 * @param key referenced key
463 * @param h page
464 * @param index index on page to delete
465 *
466 * @return #RET_SUCCESS, #RET_ERROR.
467 */
468 int
469 __bt_dleaf(t, key, h, index)
470 BTREE *t;
471 const DBT *key;
472 PAGE *h;
473 u_int index;
474 {
475 BLEAF *bl;
476 indx_t cnt, *ip, offset;
477 u_int32_t nbytes;
478 void *to;
479 char *from;
480
481 /* If this record is referenced by the cursor, delete the cursor. */
482 if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
483 !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
484 t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index == index &&
485 __bt_curdel(t, key, h, index))
486 return (RET_ERROR);
487
488 /* If the entry uses overflow pages, make them available for reuse. */
489 to = bl = GETBLEAF(h, index);
490 if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR)
491 return (RET_ERROR);
492 if (bl->flags & P_BIGDATA &&
493 __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR)
494 return (RET_ERROR);
495
496 /* Pack the remaining key/data items at the end of the page. */
497 nbytes = NBLEAF(bl);
498 from = (char *)h + h->upper;
499 memmove(from + nbytes, from, (char *)to - from);
500 h->upper += nbytes;
501
502 /* Adjust the indices' offsets, shift the indices down. */
503 offset = h->linp[index];
504 for (cnt = index, ip = &h->linp[0]; cnt--; ++ip)
505 if (ip[0] < offset)
506 ip[0] += nbytes;
507 for (cnt = NEXTINDEX(h) - index; --cnt; ++ip)
508 ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
509 h->lower -= sizeof(indx_t);
510
511 /* If the cursor is on this page, adjust it as necessary. */
512 if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
513 !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
514 t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index > index)
515 --t->bt_cursor.pg.index;
516
517 return (RET_SUCCESS);
518 }
519
520 /**
521 * __bt_curdel --
522 * Delete the cursor.
523 *
524 * @param t tree
525 * @param key referenced key (or @CODE{NULL})
526 * @param h page
527 * @param index index on page to delete
528 *
529 * @return #RET_SUCCESS, #RET_ERROR.
530 */
531 static int
532 __bt_curdel(t, key, h, index)
533 BTREE *t;
534 const DBT *key;
535 PAGE *h;
536 u_int index;
537 {
538 CURSOR *c;
539 EPG e;
540 PAGE *pg;
541 int curcopy, status;
542
543 /*
544 * If there are duplicates, move forward or backward to one.
545 * Otherwise, copy the key into the cursor area.
546 */
547 c = &t->bt_cursor;
548 F_CLR(c, CURS_AFTER | CURS_BEFORE | CURS_ACQUIRE);
549
550 curcopy = 0;
551 if (!F_ISSET(t, B_NODUPS)) {
552 /*
553 * We're going to have to do comparisons. If we weren't
554 * provided a copy of the key, i.e. the user is deleting
555 * the current cursor position, get one.
556 */
557 if (key == NULL) {
558 e.page = h;
559 e.index = index;
560 if ((status = __bt_ret(t, &e,
561 &c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS)
562 return (status);
563 curcopy = 1;
564 key = &c->key;
565 }
566 /* Check previous key, if not at the beginning of the page. */
567 if (index > 0) {
568 e.page = h;
569 e.index = index - 1;
570 if (__bt_cmp(t, key, &e) == 0) {
571 F_SET(c, CURS_BEFORE);
572 goto dup2;
573 }
574 }
575 /* Check next key, if not at the end of the page. */
576 if (index < NEXTINDEX(h) - 1) {
577 e.page = h;
578 e.index = index + 1;
579 if (__bt_cmp(t, key, &e) == 0) {
580 F_SET(c, CURS_AFTER);
581 goto dup2;
582 }
583 }
584 /* Check previous key if at the beginning of the page. */
585 if (index == 0 && h->prevpg != P_INVALID) {
586 if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
587 return (RET_ERROR);
588 e.page = pg;
589 e.index = NEXTINDEX(pg) - 1;
590 if (__bt_cmp(t, key, &e) == 0) {
591 F_SET(c, CURS_BEFORE);
592 goto dup1;
593 }
594 mpool_put(t->bt_mp, pg, 0);
595 }
596 /* Check next key if at the end of the page. */
597 if (index == NEXTINDEX(h) - 1 && h->nextpg != P_INVALID) {
598 if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
599 return (RET_ERROR);
600 e.page = pg;
601 e.index = 0;
602 if (__bt_cmp(t, key, &e) == 0) {
603 F_SET(c, CURS_AFTER);
604 dup1: mpool_put(t->bt_mp, pg, 0);
605 dup2: c->pg.pgno = e.page->pgno;
606 c->pg.index = e.index;
607 return (RET_SUCCESS);
608 }
609 mpool_put(t->bt_mp, pg, 0);
610 }
611 }
612 e.page = h;
613 e.index = index;
614 if (curcopy || (status =
615 __bt_ret(t, &e, &c->key, &c->key, NULL, NULL, 1)) == RET_SUCCESS) {
616 F_SET(c, CURS_ACQUIRE);
617 return (RET_SUCCESS);
618 }
619 return (status);
620 }
621
622 /**
623 * __bt_relink --
624 * Link around a deleted page.
625 *
626 * @param t tree
627 * @param h page to be deleted
628 */
629 static int
630 __bt_relink(t, h)
631 BTREE *t;
632 PAGE *h;
633 {
634 PAGE *pg;
635
636 if (h->nextpg != P_INVALID) {
637 if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
638 return (RET_ERROR);
639 pg->prevpg = h->prevpg;
640 mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
641 }
642 if (h->prevpg != P_INVALID) {
643 if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
644 return (RET_ERROR);
645 pg->nextpg = h->nextpg;
646 mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
647 }
648 return (0);
649 }
/* ![[top]](../icons/top.png)
![[bottom]](../icons/n_bottom.png)
*/