#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid[] = "@(#)bt_delete.c 8.13 (Berkeley) 7/28/94";
#endif
#include <sys/cdefs.h>
__FBSDID("$FreeBSD: src/lib/libc/db/btree/bt_delete.c,v 1.2 2002/03/21 22:46:25 obrien Exp $");
#include <sys/types.h>
#include <errno.h>
#include <stdio.h>
#include <string.h>
#include <db.h>
#include "btree.h"
static int __bt_bdelete(BTREE *, const DBT *);
static int __bt_curdel(BTREE *, const DBT *, PAGE *, u_int);
static int __bt_pdelete(BTREE *, PAGE *);
static int __bt_relink(BTREE *, PAGE *);
static int __bt_stkacq(BTREE *, PAGE **, CURSOR *);
int
__bt_delete(dbp, key, flags)
const DB *dbp;
const DBT *key;
u_int flags;
{
BTREE *t;
CURSOR *c;
PAGE *h;
int status;
t = dbp->internal;
if (t->bt_pinned != NULL) {
mpool_put(t->bt_mp, t->bt_pinned, 0);
t->bt_pinned = NULL;
}
if (F_ISSET(t, B_RDONLY)) {
errno = EPERM;
return (RET_ERROR);
}
switch (flags) {
case 0:
status = __bt_bdelete(t, key);
break;
case R_CURSOR:
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 (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;
}
default:
errno = EINVAL;
return (RET_ERROR);
}
if (status == RET_SUCCESS)
F_SET(t, B_MODIFIED);
return (status);
}
static int
__bt_stkacq(t, hp, c)
BTREE *t;
PAGE **hp;
CURSOR *c;
{
BINTERNAL *bi;
EPG *e;
EPGNO *parent;
PAGE *h;
indx_t index;
pgno_t pgno;
recno_t nextpg, prevpg;
int exact, level;
h = *hp;
mpool_put(t->bt_mp, h, 0);
if ((e = __bt_search(t, &c->key, &exact)) == NULL)
return (1);
h = e->page;
if (h->pgno == c->pg.pgno)
goto ret;
while (h->pgno != c->pg.pgno) {
if ((nextpg = h->nextpg) == P_INVALID)
break;
mpool_put(t->bt_mp, h, 0);
for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
return (1);
if (parent->index != NEXTINDEX(h) - 1) {
index = parent->index + 1;
BT_PUSH(t, h->pgno, index);
break;
}
mpool_put(t->bt_mp, h, 0);
}
while (level--) {
bi = GETBINTERNAL(h, index);
pgno = bi->pgno;
BT_PUSH(t, pgno, 0);
mpool_put(t->bt_mp, h, 0);
if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
return (1);
index = 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;
mpool_put(t->bt_mp, h, 0);
if ((e = __bt_search(t, &c->key, &exact)) == NULL)
return (1);
h = e->page;
while (h->pgno != c->pg.pgno) {
if ((prevpg = h->prevpg) == P_INVALID)
break;
mpool_put(t->bt_mp, h, 0);
for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
return (1);
if (parent->index != 0) {
index = parent->index - 1;
BT_PUSH(t, h->pgno, index);
break;
}
mpool_put(t->bt_mp, h, 0);
}
while (level--) {
bi = GETBINTERNAL(h, index);
pgno = bi->pgno;
mpool_put(t->bt_mp, h, 0);
if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
return (1);
index = NEXTINDEX(h) - 1;
BT_PUSH(t, pgno, index);
}
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);
}
static int
__bt_bdelete(t, key)
BTREE *t;
const DBT *key;
{
EPG *e;
PAGE *h;
int deleted, exact, redo;
deleted = 0;
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);
}
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);
if (e->index == NEXTINDEX(h))
redo = 1;
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;
}
if (NEXTINDEX(h) == 0) {
if (__bt_pdelete(t, h))
return (RET_ERROR);
goto loop;
}
mpool_put(t->bt_mp, h, MPOOL_DIRTY);
if (redo)
goto loop;
return (RET_SUCCESS);
}
static int
__bt_pdelete(t, h)
BTREE *t;
PAGE *h;
{
BINTERNAL *bi;
PAGE *pg;
EPGNO *parent;
indx_t cnt, index, *ip, offset;
u_int32_t nksize;
char *from;
while ((parent = BT_POP(t)) != NULL) {
if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
return (RET_ERROR);
index = parent->index;
bi = GETBINTERNAL(pg, index);
if (bi->flags & P_BIGKEY &&
__ovfl_delete(t, bi->bytes) == RET_ERROR) {
mpool_put(t->bt_mp, pg, 0);
return (RET_ERROR);
}
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 {
nksize = NBINTERNAL(bi->ksize);
from = (char *)pg + pg->upper;
memmove(from + nksize, from, (char *)bi - from);
pg->upper += nksize;
offset = pg->linp[index];
for (cnt = index, ip = &pg->linp[0]; cnt--; ++ip)
if (ip[0] < offset)
ip[0] += nksize;
for (cnt = NEXTINDEX(pg) - index; --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;
}
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));
}
int
__bt_dleaf(t, key, h, index)
BTREE *t;
const DBT *key;
PAGE *h;
u_int index;
{
BLEAF *bl;
indx_t cnt, *ip, offset;
u_int32_t nbytes;
void *to;
char *from;
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 == index &&
__bt_curdel(t, key, h, index))
return (RET_ERROR);
to = bl = GETBLEAF(h, index);
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);
nbytes = NBLEAF(bl);
from = (char *)h + h->upper;
memmove(from + nbytes, from, (char *)to - from);
h->upper += nbytes;
offset = h->linp[index];
for (cnt = index, ip = &h->linp[0]; cnt--; ++ip)
if (ip[0] < offset)
ip[0] += nbytes;
for (cnt = NEXTINDEX(h) - index; --cnt; ++ip)
ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
h->lower -= sizeof(indx_t);
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 > index)
--t->bt_cursor.pg.index;
return (RET_SUCCESS);
}
static int
__bt_curdel(t, key, h, index)
BTREE *t;
const DBT *key;
PAGE *h;
u_int index;
{
CURSOR *c;
EPG e;
PAGE *pg;
int curcopy, status;
c = &t->bt_cursor;
F_CLR(c, CURS_AFTER | CURS_BEFORE | CURS_ACQUIRE);
curcopy = 0;
if (!F_ISSET(t, B_NODUPS)) {
if (key == NULL) {
e.page = h;
e.index = index;
if ((status = __bt_ret(t, &e,
&c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS)
return (status);
curcopy = 1;
key = &c->key;
}
if (index > 0) {
e.page = h;
e.index = index - 1;
if (__bt_cmp(t, key, &e) == 0) {
F_SET(c, CURS_BEFORE);
goto dup2;
}
}
if (index < NEXTINDEX(h) - 1) {
e.page = h;
e.index = index + 1;
if (__bt_cmp(t, key, &e) == 0) {
F_SET(c, CURS_AFTER);
goto dup2;
}
}
if (index == 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);
}
if (index == 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 = index;
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);
}
static int
__bt_relink(t, h)
BTREE *t;
PAGE *h;
{
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);
}