#include <sys/types.h>
#include <errno.h>
#include <stdio.h>
#include <string.h>
#include "../include/db.h"
#include "btree.h"

Include dependency graph for bt_delete.c:

Functions
static int	__bt_bdelete (BTREE t, const DBT key)

static int	__bt_curdel (BTREE t, const DBT key, PAGE *h, u_int idx)

int	__bt_delete (DB dbp, const DBT key, u_int flags) const

int	__bt_dleaf (BTREE t, const DBT key, PAGE *h, u_int idx)

static int	__bt_pdelete (BTREE t, PAGE h)

static int	__bt_relink (BTREE t, PAGE h)

static int	__bt_stkacq (BTREE t, PAGE hp, CURSOR c)

static int __bt_bdelete	__P ((BTREE , const DBT ))

static int __bt_curdel	__P ((BTREE , const DBT , PAGE *, u_int))

static int __bt_pdelete	__P ((BTREE , PAGE ))

static int __bt_stkacq	__P ((BTREE , PAGE , CURSOR ))

Function Documentation

◆ __bt_bdelete()

static int __bt_bdelete	(	BTREE *	t,
		const DBT *	key
	)

static

Definition at line 291 of file bt_delete.c.

References __bt_cmp(), __bt_dleaf(), __bt_pdelete(), __bt_search(), B_NODUPS, _btree::bt_mp, F_ISSET, _epg::index, MPOOL_DIRTY, mpool_put(), NEXTINDEX, NULL, _epg::page, RET_ERROR, RET_SPECIAL, and RET_SUCCESS.

Referenced by __bt_delete().

 {
    EPG *e;
    PAGE *h;
    int deleted, exact, redo;
 
    deleted = 0;
 
    /* Find any matching record; __bt_search pins the page. */
 loop: if ((e = __bt_search(t, key, &exact)) == NULL)
       return (deleted ? RET_SUCCESS : RET_ERROR);
    if (!exact) {
       mpool_put(t->bt_mp, e->page, 0);
       return (deleted ? RET_SUCCESS : RET_SPECIAL);
    }
 
    /*
     * Delete forward, then delete backward, from the found key.  If
     * there are duplicates and we reach either side of the page, do
     * the key search again, so that we get them all.
     */
    redo = 0;
    h = e->page;
    do {
       if (__bt_dleaf(t, key, h, e->index)) {
          mpool_put(t->bt_mp, h, 0);
          return (RET_ERROR);
       }
       if (F_ISSET(t, B_NODUPS)) {
          if (NEXTINDEX(h) == 0) {
             if (__bt_pdelete(t, h))
                return (RET_ERROR);
          } else
             mpool_put(t->bt_mp, h, MPOOL_DIRTY);
          return (RET_SUCCESS);
       }
       deleted = 1;
    } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);
 
    /* Check for right-hand edge of the page. */
    if (e->index == NEXTINDEX(h))
       redo = 1;
 
    /* Delete from the key to the beginning of the page. */
    while (e->index-- > 0) {
       if (__bt_cmp(t, key, e) != 0)
          break;
       if (__bt_dleaf(t, key, h, e->index) == RET_ERROR) {
          mpool_put(t->bt_mp, h, 0);
          return (RET_ERROR);
       }
       if (e->index == 0)
          redo = 1;
    }
 
    /* Check for an empty page. */
    if (NEXTINDEX(h) == 0) {
       if (__bt_pdelete(t, h))
          return (RET_ERROR);
       goto loop;
    }
 
    /* Put the page. */
    mpool_put(t->bt_mp, h, MPOOL_DIRTY);
 
    if (redo)
       goto loop;
    return (RET_SUCCESS);
 }

◆ __bt_curdel()

static int __bt_curdel	(	BTREE *	t,
		const DBT *	key,
		PAGE *	h,
		u_int	idx
	)

static

Definition at line 539 of file bt_delete.c.

References __bt_cmp(), __bt_ret(), B_NODUPS, _btree::bt_cursor, _btree::bt_mp, c, CURS_ACQUIRE, CURS_AFTER, CURS_BEFORE, F_CLR, F_ISSET, F_SET, _epgno::index, _epg::index, _cursor::key, mpool_get(), mpool_put(), NEXTINDEX, _page::nextpg, NULL, P_INVALID, _epg::page, _cursor::pg, _page::pgno, _epgno::pgno, _page::prevpg, RET_ERROR, RET_SUCCESS, and status.

