begriffs open source - libderp/blob - src/treemap.c

   1 #include "treemap.h"
   2
   3 #include <stdlib.h>
   4
   5 /* AA Tree, which came from Arne Andersson
   6  * Balanced Search Trees Made Simple
   7  * https://user.it.uu.se/~arnea/ps/simp.pdf
   8  *
   9  * As fast as an RB-tree, but free of those
  10  * ugly special cases. */
  11
  12 struct tm_node
  13 {
  14         int level;
  15         struct map_pair *pair;
  16         struct tm_node *left, *right;
  17 };
  18
  19 struct treemap
  20 {
  21         struct tm_node *root, *bottom;
  22         struct tm_node *deleted, *last;
  23
  24         dtor *key_dtor;
  25         dtor *val_dtor;
  26         comparator *cmp;
  27         void *cmp_aux;
  28         void *dtor_aux;
  29 };
  30
  31 treemap *
  32 tm_new(comparator *cmp, void *cmp_aux)
  33 {
  34         treemap *t = malloc(sizeof *t);
  35         struct tm_node *bottom = malloc(sizeof *bottom);
  36         if (!t || !bottom)
  37         {
  38                 free(t);
  39                 free(bottom);
  40                 return NULL;
  41         }
  42         /* sentinel living below all leaves */
  43         *bottom = (struct tm_node){
  44                 .left = bottom, .right = bottom, .level = 0
  45         };
  46         *t = (treemap){
  47                 .root = bottom,
  48                 .bottom = bottom,
  49                 .cmp = cmp,
  50                 .cmp_aux = cmp_aux
  51         };
  52         return t;
  53 }
  54
  55 void
  56 tm_free(treemap *t)
  57 {
  58
  59 }
  60
  61 void
  62 tm_dtor(treemap *t, dtor *key_dtor, dtor *val_dtor, void *dtor_aux)
  63 {
  64         if (!t)
  65                 return;
  66         t->key_dtor = key_dtor;
  67         t->val_dtor = val_dtor;
  68         t->dtor_aux = dtor_aux;
  69 }
  70
  71 static size_t
  72 _tm_length(const struct tm_node *n, const struct tm_node *bottom)
  73 {
  74         if (n == bottom)
  75                 return 0;
  76         return 1 +
  77                 _tm_length(n->left, bottom) + _tm_length(n->right, bottom);
  78 }
  79
  80 size_t
  81 tm_length(const treemap *t)
  82 {
  83         return t ? _tm_length(t->root, t->bottom) : 0;
  84 }
  85
  86 bool
  87 tm_is_empty(const treemap *t)
  88 {
  89         return tm_length(t) == 0;
  90 }
  91
  92 static void *
  93 _tm_at(const treemap *t, const struct tm_node *n, const void *key)
  94 {
  95         if (n == t->bottom)
  96                 return NULL;
  97         int x = t->cmp(n->pair->k, key, t->cmp_aux);
  98         if (x == 0)
  99                 return n->pair->v;
 100         else if (x < 0)
 101                 return _tm_at(t, n->left, key);
 102         return _tm_at(t, n->right, key);
 103 }
 104
 105 void *
 106 tm_at(const treemap *t, const void *key)
 107 {
 108         return t ? _tm_at(t, t->root, key) : NULL;
 109 }
 110
 111 static struct tm_node *
 112 _tm_skew(struct tm_node *n) {
 113    if (n->level != n->left->level)
 114            return n;
 115    struct tm_node *left = n->left;
 116    n->left = left->right;
 117    left->right = n;
 118    n = left;
 119    return n;
 120 }
 121
 122 static struct tm_node *
 123 _tm_split(struct tm_node *n) {
 124    if(n->right->right->level != n->level)
 125            return n;
 126    struct tm_node *right = n->right;
 127    n->right = right->left;
 128    right->left = n;
 129    n = right;
 130    n->level++;
 131    return n;
 132 }
 133
 134 static struct tm_node *
 135 _tm_insert(treemap *t, struct tm_node *n, struct tm_node *prealloc)
 136 {
 137         if (n == t->bottom)
 138                 return prealloc;
 139         int x = t->cmp(n->pair->k, prealloc->pair->k, t->cmp_aux);
 140         if (x < 0)
 141                 n->left = _tm_insert(t, n->left, prealloc);
 142         else if (x > 0)
 143                 n->right = _tm_insert(t, n->right, prealloc);
 144         else
 145         {
 146                 // TODO: free the right stuff in prealloc
 147                 return n;
 148         }
 149         return _tm_split(_tm_skew(n));
 150 }
 151
 152 bool
 153 tm_insert(treemap *t, void *key, void *val)
 154 {
 155         if (!t)
 156                 return false;
 157         /* attempt the malloc before potentially splitting
 158          * and skewing the tree, so the insertion can be a
 159          * no-op on failure */
 160         struct tm_node *prealloc = malloc(sizeof *prealloc);
 161         struct map_pair *p = malloc(sizeof *p);
 162         if (!prealloc || !p)
 163         {
 164                 free(prealloc);
 165                 free(p);
 166                 return false;
 167         }
 168         *p = (struct map_pair){.k = key, .v = val};
 169         *prealloc = (struct tm_node){
 170                 .level = 1, .pair = p, .left = t->bottom, .right = t->bottom
 171         };
 172
 173         return _tm_insert(t, t->root, prealloc);
 174 }
 175
 176 bool
 177 tm_remove(treemap *t, void *key)
 178 {
 179
 180 }
 181
 182 void
 183 tm_clear(treemap *t)
 184 {
 185
 186 }