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