chain.c, etc.: Add POSIX hsearch(3) and tsearch(3) support.

[wordchain] / chain.c

diff --git a/chain.c b/chain.c
index 50a92b885c7ace00f151bb314e89ee71db2e73b0..69de698db1a8f78c993007d9d21905c670f726a3 100644 (file)
--- a/chain.c
+++ b/chain.c
@@ -1,3 +1,4 @@
+#define _GNU_SOURCE
 #include <assert.h>
 #include <stdarg.h>
 #include <stdio.h>
@@ -24,6 +25,8 @@
 #define LIBAVL_TBST 18
 #define LIBAVL_TRB 19
 #define MLIB_SYM 20
+#define POSIX_HSEARCH 21
+#define POSIX_TSEARCH 22
 
 #define QPITER_FANF 1
 #define QPITER_MDW 2
@@ -125,6 +128,14 @@
 #  include <unistd.h>
 #  include <mLib/sym.h>
 #  include <mLib/unihash.h>
+#elif TREE == POSIX_HSEARCH
+#  include <errno.h>
+#  include <search.h>
+#  ifndef HSEARCH_INITSZ
+#    define HSEARCH_INITSZ 1024
+#  endif
+#elif TREE == POSIX_TSEARCH
+#  include <search.h>
 #else
 #  error "unknown `TREE' value"
 #endif
@@ -194,7 +205,7 @@ struct node {
   short chlen;
 # define CHLEN(node) ((node)->chlen)
 
-#elif USE_LIBAVL
+#elif USE_LIBAVL || TREE == POSIX_TSEARCH
 
   union {
     struct word w;
@@ -215,7 +226,9 @@ struct node {
 
 #endif
 
-#if TREE == MLIB_SYM || (USE_QPTRIE && QPTRIE_ITER == QPITER_LIST)
+#if TREE == MLIB_SYM || \
+    (USE_QPTRIE && QPTRIE_ITER == QPITER_LIST) || \
+    TREE == POSIX_HSEARCH || TREE == POSIX_TSEARCH
   struct node *next;
 #endif
 
@@ -236,7 +249,7 @@ static void bail(const char *msg, ...)
   exit(2);
 }
 
-#if USE_XYLA || TREE == SGT_TREE234 || USE_LIBAVL
+#if USE_XYLA || TREE == SGT_TREE234 || USE_LIBAVL || TREE == POSIX_TSEARCH
 
 static int compare_words(const char *a, size_t alen,
                         const char *b, size_t blen)
@@ -605,6 +618,117 @@ static void free_node(void *n, void *arg) { free(n); }
 
 #  define CHECK do ; while (0)
 
+#elif TREE == POSIX_HSEARCH
+
+#  define DECLS                                                                \
+       ENTRY *e, ee;                                                   \
+       size_t hmax = HSEARCH_INITSZ, hcap = 3*(hmax/4), hused = 0;     \
+       struct node *all = 0, **all_tail = &all                         \
+
+#  define INIT do {                                                    \
+       if (!hcreate(hmax))                                             \
+         bail("hcreate (initial) failed: %s", strerror(errno));        \
+   } while (0)
+
+#  define INSERT do {                                                  \
+       if (hused >= hcap) {                                            \
+         hdestroy();                                                   \
+         hmax *= 2; hcap *= 2;                                         \
+         if (!hcreate(hmax))                                           \
+           bail("hcreate (grow) failed: %s", strerror(errno));         \
+         for (next = all; next; next = next->next) {                   \
+           ee.key = (/*unconst*/ char *)WORDPTR(next); ee.data = next; \
+           if (!hsearch(ee, ENTER))                                    \
+             bail("hsearch (grow) failed: table full");                \
+         }                                                             \
+       }                                                               \
+       ee.key = (char *)(node + 1); ee.data = 0;                       \
+       e = hsearch(ee, ENTER);                                         \
+       if (!e)                                                         \
+         bail("hsearch (insert) failed: table full");                  \
+       else if (!e->data) {                                            \
+         e->data = node;                                               \
+         node->next = 0; *all_tail = node; all_tail = &node->next;     \
+         hused++;                                                      \
+       } else {                                                        \
+         fprintf(stderr, ";; duplicate `%s'\n", buf);                  \
+         free(node); node = 0;                                         \
+       }                                                               \
+   } while (0)
+
+#  define ITERATE for (next = all; node = next, node; next = next->next)
+
+#  define FOCUS do ; while (0)
+
+#  define GETPREFIX do {                                               \
+       word.n = WORDLEN(node) - 1; assert(word.n < WORDMAX);           \
+       memcpy(buf, WORDPTR(node), word.n); buf[word.n] = 0;            \
+   } while (0)
+
+#  define LOOKUP                                                       \
+       (ee.key = (/*unconst*/ char *)word.p,                           \
+        e = hsearch(ee, FIND), e ? e->data : 0)
+
+#  define FREE do {                                                    \
+       node = all;                                                     \
+       while (node) { next = node->next; free(node); node = next; }    \
+       hdestroy();                                                     \
+   } while (0)
+
+#  define CHECK do ; while (0)
+
+#elif TREE == POSIX_TSEARCH
+
+typedef struct { struct node *node; } TNODE;
+
+static int word_cmp(const void *x, const void *y)
+{
+  const struct word *nx = x, *ny = y;
+
+  return (compare_words(nx->p, nx->n, ny->p, ny->n));
+}
+
+#  define DECLS                                                                \
+       void *root = 0;                                                 \
+       struct node *all = 0, **all_tail = &all;                        \
+       TNODE *tn
+
+#  define INIT do ; while (0)
+
+#  define PREPNODE do {                                                        \
+       node = malloc(sizeof(*node) + word.n + 1);                      \
+         if (!node) bail("out of memory");                             \
+       memcpy(node + 1, buf, word.n + 1);                              \
+       node->u.w.p = (const char *)(node + 1); node->u.w.n = word.n;   \
+   } while (0)
+
+#  define INSERT do {                                                  \
+       tn = tsearch(node, &root, word_cmp);                            \
+       if (tn->node == node) {                                         \
+         node->next = 0; *all_tail = node; all_tail = &node->next;     \
+       } else {                                                        \
+         fprintf(stderr, ";; duplicate `%s'\n", buf);                  \
+         free(node); node = 0;                                         \
+       }                                                               \
+   } while (0)
+
+#  define ITERATE for (next = all; node = next, node; next = next->next)
+
+#  define FOCUS do ; while (0)
+
+#  define LOOKUP (tn = tfind(&word, &root, word_cmp), tn ? tn->node : 0)
+
+#  ifdef __GLIBC__
+#    define FREE do tdestroy(root, free); while (0)
+#  else
+#    define FREE do {                                                  \
+       for (next = all; node = next, node; next = next->next)          \
+         { tdelete(node, &root, word_cmp); free(node); }               \
+     } while (0)
+#  endif
+
+#  define CHECK do ; while (0)
+
 #endif
 
 #ifndef PREPNODE