simple search.h tests

diff --git a/src/functional/search_hsearch.c b/src/functional/search_hsearch.c
new file mode 100644 (file)
index 0000000..0bd6529
--- /dev/null
+++ b/src/functional/search_hsearch.c
@@ -0,0 +1,48 @@
+#include <stdlib.h>
+#include <string.h>
+#include <search.h>
+#include <errno.h>
+#include "test.h"
+
+#define set(k,v) do{ \
+       e = hsearch((ENTRY){.key = k, .data = (void*)v}, ENTER); \
+       if (!e || strcmp(e->key, k) != 0) \
+               t_error("hsearch ENTER %s %d failed\n", k, v); \
+}while(0)
+
+#define get(k) hsearch((ENTRY){.key = k, .data = 0}, FIND)
+
+int main()
+{
+       ENTRY *e;
+
+       if (hcreate(-1) || errno != ENOMEM)
+               t_error("hcreate((size_t)-1) should fail with ENOMEM got %s\n", strerror(errno));
+       if (!hcreate(13))
+               t_error("hcreate(13) failed\n");
+       set("", 0);
+       set("a", 1);
+       set("b", 2);
+       set("abc", 3);
+       set("cd", 4);
+       set("e", 5);
+       set("ef", 6);
+       set("g", 7);
+       set("h", 8);
+       set("iiiiiiiiii", 9);
+       if (!get("a"))
+               t_error("hsearch FIND a failed\n");
+       if (get("c"))
+               t_error("hsearch FIND c should fail\n");
+       set("g", 10);
+       if (e && (int)(e->data) != 7)
+               t_error("hsearch ENTER g 10 returned data %d, wanted 7\n", (int)(e->data));
+       set("g", 10);
+       if (e && (int)(e->data) != 7)
+               t_error("hsearch ENTER g 10 returned data %d, wanted 7\n", (int)(e->data));
+       set("j", 10);
+       if (e && (int)(e->data) != 10)
+               t_error("hsearch ENTER j 10 returned data %d, wanted 10\n", (int)(e->data));
+       hdestroy();
+       return t_status;
+}

diff --git a/src/functional/search_insque.c b/src/functional/search_insque.c
new file mode 100644 (file)
index 0000000..0da76a8
--- /dev/null
+++ b/src/functional/search_insque.c
@@ -0,0 +1,41 @@
+#include <stdlib.h>
+#include <search.h>
+#include "test.h"
+
+struct q {
+       struct q *n;
+       struct q *p;
+       int i;
+};
+
+static struct q *new(int i)
+{
+       struct q *q = malloc(sizeof *q);
+       q->i = i;
+       return q;
+}
+
+int main()
+{
+       struct q *q = new(0);
+       struct q *p;
+       int i;
+
+       insque(q, 0);
+       for (i = 1; i < 10; i++) {
+               insque(new(i), q);
+               q = q->n;
+       }
+       p = q;
+       while (q) {
+               if (q->i != --i)
+                       t_error("walking queue: got %d, wanted %d\n", q->i, i);
+               q = q->p;
+       }
+       remque(p->p);
+       if (p->p->i != p->i-2)
+               t_error("remque: got %d, wanted %d\n", p->p->i, p->i-2);
+       if (p->p->n->i != p->i)
+               t_error("remque: got %d, wanted %d\n", p->p->n->i, p->i);
+       return t_status;
+}

diff --git a/src/functional/search_lsearch.c b/src/functional/search_lsearch.c
new file mode 100644 (file)
index 0000000..8aaffa6
--- /dev/null
+++ b/src/functional/search_lsearch.c
@@ -0,0 +1,44 @@
+#include <string.h>
+#include <search.h>
+#include "test.h"
+
+#define W 80
+static char tab[100][W];
+static size_t nel;
+
+#define set(k) do{ \
+       char *r = lsearch(k, tab, &nel, W, (int(*)(const void*,const void*))strcmp); \
+       if (strcmp(r, k) != 0) \
+               t_error("lsearch %s failed\n", #k); \
+}while(0)
+
+#define get(k) lfind(k, tab, &nel, W, (int(*)(const void*,const void*))strcmp)
+
+int main()
+{
+       size_t n;
+
+       set("");
+       set("a");
+       set("b");
+       set("abc");
+       set("cd");
+       set("e");
+       set("ef");
+       set("g");
+       set("h");
+       set("iiiiiiiiii");
+       if (!get("a"))
+               t_error("lfind a failed\n");
+       if (get("c"))
+               t_error("lfind c should fail\n");
+       n = nel;
+       set("g");
+       if (nel != n)
+               t_error("lsearch g should not modify the table size (%d, was %d)\n", nel, n);
+       n = nel;
+       set("j");
+       if (nel != n+1)
+               t_error("lsearch j should increase the table size (%d, was %d)\n", nel, n);
+       return t_status;
+}

