begriffs open source - libderp/blob - test/t_treemap.c

   1 #include <assert.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 #include "derp/common.h"
   6 #include "derp/treemap.h"
   7
   8 #ifdef HAVE_BOEHM_GC
   9 #include <gc/gc.h>
  10
  11 #undef malloc
  12 #define malloc(x) GC_malloc(x)
  13 #undef realloc
  14 #define realloc(x,y) GC_realloc(x,y)
  15 #undef free
  16 #define free(x) GC_free(x)
  17 #endif
  18
  19 int ivals[] = {0,1,2,3,4,5,6,7,8,9};
  20
  21 int icmp(const void *a, const void *b, void *aux)
  22 {
  23         (void)aux;
  24         return *(int*)a - *(int*)b;
  25 }
  26
  27 int main(void)
  28 {
  29 #ifdef HAVE_BOEHM_GC
  30         GC_set_find_leak(1);
  31         derp_use_alloc_funcs(GC_malloc, GC_realloc, GC_free);
  32 #endif
  33
  34         treemap *t = tm_new(derp_strcmp, NULL);
  35         assert(tm_length(t) == 0);
  36         assert(tm_is_empty(t));
  37
  38         assert(!tm_at(t, "zero"));
  39         tm_insert(t, "zero", ivals);
  40         assert(tm_length(t) == 1);
  41         assert(*(int*)tm_at(t, "zero") == 0);
  42
  43         /* change it */
  44         tm_insert(t, "zero", ivals+1);
  45         assert(tm_length(t) == 1);
  46         assert(*(int*)tm_at(t, "zero") == 1);
  47         /* set it back */
  48         tm_insert(t, "zero", ivals);
  49         assert(*(int*)tm_at(t, "zero") == 0);
  50
  51         tm_insert(t, "one", ivals+1);
  52         assert(tm_length(t) == 2);
  53         assert(*(int*)tm_at(t, "zero") == 0);
  54         assert(*(int*)tm_at(t, "one") == 1);
  55         assert(!tm_at(t, "flurgle"));
  56
  57         tm_remove(t, "one");
  58         assert(!tm_at(t, "one"));
  59
  60         tm_clear(t);
  61         assert(tm_length(t) == 0);
  62         assert(!tm_at(t, "zero"));
  63
  64         /* iterator should sort */
  65         tm_insert(t, "d", NULL);
  66         tm_insert(t, "a", NULL);
  67         tm_insert(t, "e", NULL);
  68         tm_insert(t, "c", NULL);
  69         tm_insert(t, "b", NULL);
  70
  71         tm_iter *i = tm_iter_begin(t);
  72         assert(*(char*)tm_iter_next(i)->k == 'a');
  73         assert(*(char*)tm_iter_next(i)->k == 'b');
  74         assert(*(char*)tm_iter_next(i)->k == 'c');
  75         assert(*(char*)tm_iter_next(i)->k == 'd');
  76         assert(*(char*)tm_iter_next(i)->k == 'e');
  77         assert(!tm_iter_next(i));
  78         tm_iter_free(i);
  79         tm_clear(t);
  80
  81         /* test for memory leak */
  82         tm_dtor(t, derp_free, derp_free, NULL);
  83         char *key = malloc(5),
  84                  *dupkey = malloc(5),
  85                  *otherkey = malloc(3);
  86         int  *val1 = malloc(sizeof *val1),
  87              *val2 = malloc(sizeof *val2),
  88              *val3 = malloc(sizeof *val3);
  89         strcpy(key, "life");
  90         strcpy(dupkey, "life");
  91         *val1 = 42;
  92         *val2 = 13;
  93         tm_insert(t, key, val1);
  94         /* will free key, since dupkey is the same */
  95         tm_insert(t, dupkey, val2);
  96         /* safe to double-insert same key */
  97         tm_insert(t, dupkey, val2);
  98
  99         /* tm_remove should free as needed */
 100         *val3 = 200;
 101         strcpy(otherkey, "hi");
 102         tm_insert(t, otherkey, val3);
 103         tm_remove(t, otherkey);
 104
 105         tm_free(t);
 106
 107         treemap *t2 = tm_new(icmp, NULL);
 108         /* insert in ascending order, inherently unbalanced,
 109          * to exercise split/skew */
 110         for (size_t i = 0; i < 10; i++)
 111                 tm_insert(t2, ivals+i, ivals+i);
 112         assert(tm_length(t2) == 10);
 113
 114         /* all there? */
 115         for (size_t i = 0; i < 10; i++)
 116                 assert(*(int*)tm_at(t2, ivals+i) == (int)i);
 117
 118         /* remove odd ones */
 119         for (size_t i = 1; i < 10; i+=2)
 120                 tm_remove(t2, ivals+i);
 121         assert(tm_length(t2) == 5);
 122
 123         /* evens should still be there */
 124         for (size_t i = 0; i < 10; i+=2)
 125                 assert((int)i == *(int*)tm_at(t2, ivals+i));
 126
 127         /* remove evens */
 128         for (size_t i = 0; i < 10; i+=2)
 129                 tm_remove(t2, ivals+i);
 130         assert(tm_is_empty(t2));
 131
 132         tm_free(t2);
 133
 134 #ifdef HAVE_BOEHM_GC
 135         GC_gcollect();
 136 #endif
 137         return 0;
 138 }