Order results manually for NDBM as well as GDBM

Commit 3a753221a3dddaf4870a86a4dca4771ed2cd80b3 in 2003 (!) worked
around the fact that GDBM's firstkey/nextkey interface doesn't return
ordered results.  However, at least when using GDBM's NDBM compatibility
interface, this may be true for NDBM too.  Extend the manual result
ordering code to cover both of these backends.

* libdb/db_gdbm.c (parent_keys, datum_compare, datum_equals, datum_hash,
datum_free, empty_datum, man_gdbm_firstkey, man_gdbm_nextkey,
man_gdbm_close): Move to ...
* libdb/db_xdbm.c (parent_keys, datum_compare, datum_equals, datum_hash,
datum_free, empty_datum, man_xdbm_firstkey, man_xdbm_nextkey,
man_xdbm_close): ... here (new file).
* libdb/db_xdbm.h: New file.
* libdb/db_gdbm.c (unsorted_firstkey, unsorted_nextkey, raw_close): New
functions, wrapping gdbm_firstkey, gdbm_nextkey, and gdbm_close
respectively.
(man_gdbm_firstkey, man_gdbm_nextkey, man_gdbm_close): Add GDBM-specific
wrappers for the generic man_xdbm_* functions.
* libdb/db_ndbm.c (man_ndbm_close): Move NDBM-specific code ...
(raw_close): ... here.
(unsorted_firstkey, unsorted_nextkey): New functions, wrapping
dbm_firstkey and dbm_nextkey respectively.
(man_ndbm_close, man_ndbm_firstkey, man_ndbm_nextkey): Add NDBM-specific
wrappers for the generic man_xdbm_* functions.
* libdb/mydbm.h (man_ndbm_firstkey, man_ndbm_nextkey): Add prototypes.
(MYDBM_FIRSTKEY) [NDBM]: Rewrite in terms of man_ndbm_firstkey.
(MYDBM_NEXTKEY) [NDBM]: Rewrite in terms of man_ndbm_nextkey.
* libdb/Makefile.am (libmandb_la_SOURCES): Add db_xdbm.c and db_xdbm.h.
* NEWS: Document this.

6 files changed, 256 insertions, 119 deletions

diff --git a/libdb/Makefile.am b/libdb/Makefile.am
index 0015b84b..2851dfa3 100644
--- a/libdb/Makefile.am
+++ b/libdb/Makefile.am
@@ -39,6 +39,8 @@ libmandb_la_SOURCES = \
 	db_storage.h \
 	db_store.c \
 	db_ver.c \
+	db_xdbm.c \
+	db_xdbm.h \
 	mydbm.h
 
 libmandb_la_LIBADD = ../lib/libman.la $(DBLIBS)
diff --git a/libdb/db_gdbm.c b/libdb/db_gdbm.c
index d8fb988d..1062f357 100644
--- a/libdb/db_gdbm.c
+++ b/libdb/db_gdbm.c
@@ -34,23 +34,16 @@
 #include <sys/stat.h>
 #include <unistd.h>
 
-#include "gl_hash_map.h"
-#include "gl_rbtree_list.h"
-#include "gl_xlist.h"
-#include "gl_xmap.h"
-#include "hash-pjw-bare.h"
 #include "stat-time.h"
 #include "timespec.h"
 
 #include "manconfig.h"
 
 #include "cleanup.h"
-#include "glcontainers.h"
 
+#include "db_xdbm.h"
 #include "mydbm.h"
 
-static gl_map_t parent_keys;
-
 /* setjmp/longjmp handling to defend against _gdbm_fatal exiting under our
  * feet.  Not thread-safe, but there is no plan for man-db to ever use
  * threads.
@@ -103,111 +96,24 @@ man_gdbm_wrapper man_gdbm_open_wrapper (const char *name, int flags)
 	return wrap;
 }
 
-static int datum_compare (const void *a, const void *b)
-{
-	const datum *left = (const datum *) a;
-	const datum *right = (const datum *) b;
-	int cmp;
-	size_t minsize;
-
-	/* Sentinel NULL elements sort to the end. */
-	if (!MYDBM_DPTR (*left))
-		return 1;
-	else if (!MYDBM_DPTR (*right))
-		return -1;
-
-	if (MYDBM_DSIZE (*left) < MYDBM_DSIZE (*right))
-		minsize = MYDBM_DSIZE (*left);
-	else
-		minsize = MYDBM_DSIZE (*right);
-	cmp = strncmp (MYDBM_DPTR (*left), MYDBM_DPTR (*right), minsize);
-	if (cmp)
-		return cmp;
-	else if (MYDBM_DSIZE (*left) < MYDBM_DSIZE (*right))
-		return 1;
-	else if (MYDBM_DSIZE (*left) > MYDBM_DSIZE (*right))
-		return -1;
-	else
-		return 0;
-}
-
-static bool datum_equals (const void *a, const void *b)
+static datum unsorted_firstkey (man_gdbm_wrapper wrap)
 {
-	return datum_compare (a, b) == 0;
+	return gdbm_firstkey (wrap->file);
 }
 
