CEP/C/mod_aa.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 #include "misc.h"
   5 #include "module.h"
   6 #include "mod_aa.h"
   7
   8 struct node {
   9         void *data;
  10         int level;
  11         struct node *left;
  12         struct node *right;
  13 };
  14
  15 struct aa_tree {
  16         int size;
  17         struct node *root;
  18         int (*compare)(const void *key1, const void *key2);
  19         void (*destroy)(void *data);
  20         void (*dump)(const void *data);
  21 };
  22
  23 static struct aa_tree cep_aa_tree;
  24
  25 static struct node *aa_node_alloc(void *data)
  26 {
  27         struct node *new;
  28
  29         new = malloc(sizeof(*new));
  30         if (!new)
  31                 fatal("Could not allocate memory");
  32
  33         new->data = data;
  34         new->left = new->right = NULL;
  35         new->level = 1;
  36
  37         return new;
  38 }
  39
  40 static struct node *skew(struct node *node)
  41 {
  42         struct node *left;
  43
  44         if (!node || !node->left || !node->left->right)
  45                 goto out;
  46
  47         if (node->left->level == node->level) {
  48                 /*
  49                  * Swap the pointers of horizontal left
  50                  * links.
  51                  */
  52
  53                 left = node->left;
  54                 node->left = left->right;
  55                 left->right = node;
  56
  57                 return left;
  58         }
  59
  60 out:
  61         return node;
  62 }
  63
  64 static struct node *split(struct node *node)
  65 {
  66         struct node *right;
  67
  68         if (!node || !node->right ||
  69             !node->right->right || !node->right->left)
  70                 goto out;
  71
  72         if (node->level == node->right->right->level) {
  73                 /*
  74                  * We have three horizontal right links.
  75                  * Take the middle element, elevate it, and return
  76                  * that.
  77                  */
  78
  79                 right = node->right;
  80                 node->right = right->left;
  81                 right->left = node;
  82                 right->level++;
  83
  84                 return right;
  85         }
  86
  87 out:
  88         return node;
  89 }
  90
  91 static struct node *__aa_insert(void *data, struct node *node)
  92 {
  93         int cmpval;
  94
  95         if (!node)
  96                 return aa_node_alloc(data);
  97
  98         cmpval = cep_aa_tree.compare(data, node->data);
  99         if (cmpval < 0) {
 100                 /* move to the left */
 101                 node->left = __aa_insert(data, node->left);
 102         } else if (cmpval > 0) {
 103                 /* move to the right */
 104                 node->right = __aa_insert(data, node->right);
 105         } else {
 106                 /* duplicated, just ignore it */
 107                 goto out;
 108         }
 109
 110         node = skew(node);
 111         node = split(node);
 112
 113 out:
 114         return node;
 115 }
 116
 117 static void aa_insert(void *data)
 118 {
 119         cep_aa_tree.root = __aa_insert(data, cep_aa_tree.root);
 120         cep_aa_tree.size++;
 121 }
 122
 123 static void *lookup(const void *data, struct node *node)
 124 {
 125         void *ret;
 126         int cmpval;
 127
 128         if (!node) {
 129                 /* not found */
 130                 return NULL;
 131         }
 132
 133         cmpval = cep_aa_tree.compare(data, node->data);
 134         if (cmpval < 0) {
 135                 /* move to the left */
 136                 ret = lookup(data, node->left);
 137         } else if (cmpval > 0) {
 138                 /* move to the right */
 139                 ret = lookup(data, node->right);
 140         } else {
 141                 /* found */
 142                 ret = node->data;
 143         }
 144
 145         return ret;
 146 }
 147
 148 static void *aa_lookup(const void *data)
 149 {
 150         return lookup(data, cep_aa_tree.root);
 151 }
 152
 153 static void aa_init(int (*compare)(const void *key1, const void *key2),
 154                     void (*destroy)(void *data),
 155                     void (*dump)(const void *data))
 156
 157 {
 158         cep_aa_tree.size = 0;
 159         cep_aa_tree.root = NULL;
 160         cep_aa_tree.compare = compare;
 161         cep_aa_tree.destroy = destroy;
 162         cep_aa_tree.dump  = dump;
 163 }
 164
 165 static size_t aa_size(void)
 166 {
 167         return cep_aa_tree.size;
 168 }
 169
 170 static void dump(struct node *node)
 171 {
 172         if (!node)
 173                 return;
 174
 175         dump(node->left);
 176
 177         cep_aa_tree.dump(node->data);
 178
 179         dump(node->right);
 180 }
 181
 182 static void aa_dump(void)
 183 {
 184         dump(cep_aa_tree.root);
 185 }
 186
 187 static void destroy(struct node *node)
 188 {
 189         if (!node)
 190                 return;
 191
 192         destroy(node->left);
 193         destroy(node->right);
 194
 195         cep_aa_tree.destroy(node->data);
 196         free(node);
 197 }
 198
 199 static void aa_destroy(void)
 200 {
 201         destroy(cep_aa_tree.root);
 202 }
 203
 204 struct module aa_module = {
 205         .mod_name    = "AA TREE",
 206         .mod_init    = aa_init,
 207         .mod_destroy = aa_destroy,
 208         .mod_insert  = aa_insert,
 209         .mod_lookup  = aa_lookup,
 210         .mod_dump    = aa_dump,
 211         .mod_size    = aa_size,
 212 };