/[resiprocate]/main/contrib/db/btree/bt_delete.c
ViewVC logotype

Contents of /main/contrib/db/btree/bt_delete.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 5295 - (show annotations) (download)
Mon Aug 22 00:30:05 2005 UTC (14 years, 2 months ago) by jason
File MIME type: text/plain
File size: 15177 byte(s)
merged 5270:HEAD from b-directory-reorg
1 /*-
2 * See the file LICENSE for redistribution information.
3 *
4 * Copyright (c) 1996-2004
5 * Sleepycat Software. All rights reserved.
6 */
7 /*
8 * Copyright (c) 1990, 1993, 1994, 1995, 1996
9 * Keith Bostic. All rights reserved.
10 */
11 /*
12 * Copyright (c) 1990, 1993, 1994, 1995
13 * The Regents of the University of California. All rights reserved.
14 *
15 * This code is derived from software contributed to Berkeley by
16 * Mike Olson.
17 *
18 * Redistribution and use in source and binary forms, with or without
19 * modification, are permitted provided that the following conditions
20 * are met:
21 * 1. Redistributions of source code must retain the above copyright
22 * notice, this list of conditions and the following disclaimer.
23 * 2. Redistributions in binary form must reproduce the above copyright
24 * notice, this list of conditions and the following disclaimer in the
25 * documentation and/or other materials provided with the distribution.
26 * 3. Neither the name of the University nor the names of its contributors
27 * may be used to endorse or promote products derived from this software
28 * without specific prior written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
31 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
32 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
34 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
35 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
36 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
38 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
39 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
40 * SUCH DAMAGE.
41 *
42 * $Id: bt_delete.c,v 11.49 2004/02/27 12:38:28 bostic Exp $
43 */
44
45 #include "db_config.h"
46
47 #ifndef NO_SYSTEM_INCLUDES
48 #include <sys/types.h>
49
50 #include <string.h>
51 #endif
52
53 #include "db_int.h"
54 #include "dbinc/db_page.h"
55 #include "dbinc/db_shash.h"
56 #include "dbinc/btree.h"
57 #include "dbinc/lock.h"
58 #include "dbinc/mp.h"
59
60 /*
61 * __bam_ditem --
62 * Delete one or more entries from a page.
63 *
64 * PUBLIC: int __bam_ditem __P((DBC *, PAGE *, u_int32_t));
65 */
66 int
67 __bam_ditem(dbc, h, indx)
68 DBC *dbc;
69 PAGE *h;
70 u_int32_t indx;
71 {
72 BINTERNAL *bi;
73 BKEYDATA *bk;
74 DB *dbp;
75 DB_MPOOLFILE *mpf;
76 u_int32_t nbytes;
77 int ret;
78 db_indx_t *inp;
79
80 dbp = dbc->dbp;
81 mpf = dbp->mpf;
82 inp = P_INP(dbp, h);
83
84 switch (TYPE(h)) {
85 case P_IBTREE:
86 bi = GET_BINTERNAL(dbp, h, indx);
87 switch (B_TYPE(bi->type)) {
88 case B_DUPLICATE:
89 case B_KEYDATA:
90 nbytes = BINTERNAL_SIZE(bi->len);
91 break;
92 case B_OVERFLOW:
93 nbytes = BINTERNAL_SIZE(bi->len);
94 if ((ret =
95 __db_doff(dbc, ((BOVERFLOW *)bi->data)->pgno)) != 0)
96 return (ret);
97 break;
98 default:
99 return (__db_pgfmt(dbp->dbenv, PGNO(h)));
100 }
101 break;
102 case P_IRECNO:
103 nbytes = RINTERNAL_SIZE;
104 break;
105 case P_LBTREE:
106 /*
107 * If it's a duplicate key, discard the index and don't touch
108 * the actual page item.
109 *
110 * !!!
111 * This works because no data item can have an index matching
112 * any other index so even if the data item is in a key "slot",
113 * it won't match any other index.
114 */
115 if ((indx % 2) == 0) {
116 /*
117 * Check for a duplicate after us on the page. NOTE:
118 * we have to delete the key item before deleting the
119 * data item, otherwise the "indx + P_INDX" calculation
120 * won't work!
121 */
122 if (indx + P_INDX < (u_int32_t)NUM_ENT(h) &&
123 inp[indx] == inp[indx + P_INDX])
124 return (__bam_adjindx(dbc,
125 h, indx, indx + O_INDX, 0));
126 /*
127 * Check for a duplicate before us on the page. It
128 * doesn't matter if we delete the key item before or
129 * after the data item for the purposes of this one.
130 */
131 if (indx > 0 && inp[indx] == inp[indx - P_INDX])
132 return (__bam_adjindx(dbc,
133 h, indx, indx - P_INDX, 0));
134 }
135 /* FALLTHROUGH */
136 case P_LDUP:
137 case P_LRECNO:
138 bk = GET_BKEYDATA(dbp, h, indx);
139 switch (B_TYPE(bk->type)) {
140 case B_DUPLICATE:
141 nbytes = BOVERFLOW_SIZE;
142 break;
143 case B_OVERFLOW:
144 nbytes = BOVERFLOW_SIZE;
145 if ((ret = __db_doff(
146 dbc, (GET_BOVERFLOW(dbp, h, indx))->pgno)) != 0)
147 return (ret);
148 break;
149 case B_KEYDATA:
150 nbytes = BKEYDATA_SIZE(bk->len);
151 break;
152 default:
153 return (__db_pgfmt(dbp->dbenv, PGNO(h)));
154 }
155 break;
156 default:
157 return (__db_pgfmt(dbp->dbenv, PGNO(h)));
158 }
159
160 /* Delete the item and mark the page dirty. */
161 if ((ret = __db_ditem(dbc, h, indx, nbytes)) != 0)
162 return (ret);
163 if ((ret = __memp_fset(mpf, h, DB_MPOOL_DIRTY)) != 0)
164 return (ret);
165
166 return (0);
167 }
168
169 /*
170 * __bam_adjindx --
171 * Adjust an index on the page.
172 *
173 * PUBLIC: int __bam_adjindx __P((DBC *, PAGE *, u_int32_t, u_int32_t, int));
174 */
175 int
176 __bam_adjindx(dbc, h, indx, indx_copy, is_insert)
177 DBC *dbc;
178 PAGE *h;
179 u_int32_t indx, indx_copy;
180 int is_insert;
181 {
182 DB *dbp;
183 DB_MPOOLFILE *mpf;
184 db_indx_t copy, *inp;
185 int ret;
186
187 dbp = dbc->dbp;
188 mpf = dbp->mpf;
189 inp = P_INP(dbp, h);
190
191 /* Log the change. */
192 if (DBC_LOGGING(dbc)) {
193 if ((ret = __bam_adj_log(dbp, dbc->txn, &LSN(h), 0,
194 PGNO(h), &LSN(h), indx, indx_copy, (u_int32_t)is_insert)) != 0)
195 return (ret);
196 } else
197 LSN_NOT_LOGGED(LSN(h));
198
199 /* Shuffle the indices and mark the page dirty. */
200 if (is_insert) {
201 copy = inp[indx_copy];
202 if (indx != NUM_ENT(h))
203 memmove(&inp[indx + O_INDX], &inp[indx],
204 sizeof(db_indx_t) * (NUM_ENT(h) - indx));
205 inp[indx] = copy;
206 ++NUM_ENT(h);
207 } else {
208 --NUM_ENT(h);
209 if (indx != NUM_ENT(h))
210 memmove(&inp[indx], &inp[indx + O_INDX],
211 sizeof(db_indx_t) * (NUM_ENT(h) - indx));
212 }
213 if ((ret = __memp_fset(mpf, h, DB_MPOOL_DIRTY)) != 0)
214 return (ret);
215
216 return (0);
217 }
218
219 /*
220 * __bam_dpages --
221 * Delete a set of locked pages.
222 *
223 * PUBLIC: int __bam_dpages __P((DBC *, EPG *));
224 */
225 int
226 __bam_dpages(dbc, stack_epg)
227 DBC *dbc;
228 EPG *stack_epg;
229 {
230 BTREE_CURSOR *cp;
231 BINTERNAL *bi;
232 DB *dbp;
233 DBT a, b;
234 DB_LOCK c_lock, p_lock;
235 DB_MPOOLFILE *mpf;
236 EPG *epg;
237 PAGE *child, *parent;
238 db_indx_t nitems;
239 db_pgno_t pgno, root_pgno;
240 db_recno_t rcnt;
241 int done, ret, t_ret;
242
243 dbp = dbc->dbp;
244 mpf = dbp->mpf;
245 cp = (BTREE_CURSOR *)dbc->internal;
246
247 /*
248 * We have the entire stack of deletable pages locked.
249 *
250 * Btree calls us with a pointer to the beginning of a stack, where
251 * the first page in the stack is to have a single item deleted, and
252 * the rest of the pages are to be removed.
253 *
254 * Recno calls us with a pointer into the middle of the stack, where
255 * the referenced page is to have a single item deleted, and pages
256 * after the stack reference are to be removed.
257 *
258 * First, discard any pages that we don't care about.
259 */
260 ret = 0;
261 for (epg = cp->sp; epg < stack_epg; ++epg) {
262 if ((t_ret = __memp_fput(mpf, epg->page, 0)) != 0 && ret == 0)
263 ret = t_ret;
264 if ((t_ret = __TLPUT(dbc, epg->lock)) != 0 && ret == 0)
265 ret = t_ret;
266 }
267 if (ret != 0)
268 goto err;
269
270 /*
271 * !!!
272 * There is an interesting deadlock situation here. We have to relink
273 * the leaf page chain around the leaf page being deleted. Consider
274 * a cursor walking through the leaf pages, that has the previous page
275 * read-locked and is waiting on a lock for the page we're deleting.
276 * It will deadlock here. Before we unlink the subtree, we relink the
277 * leaf page chain.
278 */
279 if ((ret = __bam_relink(dbc, cp->csp->page, NULL)) != 0)
280 goto err;
281
282 /*
283 * Delete the last item that references the underlying pages that are
284 * to be deleted, and adjust cursors that reference that page. Then,
285 * save that page's page number and item count and release it. If
286 * the application isn't retaining locks because it's running without
287 * transactions, this lets the rest of the tree get back to business
288 * immediately.
289 */
290 if ((ret = __bam_ditem(dbc, epg->page, epg->indx)) != 0)
291 goto err;
292 if ((ret = __bam_ca_di(dbc, PGNO(epg->page), epg->indx, -1)) != 0)
293 goto err;
294
295 pgno = PGNO(epg->page);
296 nitems = NUM_ENT(epg->page);
297
298 ret = __memp_fput(mpf, epg->page, 0);
299 if ((t_ret = __TLPUT(dbc, epg->lock)) != 0 && ret == 0)
300 ret = t_ret;
301 if (ret != 0)
302 goto err_inc;
303
304 /* Free the rest of the pages in the stack. */
305 while (++epg <= cp->csp) {
306 /*
307 * Delete page entries so they will be restored as part of
308 * recovery. We don't need to do cursor adjustment here as
309 * the pages are being emptied by definition and so cannot
310 * be referenced by a cursor.
311 */
312 if (NUM_ENT(epg->page) != 0) {
313 DB_ASSERT(NUM_ENT(epg->page) == 1);
314
315 if ((ret = __bam_ditem(dbc, epg->page, epg->indx)) != 0)
316 goto err;
317 }
318
319 ret = __db_free(dbc, epg->page);
320 epg->page = NULL;
321 if ((t_ret = __TLPUT(dbc, epg->lock)) != 0 && ret == 0)
322 ret = t_ret;
323 if (ret != 0)
324 goto err_inc;
325 }
326
327 if (0) {
328 err_inc: ++epg;
329 err: for (; epg <= cp->csp; ++epg) {
330 if (epg->page != NULL)
331 (void)__memp_fput(mpf, epg->page, 0);
332 (void)__TLPUT(dbc, epg->lock);
333 }
334 BT_STK_CLR(cp);
335 return (ret);
336 }
337 BT_STK_CLR(cp);
338
339 /*
340 * If we just deleted the next-to-last item from the root page, the
341 * tree can collapse one or more levels. While there remains only a
342 * single item on the root page, write lock the last page referenced
343 * by the root page and copy it over the root page.
344 */
345 root_pgno = cp->root;
346 if (pgno != root_pgno || nitems != 1)
347 return (0);
348
349 for (done = 0; !done;) {
350 /* Initialize. */
351 parent = child = NULL;
352 LOCK_INIT(p_lock);
353 LOCK_INIT(c_lock);
354
355 /* Lock the root. */
356 pgno = root_pgno;
357 if ((ret =
358 __db_lget(dbc, 0, pgno, DB_LOCK_WRITE, 0, &p_lock)) != 0)
359 goto stop;
360 if ((ret = __memp_fget(mpf, &pgno, 0, &parent)) != 0)
361 goto stop;
362
363 if (NUM_ENT(parent) != 1)
364 goto stop;
365
366 switch (TYPE(parent)) {
367 case P_IBTREE:
368 /*
369 * If this is overflow, then try to delete it.
370 * The child may or may not still point at it.
371 */
372 bi = GET_BINTERNAL(dbp, parent, 0);
373 if (B_TYPE(bi->type) == B_OVERFLOW)
374 if ((ret = __db_doff(dbc,
375 ((BOVERFLOW *)bi->data)->pgno)) != 0)
376 goto stop;
377 pgno = bi->pgno;
378 break;
379 case P_IRECNO:
380 pgno = GET_RINTERNAL(dbp, parent, 0)->pgno;
381 break;
382 default:
383 goto stop;
384 }
385
386 /* Lock the child page. */
387 if ((ret =
388 __db_lget(dbc, 0, pgno, DB_LOCK_WRITE, 0, &c_lock)) != 0)
389 goto stop;
390 if ((ret = __memp_fget(mpf, &pgno, 0, &child)) != 0)
391 goto stop;
392
393 /* Log the change. */
394 if (DBC_LOGGING(dbc)) {
395 memset(&a, 0, sizeof(a));
396 a.data = child;
397 a.size = dbp->pgsize;
398 memset(&b, 0, sizeof(b));
399 b.data = P_ENTRY(dbp, parent, 0);
400 b.size = TYPE(parent) == P_IRECNO ? RINTERNAL_SIZE :
401 BINTERNAL_SIZE(((BINTERNAL *)b.data)->len);
402 if ((ret = __bam_rsplit_log(dbp, dbc->txn,
403 &child->lsn, 0, PGNO(child), &a, PGNO(parent),
404 RE_NREC(parent), &b, &parent->lsn)) != 0)
405 goto stop;
406 } else
407 LSN_NOT_LOGGED(child->lsn);
408
409 /*
410 * Make the switch.
411 *
412 * One fixup -- internal pages below the top level do not store
413 * a record count, so we have to preserve it if we're not
414 * converting to a leaf page. Note also that we are about to
415 * overwrite the parent page, including its LSN. This is OK
416 * because the log message we wrote describing this update
417 * stores its LSN on the child page. When the child is copied
418 * onto the parent, the correct LSN is copied into place.
419 */
420 COMPQUIET(rcnt, 0);
421 if (F_ISSET(cp, C_RECNUM) && LEVEL(child) > LEAFLEVEL)
422 rcnt = RE_NREC(parent);
423 memcpy(parent, child, dbp->pgsize);
424 PGNO(parent) = root_pgno;
425 if (F_ISSET(cp, C_RECNUM) && LEVEL(child) > LEAFLEVEL)
426 RE_NREC_SET(parent, rcnt);
427
428 /* Mark the pages dirty. */
429 if ((ret = __memp_fset(mpf, parent, DB_MPOOL_DIRTY)) != 0)
430 goto stop;
431 if ((ret = __memp_fset(mpf, child, DB_MPOOL_DIRTY)) != 0)
432 goto stop;
433
434 /* Adjust the cursors. */
435 if ((ret = __bam_ca_rsplit(dbc, PGNO(child), root_pgno)) != 0)
436 goto stop;
437
438 /*
439 * Free the page copied onto the root page and discard its
440 * lock. (The call to __db_free() discards our reference
441 * to the page.)
442 */
443 if ((ret = __db_free(dbc, child)) != 0) {
444 child = NULL;
445 goto stop;
446 }
447 child = NULL;
448
449 if (0) {
450 stop: done = 1;
451 }
452 if ((t_ret = __TLPUT(dbc, p_lock)) != 0 && ret == 0)
453 ret = t_ret;
454 if (parent != NULL &&
455 (t_ret = __memp_fput(mpf, parent, 0)) != 0 && ret == 0)
456 ret = t_ret;
457 if ((t_ret = __TLPUT(dbc, c_lock)) != 0 && ret == 0)
458 ret = t_ret;
459 if (child != NULL &&
460 (t_ret = __memp_fput(mpf, child, 0)) != 0 && ret == 0)
461 ret = t_ret;
462 }
463
464 return (ret);
465 }
466
467 /*
468 * __bam_relink --
469 * Relink around a deleted page.
470 *
471 * PUBLIC: int __bam_relink __P((DBC *, PAGE *, PAGE **));
472 */
473 int
474 __bam_relink(dbc, pagep, new_next)
475 DBC *dbc;
476 PAGE *pagep, **new_next;
477 {
478 DB *dbp;
479 PAGE *np, *pp;
480 DB_LOCK npl, ppl;
481 DB_LSN *nlsnp, *plsnp, ret_lsn;
482 DB_MPOOLFILE *mpf;
483 int ret, t_ret;
484
485 dbp = dbc->dbp;
486 np = pp = NULL;
487 LOCK_INIT(npl);
488 LOCK_INIT(ppl);
489 nlsnp = plsnp = NULL;
490 mpf = dbp->mpf;
491 ret = 0;
492
493 /*
494 * Retrieve and lock the one/two pages. For a remove, we may need
495 * two pages (the before and after). For an add, we only need one
496 * because, the split took care of the prev.
497 */
498 if (pagep->next_pgno != PGNO_INVALID) {
499 if ((ret = __db_lget(dbc,
500 0, pagep->next_pgno, DB_LOCK_WRITE, 0, &npl)) != 0)
501 goto err;
502 if ((ret = __memp_fget(mpf, &pagep->next_pgno, 0, &np)) != 0) {
503 ret = __db_pgerr(dbp, pagep->next_pgno, ret);
504 goto err;
505 }
506 nlsnp = &np->lsn;
507 }
508 if (pagep->prev_pgno != PGNO_INVALID) {
509 if ((ret = __db_lget(dbc,
510 0, pagep->prev_pgno, DB_LOCK_WRITE, 0, &ppl)) != 0)
511 goto err;
512 if ((ret = __memp_fget(mpf, &pagep->prev_pgno, 0, &pp)) != 0) {
513 ret = __db_pgerr(dbp, pagep->prev_pgno, ret);
514 goto err;
515 }
516 plsnp = &pp->lsn;
517 }
518
519 /* Log the change. */
520 if (DBC_LOGGING(dbc)) {
521 if ((ret = __bam_relink_log(dbp, dbc->txn, &ret_lsn, 0,
522 pagep->pgno, &pagep->lsn, pagep->prev_pgno, plsnp,
523 pagep->next_pgno, nlsnp)) != 0)
524 goto err;
525 } else
526 LSN_NOT_LOGGED(ret_lsn);
527 if (np != NULL)
528 np->lsn = ret_lsn;
529 if (pp != NULL)
530 pp->lsn = ret_lsn;
531 pagep->lsn = ret_lsn;
532
533 /*
534 * Modify and release the two pages.
535 *
536 * !!!
537 * The parameter new_next gets set to the page following the page we
538 * are removing. If there is no following page, then new_next gets
539 * set to NULL.
540 */
541 if (np != NULL) {
542 np->prev_pgno = pagep->prev_pgno;
543 if (new_next == NULL)
544 ret = __memp_fput(mpf, np, DB_MPOOL_DIRTY);
545 else {
546 *new_next = np;
547 ret = __memp_fset(mpf, np, DB_MPOOL_DIRTY);
548 }
549 if ((t_ret = __TLPUT(dbc, npl)) != 0 && ret == 0)
550 ret = t_ret;
551 if (ret != 0)
552 goto err;
553 } else if (new_next != NULL)
554 *new_next = NULL;
555
556 if (pp != NULL) {
557 pp->next_pgno = pagep->next_pgno;
558 ret = __memp_fput(mpf, pp, DB_MPOOL_DIRTY);
559 if ((t_ret = __TLPUT(dbc, ppl)) != 0 && ret == 0)
560 ret = t_ret;
561 if (ret != 0)
562 goto err;
563 }
564 return (0);
565
566 err: if (np != NULL)
567 (void)__memp_fput(mpf, np, 0);
568 (void)__TLPUT(dbc, npl);
569 if (pp != NULL)
570 (void)__memp_fput(mpf, pp, 0);
571 (void)__TLPUT(dbc, ppl);
572 return (ret);
573 }

webmaster AT resiprocate DOT org
ViewVC Help
Powered by ViewVC 1.1.27