diff options
Diffstat (limited to 'libdb/db_gdbm.c')
-rw-r--r-- | libdb/db_gdbm.c | 171 |
1 files changed, 168 insertions, 3 deletions
diff --git a/libdb/db_gdbm.c b/libdb/db_gdbm.c index 0603d61c..70182575 100644 --- a/libdb/db_gdbm.c +++ b/libdb/db_gdbm.c @@ -24,15 +24,177 @@ # include "config.h" #endif /* HAVE_CONFIG_H */ -#if defined(GDBM) && !defined(HAVE_GDBM_EXISTS) +#ifdef GDBM -#ifdef STDC_HEADERS +#if defined(STDC_HEADERS) +# include <string.h> # include <stdlib.h> +#elif defined(HAVE_STRING_H) +# include <string.h> +#elif defined(HAVE_STRINGS_H) +# include <strings.h> #endif /* STDC_HEADERS */ #include "manconfig.h" +#include "lib/hashtable.h" #include "mydbm.h" +static struct hashtable *parent_sortkey_hash; + +struct sortkey { + datum key; + struct sortkey *next; +}; + +man_gdbm_wrapper man_gdbm_open_wrapper (const char *name, GDBM_FILE file) +{ + man_gdbm_wrapper wrap; + + if (!file) + return NULL; + + wrap = xmalloc (sizeof *wrap); + wrap->name = xstrdup (name); + wrap->file = file; + + return wrap; +} + +static void parent_sortkey_hash_free (void *defn) +{ + /* Automatically free child hashtables on removal. */ + hash_free ((struct hashtable *) defn); +} + +static void sortkey_hash_free (void *defn) +{ + struct sortkey *key = (struct sortkey *) defn; + free (key->key.dptr); + free (key); +} + +static int sortkey_compare (const void *a, const void *b) +{ + const struct sortkey **left = (const struct sortkey **) a; + const struct sortkey **right = (const struct sortkey **) b; + int cmp; + + /* Sentinel NULL elements sort to the end. */ + if (!(*left)->key.dptr) + return 1; + else if (!(*right)->key.dptr) + return -1; + + cmp = strncmp ((*left)->key.dptr, (*right)->key.dptr, + ((*left)->key.dsize < (*right)->key.dsize) + ? (*left)->key.dsize : (*right)->key.dsize); + if (cmp) + return cmp; + else if ((*left)->key.dsize < (*right)->key.dsize) + return 1; + else if ((*left)->key.dsize > (*right)->key.dsize) + return -1; + else + return 0; +} + +static datum empty_datum = { NULL, 0 }; + +/* We keep a hashtable of filenames to sorted lists of keys. Each list is + * stored both with links from each element to the next and in a hashtable, + * so that both sequential access and random access are quick. This is + * necessary for a reasonable ordered implementation of nextkey. + */ +datum man_gdbm_firstkey (man_gdbm_wrapper wrap) +{ + struct hashtable *sortkey_hash; + struct sortkey **keys, *firstkey; + int numkeys = 0, maxkeys = 256; + int i; + + /* Build the raw list of keys and sort it. */ + keys = xmalloc (maxkeys * sizeof *keys); + keys[0] = xmalloc (sizeof **keys); + keys[0]->key = gdbm_firstkey (wrap->file); + while (keys[numkeys]->key.dptr) { + if (++numkeys >= maxkeys) { + maxkeys *= 2; + keys = xrealloc (keys, maxkeys * sizeof *keys); + } + keys[numkeys] = xmalloc (sizeof **keys); + keys[numkeys]->key = + gdbm_nextkey (wrap->file, keys[numkeys - 1]->key); + } + free (keys[numkeys]); + keys[numkeys] = NULL; /* simplifies the empty case */ + qsort (keys, numkeys, sizeof *keys, &sortkey_compare); + + /* Link the elements together and insert them into a hash. */ + sortkey_hash = hash_create (&sortkey_hash_free); + for (i = 0; i < numkeys; ++i) { + if (i < numkeys - 1) + keys[i]->next = keys[i + 1]; + else + keys[i]->next = NULL; + hash_install (sortkey_hash, + keys[i]->key.dptr, keys[i]->key.dsize, keys[i]); + } + firstkey = keys[0]; + free (keys); /* element memory now owned by hashtable */ + + if (!parent_sortkey_hash) + parent_sortkey_hash = hash_create (&parent_sortkey_hash_free); + + /* Remember this structure for use by nextkey. */ + hash_install (parent_sortkey_hash, + wrap->name, strlen (wrap->name), sortkey_hash); + + if (firstkey) + return copy_datum (firstkey->key); + else + return empty_datum; /* dptr is NULL, so no copy needed */ +} + +datum man_gdbm_nextkey (man_gdbm_wrapper wrap, datum key) +{ + struct hashtable *sortkey_hash; + struct sortkey *sortkey; + + if (!parent_sortkey_hash) + return empty_datum; + sortkey_hash = hash_lookup (parent_sortkey_hash, + wrap->name, strlen (wrap->name)); + if (!sortkey_hash) + return empty_datum; + + sortkey = hash_lookup (sortkey_hash, key.dptr, key.dsize); + if (!sortkey || !sortkey->next) + return empty_datum; + + return copy_datum (sortkey->next->key); +} + +void man_gdbm_close (man_gdbm_wrapper wrap) +{ + if (!wrap) + return; + + if (parent_sortkey_hash) { + struct hashtable *sortkey_hash = + hash_lookup (parent_sortkey_hash, + wrap->name, strlen (wrap->name)); + if (sortkey_hash) + hash_remove (parent_sortkey_hash, + wrap->name, strlen (wrap->name)); + } + + free (wrap->name); + gdbm_close (wrap->file); + free (wrap); +} + +#ifndef HAVE_GDBM_EXISTS + int gdbm_exists (GDBM_FILE dbf, datum key) { char *memory; @@ -45,4 +207,7 @@ int gdbm_exists (GDBM_FILE dbf, datum key) return 0; } -#endif /* GDBM && !HAVE_GDBM_EXISTS*/ + +#endif /* !HAVE_GDBM_EXISTS */ + +#endif /* GDBM */ |