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