#include "db_config.h"
#ifndef lint
static const char revid[] = "$Id: hash_page.c,v 1.2 2004/03/30 01:23:27 jtownsen Exp $";
#endif
#ifndef NO_SYSTEM_INCLUDES
#include <sys/types.h>
#include <string.h>
#endif
#include "db_int.h"
#include "dbinc/db_page.h"
#include "dbinc/db_shash.h"
#include "dbinc/hash.h"
#include "dbinc/lock.h"
#include "dbinc/mp.h"
static int __ham_c_delpg
__P((DBC *, db_pgno_t, db_pgno_t, u_int32_t, db_ham_mode, u_int32_t *));
int
__ham_item(dbc, mode, pgnop)
DBC *dbc;
db_lockmode_t mode;
db_pgno_t *pgnop;
{
DB *dbp;
HASH_CURSOR *hcp;
db_pgno_t next_pgno;
int ret;
dbp = dbc->dbp;
hcp = (HASH_CURSOR *)dbc->internal;
if (F_ISSET(hcp, H_DELETED)) {
__db_err(dbp->dbenv, "Attempt to return a deleted item");
return (EINVAL);
}
F_CLR(hcp, H_OK | H_NOMORE);
if ((ret = __ham_get_cpage(dbc, mode)) != 0)
return (ret);
recheck:
if (hcp->seek_size && hcp->seek_found_page == PGNO_INVALID &&
hcp->seek_size < P_FREESPACE(dbp, hcp->page))
hcp->seek_found_page = hcp->pgno;
if (hcp->indx < NUM_ENT(hcp->page) &&
HPAGE_TYPE(dbp, hcp->page, H_DATAINDEX(hcp->indx)) == H_OFFDUP) {
memcpy(pgnop,
HOFFDUP_PGNO(H_PAIRDATA(dbp, hcp->page, hcp->indx)),
sizeof(db_pgno_t));
F_SET(hcp, H_OK);
return (0);
}
if (F_ISSET(hcp, H_ISDUP))
memcpy(&hcp->dup_len,
HKEYDATA_DATA(H_PAIRDATA(dbp, hcp->page, hcp->indx)) +
hcp->dup_off, sizeof(db_indx_t));
if (hcp->indx >= (db_indx_t)NUM_ENT(hcp->page)) {
if (NEXT_PGNO(hcp->page) == PGNO_INVALID) {
F_SET(hcp, H_NOMORE);
return (DB_NOTFOUND);
}
next_pgno = NEXT_PGNO(hcp->page);
hcp->indx = 0;
if ((ret = __ham_next_cpage(dbc, next_pgno, 0)) != 0)
return (ret);
goto recheck;
}
F_SET(hcp, H_OK);
return (0);
}
int
__ham_item_reset(dbc)
DBC *dbc;
{
DB *dbp;
DB_MPOOLFILE *mpf;
HASH_CURSOR *hcp;
int ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
hcp = (HASH_CURSOR *)dbc->internal;
ret = 0;
if (hcp->page != NULL)
ret = __memp_fput(mpf, hcp->page, 0);
__ham_item_init(dbc);
return (ret);
}
void
__ham_item_init(dbc)
DBC *dbc;
{
HASH_CURSOR *hcp;
hcp = (HASH_CURSOR *)dbc->internal;
(void)__TLPUT(dbc, hcp->lock);
hcp->bucket = BUCKET_INVALID;
hcp->lbucket = BUCKET_INVALID;
LOCK_INIT(hcp->lock);
hcp->lock_mode = DB_LOCK_NG;
hcp->dup_off = 0;
hcp->dup_len = 0;
hcp->dup_tlen = 0;
hcp->seek_size = 0;
hcp->seek_found_page = PGNO_INVALID;
hcp->flags = 0;
hcp->pgno = PGNO_INVALID;
hcp->indx = NDX_INVALID;
hcp->page = NULL;
}
int
__ham_item_last(dbc, mode, pgnop)
DBC *dbc;
db_lockmode_t mode;
db_pgno_t *pgnop;
{
HASH_CURSOR *hcp;
int ret;
hcp = (HASH_CURSOR *)dbc->internal;
if ((ret = __ham_item_reset(dbc)) != 0)
return (ret);
hcp->bucket = hcp->hdr->max_bucket;
hcp->pgno = BUCKET_TO_PAGE(hcp, hcp->bucket);
F_SET(hcp, H_OK);
return (__ham_item_prev(dbc, mode, pgnop));
}
int
__ham_item_first(dbc, mode, pgnop)
DBC *dbc;
db_lockmode_t mode;
db_pgno_t *pgnop;
{
HASH_CURSOR *hcp;
int ret;
hcp = (HASH_CURSOR *)dbc->internal;
if ((ret = __ham_item_reset(dbc)) != 0)
return (ret);
F_SET(hcp, H_OK);
hcp->bucket = 0;
hcp->pgno = BUCKET_TO_PAGE(hcp, hcp->bucket);
return (__ham_item_next(dbc, mode, pgnop));
}
int
__ham_item_prev(dbc, mode, pgnop)
DBC *dbc;
db_lockmode_t mode;
db_pgno_t *pgnop;
{
DB *dbp;
HASH_CURSOR *hcp;
db_pgno_t next_pgno;
int ret;
hcp = (HASH_CURSOR *)dbc->internal;
dbp = dbc->dbp;
F_CLR(hcp, H_OK | H_NOMORE | H_DELETED);
if ((ret = __ham_get_cpage(dbc, mode)) != 0)
return (ret);
if (!F_ISSET(hcp, H_NEXT_NODUP) && F_ISSET(hcp, H_ISDUP)) {
if (HPAGE_TYPE(dbp, hcp->page, H_DATAINDEX(hcp->indx)) ==
H_OFFDUP) {
memcpy(pgnop,
HOFFDUP_PGNO(H_PAIRDATA(dbp, hcp->page, hcp->indx)),
sizeof(db_pgno_t));
F_SET(hcp, H_OK);
return (0);
}
if (hcp->dup_off != 0) {
memcpy(&hcp->dup_len, HKEYDATA_DATA(
H_PAIRDATA(dbp, hcp->page, hcp->indx))
+ hcp->dup_off - sizeof(db_indx_t),
sizeof(db_indx_t));
hcp->dup_off -=
DUP_SIZE(hcp->dup_len);
return (__ham_item(dbc, mode, pgnop));
}
}
if (F_ISSET(hcp, H_DUPONLY)) {
F_CLR(hcp, H_OK);
F_SET(hcp, H_NOMORE);
return (0);
} else
F_CLR(hcp, H_ISDUP);
if (hcp->indx == 0) {
hcp->pgno = PREV_PGNO(hcp->page);
if (hcp->pgno == PGNO_INVALID) {
F_SET(hcp, H_NOMORE);
return (DB_NOTFOUND);
} else if ((ret =
__ham_next_cpage(dbc, hcp->pgno, 0)) != 0)
return (ret);
else
hcp->indx = NUM_ENT(hcp->page);
}
if (hcp->indx == NDX_INVALID) {
DB_ASSERT(hcp->page != NULL);
hcp->indx = NUM_ENT(hcp->page);
for (next_pgno = NEXT_PGNO(hcp->page);
next_pgno != PGNO_INVALID;
next_pgno = NEXT_PGNO(hcp->page)) {
if ((ret = __ham_next_cpage(dbc, next_pgno, 0)) != 0)
return (ret);
hcp->indx = NUM_ENT(hcp->page);
}
if (hcp->indx == 0) {
F_SET(hcp, H_NOMORE);
return (DB_NOTFOUND);
}
}
hcp->indx -= 2;
return (__ham_item(dbc, mode, pgnop));
}
int
__ham_item_next(dbc, mode, pgnop)
DBC *dbc;
db_lockmode_t mode;
db_pgno_t *pgnop;
{
HASH_CURSOR *hcp;
int ret;
hcp = (HASH_CURSOR *)dbc->internal;
if ((ret = __ham_get_cpage(dbc, mode)) != 0)
return (ret);
if (F_ISSET(hcp, H_DELETED)) {
if (hcp->indx != NDX_INVALID &&
F_ISSET(hcp, H_ISDUP) &&
HPAGE_TYPE(dbc->dbp, hcp->page, H_DATAINDEX(hcp->indx))
== H_DUPLICATE && hcp->dup_tlen == hcp->dup_off) {
if (F_ISSET(hcp, H_DUPONLY)) {
F_CLR(hcp, H_OK);
F_SET(hcp, H_NOMORE);
return (0);
} else {
F_CLR(hcp, H_ISDUP);
hcp->indx += 2;
}
} else if (!F_ISSET(hcp, H_ISDUP) && F_ISSET(hcp, H_DUPONLY)) {
F_CLR(hcp, H_OK);
F_SET(hcp, H_NOMORE);
return (0);
} else if (F_ISSET(hcp, H_ISDUP) &&
F_ISSET(hcp, H_NEXT_NODUP)) {
F_CLR(hcp, H_ISDUP);
hcp->indx += 2;
}
F_CLR(hcp, H_DELETED);
} else if (hcp->indx == NDX_INVALID) {
hcp->indx = 0;
F_CLR(hcp, H_ISDUP);
} else if (F_ISSET(hcp, H_NEXT_NODUP)) {
hcp->indx += 2;
F_CLR(hcp, H_ISDUP);
} else if (F_ISSET(hcp, H_ISDUP) && hcp->dup_tlen != 0) {
if (hcp->dup_off + DUP_SIZE(hcp->dup_len) >=
hcp->dup_tlen && F_ISSET(hcp, H_DUPONLY)) {
F_CLR(hcp, H_OK);
F_SET(hcp, H_NOMORE);
return (0);
}
hcp->dup_off += DUP_SIZE(hcp->dup_len);
if (hcp->dup_off >= hcp->dup_tlen) {
F_CLR(hcp, H_ISDUP);
hcp->indx += 2;
}
} else if (F_ISSET(hcp, H_DUPONLY)) {
F_CLR(hcp, H_OK);
F_SET(hcp, H_NOMORE);
return (0);
} else {
hcp->indx += 2;
F_CLR(hcp, H_ISDUP);
}
return (__ham_item(dbc, mode, pgnop));
}
void
__ham_putitem(dbp, p, dbt, type)
DB *dbp;
PAGE *p;
const DBT *dbt;
int type;
{
u_int16_t n, off;
db_indx_t *inp;
n = NUM_ENT(p);
inp = P_INP(dbp, p);
if (type == H_OFFPAGE) {
off = HOFFSET(p) - dbt->size;
HOFFSET(p) = inp[n] = off;
memcpy(P_ENTRY(dbp, p, n), dbt->data, dbt->size);
} else {
off = HOFFSET(p) - HKEYDATA_SIZE(dbt->size);
HOFFSET(p) = inp[n] = off;
PUT_HKEYDATA(P_ENTRY(dbp, p, n), dbt->data, dbt->size, type);
}
NUM_ENT(p) += 1;
}
void
__ham_reputpair(dbp, p, ndx, key, data)
DB *dbp;
PAGE *p;
u_int32_t ndx;
const DBT *key, *data;
{
db_indx_t i, *inp, movebytes, newbytes;
size_t psize;
u_int8_t *from;
psize = dbp->pgsize;
inp = P_INP(dbp, p);
movebytes = (db_indx_t)(
(ndx == 0 ? psize : inp[H_DATAINDEX(ndx - 2)]) - HOFFSET(p));
newbytes = key->size + data->size;
from = (u_int8_t *)p + HOFFSET(p);
memmove(from - newbytes, from, movebytes);
for (i = NUM_ENT(p) - 1; ; i-- ) {
inp[i + 2] = inp[i] - newbytes;
if (i == H_KEYINDEX(ndx))
break;
}
inp[H_KEYINDEX(ndx)] = (db_indx_t)(
(ndx == 0 ? psize : inp[H_DATAINDEX(ndx - 2)]) - key->size);
inp[H_DATAINDEX(ndx)] = inp[H_KEYINDEX(ndx)] - data->size;
memcpy(P_ENTRY(dbp, p, H_KEYINDEX(ndx)), key->data, key->size);
memcpy(P_ENTRY(dbp, p, H_DATAINDEX(ndx)), data->data, data->size);
HOFFSET(p) -= newbytes;
NUM_ENT(p) += 2;
}
int
__ham_del_pair(dbc, reclaim_page)
DBC *dbc;
int reclaim_page;
{
DB *dbp;
DBT data_dbt, key_dbt;
DB_LSN new_lsn, *n_lsn, tmp_lsn;
DB_MPOOLFILE *mpf;
HASH_CURSOR *hcp;
PAGE *n_pagep, *nn_pagep, *p, *p_pagep;
db_ham_mode op;
db_indx_t ndx;
db_pgno_t chg_pgno, pgno, tmp_pgno;
int ret, t_ret;
u_int32_t order;
dbp = dbc->dbp;
mpf = dbp->mpf;
hcp = (HASH_CURSOR *)dbc->internal;
n_pagep = p_pagep = nn_pagep = NULL;
ndx = hcp->indx;
if (hcp->page == NULL && (ret = __memp_fget(
mpf, &hcp->pgno, DB_MPOOL_CREATE, &hcp->page)) != 0)
return (ret);
p = hcp->page;
ret = 0;
if (HPAGE_PTYPE(H_PAIRKEY(dbp, p, ndx)) == H_OFFPAGE) {
memcpy(&pgno, HOFFPAGE_PGNO(P_ENTRY(dbp, p, H_KEYINDEX(ndx))),
sizeof(db_pgno_t));
ret = __db_doff(dbc, pgno);
}
if (ret == 0)
switch (HPAGE_PTYPE(H_PAIRDATA(dbp, p, ndx))) {
case H_OFFPAGE:
memcpy(&pgno,
HOFFPAGE_PGNO(P_ENTRY(dbp, p, H_DATAINDEX(ndx))),
sizeof(db_pgno_t));
ret = __db_doff(dbc, pgno);
break;
case H_OFFDUP:
case H_DUPLICATE:
F_CLR(hcp, H_ISDUP);
break;
}
if (ret)
return (ret);
if (DBC_LOGGING(dbc)) {
key_dbt.data = P_ENTRY(dbp, p, H_KEYINDEX(ndx));
key_dbt.size = LEN_HITEM(dbp, p, dbp->pgsize, H_KEYINDEX(ndx));
data_dbt.data = P_ENTRY(dbp, p, H_DATAINDEX(ndx));
data_dbt.size =
LEN_HITEM(dbp, p, dbp->pgsize, H_DATAINDEX(ndx));
if ((ret = __ham_insdel_log(dbp,
dbc->txn, &new_lsn, 0, DELPAIR, PGNO(p), (u_int32_t)ndx,
&LSN(p), &key_dbt, &data_dbt)) != 0)
return (ret);
} else
LSN_NOT_LOGGED(new_lsn);
LSN(p) = new_lsn;
__ham_dpair(dbp, p, ndx);
F_SET(hcp, H_DELETED);
F_CLR(hcp, H_OK);
if ((ret = __ham_c_update(dbc, 0, 0, 0)) != 0)
return (ret);
if (!STD_LOCKING(dbc)) {
--hcp->hdr->nelem;
if ((ret = __ham_dirty_meta(dbc)) != 0)
return (ret);
}
if (!reclaim_page ||
NUM_ENT(p) != 0 ||
(PREV_PGNO(p) == PGNO_INVALID && NEXT_PGNO(p) == PGNO_INVALID))
return (__memp_fset(mpf, p, DB_MPOOL_DIRTY));
if (PREV_PGNO(p) == PGNO_INVALID) {
if ((ret = __memp_fget(mpf, &NEXT_PGNO(p), 0, &n_pagep)) != 0)
return (ret);
if (NEXT_PGNO(n_pagep) != PGNO_INVALID && (ret =
__memp_fget(mpf, &NEXT_PGNO(n_pagep), 0, &nn_pagep)) != 0)
goto err;
if (DBC_LOGGING(dbc)) {
key_dbt.data = n_pagep;
key_dbt.size = dbp->pgsize;
if ((ret = __ham_copypage_log(dbp,
dbc->txn, &new_lsn, 0, PGNO(p),
&LSN(p), PGNO(n_pagep), &LSN(n_pagep),
NEXT_PGNO(n_pagep),
nn_pagep == NULL ? NULL : &LSN(nn_pagep),
&key_dbt)) != 0)
goto err;
} else
LSN_NOT_LOGGED(new_lsn);
LSN(p) = new_lsn;
LSN(n_pagep) = new_lsn;
if (NEXT_PGNO(n_pagep) != PGNO_INVALID)
LSN(nn_pagep) = new_lsn;
if (nn_pagep != NULL) {
PREV_PGNO(nn_pagep) = PGNO(p);
if ((ret =
__memp_fput(mpf, nn_pagep, DB_MPOOL_DIRTY)) != 0) {
nn_pagep = NULL;
goto err;
}
}
tmp_pgno = PGNO(p);
tmp_lsn = LSN(p);
memcpy(p, n_pagep, dbp->pgsize);
PGNO(p) = tmp_pgno;
LSN(p) = tmp_lsn;
PREV_PGNO(p) = PGNO_INVALID;
if ((ret = __ham_c_delpg(dbc, PGNO(n_pagep),
PGNO(p), 0, DB_HAM_DELFIRSTPG, &order)) != 0)
goto err;
hcp->indx = 0;
hcp->pgno = PGNO(p);
hcp->order += order;
if ((ret = __memp_fset(mpf, p, DB_MPOOL_DIRTY)) != 0)
goto err;
if ((ret = __db_free(dbc, n_pagep)) != 0) {
n_pagep = NULL;
goto err;
}
} else {
if ((ret = __memp_fget(mpf, &PREV_PGNO(p), 0, &p_pagep)) != 0)
goto err;
if (NEXT_PGNO(p) != PGNO_INVALID) {
if ((ret =
__memp_fget(mpf, &NEXT_PGNO(p), 0, &n_pagep)) != 0)
goto err;
n_lsn = &LSN(n_pagep);
} else {
n_pagep = NULL;
n_lsn = NULL;
}
NEXT_PGNO(p_pagep) = NEXT_PGNO(p);
if (n_pagep != NULL)
PREV_PGNO(n_pagep) = PGNO(p_pagep);
if (DBC_LOGGING(dbc)) {
if ((ret = __ham_newpage_log(dbp, dbc->txn,
&new_lsn, 0, DELOVFL, PREV_PGNO(p), &LSN(p_pagep),
PGNO(p), &LSN(p), NEXT_PGNO(p), n_lsn)) != 0)
goto err;
} else
LSN_NOT_LOGGED(new_lsn);
LSN(p_pagep) = new_lsn;
if (n_pagep)
LSN(n_pagep) = new_lsn;
LSN(p) = new_lsn;
if (NEXT_PGNO(p) == PGNO_INVALID) {
hcp->pgno = PGNO(p_pagep);
hcp->indx = NUM_ENT(p_pagep);
op = DB_HAM_DELLASTPG;
} else {
hcp->pgno = NEXT_PGNO(p);
hcp->indx = 0;
op = DB_HAM_DELMIDPG;
}
hcp->page = NULL;
chg_pgno = PGNO(p);
ret = __db_free(dbc, p);
if ((t_ret =
__memp_fput(mpf, p_pagep, DB_MPOOL_DIRTY)) != 0 && ret == 0)
ret = t_ret;
if (n_pagep != NULL && (t_ret =
__memp_fput(mpf, n_pagep, DB_MPOOL_DIRTY)) != 0 && ret == 0)
ret = t_ret;
if (ret != 0)
return (ret);
if ((ret = __ham_c_delpg(dbc,
chg_pgno, hcp->pgno, hcp->indx, op, &order)) != 0)
return (ret);
hcp->order += order;
}
return (ret);
err:
if (n_pagep != NULL)
(void)__memp_fput(mpf, n_pagep, 0);
if (nn_pagep != NULL)
(void)__memp_fput(mpf, nn_pagep, 0);
if (p_pagep != NULL)
(void)__memp_fput(mpf, p_pagep, 0);
return (ret);
}
int
__ham_replpair(dbc, dbt, make_dup)
DBC *dbc;
DBT *dbt;
u_int32_t make_dup;
{
DB *dbp;
DBT old_dbt, tdata, tmp;
DB_ENV *dbenv;
DB_LSN new_lsn;
HASH_CURSOR *hcp;
int32_t change;
u_int32_t dup_flag, len, memsize;
int beyond_eor, is_big, ret, type;
u_int8_t *beg, *dest, *end, *hk, *src;
void *memp;
dbp = dbc->dbp;
dbenv = dbp->dbenv;
hcp = (HASH_CURSOR *)dbc->internal;
change = dbt->size - dbt->dlen;
hk = H_PAIRDATA(dbp, hcp->page, hcp->indx);
is_big = HPAGE_PTYPE(hk) == H_OFFPAGE;
if (is_big)
memcpy(&len, HOFFPAGE_TLEN(hk), sizeof(u_int32_t));
else
len = LEN_HKEYDATA(dbp, hcp->page,
dbp->pgsize, H_DATAINDEX(hcp->indx));
beyond_eor = dbt->doff + dbt->dlen > len;
if (beyond_eor)
change += dbt->doff + dbt->dlen - len;
if (change > (int32_t)P_FREESPACE(dbp, hcp->page) ||
beyond_eor || is_big) {
memset(&tmp, 0, sizeof(tmp));
if ((ret =
__db_ret(dbp, hcp->page, H_KEYINDEX(hcp->indx),
&tmp, &dbc->my_rkey.data, &dbc->my_rkey.ulen)) != 0)
return (ret);
dup_flag = F_ISSET(hcp, H_ISDUP);
if (dbt->doff == 0 && dbt->dlen == len) {
ret = __ham_del_pair(dbc, 0);
if (ret == 0)
ret = __ham_add_el(dbc,
&tmp, dbt, dup_flag ? H_DUPLICATE : H_KEYDATA);
} else {
type = HPAGE_PTYPE(hk) != H_OFFPAGE ?
HPAGE_PTYPE(hk) : H_KEYDATA;
memset(&tdata, 0, sizeof(tdata));
memp = NULL;
memsize = 0;
if ((ret = __db_ret(dbp, hcp->page,
H_DATAINDEX(hcp->indx), &tdata, &memp, &memsize))
!= 0)
goto err;
if ((ret = __ham_del_pair(dbc, 0)) != 0) {
__os_free(dbenv, memp);
goto err;
}
if (change > 0) {
if ((ret = __os_realloc(dbenv,
tdata.size + change, &tdata.data)) != 0)
return (ret);
memp = tdata.data;
memsize = tdata.size + change;
memset((u_int8_t *)tdata.data + tdata.size,
0, change);
}
end = (u_int8_t *)tdata.data + tdata.size;
src = (u_int8_t *)tdata.data + dbt->doff + dbt->dlen;
if (src < end && tdata.size > dbt->doff + dbt->dlen) {
len = tdata.size - dbt->doff - dbt->dlen;
dest = src + change;
memmove(dest, src, len);
}
memcpy((u_int8_t *)tdata.data + dbt->doff,
dbt->data, dbt->size);
tdata.size += change;
ret = __ham_add_el(dbc, &tmp, &tdata, type);
__os_free(dbenv, memp);
}
F_SET(hcp, dup_flag);
err: return (ret);
}
beg = HKEYDATA_DATA(H_PAIRDATA(dbp, hcp->page, hcp->indx));
beg += dbt->doff;
if (DBC_LOGGING(dbc)) {
old_dbt.data = beg;
old_dbt.size = dbt->dlen;
if ((ret = __ham_replace_log(dbp,
dbc->txn, &new_lsn, 0, PGNO(hcp->page),
(u_int32_t)H_DATAINDEX(hcp->indx), &LSN(hcp->page),
(u_int32_t)dbt->doff, &old_dbt, dbt, make_dup)) != 0)
return (ret);
} else
LSN_NOT_LOGGED(new_lsn);
LSN(hcp->page) = new_lsn;
__ham_onpage_replace(dbp, hcp->page, (u_int32_t)H_DATAINDEX(hcp->indx),
(int32_t)dbt->doff, change, dbt);
return (0);
}
void
__ham_onpage_replace(dbp, pagep, ndx, off, change, dbt)
DB *dbp;
PAGE *pagep;
u_int32_t ndx;
int32_t off;
int32_t change;
DBT *dbt;
{
db_indx_t i, *inp;
int32_t len;
size_t pgsize;
u_int8_t *src, *dest;
int zero_me;
pgsize = dbp->pgsize;
inp = P_INP(dbp, pagep);
if (change != 0) {
zero_me = 0;
src = (u_int8_t *)(pagep) + HOFFSET(pagep);
if (off < 0)
len = inp[ndx] - HOFFSET(pagep);
else if ((u_int32_t)off >=
LEN_HKEYDATA(dbp, pagep, pgsize, ndx)) {
len = (int32_t)(HKEYDATA_DATA(P_ENTRY(dbp, pagep, ndx))
+ LEN_HKEYDATA(dbp, pagep, pgsize, ndx) - src);
zero_me = 1;
} else
len = (int32_t)(
(HKEYDATA_DATA(P_ENTRY(dbp, pagep, ndx)) + off) -
src);
dest = src - change;
memmove(dest, src, len);
if (zero_me)
memset(dest + len, 0, change);
for (i = ndx; i < NUM_ENT(pagep); i++)
inp[i] -= change;
HOFFSET(pagep) -= change;
}
if (off >= 0)
memcpy(HKEYDATA_DATA(P_ENTRY(dbp, pagep, ndx)) + off,
dbt->data, dbt->size);
else
memcpy(P_ENTRY(dbp, pagep, ndx), dbt->data, dbt->size);
}
int
__ham_split_page(dbc, obucket, nbucket)
DBC *dbc;
u_int32_t obucket, nbucket;
{
DB *dbp;
DBC **carray;
DBT key, page_dbt;
DB_ENV *dbenv;
DB_LOCK block;
DB_LSN new_lsn;
DB_MPOOLFILE *mpf;
HASH_CURSOR *hcp, *cp;
PAGE **pp, *old_pagep, *temp_pagep, *new_pagep;
db_indx_t n;
db_pgno_t bucket_pgno, npgno, next_pgno;
u_int32_t big_len, len;
int found, i, ret, t_ret;
void *big_buf;
dbp = dbc->dbp;
dbenv = dbp->dbenv;
mpf = dbp->mpf;
hcp = (HASH_CURSOR *)dbc->internal;
temp_pagep = old_pagep = new_pagep = NULL;
carray = NULL;
LOCK_INIT(block);
bucket_pgno = BUCKET_TO_PAGE(hcp, obucket);
if ((ret = __db_lget(dbc,
0, bucket_pgno, DB_LOCK_WRITE, 0, &block)) != 0)
goto err;
if ((ret = __memp_fget(mpf,
&bucket_pgno, DB_MPOOL_CREATE, &old_pagep)) != 0)
goto err;
npgno = BUCKET_TO_PAGE(hcp, nbucket);
if ((ret = __memp_fget(mpf, &npgno, DB_MPOOL_CREATE, &new_pagep)) != 0)
goto err;
P_INIT(new_pagep,
dbp->pgsize, npgno, PGNO_INVALID, PGNO_INVALID, 0, P_HASH);
temp_pagep = hcp->split_buf;
memcpy(temp_pagep, old_pagep, dbp->pgsize);
if (DBC_LOGGING(dbc)) {
page_dbt.size = dbp->pgsize;
page_dbt.data = old_pagep;
if ((ret = __ham_splitdata_log(dbp,
dbc->txn, &new_lsn, 0, SPLITOLD,
PGNO(old_pagep), &page_dbt, &LSN(old_pagep))) != 0)
goto err;
} else
LSN_NOT_LOGGED(new_lsn);
LSN(old_pagep) = new_lsn;
P_INIT(old_pagep, dbp->pgsize, PGNO(old_pagep), PGNO_INVALID,
PGNO_INVALID, 0, P_HASH);
big_len = 0;
big_buf = NULL;
key.flags = 0;
while (temp_pagep != NULL) {
if ((ret = __ham_get_clist(dbp,
PGNO(temp_pagep), NDX_INVALID, &carray)) != 0)
goto err;
for (n = 0; n < (db_indx_t)NUM_ENT(temp_pagep); n += 2) {
if ((ret = __db_ret(dbp, temp_pagep,
H_KEYINDEX(n), &key, &big_buf, &big_len)) != 0)
goto err;
if (__ham_call_hash(dbc, key.data, key.size) == obucket)
pp = &old_pagep;
else
pp = &new_pagep;
len = LEN_HITEM(dbp, temp_pagep, dbp->pgsize,
H_DATAINDEX(n)) +
LEN_HITEM(dbp, temp_pagep, dbp->pgsize,
H_KEYINDEX(n)) +
2 * sizeof(db_indx_t);
if (P_FREESPACE(dbp, *pp) < len) {
if (DBC_LOGGING(dbc)) {
page_dbt.size = dbp->pgsize;
page_dbt.data = *pp;
if ((ret = __ham_splitdata_log(dbp,
dbc->txn, &new_lsn, 0,
SPLITNEW, PGNO(*pp), &page_dbt,
&LSN(*pp))) != 0)
goto err;
} else
LSN_NOT_LOGGED(new_lsn);
LSN(*pp) = new_lsn;
if ((ret =
__ham_add_ovflpage(dbc, *pp, 1, pp)) != 0)
goto err;
}
if (carray != NULL) {
found = 0;
for (i = 0; carray[i] != NULL; i++) {
cp =
(HASH_CURSOR *)carray[i]->internal;
if (cp->pgno == PGNO(temp_pagep) &&
cp->indx == n) {
cp->pgno = PGNO(*pp);
cp->indx = NUM_ENT(*pp);
found = 1;
}
}
if (found && DBC_LOGGING(dbc) &&
IS_SUBTRANSACTION(dbc->txn)) {
if ((ret =
__ham_chgpg_log(dbp,
dbc->txn, &new_lsn, 0,
DB_HAM_SPLIT, PGNO(temp_pagep),
PGNO(*pp), n, NUM_ENT(*pp))) != 0)
goto err;
}
}
__ham_copy_item(dbp, temp_pagep, H_KEYINDEX(n), *pp);
__ham_copy_item(dbp, temp_pagep, H_DATAINDEX(n), *pp);
}
next_pgno = NEXT_PGNO(temp_pagep);
if (PGNO(temp_pagep) != bucket_pgno && (ret =
__db_free(dbc, temp_pagep)) != 0) {
temp_pagep = NULL;
goto err;
}
if (next_pgno == PGNO_INVALID)
temp_pagep = NULL;
else if ((ret = __memp_fget(
mpf, &next_pgno, DB_MPOOL_CREATE, &temp_pagep)) != 0)
goto err;
if (temp_pagep != NULL) {
if (DBC_LOGGING(dbc)) {
page_dbt.size = dbp->pgsize;
page_dbt.data = temp_pagep;
if ((ret = __ham_splitdata_log(dbp,
dbc->txn, &new_lsn, 0,
SPLITOLD, PGNO(temp_pagep),
&page_dbt, &LSN(temp_pagep))) != 0)
goto err;
} else
LSN_NOT_LOGGED(new_lsn);
LSN(temp_pagep) = new_lsn;
}
if (carray != NULL)
__os_free(dbenv, carray);
carray = NULL;
}
if (big_buf != NULL)
__os_free(dbenv, big_buf);
if (temp_pagep != NULL && PGNO(temp_pagep) != bucket_pgno &&
(ret = __db_free(dbc, temp_pagep)) != 0) {
temp_pagep = NULL;
goto err;
}
if (DBC_LOGGING(dbc)) {
page_dbt.size = dbp->pgsize;
page_dbt.data = old_pagep;
if ((ret = __ham_splitdata_log(dbp, dbc->txn,
&new_lsn, 0, SPLITNEW, PGNO(old_pagep), &page_dbt,
&LSN(old_pagep))) != 0)
goto err;
LSN(old_pagep) = new_lsn;
page_dbt.data = new_pagep;
if ((ret = __ham_splitdata_log(dbp, dbc->txn, &new_lsn, 0,
SPLITNEW, PGNO(new_pagep), &page_dbt,
&LSN(new_pagep))) != 0)
goto err;
LSN(new_pagep) = new_lsn;
} else {
LSN_NOT_LOGGED(LSN(old_pagep));
LSN_NOT_LOGGED(LSN(new_pagep));
}
ret = __memp_fput(mpf, old_pagep, DB_MPOOL_DIRTY);
if ((t_ret =
__memp_fput(mpf, new_pagep, DB_MPOOL_DIRTY)) != 0 && ret == 0)
ret = t_ret;
if (0) {
err: if (old_pagep != NULL)
(void)__memp_fput(mpf, old_pagep, DB_MPOOL_DIRTY);
if (new_pagep != NULL) {
P_INIT(new_pagep, dbp->pgsize,
npgno, PGNO_INVALID, PGNO_INVALID, 0, P_HASH);
(void)__memp_fput(mpf, new_pagep, DB_MPOOL_DIRTY);
}
if (temp_pagep != NULL && PGNO(temp_pagep) != bucket_pgno)
(void)__memp_fput(mpf, temp_pagep, DB_MPOOL_DIRTY);
}
if (LOCK_ISSET(block))
__TLPUT(dbc, block);
if (carray != NULL)
__os_free(dbenv, carray);
return (ret);
}
int
__ham_add_el(dbc, key, val, type)
DBC *dbc;
const DBT *key, *val;
int type;
{
const DBT *pkey, *pdata;
DB *dbp;
DBT key_dbt, data_dbt;
DB_LSN new_lsn;
DB_MPOOLFILE *mpf;
HASH_CURSOR *hcp;
HOFFPAGE doff, koff;
db_pgno_t next_pgno, pgno;
u_int32_t data_size, key_size, pairsize, rectype;
int do_expand, is_keybig, is_databig, ret;
int key_type, data_type;
dbp = dbc->dbp;
mpf = dbp->mpf;
hcp = (HASH_CURSOR *)dbc->internal;
do_expand = 0;
pgno = hcp->seek_found_page != PGNO_INVALID ?
hcp->seek_found_page : hcp->pgno;
if (hcp->page == NULL &&
(ret = __memp_fget(mpf, &pgno, DB_MPOOL_CREATE, &hcp->page)) != 0)
return (ret);
key_size = HKEYDATA_PSIZE(key->size);
data_size = HKEYDATA_PSIZE(val->size);
is_keybig = ISBIG(hcp, key->size);
is_databig = ISBIG(hcp, val->size);
if (is_keybig)
key_size = HOFFPAGE_PSIZE;
if (is_databig)
data_size = HOFFPAGE_PSIZE;
pairsize = key_size + data_size;
while (H_NUMPAIRS(hcp->page) && NEXT_PGNO(hcp->page) != PGNO_INVALID) {
if (P_FREESPACE(dbp, hcp->page) >= pairsize)
break;
next_pgno = NEXT_PGNO(hcp->page);
if ((ret = __ham_next_cpage(dbc, next_pgno, 0)) != 0)
return (ret);
}
if (P_FREESPACE(dbp, hcp->page) < pairsize) {
do_expand = 1;
if ((ret = __ham_add_ovflpage(dbc,
(PAGE *)hcp->page, 1, (PAGE **)&hcp->page)) != 0)
return (ret);
hcp->pgno = PGNO(hcp->page);
}
hcp->indx = NUM_ENT(hcp->page);
F_CLR(hcp, H_DELETED);
if (is_keybig) {
koff.type = H_OFFPAGE;
UMRW_SET(koff.unused[0]);
UMRW_SET(koff.unused[1]);
UMRW_SET(koff.unused[2]);
if ((ret = __db_poff(dbc, key, &koff.pgno)) != 0)
return (ret);
koff.tlen = key->size;
key_dbt.data = &koff;
key_dbt.size = sizeof(koff);
pkey = &key_dbt;
key_type = H_OFFPAGE;
} else {
pkey = key;
key_type = H_KEYDATA;
}
if (is_databig) {
doff.type = H_OFFPAGE;
UMRW_SET(doff.unused[0]);
UMRW_SET(doff.unused[1]);
UMRW_SET(doff.unused[2]);
if ((ret = __db_poff(dbc, val, &doff.pgno)) != 0)
return (ret);
doff.tlen = val->size;
data_dbt.data = &doff;
data_dbt.size = sizeof(doff);
pdata = &data_dbt;
data_type = H_OFFPAGE;
} else {
pdata = val;
data_type = type;
}
if (DBC_LOGGING(dbc)) {
rectype = PUTPAIR;
if (is_databig)
rectype |= PAIR_DATAMASK;
if (is_keybig)
rectype |= PAIR_KEYMASK;
if (type == H_DUPLICATE)
rectype |= PAIR_DUPMASK;
if ((ret = __ham_insdel_log(dbp, dbc->txn, &new_lsn, 0,
rectype, PGNO(hcp->page), (u_int32_t)NUM_ENT(hcp->page),
&LSN(hcp->page), pkey, pdata)) != 0)
return (ret);
} else
LSN_NOT_LOGGED(new_lsn);
LSN(hcp->page) = new_lsn;
__ham_putitem(dbp, hcp->page, pkey, key_type);
__ham_putitem(dbp, hcp->page, pdata, data_type);
hcp->pgno = PGNO(hcp->page);
if (!STD_LOCKING(dbc)) {
hcp->hdr->nelem++;
if ((ret = __ham_dirty_meta(dbc)) != 0)
return (ret);
}
if (do_expand || (hcp->hdr->ffactor != 0 &&
(u_int32_t)H_NUMPAIRS(hcp->page) > hcp->hdr->ffactor))
F_SET(hcp, H_EXPAND);
return (0);
}
void
__ham_copy_item(dbp, src_page, src_ndx, dest_page)
DB *dbp;
PAGE *src_page;
u_int32_t src_ndx;
PAGE *dest_page;
{
u_int32_t len;
size_t pgsize;
void *src, *dest;
db_indx_t *inp;
pgsize = dbp->pgsize;
inp = P_INP(dbp, dest_page);
src = P_ENTRY(dbp, src_page, src_ndx);
len = (u_int32_t)LEN_HITEM(dbp, src_page, pgsize, src_ndx);
HOFFSET(dest_page) -= len;
inp[NUM_ENT(dest_page)] = HOFFSET(dest_page);
dest = P_ENTRY(dbp, dest_page, NUM_ENT(dest_page));
NUM_ENT(dest_page)++;
memcpy(dest, src, len);
}
int
__ham_add_ovflpage(dbc, pagep, release, pp)
DBC *dbc;
PAGE *pagep;
int release;
PAGE **pp;
{
DB *dbp;
DB_LSN new_lsn;
DB_MPOOLFILE *mpf;
PAGE *new_pagep;
int ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
if ((ret = __db_new(dbc, P_HASH, &new_pagep)) != 0)
return (ret);
if (DBC_LOGGING(dbc)) {
if ((ret = __ham_newpage_log(dbp, dbc->txn, &new_lsn, 0,
PUTOVFL, PGNO(pagep), &LSN(pagep), PGNO(new_pagep),
&LSN(new_pagep), PGNO_INVALID, NULL)) != 0) {
(void)__memp_fput(mpf, pagep, DB_MPOOL_DIRTY);
return (ret);
}
} else
LSN_NOT_LOGGED(new_lsn);
LSN(pagep) = LSN(new_pagep) = new_lsn;
NEXT_PGNO(pagep) = PGNO(new_pagep);
PREV_PGNO(new_pagep) = PGNO(pagep);
if (release)
ret = __memp_fput(mpf, pagep, DB_MPOOL_DIRTY);
*pp = new_pagep;
return (ret);
}
int
__ham_get_cpage(dbc, mode)
DBC *dbc;
db_lockmode_t mode;
{
DB *dbp;
DB_LOCK tmp_lock;
DB_MPOOLFILE *mpf;
HASH_CURSOR *hcp;
int ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
hcp = (HASH_CURSOR *)dbc->internal;
ret = 0;
LOCK_INIT(tmp_lock);
if (STD_LOCKING(dbc)) {
if (hcp->lbucket != hcp->bucket &&
(ret = __TLPUT(dbc, hcp->lock)) != 0)
return (ret);
if ((LOCK_ISSET(hcp->lock) &&
(hcp->lock_mode == DB_LOCK_READ &&
mode == DB_LOCK_WRITE))) {
tmp_lock = hcp->lock;
LOCK_INIT(hcp->lock);
}
if (!LOCK_ISSET(hcp->lock))
if ((ret = __ham_lock_bucket(dbc, mode)) != 0)
return (ret);
if (ret == 0) {
hcp->lock_mode = mode;
hcp->lbucket = hcp->bucket;
if (LOCK_ISSET(tmp_lock))
ret = __lock_put(dbp->dbenv, &tmp_lock);
} else if (LOCK_ISSET(tmp_lock))
hcp->lock = tmp_lock;
}
if (ret == 0 && hcp->page == NULL) {
if (hcp->pgno == PGNO_INVALID)
hcp->pgno = BUCKET_TO_PAGE(hcp, hcp->bucket);
if ((ret = __memp_fget(mpf,
&hcp->pgno, DB_MPOOL_CREATE, &hcp->page)) != 0)
return (ret);
}
return (0);
}
int
__ham_next_cpage(dbc, pgno, dirty)
DBC *dbc;
db_pgno_t pgno;
int dirty;
{
DB *dbp;
DB_MPOOLFILE *mpf;
HASH_CURSOR *hcp;
PAGE *p;
int ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
hcp = (HASH_CURSOR *)dbc->internal;
if (hcp->page != NULL && (ret =
__memp_fput(mpf, hcp->page, dirty ? DB_MPOOL_DIRTY : 0)) != 0)
return (ret);
hcp->page = NULL;
if ((ret = __memp_fget(mpf, &pgno, DB_MPOOL_CREATE, &p)) != 0)
return (ret);
hcp->page = p;
hcp->pgno = pgno;
hcp->indx = 0;
return (0);
}
int
__ham_lock_bucket(dbc, mode)
DBC *dbc;
db_lockmode_t mode;
{
HASH_CURSOR *hcp;
db_pgno_t pgno;
int gotmeta, ret;
hcp = (HASH_CURSOR *)dbc->internal;
gotmeta = hcp->hdr == NULL ? 1 : 0;
if (gotmeta)
if ((ret = __ham_get_meta(dbc)) != 0)
return (ret);
pgno = BUCKET_TO_PAGE(hcp, hcp->bucket);
if (gotmeta)
if ((ret = __ham_release_meta(dbc)) != 0)
return (ret);
ret = __db_lget(dbc, 0, pgno, mode, 0, &hcp->lock);
hcp->lock_mode = mode;
return (ret);
}
void
__ham_dpair(dbp, p, indx)
DB *dbp;
PAGE *p;
u_int32_t indx;
{
db_indx_t delta, n, *inp;
u_int8_t *dest, *src;
inp = P_INP(dbp, p);
delta = H_PAIRSIZE(dbp, p, dbp->pgsize, indx);
if ((db_indx_t)indx != NUM_ENT(p) - 2) {
src = (u_int8_t *)p + HOFFSET(p);
dest = src + delta;
memmove(dest, src, inp[H_DATAINDEX(indx)] - HOFFSET(p));
}
HOFFSET(p) = HOFFSET(p) + delta;
NUM_ENT(p) = NUM_ENT(p) - 2;
for (n = (db_indx_t)indx; n < (db_indx_t)(NUM_ENT(p)); n++)
inp[n] = inp[n + 2] + delta;
}
static int
__ham_c_delpg(dbc, old_pgno, new_pgno, num_ent, op, orderp)
DBC *dbc;
db_pgno_t old_pgno, new_pgno;
u_int32_t num_ent;
db_ham_mode op;
u_int32_t *orderp;
{
DB *dbp, *ldbp;
DB_ENV *dbenv;
DB_LSN lsn;
DB_TXN *my_txn;
DBC *cp;
HASH_CURSOR *hcp;
int found, ret;
db_indx_t indx;
u_int32_t order;
indx = (op == DB_HAM_DELLASTPG) ? num_ent : 0;
dbp = dbc->dbp;
dbenv = dbp->dbenv;
my_txn = IS_SUBTRANSACTION(dbc->txn) ? dbc->txn : NULL;
found = 0;
MUTEX_THREAD_LOCK(dbenv, dbenv->dblist_mutexp);
order = 1;
for (ldbp = __dblist_get(dbenv, dbp->adj_fileid);
ldbp != NULL && ldbp->adj_fileid == dbp->adj_fileid;
ldbp = LIST_NEXT(ldbp, dblistlinks)) {
MUTEX_THREAD_LOCK(dbenv, dbp->mutexp);
for (cp = TAILQ_FIRST(&ldbp->active_queue); cp != NULL;
cp = TAILQ_NEXT(cp, links)) {
if (cp == dbc || cp->dbtype != DB_HASH)
continue;
hcp = (HASH_CURSOR *)cp->internal;
if (hcp->pgno == new_pgno) {
if (hcp->indx == indx &&
F_ISSET(hcp, H_DELETED) &&
hcp->order >= order)
order = hcp->order + 1;
DB_ASSERT(op != DB_HAM_DELFIRSTPG ||
hcp->indx == NDX_INVALID ||
(hcp->indx == 0 &&
F_ISSET(hcp, H_DELETED)));
}
}
MUTEX_THREAD_UNLOCK(dbenv, dbp->mutexp);
}
for (ldbp = __dblist_get(dbenv, dbp->adj_fileid);
ldbp != NULL && ldbp->adj_fileid == dbp->adj_fileid;
ldbp = LIST_NEXT(ldbp, dblistlinks)) {
MUTEX_THREAD_LOCK(dbenv, dbp->mutexp);
for (cp = TAILQ_FIRST(&ldbp->active_queue); cp != NULL;
cp = TAILQ_NEXT(cp, links)) {
if (cp == dbc || cp->dbtype != DB_HASH)
continue;
hcp = (HASH_CURSOR *)cp->internal;
if (hcp->pgno == old_pgno) {
switch (op) {
case DB_HAM_DELFIRSTPG:
hcp->pgno = new_pgno;
if (hcp->indx == indx)
hcp->order += order;
break;
case DB_HAM_DELMIDPG:
hcp->pgno = new_pgno;
DB_ASSERT(hcp->indx == 0 &&
F_ISSET(hcp, H_DELETED));
hcp->order += order;
break;
case DB_HAM_DELLASTPG:
hcp->pgno = new_pgno;
DB_ASSERT(hcp->indx == 0 &&
F_ISSET(hcp, H_DELETED));
hcp->indx = indx;
hcp->order += order;
break;
default:
DB_ASSERT(0);
return (__db_panic(dbenv, EINVAL));
}
if (my_txn != NULL && cp->txn != my_txn)
found = 1;
}
}
MUTEX_THREAD_UNLOCK(dbenv, dbp->mutexp);
}
MUTEX_THREAD_UNLOCK(dbenv, dbenv->dblist_mutexp);
if (found != 0 && DBC_LOGGING(dbc)) {
if ((ret = __ham_chgpg_log(dbp, my_txn, &lsn, 0, op,
old_pgno, new_pgno, indx, order)) != 0)
return (ret);
}
*orderp = order;
return (0);
}