-static size_t datum_hash (const void *value)
+static datum unsorted_nextkey (man_gdbm_wrapper wrap, datum key)
 {
-	const datum *d = value;
-	return hash_pjw_bare (MYDBM_DPTR (*d), MYDBM_DSIZE (*d));
+	return gdbm_nextkey (wrap->file, key);
 }
 
-static void datum_free (const void *value)
-{
-	MYDBM_FREE_DPTR (*(datum *) value);
-}
-
-static datum empty_datum = { NULL, 0 };
-
-/* We keep a map of filenames to sorted lists of keys.  Each list is stored
- * using a hash-based implementation that allows lookup by name and
- * traversal to the next item in O(log n) time, which is necessary for a
- * reasonable ordered implementation of nextkey.
- */
 datum man_gdbm_firstkey (man_gdbm_wrapper wrap)
 {
-	gl_list_t keys;
-	datum *key;
-
-	/* Build the raw sorted list of keys. */
-	keys = gl_list_create_empty (GL_RBTREE_LIST, datum_equals, datum_hash,
-				     datum_free, false);
-	key = XMALLOC (datum);
-	*key = gdbm_firstkey (wrap->file);
-	while (MYDBM_DPTR (*key)) {
-		datum *next;
-
-		gl_sortedlist_add (keys, datum_compare, key);
-		next = XMALLOC (datum);
-		*next = gdbm_nextkey (wrap->file, *key);
-		key = next;
-	}
-
-	if (!parent_keys) {
-		parent_keys = new_string_map (GL_HASH_MAP,
-					      (gl_listelement_dispose_fn)
-					      gl_list_free);
-		push_cleanup ((cleanup_fun) gl_map_free, parent_keys, 0);
-	}
-
-	/* Remember this structure for use by nextkey. */
-	gl_map_put (parent_keys, xstrdup (wrap->name), keys);
-
-	if (gl_list_size (keys))
-		return copy_datum (*(datum *) gl_list_get_at (keys, 0));
-	else
-		return empty_datum;
+	return man_xdbm_firstkey (wrap, unsorted_firstkey, unsorted_nextkey);
 }
 
 datum man_gdbm_nextkey (man_gdbm_wrapper wrap, datum key)
 {
-	gl_list_t keys;
-	gl_list_node_t node, next_node;
-
-	if (!parent_keys)
-		return empty_datum;
-	keys = (gl_list_t) gl_map_get (parent_keys, wrap->name);
-	if (!keys)
-		return empty_datum;
-
-	node = gl_sortedlist_search (keys, datum_compare, &key);
-	if (!node)
-		return empty_datum;
-	next_node = gl_list_next_node (keys, node);
-	if (!next_node)
-		return empty_datum;
-
-	return copy_datum (*(datum *) gl_list_node_value (keys, next_node));
+	return man_xdbm_nextkey (wrap, key);
 }
 
 struct timespec man_gdbm_get_time (man_gdbm_wrapper wrap)
@@ -232,17 +138,14 @@ void man_gdbm_set_time (man_gdbm_wrapper wrap, const struct timespec time)
 	futimens (gdbm_fdesc (wrap->file), times);
 }
 
-void man_gdbm_close (man_gdbm_wrapper wrap)
+static void raw_close (man_gdbm_wrapper wrap)
 {
-	if (!wrap)
-		return;
-
-	if (parent_keys)
-		gl_map_remove (parent_keys, wrap->name);
-
-	free (wrap->name);
 	gdbm_close (wrap->file);
-	free (wrap);
+}
+
+void man_gdbm_close (man_gdbm_wrapper wrap)
+{
+	man_xdbm_close (wrap, raw_close);
 }
 
 #ifndef HAVE_GDBM_EXISTS
diff --git a/libdb/db_ndbm.c b/libdb/db_ndbm.c
index c5a6d0b9..64000c1c 100644
--- a/libdb/db_ndbm.c
+++ b/libdb/db_ndbm.c
@@ -41,19 +41,20 @@
 
 #include "manconfig.h"
 
-#include "mydbm.h"
 #include "db_storage.h"
+#include "db_xdbm.h"
+#include "mydbm.h"
 
 /* release the lock and close the database */
-void man_ndbm_close (man_ndbm_wrapper wrap)
+static void raw_close (man_ndbm_wrapper wrap)
 {
-	if (!wrap)
-		return;
-
-	free (wrap->name);
 	flock (dbm_dirfno (wrap->file), LOCK_UN);
 	dbm_close (wrap->file);
-	free (wrap);
+}
+
+void man_ndbm_close (man_ndbm_wrapper wrap)
+{
+	man_xdbm_close (wrap, raw_close);
 }
 
 /* open a ndbm type database, with file locking. */
