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

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