Work around the fact that GDBM's firstkey/nextkey interface doesn't

return ordered results.

* libdb/db_gdbm.c (man_gdbm_open_wrapper): New function. Wraps the
return value from gdbm_open() in a structure that remembers the
file name.
(parent_sortkey_hash_free, sortkey_hash_free): New functions to
free hashtables used here.
(sortkey_compare): New comparison function for qsort().
(man_gdbm_firstkey): New function. Retrieve all keys using
gdbm_firstkey() and gdbm_nextkey() in advance, sort them into an
ordered hashtable, remember that hashtable for later, and return
the first key.
(man_gdbm_nextkey): New function. Find the previously remembered
ordered hashtable and return the next element from it.
(man_gdbm_close): New function. Clean up remembered data.
* libdb/db_lookup.c (copy_datum): Define even if using GDBM.
(gripe_lock): Explain why this isn't used for GDBM.
* libdb/mydbm.h (man_gdbm_wrapper): New type.
(man_gdbm_open_wrapper, man_gdbm_firstkey, man_gdbm_nextkey,
man_gdbm_close): Add prototypes.
(MYDBM_FILE): Change to man_gdbm_wrapper for GDBM. Adjust all
other MYDBM_* macros to cope with this and use man_gdbm_*
functions where necessary.
(copy_datum): Declare for all database types. Remove __inline__.
* docs/NEWS: Document this.

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 */