Referenced by __bt_dleaf().

 {
    CURSOR *c;
    EPG e;
    PAGE *pg;
    int curcopy, status;
 
    /*
     * If there are duplicates, move forward or backward to one.
     * Otherwise, copy the key into the cursor area.
     */
    c = &t->bt_cursor;
    F_CLR(c, CURS_AFTER | CURS_BEFORE | CURS_ACQUIRE);
 
    curcopy = 0;
    if (!F_ISSET(t, B_NODUPS)) {
       /*
        * We're going to have to do comparisons.  If we weren't
        * provided a copy of the key, i.e. the user is deleting
        * the current cursor position, get one.
        */
       if (key == NULL) {
          e.page = h;
          e.index = idx;
          if ((status = __bt_ret(t, &e,
              &c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS)
             return (status);
          curcopy = 1;
          key = &c->key;
       }
       /* Check previous key, if not at the beginning of the page. */
       if (idx > 0) {
          e.page = h;
          e.index = idx - 1;
          if (__bt_cmp(t, key, &e) == 0) {
             F_SET(c, CURS_BEFORE);
             goto dup2;
          }
       }
       /* Check next key, if not at the end of the page. */
       if (idx < NEXTINDEX(h) - 1) {
          e.page = h;
          e.index = idx + 1;
          if (__bt_cmp(t, key, &e) == 0) {
             F_SET(c, CURS_AFTER);
             goto dup2;
          }
       }
       /* Check previous key if at the beginning of the page. */
       if (idx == 0 && h->prevpg != P_INVALID) {
          if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
             return (RET_ERROR);
          e.page = pg;
          e.index = NEXTINDEX(pg) - 1;
          if (__bt_cmp(t, key, &e) == 0) {
             F_SET(c, CURS_BEFORE);
             goto dup1;
          }
          mpool_put(t->bt_mp, pg, 0);
       }
       /* Check next key if at the end of the page. */
       if (idx == NEXTINDEX(h) - 1 && h->nextpg != P_INVALID) {
          if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
             return (RET_ERROR);
          e.page = pg;
          e.index = 0;
          if (__bt_cmp(t, key, &e) == 0) {
             F_SET(c, CURS_AFTER);
 dup1:          mpool_put(t->bt_mp, pg, 0);
 dup2:          c->pg.pgno = e.page->pgno;
             c->pg.index = e.index;
             return (RET_SUCCESS);
          }
          mpool_put(t->bt_mp, pg, 0);
       }
    }
    e.page = h;
    e.index = idx;
    if (curcopy || (status =
        __bt_ret(t, &e, &c->key, &c->key, NULL, NULL, 1)) == RET_SUCCESS) {
       F_SET(c, CURS_ACQUIRE);
       return (RET_SUCCESS);
    }
    return (status);
 }

◆ __bt_delete()

int __bt_delete	(	DB *	dbp,
		const DBT *	key,
		u_int	flags
	)		const

Definition at line 63 of file bt_delete.c.

References __bt_bdelete(), __bt_dleaf(), __bt_pdelete(), __bt_stkacq(), B_MODIFIED, B_RDONLY, _btree::bt_cursor, _btree::bt_mp, _btree::bt_pinned, c, CURS_ACQUIRE, CURS_AFTER, CURS_BEFORE, CURS_INIT, errno, F_ISSET, F_SET, _epgno::index, __db::internal, MPOOL_DIRTY, mpool_get(), mpool_put(), NEXTINDEX, NULL, _cursor::pg, _epgno::pgno, R_CURSOR, RET_ERROR, RET_SPECIAL, RET_SUCCESS, and status.

Referenced by __bt_open().

 {
    BTREE *t;
    CURSOR *c;
    PAGE *h;
    int status;
 
    t = dbp->internal;
 
    /* Toss any page pinned across calls. */
    if (t->bt_pinned != NULL) {
       mpool_put(t->bt_mp, t->bt_pinned, 0);
       t->bt_pinned = NULL;
    }
 
    /* Check for change to a read-only tree. */
    if (F_ISSET(t, B_RDONLY)) {
       errno = EPERM;
       return (RET_ERROR);
    }
 
    switch (flags) {
    case 0:
       status = __bt_bdelete(t, key);
       break;
    case R_CURSOR:
       /*
        * If flags is R_CURSOR, delete the cursor.  Must already
        * have started a scan and not have already deleted it.
        */
       c = &t->bt_cursor;
       if (F_ISSET(c, CURS_INIT)) {
          if (F_ISSET(c, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE))
             return (RET_SPECIAL);
          if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
             return (RET_ERROR);
 
          /*
           * If the page is about to be emptied, we'll need to
           * delete it, which means we have to acquire a stack.
           */
          if (NEXTINDEX(h) == 1)
             if (__bt_stkacq(t, &h, &t->bt_cursor))
                return (RET_ERROR);
 
          status = __bt_dleaf(t, NULL, h, c->pg.index);
 
          if (NEXTINDEX(h) == 0 && status == RET_SUCCESS) {
             if (__bt_pdelete(t, h))
                return (RET_ERROR);
          } else
             mpool_put(t->bt_mp,
                 h, status == RET_SUCCESS ? MPOOL_DIRTY : 0);
          break;
       }
       /* FALLTHROUGH */
    default:
       errno = EINVAL;
       return (RET_ERROR);
    }
    if (status == RET_SUCCESS)
       F_SET(t, B_MODIFIED);
    return (status);
 }

◆ __bt_dleaf()

int __bt_dleaf	(	BTREE *	t,
		const DBT *	key,
		PAGE *	h,
		u_int	idx
	)

Definition at line 474 of file bt_delete.c.

References __bt_curdel(), __ovfl_delete(), _btree::bt_cursor, _bleaf::bytes, CURS_ACQUIRE, CURS_INIT, F_ISSET, _bleaf::flags, GETBLEAF, _epgno::index, _bleaf::ksize, _page::linp, _page::lower, NBLEAF, NEXTINDEX, P_BIGDATA, P_BIGKEY, _cursor::pg, _page::pgno, _epgno::pgno, RET_ERROR, RET_SUCCESS, and _page::upper.

Referenced by __bt_bdelete(), __bt_delete(), and __bt_put().

 {
    BLEAF *bl;
    indx_t cnt, *ip, offset;
    u_int32_t nbytes;
    void *to;
    char *from;
 
    /* If this record is referenced by the cursor, delete the cursor. */
    if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
        !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
        t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index == idx &&
        __bt_curdel(t, key, h, idx))
       return (RET_ERROR);
 
    /* If the entry uses overflow pages, make them available for reuse. */
    to = bl = GETBLEAF(h, idx);
    if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR)
       return (RET_ERROR);
    if (bl->flags & P_BIGDATA &&
        __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR)
       return (RET_ERROR);
 
    /* Pack the remaining key/data items at the end of the page. */
    nbytes = NBLEAF(bl);
    from = (char *)h + h->upper;
    memmove(from + nbytes, from, (char *)to - from);
    h->upper += nbytes;
 
    /* Adjust the indices' offsets, shift the indices down. */
    offset = h->linp[idx];
    for (cnt = idx, ip = &h->linp[0]; cnt--; ++ip)
       if (ip[0] < offset)
          ip[0] += nbytes;
    for (cnt = NEXTINDEX(h) - idx; --cnt; ++ip)
       ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
    h->lower -= sizeof(indx_t);
 
    /* If the cursor is on this page, adjust it as necessary. */
    if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
        !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
        t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index > idx)
       --t->bt_cursor.pg.index;
 
    return (RET_SUCCESS);
 }

