diff options
Diffstat (limited to 'dbm/sdbm/sdbm.c')
| -rw-r--r-- | dbm/sdbm/sdbm.c | 584 |
1 files changed, 584 insertions, 0 deletions
diff --git a/dbm/sdbm/sdbm.c b/dbm/sdbm/sdbm.c new file mode 100644 index 0000000..a1ce695 --- /dev/null +++ b/dbm/sdbm/sdbm.c @@ -0,0 +1,584 @@ +/* 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 + * ex-public domain, ported to APR for Apache 2 + * core routines + */ + +#include "apr.h" +#include "apr_file_io.h" +#include "apr_strings.h" +#include "apr_errno.h" +#include "apr_sdbm.h" + +#include "sdbm_tune.h" +#include "sdbm_pair.h" +#include "sdbm_private.h" + +#include <string.h> /* for memset() */ +#include <stdlib.h> /* for malloc() and free() */ + +/* + * forward + */ +static int getdbit (apr_sdbm_t *, long); +static apr_status_t setdbit(apr_sdbm_t *, long); +static apr_status_t getpage(apr_sdbm_t *db, long); +static apr_status_t getnext(apr_sdbm_datum_t *key, apr_sdbm_t *db); +static apr_status_t makroom(apr_sdbm_t *, long, int); + +/* + * useful macros + */ +#define bad(x) ((x).dptr == NULL || (x).dsize <= 0) +#define exhash(item) sdbm_hash((item).dptr, (item).dsize) + +#define OFF_PAG(off) (apr_off_t) (off) * PBLKSIZ +#define OFF_DIR(off) (apr_off_t) (off) * DBLKSIZ + +static const long masks[] = { + 000000000000, 000000000001, 000000000003, 000000000007, + 000000000017, 000000000037, 000000000077, 000000000177, + 000000000377, 000000000777, 000000001777, 000000003777, + 000000007777, 000000017777, 000000037777, 000000077777, + 000000177777, 000000377777, 000000777777, 000001777777, + 000003777777, 000007777777, 000017777777, 000037777777, + 000077777777, 000177777777, 000377777777, 000777777777, + 001777777777, 003777777777, 007777777777, 017777777777 +}; + +const apr_sdbm_datum_t sdbm_nullitem = { NULL, 0 }; + +static apr_status_t database_cleanup(void *data) +{ + apr_sdbm_t *db = data; + + /* + * Can't rely on apr_sdbm_unlock, since it will merely + * decrement the refcnt if several locks are held. + */ + if (db->flags & (SDBM_SHARED_LOCK | SDBM_EXCLUSIVE_LOCK)) + (void) apr_file_unlock(db->dirf); + (void) apr_file_close(db->dirf); + (void) apr_file_close(db->pagf); + free(db); + + return APR_SUCCESS; +} + +static apr_status_t prep(apr_sdbm_t **pdb, const char *dirname, const char *pagname, + apr_int32_t flags, apr_fileperms_t perms, apr_pool_t *p) +{ + apr_sdbm_t *db; + apr_status_t status; + + *pdb = NULL; + + db = malloc(sizeof(*db)); + memset(db, 0, sizeof(*db)); + + db->pool = p; + + /* + * adjust user flags so that WRONLY becomes RDWR, + * as required by this package. Also set our internal + * flag for RDONLY if needed. + */ + if (!(flags & APR_FOPEN_WRITE)) { + db->flags |= SDBM_RDONLY; + } + + /* + * adjust the file open flags so that we handle locking + * on our own (don't rely on any locking behavior within + * an apr_file_t, in case it's ever introduced, and set + * our own flag. + */ + if (flags & APR_FOPEN_SHARELOCK) { + db->flags |= SDBM_SHARED; + flags &= ~APR_FOPEN_SHARELOCK; + } + + flags |= APR_FOPEN_BINARY | APR_FOPEN_READ; + + /* + * open the files in sequence, and stat the dirfile. + * If we fail anywhere, undo everything, return NULL. + */ + + if ((status = apr_file_open(&db->dirf, dirname, flags, perms, p)) + != APR_SUCCESS) + goto error; + + if ((status = apr_file_open(&db->pagf, pagname, flags, perms, p)) + != APR_SUCCESS) + goto error; + + if ((status = apr_sdbm_lock(db, (db->flags & SDBM_RDONLY) + ? APR_FLOCK_SHARED + : APR_FLOCK_EXCLUSIVE)) + != APR_SUCCESS) + goto error; + + /* apr_pcalloc zeroed the buffers + * apr_sdbm_lock stated the dirf->size and invalidated the cache + */ + + /* + * if we are opened in SHARED mode, unlock ourself + */ + if (db->flags & SDBM_SHARED) + if ((status = apr_sdbm_unlock(db)) != APR_SUCCESS) + goto error; + + /* make sure that we close the database at some point */ + apr_pool_cleanup_register(p, db, database_cleanup, apr_pool_cleanup_null); + + /* Done! */ + *pdb = db; + return APR_SUCCESS; + +error: + if (db->dirf && db->pagf) + (void) apr_sdbm_unlock(db); + if (db->dirf != NULL) + (void) apr_file_close(db->dirf); + if (db->pagf != NULL) { + (void) apr_file_close(db->pagf); + } + free(db); + return status; +} + +APU_DECLARE(apr_status_t) apr_sdbm_open(apr_sdbm_t **db, const char *file, + apr_int32_t flags, + apr_fileperms_t perms, apr_pool_t *p) +{ + char *dirname = apr_pstrcat(p, file, APR_SDBM_DIRFEXT, NULL); + char *pagname = apr_pstrcat(p, file, APR_SDBM_PAGFEXT, NULL); + + return prep(db, dirname, pagname, flags, perms, p); +} + +APU_DECLARE(apr_status_t) apr_sdbm_close(apr_sdbm_t *db) +{ + return apr_pool_cleanup_run(db->pool, db, database_cleanup); +} + +APU_DECLARE(apr_status_t) apr_sdbm_fetch(apr_sdbm_t *db, apr_sdbm_datum_t *val, + apr_sdbm_datum_t key) +{ + apr_status_t status; + + if (db == NULL || bad(key)) + return APR_EINVAL; + + if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS) + return status; + + if ((status = getpage(db, exhash(key))) == APR_SUCCESS) { + *val = getpair(db->pagbuf, key); + /* ### do we want a not-found result? */ + } + + (void) apr_sdbm_unlock(db); + + return status; +} + +static apr_status_t write_page(apr_sdbm_t *db, const char *buf, long pagno) +{ + apr_status_t status; + apr_off_t off = OFF_PAG(pagno); + + if ((status = apr_file_seek(db->pagf, APR_SET, &off)) == APR_SUCCESS) + status = apr_file_write_full(db->pagf, buf, PBLKSIZ, NULL); + + return status; +} + +APU_DECLARE(apr_status_t) apr_sdbm_delete(apr_sdbm_t *db, + const apr_sdbm_datum_t key) +{ + apr_status_t status; + + if (db == NULL || bad(key)) + return APR_EINVAL; + if (apr_sdbm_rdonly(db)) + return APR_EINVAL; + + if ((status = apr_sdbm_lock(db, APR_FLOCK_EXCLUSIVE)) != APR_SUCCESS) + return status; + + if ((status = getpage(db, exhash(key))) == APR_SUCCESS) { + if (!delpair(db->pagbuf, key)) + /* ### should we define some APRUTIL codes? */ + status = APR_EGENERAL; + else + status = write_page(db, db->pagbuf, db->pagbno); + } + + (void) apr_sdbm_unlock(db); + + return status; +} + +APU_DECLARE(apr_status_t) apr_sdbm_store(apr_sdbm_t *db, apr_sdbm_datum_t key, + apr_sdbm_datum_t val, int flags) +{ + int need; + register long hash; + apr_status_t status; + + if (db == NULL || bad(key)) + return APR_EINVAL; + if (apr_sdbm_rdonly(db)) + return APR_EINVAL; + need = key.dsize + val.dsize; + /* + * is the pair too big (or too small) for this database ?? + */ + if (need < 0 || need > PAIRMAX) + return APR_EINVAL; + + if ((status = apr_sdbm_lock(db, APR_FLOCK_EXCLUSIVE)) != APR_SUCCESS) + return status; + + if ((status = getpage(db, (hash = exhash(key)))) == APR_SUCCESS) { + + /* + * if we need to replace, delete the key/data pair + * first. If it is not there, ignore. + */ + if (flags == APR_SDBM_REPLACE) + (void) delpair(db->pagbuf, key); + else if (!(flags & APR_SDBM_INSERTDUP) && duppair(db->pagbuf, key)) { + status = APR_EEXIST; + goto error; + } + /* + * if we do not have enough room, we have to split. + */ + if (!fitpair(db->pagbuf, need)) + if ((status = makroom(db, hash, need)) != APR_SUCCESS) + goto error; + /* + * we have enough room or split is successful. insert the key, + * and update the page file. + */ + (void) putpair(db->pagbuf, key, val); + + status = write_page(db, db->pagbuf, db->pagbno); + } + +error: + (void) apr_sdbm_unlock(db); + + return status; +} + +/* + * makroom - make room by splitting the overfull page + * this routine will attempt to make room for SPLTMAX times before + * giving up. + */ +static apr_status_t makroom(apr_sdbm_t *db, long hash, int need) +{ + long newp; + char twin[PBLKSIZ]; + char *pag = db->pagbuf; + char *new = twin; + register int smax = SPLTMAX; + apr_status_t status; + + do { + /* + * split the current page + */ + (void) splpage(pag, new, db->hmask + 1); + /* + * address of the new page + */ + newp = (hash & db->hmask) | (db->hmask + 1); + + /* + * write delay, read avoidence/cache shuffle: + * select the page for incoming pair: if key is to go to the new page, + * write out the previous one, and copy the new one over, thus making + * it the current page. If not, simply write the new page, and we are + * still looking at the page of interest. current page is not updated + * here, as sdbm_store will do so, after it inserts the incoming pair. + */ + if (hash & (db->hmask + 1)) { + if ((status = write_page(db, db->pagbuf, db->pagbno)) + != APR_SUCCESS) + return status; + + db->pagbno = newp; + (void) memcpy(pag, new, PBLKSIZ); + } + else { + if ((status = write_page(db, new, newp)) != APR_SUCCESS) + return status; + } + + if ((status = setdbit(db, db->curbit)) != APR_SUCCESS) + return status; + /* + * see if we have enough room now + */ + if (fitpair(pag, need)) + return APR_SUCCESS; + /* + * try again... update curbit and hmask as getpage would have + * done. because of our update of the current page, we do not + * need to read in anything. BUT we have to write the current + * [deferred] page out, as the window of failure is too great. + */ + db->curbit = 2 * db->curbit + + ((hash & (db->hmask + 1)) ? 2 : 1); + db->hmask |= db->hmask + 1; + + if ((status = write_page(db, db->pagbuf, db->pagbno)) + != APR_SUCCESS) + return status; + + } while (--smax); + + /* + * if we are here, this is real bad news. After SPLTMAX splits, + * we still cannot fit the key. say goodnight. + */ +#if 0 + (void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44); +#endif + /* ### ENOSPC not really appropriate but better than nothing */ + return APR_ENOSPC; + +} + +/* Reads 'len' bytes from file 'f' at offset 'off' into buf. + * 'off' is given relative to the start of the file. + * If EOF is returned while reading, this is taken as success. + */ +static apr_status_t read_from(apr_file_t *f, void *buf, + apr_off_t off, apr_size_t len) +{ + apr_status_t status; + + if ((status = apr_file_seek(f, APR_SET, &off)) != APR_SUCCESS || + ((status = apr_file_read_full(f, buf, len, NULL)) != APR_SUCCESS)) { + /* if EOF is reached, pretend we read all zero's */ + if (status == APR_EOF) { + memset(buf, 0, len); + status = APR_SUCCESS; + } + } + + return status; +} + +/* + * the following two routines will break if + * deletions aren't taken into account. (ndbm bug) + */ +APU_DECLARE(apr_status_t) apr_sdbm_firstkey(apr_sdbm_t *db, + apr_sdbm_datum_t *key) +{ + apr_status_t status; + + if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS) + return status; + + /* + * start at page 0 + */ + if ((status = read_from(db->pagf, db->pagbuf, OFF_PAG(0), PBLKSIZ)) + == APR_SUCCESS) { + db->pagbno = 0; + db->blkptr = 0; + db->keyptr = 0; + status = getnext(key, db); + } + + (void) apr_sdbm_unlock(db); + + return status; +} + +APU_DECLARE(apr_status_t) apr_sdbm_nextkey(apr_sdbm_t *db, + apr_sdbm_datum_t *key) +{ + apr_status_t status; + + if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS) + return status; + + status = getnext(key, db); + + (void) apr_sdbm_unlock(db); + + return status; +} + +/* + * all important binary tree traversal + */ +static apr_status_t getpage(apr_sdbm_t *db, long hash) +{ + register int hbit; + register long dbit; + register long pagb; + apr_status_t status; + + dbit = 0; + hbit = 0; + while (dbit < db->maxbno && getdbit(db, dbit)) + dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1); + + debug(("dbit: %d...", dbit)); + + db->curbit = dbit; + db->hmask = masks[hbit]; + + pagb = hash & db->hmask; + /* + * see if the block we need is already in memory. + * note: this lookaside cache has about 10% hit rate. + */ + if (pagb != db->pagbno) { + /* + * note: here, we assume a "hole" is read as 0s. + * if not, must zero pagbuf first. + * ### joe: this assumption was surely never correct? but + * ### we make it so in read_from anyway. + */ + if ((status = read_from(db->pagf, db->pagbuf, OFF_PAG(pagb), PBLKSIZ)) + != APR_SUCCESS) + return status; + + if (!chkpage(db->pagbuf)) + return APR_ENOSPC; /* ### better error? */ + db->pagbno = pagb; + + debug(("pag read: %d\n", pagb)); + } + return APR_SUCCESS; +} + +static int getdbit(apr_sdbm_t *db, long dbit) +{ + register long c; + register long dirb; + + c = dbit / BYTESIZ; + dirb = c / DBLKSIZ; + + if (dirb != db->dirbno) { + if (read_from(db->dirf, db->dirbuf, OFF_DIR(dirb), DBLKSIZ) + != APR_SUCCESS) + return 0; + + db->dirbno = dirb; + + debug(("dir read: %d\n", dirb)); + } + + return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ); +} + +static apr_status_t setdbit(apr_sdbm_t *db, long dbit) +{ + register long c; + register long dirb; + apr_status_t status; + apr_off_t off; + + c = dbit / BYTESIZ; + dirb = c / DBLKSIZ; + + if (dirb != db->dirbno) { + if ((status = read_from(db->dirf, db->dirbuf, OFF_DIR(dirb), DBLKSIZ)) + != APR_SUCCESS) + return status; + + db->dirbno = dirb; + + debug(("dir read: %d\n", dirb)); + } + + db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ); + + if (dbit >= db->maxbno) + db->maxbno += DBLKSIZ * BYTESIZ; + + off = OFF_DIR(dirb); + if ((status = apr_file_seek(db->dirf, APR_SET, &off)) == APR_SUCCESS) + status = apr_file_write_full(db->dirf, db->dirbuf, DBLKSIZ, NULL); + + return status; +} + +/* +* getnext - get the next key in the page, and if done with +* the page, try the next page in sequence +*/ +static apr_status_t getnext(apr_sdbm_datum_t *key, apr_sdbm_t *db) +{ + apr_status_t status; + for (;;) { + db->keyptr++; + *key = getnkey(db->pagbuf, db->keyptr); + if (key->dptr != NULL) + return APR_SUCCESS; + /* + * we either run out, or there is nothing on this page.. + * try the next one... If we lost our position on the + * file, we will have to seek. + */ + db->keyptr = 0; + if (db->pagbno != db->blkptr++) { + apr_off_t off = OFF_PAG(db->blkptr); + if ((status = apr_file_seek(db->pagf, APR_SET, &off)) + != APR_SUCCESS) + return status; + } + + db->pagbno = db->blkptr; + /* ### EOF acceptable here too? */ + if ((status = apr_file_read_full(db->pagf, db->pagbuf, PBLKSIZ, NULL)) + != APR_SUCCESS) + return status; + if (!chkpage(db->pagbuf)) + return APR_EGENERAL; /* ### need better error */ + } + + /* NOTREACHED */ +} + + +APU_DECLARE(int) apr_sdbm_rdonly(apr_sdbm_t *db) +{ + /* ### Should we return true if the first lock is a share lock, + * to reflect that apr_sdbm_store and apr_sdbm_delete will fail? + */ + return (db->flags & SDBM_RDONLY) != 0; +} + |