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 static struct tm_node *
 177 _tm_remove(treemap *t, struct tm_node *n, void *key)
 178 {
 179         if (n == t->bottom)
 180                 return n;
 181         t->last = n;
 182         if (t->cmp(key, n->pair->k, t->cmp_aux) < 0)
 183                 n->left = _tm_remove(t, n->left, key);
 184         else
 185         {
 186                 t->deleted = n;
 187                 n->right = _tm_remove(t, n->right, key);
 188         }
 189
 190         if (n == t->last && t->deleted != t->bottom &&
 191             t->cmp(key, t->deleted->pair->k, t->cmp_aux) == 0)
 192         {
 193                 t->deleted->pair->k = n->pair->k;
 194                 t->deleted = t->bottom;
 195                 n = n->right;
 196                 // TODO: free t->last and its data
 197         } else if (n->left->level  < n->level-1 ||
 198                    n->right->level < n->level-1) {
 199                 n->level--;
 200                 if (n->right->level > n->level)
 201                         n->right->level = n->level;
 202                 n               = _tm_skew(n);
 203                 n->right        = _tm_skew(n->right);
 204                 n->right->right = _tm_skew(n->right->right);
 205                 n               = _tm_split(n);
 206                 n->right        = _tm_split(n->right);
 207         }
 208         return n;
 209 }
 210
 211 bool
 212 tm_remove(treemap *t, void *key)
 213 {
 214         if (!t)
 215                 return false;
 216         t->root = _tm_remove(t, t->root, key);
 217         return true; // TODO: return false if key wasn't found
 218 }
 219
 220 void
 221 tm_clear(treemap *t)
 222 {
 223
 224 }