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