@@ -117,6 +118,26 @@ man_ndbm_wrapper man_ndbm_open (const char *name, int flags, int mode)
 	return wrap;
 }
 
+static datum unsorted_firstkey (man_ndbm_wrapper wrap)
+{
+	return copy_datum (dbm_firstkey (wrap->file));
+}
+
+static datum unsorted_nextkey (man_ndbm_wrapper wrap, datum key _GL_UNUSED)
+{
+	return copy_datum (dbm_nextkey (wrap->file));
+}
+
+datum man_ndbm_firstkey (man_ndbm_wrapper wrap)
+{
+	return man_xdbm_firstkey (wrap, unsorted_firstkey, unsorted_nextkey);
+}
+
+datum man_ndbm_nextkey (man_ndbm_wrapper wrap, datum key)
+{
+	return man_xdbm_nextkey (wrap, key);
+}
+
 struct timespec man_ndbm_get_time (man_ndbm_wrapper wrap)
 {
 	struct stat st;
diff --git a/libdb/db_xdbm.c b/libdb/db_xdbm.c
new file mode 100644
index 00000000..f0a9932e
--- /dev/null
+++ b/libdb/db_xdbm.c
@@ -0,0 +1,169 @@
+/*
+ * db_xdbm.c: common code for gdbm and ndbm backends
+ *
+ * Copyright (C) 2003-2019 Colin Watson.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ */
+
+#ifdef HAVE_CONFIG_H
+#  include "config.h"
+#endif /* HAVE_CONFIG_H */
+
+#if defined(GDBM) || defined(NDBM)
+
+#include <stdbool.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include "gl_hash_map.h"
+#include "gl_rbtree_list.h"
+#include "gl_xlist.h"
+#include "gl_xmap.h"
+#include "hash-pjw-bare.h"
+
+#include "manconfig.h"
+
+#include "cleanup.h"
+#include "glcontainers.h"
+
+#include "db_xdbm.h"
+#include "mydbm.h"
+
+static gl_map_t parent_keys;
+
+static int datum_compare (const void *a, const void *b)
+{
+	const datum *left = (const datum *) a;
+	const datum *right = (const datum *) b;
+	int cmp;
+	size_t minsize;
+
+	/* Sentinel NULL elements sort to the end. */
+	if (!MYDBM_DPTR (*left))
+		return 1;
+	else if (!MYDBM_DPTR (*right))
+		return -1;
+
+	if (MYDBM_DSIZE (*left) < MYDBM_DSIZE (*right))
+		minsize = MYDBM_DSIZE (*left);
+	else
+		minsize = MYDBM_DSIZE (*right);
+	cmp = strncmp (MYDBM_DPTR (*left), MYDBM_DPTR (*right), minsize);
+	if (cmp)
+		return cmp;
+	else if (MYDBM_DSIZE (*left) < MYDBM_DSIZE (*right))
+		return 1;
+	else if (MYDBM_DSIZE (*left) > MYDBM_DSIZE (*right))
+		return -1;
+	else
+		return 0;
+}
+
+static bool datum_equals (const void *a, const void *b)
+{
+	return datum_compare (a, b) == 0;
+}
+
+static size_t datum_hash (const void *value)
+{
+	const datum *d = value;
+	return hash_pjw_bare (MYDBM_DPTR (*d), MYDBM_DSIZE (*d));
+}
+
+static void datum_free (const void *value)
+{
+	MYDBM_FREE_DPTR (*(datum *) value);
+}
+
+static datum empty_datum = { NULL, 0 };
+
+/* We keep a map of filenames to sorted lists of keys.  Each list is stored
+ * using a hash-based implementation that allows lookup by name and
+ * traversal to the next item in O(log n) time, which is necessary for a
+ * reasonable ordered implementation of nextkey.
+ */
+datum man_xdbm_firstkey (MYDBM_FILE dbf,
+			 man_xdbm_unsorted_firstkey unsorted_firstkey,
+			 man_xdbm_unsorted_nextkey unsorted_nextkey)
+{
+	gl_list_t keys;
+	datum *key;
+
+	/* Build the raw sorted list of keys. */
+	keys = gl_list_create_empty (GL_RBTREE_LIST, datum_equals, datum_hash,
+				     datum_free, false);
+	key = XMALLOC (datum);
+	*key = unsorted_firstkey (dbf);
+	while (MYDBM_DPTR (*key)) {
+		datum *next;
+
+		gl_sortedlist_add (keys, datum_compare, key);
+		next = XMALLOC (datum);
+		*next = unsorted_nextkey (dbf, *key);
+		key = next;
+	}
+
+	if (!parent_keys) {
+		parent_keys = new_string_map (GL_HASH_MAP,
+					      (gl_listelement_dispose_fn)
+					      gl_list_free);
+		push_cleanup ((cleanup_fun) gl_map_free, parent_keys, 0);
+	}
+
+	/* Remember this structure for use by nextkey. */
+	gl_map_put (parent_keys, xstrdup (dbf->name), keys);
+
+	if (gl_list_size (keys))
+		return copy_datum (*(datum *) gl_list_get_at (keys, 0));
+	else
+		return empty_datum;
+}
+
+datum man_xdbm_nextkey (MYDBM_FILE dbf, datum key)
+{
+	gl_list_t keys;
+	gl_list_node_t node, next_node;
+
+	if (!parent_keys)
+		return empty_datum;
+	keys = (gl_list_t) gl_map_get (parent_keys, dbf->name);
+	if (!keys)
+		return empty_datum;
+
+	node = gl_sortedlist_search (keys, datum_compare, &key);
+	if (!node)
+		return empty_datum;
+	next_node = gl_list_next_node (keys, node);
+	if (!next_node)
+		return empty_datum;
+
+	return copy_datum (*(datum *) gl_list_node_value (keys, next_node));
+}
+
+void man_xdbm_close (MYDBM_FILE dbf, man_xdbm_raw_close raw_close)
+{
+	if (!dbf)
+		return;
+
+	if (parent_keys)
+		gl_map_remove (parent_keys, dbf->name);
+
+	free (dbf->name);
+	raw_close (dbf);
+	free (dbf);
+}
+
+#endif /* GDBM || NDBM */
diff --git a/libdb/db_xdbm.h b/libdb/db_xdbm.h
new file mode 100644
index 00000000..9d7f4bf7
--- /dev/null
+++ b/libdb/db_xdbm.h
@@ -0,0 +1,40 @@
+/*
+ * db_xdbm.c: interface to common code for gdbm and ndbm backends
+ *
+ * Copyright (C) 2019 Colin Watson.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ */
+
+#ifndef MAN_XDBM_H
+#define MAN_XDBM_H
+
+#if defined(GDBM) || defined(NDBM)
+
+#include "mydbm.h"
+
+typedef datum (*man_xdbm_unsorted_firstkey) (MYDBM_FILE dbf);
+typedef datum (*man_xdbm_unsorted_nextkey) (MYDBM_FILE dbf, datum key);
+typedef void (*man_xdbm_raw_close) (MYDBM_FILE dbf);
+
+datum man_xdbm_firstkey (MYDBM_FILE dbf,
+			 man_xdbm_unsorted_firstkey firstkey,
+			 man_xdbm_unsorted_nextkey nextkey);
+datum man_xdbm_nextkey (MYDBM_FILE dbf, datum key);
+void man_xdbm_close (MYDBM_FILE dbf, man_xdbm_raw_close raw_close);
+
+#endif /* GDBM || NDBM */
+
+#endif /* MAN_XDBM_H */
diff --git a/libdb/mydbm.h b/libdb/mydbm.h
index 88121afb..31f1d756 100644
--- a/libdb/mydbm.h
+++ b/libdb/mydbm.h
@@ -104,6 +104,8 @@ typedef struct {
 } *man_ndbm_wrapper;
 
 extern man_ndbm_wrapper man_ndbm_open (const char *name, int flags, int mode);
+extern datum man_ndbm_firstkey (man_ndbm_wrapper wrap);
+extern datum man_ndbm_nextkey (man_ndbm_wrapper wrap, datum key);
 extern struct timespec man_ndbm_get_time (man_ndbm_wrapper wrap);
 extern void man_ndbm_set_time (man_ndbm_wrapper wrap, const struct timespec time);
 extern void man_ndbm_close (man_ndbm_wrapper wrap);
@@ -123,8 +125,8 @@ extern void man_ndbm_close (man_ndbm_wrapper wrap);
 #  define MYDBM_DELETE(db, key)		dbm_delete((db)->file, key)
 #  define MYDBM_FETCH(db, key)		copy_datum(dbm_fetch((db)->file, key))
 #  define MYDBM_CLOSE(db)		man_ndbm_close(db)
-#  define MYDBM_FIRSTKEY(db)		copy_datum(dbm_firstkey((db)->file))
-#  define MYDBM_NEXTKEY(db, key)	copy_datum(dbm_nextkey((db)->file))
+#  define MYDBM_FIRSTKEY(db)		man_ndbm_firstkey(db)
+#  define MYDBM_NEXTKEY(db, key)	man_ndbm_nextkey(db, key)
 #  define MYDBM_GET_TIME(db)		man_ndbm_get_time(db)
 #  define MYDBM_SET_TIME(db, time)	man_ndbm_set_time(db, time)
 #  define MYDBM_REORG(db)		/* nothing - not implemented */