a16593d4e6a17704693ca46267cc7d4dc33044fd
[asterisk/asterisk.git] / main / db1-ast / recno / rec_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[] = "@(#)rec_delete.c        8.7 (Berkeley) 7/14/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 "recno.h"
49
50 static int rec_rdelete __P((BTREE *, recno_t));
51
52 /*
53  * __REC_DELETE -- Delete the item(s) referenced by a key.
54  *
55  * Parameters:
56  *      dbp:    pointer to access method
57  *      key:    key to delete
58  *      flags:  R_CURSOR if deleting what the cursor references
59  *
60  * Returns:
61  *      RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
62  */
63 int
64 __rec_delete(dbp, key, flags)
65         const DB *dbp;
66         const DBT *key;
67         u_int flags;
68 {
69         BTREE *t;
70         recno_t nrec;
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         switch(flags) {
82         case 0:
83                 if ((nrec = *(recno_t *)key->data) == 0)
84                         goto einval;
85                 if (nrec > t->bt_nrecs)
86                         return (RET_SPECIAL);
87                 --nrec;
88                 status = rec_rdelete(t, nrec);
89                 break;
90         case R_CURSOR:
91                 if (!F_ISSET(&t->bt_cursor, CURS_INIT))
92                         goto einval;
93                 if (t->bt_nrecs == 0)
94                         return (RET_SPECIAL);
95                 status = rec_rdelete(t, t->bt_cursor.rcursor - 1);
96                 if (status == RET_SUCCESS)
97                         --t->bt_cursor.rcursor;
98                 break;
99         default:
100 einval:         errno = EINVAL;
101                 return (RET_ERROR);
102         }
103
104         if (status == RET_SUCCESS)
105                 F_SET(t, B_MODIFIED | R_MODIFIED);
106         return (status);
107 }
108
109 /*
110  * REC_RDELETE -- Delete the data matching the specified key.
111  *
112  * Parameters:
113  *      tree:   tree
114  *      nrec:   record to delete
115  *
116  * Returns:
117  *      RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
118  */
119 static int
120 rec_rdelete(t, nrec)
121         BTREE *t;
122         recno_t nrec;
123 {
124         EPG *e;
125         PAGE *h;
126         int status;
127
128         /* Find the record; __rec_search pins the page. */
129         if ((e = __rec_search(t, nrec, SDELETE)) == NULL)
130                 return (RET_ERROR);
131
132         /* Delete the record. */
133         h = e->page;
134         status = __rec_dleaf(t, h, e->index);
135         if (status != RET_SUCCESS) {
136                 mpool_put(t->bt_mp, h, 0);
137                 return (status);
138         }
139         mpool_put(t->bt_mp, h, MPOOL_DIRTY);
140         return (RET_SUCCESS);
141 }
142
143 /*
144  * __REC_DLEAF -- Delete a single record from a recno leaf page.
145  *
146  * Parameters:
147  *      t:      tree
148  *      index:  index on current page to delete
149  *
150  * Returns:
151  *      RET_SUCCESS, RET_ERROR.
152  */
153 int
154 __rec_dleaf(t, h, index)
155         BTREE *t;
156         PAGE *h;
157         u_int32_t index;
158 {
159         RLEAF *rl;
160         indx_t *ip, cnt, offset;
161         u_int32_t nbytes;
162         char *from;
163         void *to;
164
165         /*
166          * Delete a record from a recno leaf page.  Internal records are never
167          * deleted from internal pages, regardless of the records that caused
168          * them to be added being deleted.  Pages made empty by deletion are
169          * not reclaimed.  They are, however, made available for reuse.
170          *
171          * Pack the remaining entries at the end of the page, shift the indices
172          * down, overwriting the deleted record and its index.  If the record
173          * uses overflow pages, make them available for reuse.
174          */
175         to = rl = GETRLEAF(h, index);
176         if (rl->flags & P_BIGDATA && __ovfl_delete(t, rl->bytes) == RET_ERROR)
177                 return (RET_ERROR);
178         nbytes = NRLEAF(rl);
179
180         /*
181          * Compress the key/data pairs.  Compress and adjust the [BR]LEAF
182          * offsets.  Reset the headers.
183          */
184         from = (char *)h + h->upper;
185         memmove(from + nbytes, from, (char *)to - from);
186         h->upper += nbytes;
187
188         offset = h->linp[index];
189         for (cnt = &h->linp[index] - (ip = &h->linp[0]); cnt--; ++ip)
190                 if (ip[0] < offset)
191                         ip[0] += nbytes;
192         for (cnt = &h->linp[NEXTINDEX(h)] - ip; --cnt; ++ip)
193                 ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
194         h->lower -= sizeof(indx_t);
195         --t->bt_nrecs;
196         return (RET_SUCCESS);
197 }