src/dict-splay.c

   1 /* dict-splay.c - Abstract dictionary type
   2  * Copyright 2000-2004 srvx Development Team
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.  Important limitations are
   8  * listed in the COPYING file that accompanies this software.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, email srvx-maintainers@srvx.net.
  17  */
  18
  19 #include "common.h"
  20 #include "dict.h"
  21
  22 /*
  23  *    Create new dictionary.
  24  */
  25 dict_t
  26 dict_new(void)
  27 {
  28     dict_t dict = calloc(1, sizeof(*dict));
  29     return dict;
  30 }
  31
  32 /*
  33  *    Return number of entries in the dictionary.
  34  */
  35 unsigned int
  36 dict_size(dict_t dict)
  37 {
  38     return dict->count;
  39 }
  40
  41 /*
  42  *    Set the function to be called when freeing a key structure.
  43  *    If the function is NULL, just forget about the pointer.
  44  */
  45 void
  46 dict_set_free_keys(dict_t dict, free_f free_keys)
  47 {
  48     dict->free_keys = free_keys;
  49 }
  50
  51 /*
  52  *    Set the function to free data.
  53  * If the function is NULL, just forget about the pointer.
  54  */
  55 void
  56 dict_set_free_data(dict_t dict, free_f free_data)
  57 {
  58     dict->free_data = free_data;
  59 }
  60
  61 const char *
  62 dict_foreach(dict_t dict, dict_iterator_f it_f, void *extra)
  63 {
  64     dict_iterator_t it;
  65
  66     for (it=dict_first(dict); it; it=iter_next(it)) {
  67         if (it_f(iter_key(it), iter_data(it), extra)) return iter_key(it);
  68     }
  69     return NULL;
  70 }
  71
  72 /*
  73  *   This function finds a node and pulls it to the top of the tree.
  74  *   This helps balance the tree and auto-cache things you search for.
  75  */
  76 static struct dict_node*
  77 dict_splay(struct dict_node *node, const char *key)
  78 {
  79     struct dict_node N, *l, *r, *y;
  80     if (!node) return NULL;
  81     N.l = N.r = NULL;
  82     l = r = &N;
  83
  84     while (1) {
  85         int res = irccasecmp(key, node->key);
  86         if (!res) break;
  87         if (res < 0) {
  88             if (!node->l) break;
  89             res = irccasecmp(key, node->l->key);
  90             if (res < 0) {
  91                 y = node->l;
  92                 node->l = y->r;
  93                 y->r = node;
  94                 node = y;
  95                 if (!node->l) break;
  96             }
  97             r->l = node;
  98             r = node;
  99             node = node->l;
 100         } else { /* res > 0 */
 101             if (!node->r) break;
 102             res = irccasecmp(key, node->r->key);
 103             if (res > 0) {
 104                 y = node->r;
 105                 node->r = y->l;
 106                 y->l = node;
 107                 node = y;
 108                 if (!node->r) break;
 109             }
 110             l->r = node;
 111             l = node;
 112             node = node->r;
 113         }
 114     }
 115     l->r = node->l;
 116     r->l = node->r;
 117     node->l = N.r;
 118     node->r = N.l;
 119     return node;
 120 }
 121
 122 /*
 123  *    Free node.  Free data/key using free_f functions.
 124  */
 125 static void
 126 dict_dispose_node(struct dict_node *node, free_f free_keys, free_f free_data)
 127 {
 128     if (free_keys && node->key)
 129         free_keys((void*)node->key);
 130     if (free_data && node->data)
 131         free_data(node->data);
 132     free(node);
 133 }
 134
 135 /*
 136  *    Insert an entry into the dictionary.
 137  *    Key ordering (and uniqueness) is determined by case-insensitive
 138  *    string comparison.
 139  */
 140 void
 141 dict_insert(dict_t dict, const char *key, void *data)
 142 {
 143     struct dict_node *new_node;
 144     if (!key)
 145         return;
 146     new_node = malloc(sizeof(struct dict_node));
 147     new_node->key = key;
 148     new_node->data = data;
 149     if (dict->root) {
 150         int res;
 151         dict->root = dict_splay(dict->root, key);
 152         res = irccasecmp(key, dict->root->key);
 153         if (res < 0) {
 154             /* insert just "before" current root */
 155             new_node->l = dict->root->l;
 156             new_node->r = dict->root;
 157             dict->root->l = NULL;
 158             if (dict->root->prev) {
 159                 dict->root->prev->next = new_node;
 160             } else {
 161                 dict->first = new_node;
 162             }
 163             new_node->prev = dict->root->prev;
 164             new_node->next = dict->root;
 165             dict->root->prev = new_node;
 166             dict->root = new_node;
 167         } else if (res > 0) {
 168             /* insert just "after" current root */
 169             new_node->r = dict->root->r;
 170             new_node->l = dict->root;
 171             dict->root->r = NULL;
 172             if (dict->root->next) {
 173                 dict->root->next->prev = new_node;
 174             } else {
 175                 dict->last = new_node;
 176             }
 177             new_node->next = dict->root->next;
 178             new_node->prev = dict->root;
 179             dict->root->next = new_node;
 180             dict->root = new_node;
 181         } else {
 182             /* maybe we don't want to overwrite it .. oh well */
 183             if (dict->free_data) dict->free_data(dict->root->data);
 184             if (dict->free_keys) dict->free_keys((void*)dict->root->key);
 185             free(new_node);
 186             dict->root->key = key;
 187             dict->root->data = data;
 188             /* decrement the count since we dropped the node */
 189             dict->count--;
 190         }
 191     } else {
 192         new_node->l = new_node->r = NULL;
 193         new_node->next = new_node->prev = NULL;
 194         dict->root = dict->first = dict->last = new_node;
 195     }
 196     dict->count++;
 197 }
 198
 199 /*
 200  *    Remove an entry from the dictionary.
 201  *    Return non-zero if it was found, or zero if the key was not in the
 202  *    dictionary.
 203  */
 204 int
 205 dict_remove2(dict_t dict, const char *key, int no_dispose)
 206 {
 207     struct dict_node *new_root;
 208
 209     if (!dict->root)
 210         return 0;
 211     dict->root = dict_splay(dict->root, key);
 212     if (irccasecmp(key, dict->root->key))
 213         return 0;
 214
 215     if (!dict->root->l) {
 216         new_root = dict->root->r;
 217     } else {
 218         new_root = dict_splay(dict->root->l, key);
 219         new_root->r = dict->root->r;
 220     }
 221     if (dict->root->prev) dict->root->prev->next = dict->root->next;
 222     if (dict->first == dict->root) dict->first = dict->first->next;
 223     if (dict->root->next) dict->root->next->prev = dict->root->prev;
 224     if (dict->last == dict->root) dict->last = dict->last->prev;
 225     if (no_dispose) {
 226         free(dict->root);
 227     } else {
 228         dict_dispose_node(dict->root, dict->free_keys, dict->free_data);
 229     }
 230     dict->root = new_root;
 231     dict->count--;
 232     return 1;
 233 }
 234
 235 /*
 236  *    Find an entry in the dictionary.
 237  *    If "found" is non-NULL, set it to non-zero if the key was found.
 238  *    Return the data associated with the key (or NULL if the key was
 239  *    not found).
 240  */
 241 void*
 242 dict_find(dict_t dict, const char *key, int *found)
 243 {
 244     int was_found;
 245     if (!dict || !dict->root || !key) {
 246         if (found)
 247             *found = 0;
 248         return NULL;
 249     }
 250     dict->root = dict_splay(dict->root, key);
 251     was_found = !irccasecmp(key, dict->root->key);
 252     if (found)
 253         *found = was_found;
 254     return was_found ? dict->root->data : NULL;
 255 }
 256
 257 /*
 258  *    Delete an entire dictionary.
 259  */
 260 void
 261 dict_delete(dict_t dict)
 262 {
 263     dict_iterator_t it, next;
 264     if (!dict)
 265         return;
 266     for (it=dict_first(dict); it; it=next) {
 267         next = iter_next(it);
 268         dict_dispose_node(it, dict->free_keys, dict->free_data);
 269     }
 270     free(dict);
 271 }
 272
 273 struct dict_sanity_struct {
 274     unsigned int node_count;
 275     struct dict_node *bad_node;
 276     char error[128];
 277 };
 278
 279 static int
 280 dict_sanity_check_node(struct dict_node *node, struct dict_sanity_struct *dss)
 281 {
 282     if (!node->key) {
 283         snprintf(dss->error, sizeof(dss->error), "Node %p had null key", node);
 284         return 1;
 285     }
 286     if (node->l) {
 287         if (dict_sanity_check_node(node->l, dss)) return 1;
 288         if (irccasecmp(node->l->key, node->key) >= 0) {
 289             snprintf(dss->error, sizeof(dss->error), "Node %p's left child's key '%s' >= its key '%s'", node, node->l->key, node->key);
 290             return 1;
 291         }
 292     }
 293     if (node->r) {
 294         if (dict_sanity_check_node(node->r, dss)) return 1;
 295         if (irccasecmp(node->key, node->r->key) >= 0) {
 296             snprintf(dss->error, sizeof(dss->error), "Node %p's right child's key '%s' <= its key '%s'", node, node->r->key, node->key);
 297             return 1;
 298         }
 299     }
 300     dss->node_count++;
 301     return 0;
 302 }
 303
 304 /*
 305  *    Perform sanity checks on the dict's internal structure.
 306  */
 307 char *
 308 dict_sanity_check(dict_t dict)
 309 {
 310     struct dict_sanity_struct dss;
 311     dss.node_count = 0;
 312     dss.bad_node = 0;
 313     dss.error[0] = 0;
 314     if (dict->root && dict_sanity_check_node(dict->root, &dss)) {
 315         return strdup(dss.error);
 316     } else if (dss.node_count != dict->count) {
 317         snprintf(dss.error, sizeof(dss.error), "Counted %d nodes but expected %d.", dss.node_count, dict->count);
 318         return strdup(dss.error);
 319     } else {
 320         return 0;
 321     }
 322 }