diff --git a/src/functional/search_tsearch.c b/src/functional/search_tsearch.c
new file mode 100644 (file)
index 0000000..9af5fb3
--- /dev/null
+++ b/src/functional/search_tsearch.c
@@ -0,0 +1,126 @@
+#include <stdlib.h>
+#include <string.h>
+#include <search.h>
+#include "test.h"
+
+struct e {
+       char *k;
+       int v;
+};
+
+static void *root;
+static struct e tab[100];
+static struct e *cur = tab;
+
+static int cmp(const void *a, const void *b)
+{
+       return strcmp(((struct e*)a)->k, ((struct e*)b)->k);
+}
+
+static int wantc = 'a';
+static void act(const void *node, VISIT v, int d)
+{
+       struct e *e = *(struct e **)node;
+
+       if (v == preorder)
+               if (e->k[0] < wantc)
+                       t_error("preorder visited node \"%s\" before \"%c\"\n", e->k, wantc);
+       if (v == endorder)
+               if (e->k[0] > wantc)
+                       t_error("endorder visited node \"%s\" after \"%c\"\n", e->k, wantc);
+       if (v == postorder)
+               if (e->k[0] != wantc)
+                       t_error("postorder visited node \"%s\", wanted \"%c\"\n", e->k, wantc);
+       if (v == leaf)
+               if (e->k[0] != wantc)
+                       t_error("visited leaf node \"%s\", wanted \"%c\"\n", e->k, wantc);
+       if (v == postorder || v == leaf)
+               wantc++;
+}
+
+static const void *parent;
+static char *searchkey;
+static void getparent(const void *node, VISIT v, int d)
+{
+       static const void *p;
+       struct e *e = *(struct e **)node;
+
+       if (v == preorder || v == leaf)
+               if (strcmp(searchkey, e->k) == 0)
+                       parent = p;
+       if (v == preorder || v == postorder)
+               p = node;
+}
+
+struct e *set(char *k, int v)
+{
+       struct e **p;
+       cur->k = k;
+       cur->v = v;
+       p = tsearch(cur++, &root, cmp);
+       if (!p || strcmp((*p)->k, k) != 0)
+               t_error("tsearch %s %d failed\n", k, v);
+       if (!p)
+               return 0;
+       return *p;
+}
+
+struct e **get(char *k)
+{
+       return tfind(&(struct e){.k = k}, &root, cmp);
+}
+
+struct e **del(char *k)
+{
+       return tdelete(&(struct e){.k = k}, &root, cmp);
+}
+
+int main() {
+       struct e *e;
+       struct e **p;
+
+       set("f", 6);
+       set("b", 2);
+       set("c", 3);
+       set("e", 5);
+       set("h", 8);
+       set("g", 7);
+       set("a", 1);
+       set("d", 4);
+
+       p = get("a");
+       if (!p || (*p)->v != 1)
+               t_error("tfind a failed\n");
+       if (get("z"))
+               t_error("tfind z should fail\n");
+       e = set("g", 9);
+       if (e && e->v != 7)
+               t_error("tsearch g 9 returned data %d, wanted 7\n", e->v);
+       e = set("g", 9);
+       if (e && e->v != 7)
+               t_error("tsearch g 9 returned data %d, wanted 7\n", e->v);
+       e = set("i", 9);
+       if (e && e->v != 9)
+               t_error("tsearch i 9 returned data %d, wanted 9\n", e->v);
+       if (del("foobar"))
+               t_error("tdelete foobar should fail\n");
+
+       twalk(root, act);
+       if (wantc!='j')
+               t_error("twalk did not visit all nodes (wanted 'j' got '%c')\n", wantc);
+       searchkey = "h";
+       twalk(root, getparent);
+       if (parent == 0)
+               t_error("twalk search for key \"%s\" failed\n", searchkey);
+       p = del("h");
+       if (p != parent)
+               t_error("tdelete h failed to return parent (got %p wanted %p)\n", p, parent);
+
+       p = root;
+       if (!del((*p)->k))
+               t_error("tdelete root \"%s\" failed (returned 0)\n", (*p)->k);
+       if (root == p)
+               t_error("root remained the same after delete\n");
+
+       return t_status;
+}