Lines Matching +full:page +full:- +full:level
1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
45 static int __bt_curdel(BTREE *, const DBT *, PAGE *, u_int);
46 static int __bt_pdelete(BTREE *, PAGE *);
47 static int __bt_relink(BTREE *, PAGE *);
48 static int __bt_stkacq(BTREE *, PAGE **, CURSOR *);
61 PAGE *h; in __bt_delete()
64 t = dbp->internal; in __bt_delete()
66 /* Toss any page pinned across calls. */ in __bt_delete()
67 if (t->bt_pinned != NULL) { in __bt_delete()
68 mpool_put(t->bt_mp, t->bt_pinned, 0); in __bt_delete()
69 t->bt_pinned = NULL; in __bt_delete()
72 /* Check for change to a read-only tree. */ in __bt_delete()
87 c = &t->bt_cursor; in __bt_delete()
91 if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL) in __bt_delete()
95 * If the page is about to be emptied, we'll need to in __bt_delete()
99 if (__bt_stkacq(t, &h, &t->bt_cursor)) in __bt_delete()
102 status = __bt_dleaf(t, NULL, h, c->pg.index); in __bt_delete()
108 mpool_put(t->bt_mp, in __bt_delete()
123 * __bt_stkacq --
128 * hp: pointer to current, pinned PAGE pointer
135 __bt_stkacq(BTREE *t, PAGE **hp, CURSOR *c) in __bt_stkacq()
140 PAGE *h; in __bt_stkacq()
144 int exact, level; in __bt_stkacq() local
148 * currently locked page so we don't hit an already-locked page. in __bt_stkacq()
151 mpool_put(t->bt_mp, h, 0); in __bt_stkacq()
152 if ((e = __bt_search(t, &c->key, &exact)) == NULL) in __bt_stkacq()
154 h = e->page; in __bt_stkacq()
157 if (h->pgno == c->pg.pgno) in __bt_stkacq()
161 * Move right, looking for the page. At each move we have to move in __bt_stkacq()
162 * up the stack until we don't have to move to the next page. If in __bt_stkacq()
163 * we have to change pages at an internal level, we have to fix the in __bt_stkacq()
166 while (h->pgno != c->pg.pgno) { in __bt_stkacq()
167 if ((nextpg = h->nextpg) == P_INVALID) in __bt_stkacq()
169 mpool_put(t->bt_mp, h, 0); in __bt_stkacq()
172 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { in __bt_stkacq()
173 /* Get the parent page. */ in __bt_stkacq()
174 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) in __bt_stkacq()
178 if (parent->index != NEXTINDEX(h) - 1) { in __bt_stkacq()
179 idx = parent->index + 1; in __bt_stkacq()
180 BT_PUSH(t, h->pgno, idx); in __bt_stkacq()
183 mpool_put(t->bt_mp, h, 0); in __bt_stkacq()
187 while (level--) { in __bt_stkacq()
188 /* Push the next level down onto the stack. */ in __bt_stkacq()
190 pgno = bi->pgno; in __bt_stkacq()
193 /* Lose the currently pinned page. */ in __bt_stkacq()
194 mpool_put(t->bt_mp, h, 0); in __bt_stkacq()
196 /* Get the next level down. */ in __bt_stkacq()
197 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) in __bt_stkacq()
201 mpool_put(t->bt_mp, h, 0); in __bt_stkacq()
202 if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL) in __bt_stkacq()
206 if (h->pgno == c->pg.pgno) in __bt_stkacq()
210 mpool_put(t->bt_mp, h, 0); in __bt_stkacq()
211 if ((e = __bt_search(t, &c->key, &exact)) == NULL) in __bt_stkacq()
213 h = e->page; in __bt_stkacq()
216 * Move left, looking for the page. At each move we have to move in __bt_stkacq()
218 * next page. If we have to change pages at an internal level, we in __bt_stkacq()
221 while (h->pgno != c->pg.pgno) { in __bt_stkacq()
222 if ((prevpg = h->prevpg) == P_INVALID) in __bt_stkacq()
224 mpool_put(t->bt_mp, h, 0); in __bt_stkacq()
227 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { in __bt_stkacq()
228 /* Get the parent page. */ in __bt_stkacq()
229 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) in __bt_stkacq()
233 if (parent->index != 0) { in __bt_stkacq()
234 idx = parent->index - 1; in __bt_stkacq()
235 BT_PUSH(t, h->pgno, idx); in __bt_stkacq()
238 mpool_put(t->bt_mp, h, 0); in __bt_stkacq()
242 while (level--) { in __bt_stkacq()
243 /* Push the next level down onto the stack. */ in __bt_stkacq()
245 pgno = bi->pgno; in __bt_stkacq()
247 /* Lose the currently pinned page. */ in __bt_stkacq()
248 mpool_put(t->bt_mp, h, 0); in __bt_stkacq()
250 /* Get the next level down. */ in __bt_stkacq()
251 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) in __bt_stkacq()
254 idx = NEXTINDEX(h) - 1; in __bt_stkacq()
257 mpool_put(t->bt_mp, h, 0); in __bt_stkacq()
258 if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL) in __bt_stkacq()
263 ret: mpool_put(t->bt_mp, h, 0); in __bt_stkacq()
264 return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL); in __bt_stkacq()
268 * __bt_bdelete --
282 PAGE *h; in __bt_bdelete()
287 /* Find any matching record; __bt_search pins the page. */ in __bt_bdelete()
291 mpool_put(t->bt_mp, e->page, 0); in __bt_bdelete()
297 * there are duplicates and we reach either side of the page, do in __bt_bdelete()
301 h = e->page; in __bt_bdelete()
303 if (__bt_dleaf(t, key, h, e->index)) { in __bt_bdelete()
304 mpool_put(t->bt_mp, h, 0); in __bt_bdelete()
312 mpool_put(t->bt_mp, h, MPOOL_DIRTY); in __bt_bdelete()
316 } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0); in __bt_bdelete()
318 /* Check for right-hand edge of the page. */ in __bt_bdelete()
319 if (e->index == NEXTINDEX(h)) in __bt_bdelete()
322 /* Delete from the key to the beginning of the page. */ in __bt_bdelete()
323 while (e->index-- > 0) { in __bt_bdelete()
326 if (__bt_dleaf(t, key, h, e->index) == RET_ERROR) { in __bt_bdelete()
327 mpool_put(t->bt_mp, h, 0); in __bt_bdelete()
330 if (e->index == 0) in __bt_bdelete()
334 /* Check for an empty page. */ in __bt_bdelete()
341 /* Put the page. */ in __bt_bdelete()
342 mpool_put(t->bt_mp, h, MPOOL_DIRTY); in __bt_bdelete()
350 * __bt_pdelete --
351 * Delete a single page from the tree.
355 * h: leaf page
360 * Side-effects:
361 * mpool_put's the page
364 __bt_pdelete(BTREE *t, PAGE *h) in __bt_pdelete()
367 PAGE *pg; in __bt_pdelete()
374 * Walk the parent page stack -- a LIFO stack of the pages that were in __bt_pdelete()
375 * traversed when we searched for the page where the delete occurred. in __bt_pdelete()
376 * Each stack entry is a page number and a page index offset. The in __bt_pdelete()
377 * offset is for the page traversed on the search. We've just deleted in __bt_pdelete()
378 * a page, so we have to delete the key from the parent page. in __bt_pdelete()
380 * If the delete from the parent page makes it empty, this process may in __bt_pdelete()
381 * continue all the way up the tree. We stop if we reach the root page in __bt_pdelete()
383 * delete does not empty the page. in __bt_pdelete()
386 /* Get the parent page. */ in __bt_pdelete()
387 if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) in __bt_pdelete()
390 idx = parent->index; in __bt_pdelete()
394 if (bi->flags & P_BIGKEY && in __bt_pdelete()
395 __ovfl_delete(t, bi->bytes) == RET_ERROR) { in __bt_pdelete()
396 mpool_put(t->bt_mp, pg, 0); in __bt_pdelete()
402 * root page. If it's the rootpage, turn it back into an empty in __bt_pdelete()
403 * leaf page. in __bt_pdelete()
406 if (pg->pgno == P_ROOT) { in __bt_pdelete()
407 pg->lower = BTDATAOFF; in __bt_pdelete()
408 pg->upper = t->bt_psize; in __bt_pdelete()
409 pg->flags = P_BLEAF; in __bt_pdelete()
416 /* Pack remaining key items at the end of the page. */ in __bt_pdelete()
417 nksize = NBINTERNAL(bi->ksize); in __bt_pdelete()
418 from = (char *)pg + pg->upper; in __bt_pdelete()
419 memmove(from + nksize, from, (char *)bi - from); in __bt_pdelete()
420 pg->upper += nksize; in __bt_pdelete()
423 offset = pg->linp[idx]; in __bt_pdelete()
424 for (cnt = idx, ip = &pg->linp[0]; cnt--; ++ip) in __bt_pdelete()
427 for (cnt = NEXTINDEX(pg) - idx; --cnt; ++ip) in __bt_pdelete()
429 pg->lower -= sizeof(indx_t); in __bt_pdelete()
432 mpool_put(t->bt_mp, pg, MPOOL_DIRTY); in __bt_pdelete()
436 /* Free the leaf page, as long as it wasn't the root. */ in __bt_pdelete()
437 if (h->pgno == P_ROOT) { in __bt_pdelete()
438 mpool_put(t->bt_mp, h, MPOOL_DIRTY); in __bt_pdelete()
445 * __bt_dleaf --
446 * Delete a single record from a leaf page.
451 * h: page
452 * idx: index on page to delete
458 __bt_dleaf(BTREE *t, const DBT *key, PAGE *h, u_int idx) in __bt_dleaf()
467 if (F_ISSET(&t->bt_cursor, CURS_INIT) && in __bt_dleaf()
468 !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && in __bt_dleaf()
469 t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index == idx && in __bt_dleaf()
475 if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR) in __bt_dleaf()
477 if (bl->flags & P_BIGDATA && in __bt_dleaf()
478 __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR) in __bt_dleaf()
481 /* Pack the remaining key/data items at the end of the page. */ in __bt_dleaf()
483 from = (char *)h + h->upper; in __bt_dleaf()
484 memmove(from + nbytes, from, (char *)to - from); in __bt_dleaf()
485 h->upper += nbytes; in __bt_dleaf()
488 offset = h->linp[idx]; in __bt_dleaf()
489 for (cnt = idx, ip = &h->linp[0]; cnt--; ++ip) in __bt_dleaf()
492 for (cnt = NEXTINDEX(h) - idx; --cnt; ++ip) in __bt_dleaf()
494 h->lower -= sizeof(indx_t); in __bt_dleaf()
496 /* If the cursor is on this page, adjust it as necessary. */ in __bt_dleaf()
497 if (F_ISSET(&t->bt_cursor, CURS_INIT) && in __bt_dleaf()
498 !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && in __bt_dleaf()
499 t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index > idx) in __bt_dleaf()
500 --t->bt_cursor.pg.index; in __bt_dleaf()
506 * __bt_curdel --
512 * h: page
513 * idx: index on page to delete
519 __bt_curdel(BTREE *t, const DBT *key, PAGE *h, u_int idx) in __bt_curdel()
523 PAGE *pg; in __bt_curdel()
530 c = &t->bt_cursor; in __bt_curdel()
541 e.page = h; in __bt_curdel()
544 &c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS) in __bt_curdel()
547 key = &c->key; in __bt_curdel()
549 /* Check previous key, if not at the beginning of the page. */ in __bt_curdel()
551 e.page = h; in __bt_curdel()
552 e.index = idx - 1; in __bt_curdel()
558 /* Check next key, if not at the end of the page. */ in __bt_curdel()
559 if (idx < NEXTINDEX(h) - 1) { in __bt_curdel()
560 e.page = h; in __bt_curdel()
567 /* Check previous key if at the beginning of the page. */ in __bt_curdel()
568 if (idx == 0 && h->prevpg != P_INVALID) { in __bt_curdel()
569 if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) in __bt_curdel()
571 e.page = pg; in __bt_curdel()
572 e.index = NEXTINDEX(pg) - 1; in __bt_curdel()
577 mpool_put(t->bt_mp, pg, 0); in __bt_curdel()
579 /* Check next key if at the end of the page. */ in __bt_curdel()
580 if (idx == NEXTINDEX(h) - 1 && h->nextpg != P_INVALID) { in __bt_curdel()
581 if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) in __bt_curdel()
583 e.page = pg; in __bt_curdel()
587 dup1: mpool_put(t->bt_mp, pg, 0); in __bt_curdel()
588 dup2: c->pg.pgno = e.page->pgno; in __bt_curdel()
589 c->pg.index = e.index; in __bt_curdel()
592 mpool_put(t->bt_mp, pg, 0); in __bt_curdel()
595 e.page = h; in __bt_curdel()
598 __bt_ret(t, &e, &c->key, &c->key, NULL, NULL, 1)) == RET_SUCCESS) { in __bt_curdel()
606 * __bt_relink --
607 * Link around a deleted page.
611 * h: page to be deleted
614 __bt_relink(BTREE *t, PAGE *h) in __bt_relink()
616 PAGE *pg; in __bt_relink()
618 if (h->nextpg != P_INVALID) { in __bt_relink()
619 if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) in __bt_relink()
621 pg->prevpg = h->prevpg; in __bt_relink()
622 mpool_put(t->bt_mp, pg, MPOOL_DIRTY); in __bt_relink()
624 if (h->prevpg != P_INVALID) { in __bt_relink()
625 if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) in __bt_relink()
627 pg->nextpg = h->nextpg; in __bt_relink()
628 mpool_put(t->bt_mp, pg, MPOOL_DIRTY); in __bt_relink()