1 /*- 2 * Copyright (c) 1990 The Regents of the University of California. 3 * 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[] = "@(#)bt_delete.c 5.3 (Berkeley) 09/04/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/types.h> 16 #include <errno.h> 17 #include <db.h> 18 #include <stdio.h> 19 #include <string.h> 20 #include "btree.h" 21 22 static int bt_bdelete __P((BTREE *, const DBT *)); 23 24 /* 25 * __BT_DELETE -- Delete the item(s) referenced by a key. 26 * 27 * Parameters: 28 * dbp: pointer to access method 29 * key: key to delete 30 * flags: R_CURSOR if deleting what the cursor references 31 * 32 * Returns: 33 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 34 */ 35 int 36 __bt_delete(dbp, key, flags) 37 const DB *dbp; 38 const DBT *key; 39 u_int flags; 40 { 41 BTREE *t; 42 int status; 43 44 t = dbp->internal; 45 if (ISSET(t, BTF_RDONLY)) { 46 errno = EPERM; 47 return (RET_ERROR); 48 } 49 switch(flags) { 50 case 0: 51 status = bt_bdelete(t, key); 52 break; 53 case R_CURSOR: 54 /* 55 * If flags is R_CURSOR, delete the cursor; must already have 56 * started a scan and not have already deleted the record. For 57 * the delete cursor bit to have been set requires that the 58 * scan be initialized, so no reason to check. 59 */ 60 status = ISSET(t, BTF_DELCRSR) ? 61 RET_SPECIAL : __bt_crsrdel(t, &t->bt_bcursor); 62 break; 63 default: 64 errno = EINVAL; 65 return (RET_ERROR); 66 } 67 if (status == RET_SUCCESS) 68 SET(t, BTF_MODIFIED); 69 return (status); 70 } 71 72 /* 73 * BT_BDELETE -- Delete all key/data pairs matching the specified key. 74 * 75 * Parameters: 76 * tree: tree 77 * key: key to delete 78 * 79 * Returns: 80 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 81 */ 82 static int 83 bt_bdelete(t, key) 84 BTREE *t; 85 const DBT *key; 86 { 87 EPG *e, save; 88 PAGE *h; 89 pgno_t cpgno, pg; 90 index_t cindex; 91 int deleted, exact; 92 93 /* Find any matching record; __bt_search pins the page. */ 94 if ((e = __bt_search(t, key, &exact)) == NULL) 95 return (RET_ERROR); 96 if (!exact) { 97 mpool_put(t->bt_mp, e->page, 0); 98 return (RET_SPECIAL); 99 } 100 101 /* 102 * Delete forward, then delete backward, from the found key. The 103 * ordering is so that the deletions don't mess up the page refs. 104 * The first loop deletes the found key, the second unpins the found 105 * page. 106 * 107 * If find the key referenced by the cursor, don't delete it, just 108 * flag it for future deletion. The cursor page number is P_INVALID 109 * unless the sequential scan is initialized, so no reason to check. 110 * A special case is when the already deleted cursor record was the 111 * only record found. If so, then the delete opertion fails as no 112 * records were deleted. 113 * 114 * Cycle in place in the current page until the current record doesn't 115 * match the key or the page is empty. If the latter, walk forward, 116 * skipping empty pages and repeating until an record doesn't match 117 * the key or the end of the tree is reached. 118 */ 119 cpgno = t->bt_bcursor.pgno; 120 cindex = t->bt_bcursor.index; 121 save = *e; 122 for (h = e->page, deleted = 0;;) { 123 do { 124 if (h->pgno == cpgno && e->index == cindex) { 125 if (NOTSET(t, BTF_DELCRSR)) { 126 SET(t, BTF_DELCRSR); 127 deleted = 1; 128 } 129 ++e->index; 130 } else { 131 if (__bt_dleaf(t, h, e->index)) 132 goto err; 133 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 134 deleted = 1; 135 } 136 } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0); 137 138 /* 139 * Quit if didn't find a match, no next page, or first key on 140 * the next page doesn't match. Make a special effort not to 141 * unpin the page the original match was on, but also make sure 142 * it's unpinned if an error occurs. 143 */ 144 if (e->index < NEXTINDEX(h)) 145 break; 146 for (;;) { 147 if ((pg = h->nextpg) == P_INVALID) 148 goto done1; 149 if (h->pgno != save.page->pgno) 150 mpool_put(t->bt_mp, h, 0); 151 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) { 152 if (h->pgno == save.page->pgno) 153 mpool_put(t->bt_mp, save.page, 0); 154 return (RET_ERROR); 155 } 156 if (NEXTINDEX(h) != 0) { 157 e->page = h; 158 e->index = 0; 159 break; 160 } 161 } 162 163 if (__bt_cmp(t, key, e) != 0) 164 break; 165 } 166 167 /* 168 * Reach here with the last page that was looked at pinned, and it may 169 * or may not be the same as the page with the original match. If it's 170 * not, release it. 171 */ 172 done1: if (h->pgno != save.page->pgno) 173 mpool_put(t->bt_mp, h, 0); 174 175 /* 176 * Walk backwards from the record previous to the record returned by 177 * __bt_search, skipping empty pages, until a current record doesn't 178 * match the key or reach the beginning of the tree. 179 */ 180 *e = save; 181 for (;;) { 182 if (e->index) 183 --e->index; 184 for (h = e->page; e->index; --e->index) { 185 if (__bt_cmp(t, key, e) != 0) 186 goto done2; 187 if (h->pgno == cpgno && e->index == cindex) { 188 if (NOTSET(t, BTF_DELCRSR)) { 189 SET(t, BTF_DELCRSR); 190 deleted = 1; 191 } 192 } else { 193 if (__bt_dleaf(t, h, e->index) == RET_ERROR) 194 goto err; 195 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 196 deleted = 1; 197 } 198 } 199 200 if ((pg = h->prevpg) == P_INVALID) 201 goto done2; 202 mpool_put(t->bt_mp, h, 0); 203 if ((e->page = mpool_get(t->bt_mp, pg, 0)) == NULL) 204 return (RET_ERROR); 205 e->index = NEXTINDEX(h); 206 } 207 208 /* 209 * Reach here with the last page that was looked at pinned. Release 210 * it. 211 */ 212 done2: mpool_put(t->bt_mp, h, 0); 213 return (deleted ? RET_SUCCESS : RET_SPECIAL); 214 215 err: mpool_put(t->bt_mp, h, 0); 216 return (RET_ERROR); 217 } 218 219 /* 220 * __BT_DLEAF -- Delete a single record from a leaf page. 221 * 222 * Parameters: 223 * t: tree 224 * index: index on current page to delete 225 * 226 * Returns: 227 * RET_SUCCESS, RET_ERROR. 228 */ 229 int 230 __bt_dleaf(t, h, index) 231 BTREE *t; 232 PAGE *h; 233 int index; 234 { 235 register BLEAF *bl; 236 register index_t *ip, offset; 237 register size_t nbytes; 238 register int cnt; 239 char *from; 240 void *to; 241 242 /* 243 * Delete a record from a btree leaf page. Internal records are never 244 * deleted from internal pages, regardless of the records that caused 245 * them to be added being deleted. Pages made empty by deletion are 246 * not reclaimed. They are, however, made available for reuse. 247 * 248 * Pack the remaining entries at the end of the page, shift the indices 249 * down, overwriting the deleted record and its index. If the record 250 * uses overflow pages, make them available for reuse. 251 */ 252 to = bl = GETBLEAF(h, index); 253 if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR) 254 return (RET_ERROR); 255 if (bl->flags & P_BIGDATA && 256 __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR) 257 return (RET_ERROR); 258 nbytes = NBLEAF(bl); 259 260 /* 261 * Compress the key/data pairs. Compress and adjust the [BR]LEAF 262 * offsets. Reset the headers. 263 */ 264 from = (char *)h + h->upper; 265 bcopy(from, from + nbytes, (char *)to - from); 266 h->upper += nbytes; 267 268 offset = h->linp[index]; 269 for (cnt = &h->linp[index] - (ip = &h->linp[0]); cnt--; ++ip) 270 if (ip[0] < offset) 271 ip[0] += nbytes; 272 for (cnt = &h->linp[NEXTINDEX(h)] - ip; --cnt; ++ip) 273 ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; 274 h->lower -= sizeof(index_t); 275 return (RET_SUCCESS); 276 } 277