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