◆ __bt_pdelete()

static int __bt_pdelete	(	BTREE *	t,
		PAGE *	h
	)

static

Definition at line 378 of file bt_delete.c.

References __bt_free(), __bt_relink(), __ovfl_delete(), _btree::bt_mp, BT_POP, _btree::bt_psize, BTDATAOFF, _binternal::bytes, _page::flags, _binternal::flags, GETBINTERNAL, _epgno::index, _binternal::ksize, _page::linp, _page::lower, MPOOL_DIRTY, mpool_get(), mpool_put(), NBINTERNAL, NEXTINDEX, NULL, P_BIGKEY, P_BLEAF, P_ROOT, _page::pgno, _epgno::pgno, RET_ERROR, RET_SUCCESS, and _page::upper.

Referenced by __bt_bdelete(), and __bt_delete().

 {
    BINTERNAL *bi;
    PAGE *pg;
    EPGNO *parent;
    indx_t cnt, idx, *ip, offset;
    u_int32_t nksize;
    char *from;
 
    /*
     * Walk the parent page stack -- a LIFO stack of the pages that were
     * traversed when we searched for the page where the delete occurred.
     * Each stack entry is a page number and a page index offset.  The
     * offset is for the page traversed on the search.  We've just deleted
     * a page, so we have to delete the key from the parent page.
     *
     * If the delete from the parent page makes it empty, this process may
     * continue all the way up the tree.  We stop if we reach the root page
     * (which is never deleted, it's just not worth the effort) or if the
     * delete does not empty the page.
     */
    while ((parent = BT_POP(t)) != NULL) {
       /* Get the parent page. */
       if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
          return (RET_ERROR);
 
       idx = parent->index;
       bi = GETBINTERNAL(pg, idx);
 
       /* Free any overflow pages. */
       if (bi->flags & P_BIGKEY &&
           __ovfl_delete(t, bi->bytes) == RET_ERROR) {
          mpool_put(t->bt_mp, pg, 0);
          return (RET_ERROR);
       }
 
       /*
        * Free the parent if it has only the one key and it's not the
        * root page. If it's the rootpage, turn it back into an empty
        * leaf page.
        */
       if (NEXTINDEX(pg) == 1) {
          if (pg->pgno == P_ROOT) {
             pg->lower = BTDATAOFF;
             pg->upper = t->bt_psize;
             pg->flags = P_BLEAF;
          } else {
             if (__bt_relink(t, pg) || __bt_free(t, pg))
                return (RET_ERROR);
             continue;
          }
       } else {
          /* Pack remaining key items at the end of the page. */
          nksize = NBINTERNAL(bi->ksize);
          from = (char *)pg + pg->upper;
          memmove(from + nksize, from, (char *)bi - from);
          pg->upper += nksize;
 
          /* Adjust indices' offsets, shift the indices down. */
          offset = pg->linp[idx];
          for (cnt = idx, ip = &pg->linp[0]; cnt--; ++ip)
             if (ip[0] < offset)
                ip[0] += nksize;
          for (cnt = NEXTINDEX(pg) - idx; --cnt; ++ip)
             ip[0] = ip[1] < offset ? ip[1] + nksize : ip[1];
          pg->lower -= sizeof(indx_t);
       }
 
       mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
       break;
    }
 
    /* Free the leaf page, as long as it wasn't the root. */
    if (h->pgno == P_ROOT) {
       mpool_put(t->bt_mp, h, MPOOL_DIRTY);
       return (RET_SUCCESS);
    }
    return (__bt_relink(t, h) || __bt_free(t, h));
 }

