src/functional/search_tsearch.c

   1 #ifndef _XOPEN_SOURCE
   2 #define _XOPEN_SOURCE 700
   3 #endif
   4 #include <stdlib.h>
   5 #include <string.h>
   6 #include <search.h>
   7 #include "test.h"
   8
   9 struct e {
  10         char *k;
  11         int v;
  12 };
  13
  14 static int count;
  15 static void *root;
  16 static struct e tab[100];
  17 static struct e *cur = tab;
  18
  19 static int cmp(const void *a, const void *b)
  20 {
  21         return strcmp(((struct e*)a)->k, ((struct e*)b)->k);
  22 }
  23
  24 static int wantc = 'a';
  25 static void act(const void *node, VISIT v, int d)
  26 {
  27         struct e *e = *(void**)node;
  28
  29         if (v == preorder)
  30                 if (e->k[0] < wantc)
  31                         t_error("preorder visited node \"%s\" before \"%c\"\n", e->k, wantc);
  32         if (v == endorder)
  33                 if (e->k[0] > wantc)
  34                         t_error("endorder visited node \"%s\" after \"%c\"\n", e->k, wantc);
  35         if (v == postorder)
  36                 if (e->k[0] != wantc)
  37                         t_error("postorder visited node \"%s\", wanted \"%c\"\n", e->k, wantc);
  38         if (v == leaf)
  39                 if (e->k[0] != wantc)
  40                         t_error("visited leaf node \"%s\", wanted \"%c\"\n", e->k, wantc);
  41         if (v == postorder || v == leaf)
  42                 wantc++;
  43 }
  44
  45 static const void *parent;
  46 static char *searchkey;
  47 static void getparent(const void *node, VISIT v, int d)
  48 {
  49         static const void *p;
  50         struct e *e = *(void**)node;
  51
  52         if (v == preorder || v == leaf)
  53                 if (strcmp(searchkey, e->k) == 0)
  54                         parent = p;
  55         if (v == preorder || v == postorder)
  56                 p = node;
  57 }
  58
  59 struct e *get(char *k)
  60 {
  61         void **p = tfind(&(struct e){.k = k}, &root, cmp);
  62         if (!p) return 0;
  63         return *p;
  64 }
  65
  66 struct e *set(char *k, int v)
  67 {
  68         void **p;
  69         cur->k = k;
  70         cur->v = v;
  71         if (!get(k))
  72                 count++;
  73         p = tsearch(cur++, &root, cmp);
  74         if (!p || strcmp(((struct e*)*p)->k, k) != 0)
  75                 t_error("tsearch %s %d failed\n", k, v);
  76         if (!p) {
  77                 count--;
  78                 return 0;
  79         }
  80         return *p;
  81 }
  82
  83 void *del(char *k)
  84 {
  85         void *p = tdelete(&(struct e){.k = k}, &root, cmp);
  86         if (p)
  87                 count--;
  88         return p;
  89 }
  90
  91 int main() {
  92         struct e *e;
  93         void *p;
  94
  95         set("f", 6);
  96         set("b", 2);
  97         set("c", 3);
  98         set("e", 5);
  99         set("h", 8);
 100         set("g", 7);
 101         set("a", 1);
 102         set("d", 4);
 103
 104         e = get("a");
 105         if (!e || e->v != 1)
 106                 t_error("tfind a failed\n");
 107         if (get("z"))
 108                 t_error("tfind z should fail\n");
 109         e = set("g", 9);
 110         if (e && e->v != 7)
 111                 t_error("tsearch g 9 returned data %d, wanted 7\n", e->v);
 112         e = set("g", 9);
 113         if (e && e->v != 7)
 114                 t_error("tsearch g 9 returned data %d, wanted 7\n", e->v);
 115         e = set("i", 9);
 116         if (e && e->v != 9)
 117                 t_error("tsearch i 9 returned data %d, wanted 9\n", e->v);
 118         if (del("foobar"))
 119                 t_error("tdelete foobar should fail\n");
 120
 121         twalk(root, act);
 122         if (wantc!='j')
 123                 t_error("twalk did not visit all nodes (wanted 'j' got '%c')\n", wantc);
 124         searchkey = "h";
 125         twalk(root, getparent);
 126         if (parent == 0)
 127                 t_error("twalk search for key \"%s\" failed\n", searchkey);
 128         p = del("h");
 129         if (p != parent)
 130                 t_error("tdelete h failed to return parent (got %p wanted %p)\n", p, parent);
 131
 132         e = *(void**)root;
 133         if (!del(e->k))
 134                 t_error("tdelete root \"%s\" failed (returned 0)\n", e->k);
 135
 136         for (; count; count--) {
 137                 e = *(void**)root;
 138                 if (!tdelete(e, &root, cmp))
 139                         t_error("tdelete k=%s failed during destruction\n", e->k);
 140         }
 141         if (root)
 142                 t_error("tree destruction failed: root is nonzero %p\n", root);
 143
 144         return t_status;
 145 }