nsz Git - libc-test/blob - src/functional/search_tsearch.c

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