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