diff options
Diffstat (limited to 'dbm/sdbm/sdbm_pair.c')
| -rw-r--r-- | dbm/sdbm/sdbm_pair.c | 320 |
1 files changed, 320 insertions, 0 deletions
diff --git a/dbm/sdbm/sdbm_pair.c b/dbm/sdbm/sdbm_pair.c new file mode 100644 index 0000000..50d7965 --- /dev/null +++ b/dbm/sdbm/sdbm_pair.c @@ -0,0 +1,320 @@ +/* Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/* + * sdbm - ndbm work-alike hashed database library + * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978). + * author: oz@nexus.yorku.ca + * status: ex-public domain. + * + * page-level routines + */ + +#include "apr_sdbm.h" + +#include "sdbm_tune.h" +#include "sdbm_pair.h" +#include "sdbm_private.h" + +#include <string.h> /* for memset() */ + + +#define exhash(item) sdbm_hash((item).dptr, (item).dsize) + +/* + * forward + */ +static int seepair(char *, int, char *, int); + +/* + * page format: + * +------------------------------+ + * ino | n | keyoff | datoff | keyoff | + * +------------+--------+--------+ + * | datoff | - - - ----> | + * +--------+---------------------+ + * | F R E E A R E A | + * +--------------+---------------+ + * | <---- - - - | data | + * +--------+-----+----+----------+ + * | key | data | key | + * +--------+----------+----------+ + * + * calculating the offsets for free area: if the number + * of entries (ino[0]) is zero, the offset to the END of + * the free area is the block size. Otherwise, it is the + * nth (ino[ino[0]]) entry's offset. + */ + +int +fitpair(pag, need) +char *pag; +int need; +{ + register int n; + register int off; + register int avail; + register short *ino = (short *) pag; + + off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ; + avail = off - (n + 1) * sizeof(short); + need += 2 * sizeof(short); + + debug(("avail %d need %d\n", avail, need)); + + return need <= avail; +} + +void +putpair(pag, key, val) +char *pag; +apr_sdbm_datum_t key; +apr_sdbm_datum_t val; +{ + register int n; + register int off; + register short *ino = (short *) pag; + + off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ; +/* + * enter the key first + */ + off -= key.dsize; + (void) memcpy(pag + off, key.dptr, key.dsize); + ino[n + 1] = off; +/* + * now the data + */ + off -= val.dsize; + (void) memcpy(pag + off, val.dptr, val.dsize); + ino[n + 2] = off; +/* + * adjust item count + */ + ino[0] += 2; +} + +apr_sdbm_datum_t +getpair(pag, key) +char *pag; +apr_sdbm_datum_t key; +{ + register int i; + register int n; + apr_sdbm_datum_t val; + register short *ino = (short *) pag; + + if ((n = ino[0]) == 0) + return sdbm_nullitem; + + if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0) + return sdbm_nullitem; + + val.dptr = pag + ino[i + 1]; + val.dsize = ino[i] - ino[i + 1]; + return val; +} + +int +duppair(pag, key) +char *pag; +apr_sdbm_datum_t key; +{ + register short *ino = (short *) pag; + return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0; +} + +apr_sdbm_datum_t +getnkey(pag, num) +char *pag; +int num; +{ + apr_sdbm_datum_t key; + register int off; + register short *ino = (short *) pag; + + num = num * 2 - 1; + if (ino[0] == 0 || num > ino[0]) + return sdbm_nullitem; + + off = (num > 1) ? ino[num - 1] : PBLKSIZ; + + key.dptr = pag + ino[num]; + key.dsize = off - ino[num]; + + return key; +} + +int +delpair(pag, key) +char *pag; +apr_sdbm_datum_t key; +{ + register int n; + register int i; + register short *ino = (short *) pag; + + if ((n = ino[0]) == 0) + return 0; + + if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0) + return 0; +/* + * found the key. if it is the last entry + * [i.e. i == n - 1] we just adjust the entry count. + * hard case: move all data down onto the deleted pair, + * shift offsets onto deleted offsets, and adjust them. + * [note: 0 < i < n] + */ + if (i < n - 1) { + register int m; + register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]); + register char *src = pag + ino[i + 1]; + register short zoo = (short) (dst - src); + + debug(("free-up %d ", zoo)); +/* + * shift data/keys down + */ + m = ino[i + 1] - ino[n]; + +#undef DUFF /* just use memmove. it should be plenty fast. */ +#ifdef DUFF +#define MOVB *--dst = *--src + + if (m > 0) { + register int loop = (m + 8 - 1) >> 3; + + switch (m & (8 - 1)) { + case 0: do { + MOVB; case 7: MOVB; + case 6: MOVB; case 5: MOVB; + case 4: MOVB; case 3: MOVB; + case 2: MOVB; case 1: MOVB; + } while (--loop); + } + } +#else + dst -= m; + src -= m; + memmove(dst, src, m); +#endif + +/* + * adjust offset index up + */ + while (i < n - 1) { + ino[i] = ino[i + 2] + zoo; + i++; + } + } + ino[0] -= 2; + return 1; +} + +/* + * search for the key in the page. + * return offset index in the range 0 < i < n. + * return 0 if not found. + */ +static int +seepair(pag, n, key, siz) +char *pag; +register int n; +register char *key; +register int siz; +{ + register int i; + register int off = PBLKSIZ; + register short *ino = (short *) pag; + + for (i = 1; i < n; i += 2) { + if (siz == off - ino[i] && + memcmp(key, pag + ino[i], siz) == 0) + return i; + off = ino[i + 1]; + } + return 0; +} + +void +splpage(pag, new, sbit) +char *pag; +char *new; +long sbit; +{ + apr_sdbm_datum_t key; + apr_sdbm_datum_t val; + + register int n; + register int off = PBLKSIZ; + char cur[PBLKSIZ]; + register short *ino = (short *) cur; + + (void) memcpy(cur, pag, PBLKSIZ); + (void) memset(pag, 0, PBLKSIZ); + (void) memset(new, 0, PBLKSIZ); + + n = ino[0]; + for (ino++; n > 0; ino += 2) { + key.dptr = cur + ino[0]; + key.dsize = off - ino[0]; + val.dptr = cur + ino[1]; + val.dsize = ino[0] - ino[1]; +/* + * select the page pointer (by looking at sbit) and insert + */ + (void) putpair((exhash(key) & sbit) ? new : pag, key, val); + + off = ino[1]; + n -= 2; + } + + debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, + ((short *) new)[0] / 2, + ((short *) pag)[0] / 2)); +} + +/* + * check page sanity: + * number of entries should be something + * reasonable, and all offsets in the index should be in order. + * this could be made more rigorous. + */ +int +chkpage(pag) +char *pag; +{ + register int n; + register int off; + register short *ino = (short *) pag; + + if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short)) + return 0; + + if (n > 0) { + off = PBLKSIZ; + for (ino++; n > 0; ino += 2) { + if (ino[0] < 0 || ino[0] > off || + ino[1] < 0 || ino[1] > off || + ino[1] > ino[0]) + return 0; + off = ino[1]; + n -= 2; + } + } + return 1; +} |