git.ozlabs.org Git - ccan/blob - ccan/rbtree/test/run-many.c

   1 #include <ccan/rbtree/rbtree.c>
   2 #include <ccan/tap/tap.h>
   3 #include <ccan/talloc/talloc.h>
   4 #include <string.h>
   5 #include <stdbool.h>
   6
   7 #define NUM_ELEMS 10000
   8
   9 static bool lookup_all(trbt_tree_t *rb, bool exist)
  10 {
  11         unsigned int i;
  12
  13         for (i = 0; i < NUM_ELEMS; i++) {
  14                 int *p = trbt_lookup32(rb, i);
  15                 if (p) {
  16                         if (!exist)
  17                                 return false;
  18                         if (*p != i)
  19                                 return false;
  20                 } else
  21                         if (exist)
  22                                 return false;
  23         }
  24         return true;
  25 }
  26
  27 static bool add_one(trbt_tree_t *rb, bool exist, unsigned int i)
  28 {
  29         int *p = trbt_insert32(rb, i, talloc_memdup(rb, &i, sizeof(i)));
  30         if (p) {
  31                 if (!exist)
  32                         return false;
  33                 if (*p != i)
  34                         return false;
  35         } else
  36                 if (exist)
  37                         return false;
  38         return true;
  39 }
  40
  41 static bool insert_all(trbt_tree_t *rb, bool exist)
  42 {
  43         unsigned int i;
  44
  45         for (i = 0; i < NUM_ELEMS; i++) {
  46                 if (!add_one(rb, exist, i))
  47                         return false;
  48         }
  49         return true;
  50 }
  51
  52 static void delete_all(trbt_tree_t *rb)
  53 {
  54         unsigned int i;
  55
  56         /* Don't delete them in the obvious order. */
  57         for (i = 0; i < NUM_ELEMS / 2; i++) {
  58                 trbt_delete32(rb, i);
  59         }
  60
  61         for (i = NUM_ELEMS-1; i >= NUM_ELEMS / 2; i--) {
  62                 trbt_delete32(rb, i);
  63         }
  64 }
  65
  66 int main(void)
  67 {
  68         trbt_tree_t *rb;
  69         void *ctx = talloc_strdup(NULL, "toplevel");
  70
  71         plan_tests(8);
  72
  73         rb = trbt_create(ctx, 0);
  74         ok1(rb);
  75
  76         /* None should be there. */
  77         ok1(lookup_all(rb, false));
  78
  79         /* Insert, none should be there previously. */
  80         ok1(insert_all(rb, false));
  81
  82         /* All there now. */
  83         ok1(lookup_all(rb, true));
  84
  85         /* Replace all. */
  86         ok1(insert_all(rb, true));
  87
  88         /* Delete all. */
  89         delete_all(rb);
  90
  91         /* One more time... */
  92         ok1(lookup_all(rb, false));
  93         ok1(insert_all(rb, false));
  94
  95         /* All are children of rb, so this is clean. */
  96         talloc_free(rb);
  97
  98         /* No memory leaks? */
  99         ok1(talloc_total_blocks(ctx) == 1);
 100         talloc_free(ctx);
 101
 102         /* This exits depending on whether all tests passed */
 103         return exit_status();
 104 }