regress/lib/libc/gen/rbtree/rbstress.c

   1 /* $NetBSD$ */
   2
   3 #include <sys/cdefs.h>
   4 #include <sys/tree.h>
   5 #include <stdlib.h>
   6 #include <stdio.h>
   7
   8 struct mist {
   9         RB_ENTRY(mist) rbentry;
  10         int key;
  11 };
  12 RB_HEAD(head, mist) tt;
  13
  14 static int
  15 mistcmp(struct mist *a, struct mist *b)
  16 {
  17 #if 0
  18         return (b->key - a->key); /* wrong, can overflow */
  19 #else
  20         if (b->key > a->key)
  21                 return 1;
  22         else if (b->key < a->key)
  23                 return (-1);
  24         else
  25                 return 0;
  26 #endif
  27 }
  28
  29 RB_PROTOTYPE(head, mist, rbentry, mistcmp)
  30 RB_GENERATE(head, mist, rbentry, mistcmp)
  31
  32 static struct mist *
  33 addmist(int key)
  34 {
  35         struct mist *m;
  36
  37         m = malloc(sizeof(struct mist));
  38         m->key = key;
  39         RB_INSERT(head, &tt, m);
  40         return m;
  41 }
  42
  43 static int
  44 findmist(struct mist *m)
  45 {
  46
  47         return (!!RB_FIND(head, &tt, m));
  48 }
  49
  50 #define N 1000
  51 static int
  52 test(void)
  53 {
  54         struct mist *m[N];
  55         int fail, i, j;
  56
  57         RB_INIT(&tt);
  58         fail = 0;
  59         for (i = 0; i < N; i++) {
  60                 m[i] = addmist(random() << 1); /* use all 32 bits */
  61                 for (j = 0; j <= i; j++)
  62                         if (!findmist(m[j]))
  63                                 fail++;
  64         }
  65         return fail;
  66 }
  67
  68 int
  69 main(int argc, char **argv)
  70 {
  71         int i, fail, f;
  72
  73         srandom(4711);
  74         fail = 0;
  75         for (i = 0; i < 10; i++) {
  76                 f = test();
  77                 if (f) {
  78                         printf("loop %d: %d errors\n", i, f);
  79                         fail += f;
  80                 }
  81         }
  82         exit(!!fail);
  83 }