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