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