summaryrefslogtreecommitdiff
path: root/libdb
diff options
context:
space:
mode:
Diffstat (limited to 'libdb')
-rw-r--r--libdb/db_gdbm.c171
-rw-r--r--libdb/db_lookup.c7
-rw-r--r--libdb/mydbm.h58
3 files changed, 211 insertions, 25 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 */
diff --git a/libdb/db_lookup.c b/libdb/db_lookup.c
index 16f68f83..6b595f4c 100644
--- a/libdb/db_lookup.c
+++ b/libdb/db_lookup.c
@@ -60,8 +60,9 @@ extern int errno;
#include "db_storage.h"
/* If using ndbm or BTREE, copy the static storage before doing anything
- interesting with it */
-#if defined(NDBM) || defined (BTREE)
+ * interesting with it. If using gdbm, firstkey and nextkey need to copy the
+ * storage because our ordered wrappers keep an effectively static copy.
+ */
datum copy_datum (datum dat)
{
if (dat.dptr) {
@@ -72,6 +73,8 @@ datum copy_datum (datum dat)
return dat;
}
+/* gdbm does locking itself. */
+#if defined(NDBM) || defined(BTREE)
void gripe_lock (char *filename)
{
error (0, errno, _("can't lock index cache %s"), filename);
diff --git a/libdb/mydbm.h b/libdb/mydbm.h
index 7dda6386..e4bf6b48 100644
--- a/libdb/mydbm.h
+++ b/libdb/mydbm.h
@@ -45,26 +45,43 @@
extern __inline__ int gdbm_exists(GDBM_FILE dbf, datum key);
# endif /* !HAVE_GDBM_EXISTS */
+/* gdbm_nextkey() is not lexicographically sorted, so we need to keep the
+ * filename around to use as a hash key.
+ */
+typedef struct {
+ char *name;
+ GDBM_FILE file;
+} *man_gdbm_wrapper;
+
+man_gdbm_wrapper man_gdbm_open_wrapper (const char *name, GDBM_FILE file);
+datum man_gdbm_firstkey (man_gdbm_wrapper wrap);
+datum man_gdbm_nextkey (man_gdbm_wrapper wrap, datum key);
+void man_gdbm_close (man_gdbm_wrapper wrap);
+
# define BLK_SIZE 0 /* to invoke normal fs block size */
# define DB_EXT ".db"
-# define MYDBM_FILE GDBM_FILE
-# define MYDBM_CTRWOPEN(file) gdbm_open(file, BLK_SIZE,\
- GDBM_NEWDB|GDBM_FAST, DBMODE, 0)
-# define MYDBM_CRWOPEN(file) gdbm_open(file, BLK_SIZE,\
- GDBM_WRCREAT|GDBM_FAST, DBMODE, 0)
-# define MYDBM_RWOPEN(file) gdbm_open(file, BLK_SIZE,\
- GDBM_WRITER|GDBM_FAST, DBMODE, 0)
-# define MYDBM_RDOPEN(file) gdbm_open(file, BLK_SIZE,\
- GDBM_READER, DBMODE, 0)
-# define MYDBM_INSERT(dbf, key, cont) gdbm_store(dbf, key, cont, GDBM_INSERT)
-# define MYDBM_REPLACE(dbf, key, cont) gdbm_store(dbf, key, cont, GDBM_REPLACE)
-# define MYDBM_EXISTS(dbf, key) gdbm_exists(dbf, key)
-# define MYDBM_DELETE(dbf, key) gdbm_delete(dbf, key)
-# define MYDBM_FETCH(dbf, key) gdbm_fetch(dbf, key)
-# define MYDBM_CLOSE(dbf) gdbm_close(dbf)
-# define MYDBM_FIRSTKEY(dbf) gdbm_firstkey(dbf)
-# define MYDBM_NEXTKEY(dbf, key) gdbm_nextkey(dbf, key)
-# define MYDBM_REORG(dbf) gdbm_reorganize(dbf)
+# define MYDBM_FILE man_gdbm_wrapper
+# define MYDBM_CTRWOPEN(file) man_gdbm_open_wrapper(file,\
+ gdbm_open(file, BLK_SIZE,\
+ GDBM_NEWDB|GDBM_FAST, DBMODE, 0))
+# define MYDBM_CRWOPEN(file) man_gdbm_open_wrapper(file,\
+ gdbm_open(file, BLK_SIZE,\
+ GDBM_WRCREAT|GDBM_FAST, DBMODE, 0))
+# define MYDBM_RWOPEN(file) man_gdbm_open_wrapper(file,\
+ gdbm_open(file, BLK_SIZE,\
+ GDBM_WRITER|GDBM_FAST, DBMODE, 0))
+# define MYDBM_RDOPEN(file) man_gdbm_open_wrapper(file,\
+ gdbm_open(file, BLK_SIZE,\
+ GDBM_READER, DBMODE, 0))
+# define MYDBM_INSERT(dbf, key, cont) gdbm_store((dbf)->file, key, cont, GDBM_INSERT)
+# define MYDBM_REPLACE(dbf, key, cont) gdbm_store((dbf)->file, key, cont, GDBM_REPLACE)
+# define MYDBM_EXISTS(dbf, key) gdbm_exists((dbf)->file, key)
+# define MYDBM_DELETE(dbf, key) gdbm_delete((dbf)->file, key)
+# define MYDBM_FETCH(dbf, key) gdbm_fetch((dbf)->file, key)
+# define MYDBM_CLOSE(dbf) man_gdbm_close(dbf)
+# define MYDBM_FIRSTKEY(dbf) man_gdbm_firstkey(dbf)
+# define MYDBM_NEXTKEY(dbf, key) man_gdbm_nextkey(dbf, key)
+# define MYDBM_REORG(dbf) gdbm_reorganize((dbf)->file)
# define MYDBM_FREE(x) free(x)
# elif defined(NDBM) && !defined(GDBM) && !defined(BTREE)
@@ -80,7 +97,6 @@ extern __inline__ int gdbm_exists(GDBM_FILE dbf, datum key);
# define BERKELEY_DB
# endif /* _DB_H_ */
-extern __inline__ datum copy_datum (datum dat);
extern DBM *ndbm_flopen(char *file, int flags, int mode);
extern int ndbm_flclose(DBM *dbf);
@@ -115,7 +131,6 @@ typedef struct {
size_t dsize;
} datum;
-extern __inline__ datum copy_datum (datum dat);
extern DB *btree_flopen(char *filename, int flags, int mode);
extern __inline__ int btree_close(DB *dbf);
extern __inline__ int btree_exists(DB *dbf, datum key);
@@ -150,6 +165,9 @@ extern __inline__ int btree_nextkeydata(DB *dbf, datum *key, datum *cont);
extern char *database;
extern MYDBM_FILE dbf;
+/* db_lookup.c */
+extern datum copy_datum (datum dat);
+
/* db_ver.c */
extern void dbver_wr(MYDBM_FILE dbf);
extern int dbver_rd(MYDBM_FILE dbf);
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-08 22:52:16 +0000