src/dict-splay.c

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