1 /*-
2 * Copyright (c) 1990, 1993
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 * %sccs.include.redist.c%
9 */
10
11 #if defined(LIBC_SCCS) && !defined(lint)
12 static char sccsid[] = "@(#)rec_delete.c 8.4 (Berkeley) 02/21/94";
13 #endif /* LIBC_SCCS and not lint */
14
15 #include <sys/types.h>
16
17 #include <errno.h>
18 #include <stdio.h>
19 #include <string.h>
20
21 #include <db.h>
22 #include "recno.h"
23
24 static int rec_rdelete __P((BTREE *, recno_t));
25
26 /*
27 * __REC_DELETE -- Delete the item(s) referenced by a key.
28 *
29 * Parameters:
30 * dbp: pointer to access method
31 * key: key to delete
32 * flags: R_CURSOR if deleting what the cursor references
33 *
34 * Returns:
35 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
36 */
37 int
__rec_delete(dbp,key,flags)38 __rec_delete(dbp, key, flags)
39 const DB *dbp;
40 const DBT *key;
41 u_int flags;
42 {
43 BTREE *t;
44 recno_t nrec;
45 int status;
46
47 t = dbp->internal;
48
49 /* Toss any page pinned across calls. */
50 if (t->bt_pinned != NULL) {
51 mpool_put(t->bt_mp, t->bt_pinned, 0);
52 t->bt_pinned = NULL;
53 }
54
55 switch(flags) {
56 case 0:
57 if ((nrec = *(recno_t *)key->data) == 0)
58 goto einval;
59 if (nrec > t->bt_nrecs)
60 return (RET_SPECIAL);
61 --nrec;
62 status = rec_rdelete(t, nrec);
63 break;
64 case R_CURSOR:
65 if (!ISSET(t, B_SEQINIT))
66 goto einval;
67 if (t->bt_nrecs == 0)
68 return (RET_SPECIAL);
69 status = rec_rdelete(t, t->bt_rcursor - 1);
70 if (status == RET_SUCCESS)
71 --t->bt_rcursor;
72 break;
73 default:
74 einval: errno = EINVAL;
75 return (RET_ERROR);
76 }
77
78 if (status == RET_SUCCESS)
79 SET(t, B_MODIFIED | R_MODIFIED);
80 return (status);
81 }
82
83 /*
84 * REC_RDELETE -- Delete the data matching the specified key.
85 *
86 * Parameters:
87 * tree: tree
88 * nrec: record to delete
89 *
90 * Returns:
91 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
92 */
93 static int
rec_rdelete(t,nrec)94 rec_rdelete(t, nrec)
95 BTREE *t;
96 recno_t nrec;
97 {
98 EPG *e;
99 PAGE *h;
100 int status;
101
102 /* Find the record; __rec_search pins the page. */
103 if ((e = __rec_search(t, nrec, SDELETE)) == NULL)
104 return (RET_ERROR);
105
106 /* Delete the record. */
107 h = e->page;
108 status = __rec_dleaf(t, h, e->index);
109 if (status != RET_SUCCESS) {
110 mpool_put(t->bt_mp, h, 0);
111 return (status);
112 }
113 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
114 return (RET_SUCCESS);
115 }
116
117 /*
118 * __REC_DLEAF -- Delete a single record from a recno leaf page.
119 *
120 * Parameters:
121 * t: tree
122 * index: index on current page to delete
123 *
124 * Returns:
125 * RET_SUCCESS, RET_ERROR.
126 */
127 int
__rec_dleaf(t,h,index)128 __rec_dleaf(t, h, index)
129 BTREE *t;
130 PAGE *h;
131 indx_t index;
132 {
133 register RLEAF *rl;
134 register indx_t *ip, cnt, offset;
135 register size_t nbytes;
136 char *from;
137 void *to;
138
139 /*
140 * Delete a record from a recno leaf page. Internal records are never
141 * deleted from internal pages, regardless of the records that caused
142 * them to be added being deleted. Pages made empty by deletion are
143 * not reclaimed. They are, however, made available for reuse.
144 *
145 * Pack the remaining entries at the end of the page, shift the indices
146 * down, overwriting the deleted record and its index. If the record
147 * uses overflow pages, make them available for reuse.
148 */
149 to = rl = GETRLEAF(h, index);
150 if (rl->flags & P_BIGDATA && __ovfl_delete(t, rl->bytes) == RET_ERROR)
151 return (RET_ERROR);
152 nbytes = NRLEAF(rl);
153
154 /*
155 * Compress the key/data pairs. Compress and adjust the [BR]LEAF
156 * offsets. Reset the headers.
157 */
158 from = (char *)h + h->upper;
159 memmove(from + nbytes, from, (char *)to - from);
160 h->upper += nbytes;
161
162 offset = h->linp[index];
163 for (cnt = &h->linp[index] - (ip = &h->linp[0]); cnt--; ++ip)
164 if (ip[0] < offset)
165 ip[0] += nbytes;
166 for (cnt = &h->linp[NEXTINDEX(h)] - ip; --cnt; ++ip)
167 ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
168 h->lower -= sizeof(indx_t);
169 --t->bt_nrecs;
170 return (RET_SUCCESS);
171 }
172