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