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

   1 #include "treemap.h"
   2
   3 #include <stdlib.h>
   4
   5 enum color { RED, BLACK };
   6
   7 struct tm_node
   8 {
   9         struct tm_node *left, *right, *parent;
  10         enum color color;
  11         struct map_pair *pair;
  12 };
  13
  14 struct treemap
  15 {
  16         struct tm_node *root;
  17
  18         dtor *key_dtor;
  19         dtor *val_dtor;
  20         comparator *cmp;
  21         void *cmp_aux;
  22         void *dtor_aux;
  23 };
  24
  25 treemap *
  26 tm_new(comparator *cmp, void *cmp_aux)
  27 {
  28         treemap *t = malloc(sizeof *t);
  29         if (!t)
  30                 return NULL;
  31         *t = (treemap){
  32                 .cmp = cmp,
  33                 .cmp_aux = cmp_aux
  34         };
  35         return t;
  36 }
  37
  38 void
  39 tm_free(treemap *t)
  40 {
  41
  42 }
  43
  44 void
  45 tm_dtor(treemap *t, dtor *key_dtor, dtor *val_dtor, void *dtor_aux)
  46 {
  47         if (!t)
  48                 return;
  49         t->key_dtor = key_dtor;
  50         t->val_dtor = val_dtor;
  51         t->dtor_aux = dtor_aux;
  52 }
  53
  54 static size_t
  55 _tm_length(const struct tm_node *n)
  56 {
  57         if (!n)
  58                 return 0;
  59         return 1 + _tm_length(n->left) + _tm_length(n->right);
  60 }
  61
  62 size_t
  63 tm_length(const treemap *t)
  64 {
  65         return t ? _tm_length(t->root) : 0;
  66 }
  67
  68 bool
  69 tm_is_empty(const treemap *t)
  70 {
  71         return tm_length(t) == 0;
  72 }
  73
  74 static void *
  75 _tm_at(const treemap *t, const struct tm_node *n, const void *key)
  76 {
  77         if (!n)
  78                 return NULL;
  79         int x = t->cmp(n->pair->k, key, t->cmp_aux);
  80         if (x == 0)
  81                 return n->pair->v;
  82         else if (x < 0)
  83                 return _tm_at(t, n->left, key);
  84         return _tm_at(t, n->right, key);
  85 }
  86
  87 void *
  88 tm_at(const treemap *t, const void *key)
  89 {
  90         return t ? _tm_at(t, t->root, key) : NULL;
  91 }
  92
  93 static void
  94 _tm_left_rotate(treemap *t, struct tm_node *x)
  95 {
  96         struct tm_node *y = x->right;
  97         x->right = y->left;
  98         if (y->left)
  99                 y->left->parent = x;
 100         y->parent = x->parent;
 101         if (!x->parent)
 102                 t->root = y;
 103         else if (x == x->parent->left)
 104                 x->parent->left = y;
 105         else
 106                 x->parent->right = y;
 107         y->left = x;
 108         x->parent = y;
 109 }
 110
 111 static void
 112 _tm_right_rotate(treemap *t, struct tm_node *x)
 113 {
 114         struct tm_node *y = x->left;
 115         x->left = y->right;
 116         if (y->right)
 117                 y->right->parent = x;
 118         y->parent = x->parent;
 119         if (!x->parent)
 120                 t->root = y;
 121         else if (x == x->parent->right)
 122                 x->parent->right = y;
 123         else
 124                 x->parent->left = y;
 125         y->right = x;
 126         x->parent = y;
 127 }
 128
 129 static struct tm_node *
 130 _tm_insert(treemap *t, void *key, void *val)
 131 {
 132         struct tm_node *parent = NULL, *cursor = t->root;
 133         while (cursor)
 134         {
 135                 parent = cursor;
 136                 int diff = t->cmp(key, cursor->pair->k, t->cmp_aux);
 137                 if (diff == 0)
 138                 {
 139                         if (val != cursor->pair->v && t->val_dtor)
 140                                 t->val_dtor(cursor->pair->v, t->dtor_aux);
 141                         cursor->pair->v = val;
 142                         return cursor;
 143                 }
 144                 else if (diff < 0)
 145                         cursor = cursor->left;
 146                 else
 147                         cursor = cursor->right;
 148         }
 149
 150         struct map_pair *p = malloc(sizeof *p);
 151         struct tm_node *node = malloc(sizeof *node);
 152         if (!p || !node)
 153         {
 154                 free(p);
 155                 free(node);
 156                 return NULL;
 157         }
 158         *p = (struct map_pair){
 159                 .k = key, .v = val
 160         };
 161         *node = (struct tm_node){
 162                 .color = RED, .parent = parent, .pair = p
 163         };
 164         if (!parent)
 165                 t->root = node;
 166         else if (t->cmp(key, parent->pair->k, t->cmp_aux))
 167                 parent->left = node;
 168         else
 169                 parent->right = node;
 170         return node;
 171 }
 172
 173 static void
 174 _tm_insert_fixup(treemap *t, struct tm_node *x)
 175 {
 176         struct tm_node *uncle;
 177         while (x->parent && x->parent->color == RED)
 178         {
 179                 if (x->parent->parent->left == x->parent)
 180                 {
 181                         uncle = x->parent->parent->right;
 182                         if (uncle->color == RED)
 183                         {
 184                                 x->parent->parent->color = RED;
 185                                 x->parent->color = BLACK;
 186                                 uncle->color     = BLACK;
 187                                 x = x->parent->parent;
 188                         }
 189                         else
 190                         {
 191                                 if (x == x->parent->right)
 192                                 {
 193                                         x = x->parent;
 194                                         _tm_left_rotate(t, x);
 195                                 }
 196                                 x->parent->color = BLACK;
 197                                 x->parent->parent->color = RED;
 198                                 _tm_right_rotate(t, x->parent->parent);
 199                         }
 200                 }
 201                 else
 202                 {
 203                         uncle = x->parent->parent->left;
 204                         if (uncle->color == RED)
 205                         {
 206                                 x->parent->parent->color = RED;
 207                                 x->parent->color = BLACK;
 208                                 uncle->color     = BLACK;
 209                                 x = x->parent->parent;
 210                         }
 211                         else
 212                         {
 213                                 if (x == x->parent->left)
 214                                 {
 215                                         x = x->parent;
 216                                         _tm_right_rotate(t, x);
 217                                 }
 218                                 x->parent->color = BLACK;
 219                                 x->parent->parent->color = RED;
 220                                 _tm_left_rotate(t, x->parent->parent);
 221                         }
 222                 }
 223         }
 224         t->root->color = BLACK;
 225 }
 226
 227 bool
 228 tm_insert(treemap *t, void *key, void *val)
 229 {
 230         struct tm_node *n = _tm_insert(t, key, val);
 231         if (!n)
 232                 return false;
 233         _tm_insert_fixup(t, n);
 234         return true;
 235 }
 236
 237 bool
 238 tm_remove(treemap *t, void *key)
 239 {
 240
 241 }
 242
 243 void
 244 tm_clear(treemap *t)
 245 {
 246
 247 }