◆ __bt_relink()

static int __bt_relink	(	BTREE *	t,
		PAGE *	h
	)

static

Definition at line 638 of file bt_delete.c.

References _btree::bt_mp, MPOOL_DIRTY, mpool_get(), mpool_put(), _page::nextpg, NULL, P_INVALID, _page::prevpg, and RET_ERROR.

Referenced by __bt_pdelete().

 {
    PAGE *pg;
 
    if (h->nextpg != P_INVALID) {
       if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
          return (RET_ERROR);
       pg->prevpg = h->prevpg;
       mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
    }
    if (h->prevpg != P_INVALID) {
       if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
          return (RET_ERROR);
       pg->nextpg = h->nextpg;
       mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
    }
    return (0);
 }

◆ __bt_stkacq()

static int __bt_stkacq	(	BTREE *	t,
		PAGE **	hp,
		CURSOR *	c
	)

static

Definition at line 144 of file bt_delete.c.

References __bt_search(), _btree::bt_mp, BT_POP, BT_PUSH, GETBINTERNAL, hp, _epgno::index, _cursor::key, mpool_get(), mpool_put(), NEXTINDEX, _page::nextpg, NULL, P_INVALID, _epg::page, _cursor::pg, _page::pgno, _binternal::pgno, _epgno::pgno, and _page::prevpg.

