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