From 132e3876a5bf16f33a059908269c3b9b8b458924 Mon Sep 17 00:00:00 2001 From: Szabolcs Nagy Date: Sat, 3 Aug 2013 02:05:14 +0000 Subject: [PATCH] simple search.h tests --- src/functional/search_hsearch.c | 48 ++++++++++++ src/functional/search_insque.c | 41 +++++++++++ src/functional/search_lsearch.c | 44 +++++++++++ src/functional/search_tsearch.c | 126 ++++++++++++++++++++++++++++++++ 4 files changed, 259 insertions(+) create mode 100644 src/functional/search_hsearch.c create mode 100644 src/functional/search_insque.c create mode 100644 src/functional/search_lsearch.c create mode 100644 src/functional/search_tsearch.c diff --git a/src/functional/search_hsearch.c b/src/functional/search_hsearch.c new file mode 100644 index 0000000..0bd6529 --- /dev/null +++ b/src/functional/search_hsearch.c @@ -0,0 +1,48 @@ +#include +#include +#include +#include +#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 index 0000000..0da76a8 --- /dev/null +++ b/src/functional/search_insque.c @@ -0,0 +1,41 @@ +#include +#include +#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 index 0000000..8aaffa6 --- /dev/null +++ b/src/functional/search_lsearch.c @@ -0,0 +1,44 @@ +#include +#include +#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 index 0000000..9af5fb3 --- /dev/null +++ b/src/functional/search_tsearch.c @@ -0,0 +1,126 @@ +#include +#include +#include +#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; +} -- 2.20.1