Referenced by __bt_delete().

 {
    BINTERNAL *bi;
    EPG *e;
    EPGNO *parent;
    PAGE *h;
    indx_t idx = 0;
    pgno_t pgno;
    recno_t nextpg, prevpg;
    int exact, level;
 
    /*
     * Find the first occurrence of the key in the tree.  Toss the
     * currently locked page so we don't hit an already-locked page.
     */
    h = *hp;
    mpool_put(t->bt_mp, h, 0);
    if ((e = __bt_search(t, &c->key, &exact)) == NULL)
       return (1);
    h = e->page;
 
    /* See if we got it in one shot. */
    if (h->pgno == c->pg.pgno)
       goto ret;
 
    /*
     * Move right, looking for the page.  At each move we have to move
     * up the stack until we don't have to move to the next page.  If
     * we have to change pages at an internal level, we have to fix the
     * stack back up.
     */
    while (h->pgno != c->pg.pgno) {
       if ((nextpg = h->nextpg) == P_INVALID)
          break;
       mpool_put(t->bt_mp, h, 0);
 
       /* Move up the stack. */
       for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
          /* Get the parent page. */
          if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
             return (1);
 
          /* Move to the next index. */
          if (parent->index != NEXTINDEX(h) - 1) {
             idx = parent->index + 1;
             BT_PUSH(t, h->pgno, idx);
             break;
          }
          mpool_put(t->bt_mp, h, 0);
       }
 
       /* Restore the stack. */
       while (level--) {
          /* Push the next level down onto the stack. */
          bi = GETBINTERNAL(h, idx);
          pgno = bi->pgno;
          BT_PUSH(t, pgno, 0);
 
          /* Lose the currently pinned page. */
          mpool_put(t->bt_mp, h, 0);
 
          /* Get the next level down. */
          if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
             return (1);
          idx = 0;
       }
       mpool_put(t->bt_mp, h, 0);
       if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL)
          return (1);
    }
 
    if (h->pgno == c->pg.pgno)
       goto ret;
 
    /* Reacquire the original stack. */
    mpool_put(t->bt_mp, h, 0);
    if ((e = __bt_search(t, &c->key, &exact)) == NULL)
       return (1);
    h = e->page;
 
    /*
     * Move left, looking for the page.  At each move we have to move
     * up the stack until we don't have to change pages to move to the
     * next page.  If we have to change pages at an internal level, we
     * have to fix the stack back up.
     */
    while (h->pgno != c->pg.pgno) {
       if ((prevpg = h->prevpg) == P_INVALID)
          break;
       mpool_put(t->bt_mp, h, 0);
 
       /* Move up the stack. */
       for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
          /* Get the parent page. */
          if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
             return (1);
 
          /* Move to the next index. */
          if (parent->index != 0) {
             idx = parent->index - 1;
             BT_PUSH(t, h->pgno, idx);
             break;
          }
          mpool_put(t->bt_mp, h, 0);
       }
 
       /* Restore the stack. */
       while (level--) {
          /* Push the next level down onto the stack. */
          bi = GETBINTERNAL(h, idx);
          pgno = bi->pgno;
 
          /* Lose the currently pinned page. */
          mpool_put(t->bt_mp, h, 0);
 
          /* Get the next level down. */
          if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
             return (1);
 
          idx = NEXTINDEX(h) - 1;
          BT_PUSH(t, pgno, idx);
       }
       mpool_put(t->bt_mp, h, 0);
       if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL)
          return (1);
    }
 
 
 ret:  mpool_put(t->bt_mp, h, 0);
    return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL);
 }

◆ __P() [1/4]

static int __bt_bdelete __P ( (BTREE *, const DBT *) )

static

◆ __P() [2/4]

static int __bt_curdel __P ( (BTREE *, const DBT *, PAGE *, u_int) )

static

◆ __P() [3/4]

static int __bt_relink __P ( (BTREE *, PAGE *) )

static

◆ __P() [4/4]

static int __bt_stkacq __P ( (BTREE *, PAGE **, CURSOR *) )

static

Functions

Function Documentation

◆ __bt_bdelete()

◆ __bt_curdel()

◆ __bt_delete()

◆ __bt_dleaf()

◆ __bt_pdelete()

◆ __bt_relink()

◆ __bt_stkacq()

◆ __P() [1/4]

◆ __P() [2/4]

◆ __P() [3/4]

◆ __P() [4/4]