synfig-osx/trunk/launcher/x-hash.c

   1 /* x-hash.c - basic hash tables
   2    $Id: x-hash.c,v 1.7 2003/07/17 05:25:44 jharper Exp $
   3
   4    Copyright (c) 2002 Apple Computer, Inc. All rights reserved.
   5
   6    Permission is hereby granted, free of charge, to any person
   7    obtaining a copy of this software and associated documentation files
   8    (the "Software"), to deal in the Software without restriction,
   9    including without limitation the rights to use, copy, modify, merge,
  10    publish, distribute, sublicense, and/or sell copies of the Software,
  11    and to permit persons to whom the Software is furnished to do so,
  12    subject to the following conditions:
  13
  14    The above copyright notice and this permission notice shall be
  15    included in all copies or substantial portions of the Software.
  16
  17    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  20    NONINFRINGEMENT.  IN NO EVENT SHALL THE ABOVE LISTED COPYRIGHT
  21    HOLDER(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  22    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  23    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  24    DEALINGS IN THE SOFTWARE.
  25
  26    Except as contained in this notice, the name(s) of the above
  27    copyright holders shall not be used in advertising or otherwise to
  28    promote the sale, use or other dealings in this Software without
  29    prior written authorization. */
  30
  31 #include "x-hash.h"
  32 #include "x-list.h"
  33 #include <stdlib.h>
  34 #include <assert.h>
  35
  36 struct x_hash_table_struct {
  37     unsigned int bucket_index;
  38     unsigned int total_keys;
  39     x_list **buckets;
  40
  41     x_hash_fun *hash_key;
  42     x_compare_fun *compare_keys;
  43     x_destroy_fun *destroy_key;
  44     x_destroy_fun *destroy_value;
  45 };
  46
  47 #define ITEM_NEW(k, v) X_PFX (list_prepend) ((x_list *) (k), v)
  48 #define ITEM_FREE(i) X_PFX (list_free_1) (i)
  49 #define ITEM_KEY(i) ((void *) (i)->next)
  50 #define ITEM_VALUE(i) ((i)->data)
  51
  52 #define SPLIT_THRESHOLD_FACTOR 2
  53
  54 /* http://planetmath.org/?op=getobj&from=objects&name=GoodHashTablePrimes */
  55 static const unsigned int bucket_sizes[] = {
  56     29, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157,
  57     98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917,
  58     25165843, 50331653, 100663319, 201326611, 402653189, 805306457,
  59     1610612741
  60 };
  61
  62 #define N_BUCKET_SIZES (sizeof (bucket_sizes) / sizeof (bucket_sizes[0]))
  63
  64 static inline unsigned int
  65 hash_table_total_buckets (x_hash_table *h)
  66 {
  67     return bucket_sizes[h->bucket_index];
  68 }
  69
  70 static inline void
  71 hash_table_destroy_item (x_hash_table *h, void *k, void *v)
  72 {
  73     if (h->destroy_key != 0)
  74         (*h->destroy_key) (k);
  75
  76     if (h->destroy_value != 0)
  77         (*h->destroy_value) (v);
  78 }
  79
  80 static inline unsigned int
  81 hash_table_hash_key (x_hash_table *h, void *k)
  82 {
  83     if (h->hash_key != 0)
  84         return (*h->hash_key) (k);
  85     else
  86         return (unsigned int) k;
  87 }
  88
  89 static inline int
  90 hash_table_compare_keys (x_hash_table *h, void *k1, void *k2)
  91 {
  92     if (h->compare_keys == 0)
  93         return k1 == k2;
  94     else
  95         return (*h->compare_keys) (k1, k2) == 0;
  96 }
  97
  98 static void
  99 hash_table_split (x_hash_table *h)
 100 {
 101     x_list **new, **old;
 102     x_list *node, *item, *next;
 103     int new_size, old_size;
 104     unsigned int b;
 105     int i;
 106
 107     if (h->bucket_index == N_BUCKET_SIZES - 1)
 108         return;
 109
 110     old_size = hash_table_total_buckets (h);
 111     old = h->buckets;
 112
 113     h->bucket_index++;
 114
 115     new_size = hash_table_total_buckets (h);
 116     new = calloc (new_size, sizeof (x_list *));
 117
 118     if (new == 0)
 119     {
 120         h->bucket_index--;
 121         return;
 122     }
 123
 124     for (i = 0; i < old_size; i++)
 125     {
 126         for (node = old[i]; node != 0; node = next)
 127         {
 128             next = node->next;
 129             item = node->data;
 130
 131             b = hash_table_hash_key (h, ITEM_KEY (item)) % new_size;
 132
 133             node->next = new[b];
 134             new[b] = node;
 135         }
 136     }
 137
 138     h->buckets = new;
 139     free (old);
 140 }
 141
 142 X_EXTERN x_hash_table *
 143 X_PFX (hash_table_new) (x_hash_fun *hash,
 144                         x_compare_fun *compare,
 145                         x_destroy_fun *key_destroy,
 146                         x_destroy_fun *value_destroy)
 147 {
 148     x_hash_table *h;
 149
 150     h = calloc (1, sizeof (x_hash_table));
 151     if (h == 0)
 152         return 0;
 153
 154     h->bucket_index = 0;
 155     h->buckets = calloc (hash_table_total_buckets (h), sizeof (x_list *));
 156
 157     if (h->buckets == 0)
 158     {
 159         free (h);
 160         return 0;
 161     }
 162
 163     h->hash_key = hash;
 164     h->compare_keys = compare;
 165     h->destroy_key = key_destroy;
 166     h->destroy_value = value_destroy;
 167
 168     return h;
 169 }
 170
 171 X_EXTERN void
 172 X_PFX (hash_table_free) (x_hash_table *h)
 173 {
 174     int n, i;
 175     x_list *node, *item;
 176
 177     assert (h != NULL);
 178
 179     n = hash_table_total_buckets (h);
 180
 181     for (i = 0; i < n; i++)
 182     {
 183         for (node = h->buckets[i]; node != 0; node = node->next)
 184         {
 185             item = node->data;
 186             hash_table_destroy_item (h, ITEM_KEY (item), ITEM_VALUE (item));
 187             ITEM_FREE (item);
 188         }
 189         X_PFX (list_free) (h->buckets[i]);
 190     }
 191
 192     free (h->buckets);
 193     free (h);
 194 }
 195
 196 X_EXTERN unsigned int
 197 X_PFX (hash_table_size) (x_hash_table *h)
 198 {
 199     assert (h != NULL);
 200
 201     return h->total_keys;
 202 }
 203
 204 static void
 205 hash_table_modify (x_hash_table *h, void *k, void *v, int replace)
 206 {
 207     unsigned int hash_value;
 208     x_list *node, *item;
 209
 210     assert (h != NULL);
 211
 212     hash_value = hash_table_hash_key (h, k);
 213
 214     for (node = h->buckets[hash_value % hash_table_total_buckets (h)];
 215          node != 0; node = node->next)
 216     {
 217         item = node->data;
 218
 219         if (hash_table_compare_keys (h, ITEM_KEY (item), k))
 220         {
 221             if (replace)
 222             {
 223                 hash_table_destroy_item (h, ITEM_KEY (item),
 224                                          ITEM_VALUE (item));
 225                 ITEM_KEY (item) = k;
 226                 ITEM_VALUE (item) = v;
 227             }
 228             else
 229             {
 230                 hash_table_destroy_item (h, k, ITEM_VALUE (item));
 231                 ITEM_VALUE (item) = v;
 232             }
 233             return;
 234         }
 235     }
 236
 237     /* Key isn't already in the table. Insert it. */
 238
 239     if (h->total_keys + 1
 240         > hash_table_total_buckets (h) * SPLIT_THRESHOLD_FACTOR)
 241     {
 242         hash_table_split (h);
 243     }
 244
 245     hash_value = hash_value % hash_table_total_buckets (h);
 246     h->buckets[hash_value] = X_PFX (list_prepend) (h->buckets[hash_value],
 247                                                    ITEM_NEW (k, v));
 248     h->total_keys++;
 249 }
 250
 251 X_EXTERN void
 252 X_PFX (hash_table_insert) (x_hash_table *h, void *k, void *v)
 253 {
 254     hash_table_modify (h, k, v, 0);
 255 }
 256
 257 X_EXTERN void
 258 X_PFX (hash_table_replace) (x_hash_table *h, void *k, void *v)
 259 {
 260     hash_table_modify (h, k, v, 1);
 261 }
 262
 263 X_EXTERN void
 264 X_PFX (hash_table_remove) (x_hash_table *h, void *k)
 265 {
 266     unsigned int hash_value;
 267     x_list **ptr, *item;
 268
 269     assert (h != NULL);
 270
 271     hash_value = hash_table_hash_key (h, k);
 272
 273     for (ptr = &h->buckets[hash_value % hash_table_total_buckets (h)];
 274          *ptr != 0; ptr = &((*ptr)->next))
 275     {
 276         item = (*ptr)->data;
 277
 278         if (hash_table_compare_keys (h, ITEM_KEY (item), k))
 279         {
 280             hash_table_destroy_item (h, ITEM_KEY (item), ITEM_VALUE (item));
 281             ITEM_FREE (item);
 282             item = *ptr;
 283             *ptr = item->next;
 284             X_PFX (list_free_1) (item);
 285             h->total_keys--;
 286             return;
 287         }
 288     }
 289 }
 290
 291 X_EXTERN void *
 292 X_PFX (hash_table_lookup) (x_hash_table *h, void *k, void **k_ret)
 293 {
 294     unsigned int hash_value;
 295     x_list *node, *item;
 296
 297     assert (h != NULL);
 298
 299     hash_value = hash_table_hash_key (h, k);
 300
 301     for (node = h->buckets[hash_value % hash_table_total_buckets (h)];
 302          node != 0; node = node->next)
 303     {
 304         item = node->data;
 305
 306         if (hash_table_compare_keys (h, ITEM_KEY (item), k))
 307         {
 308             if (k_ret != 0)
 309                 *k_ret = ITEM_KEY (item);
 310
 311             return ITEM_VALUE (item);
 312         }
 313     }
 314
 315     if (k_ret != 0)
 316         *k_ret = 0;
 317
 318     return 0;
 319 }
 320
 321 X_EXTERN void
 322 X_PFX (hash_table_foreach) (x_hash_table *h,
 323                             x_hash_foreach_fun *fun, void *data)
 324 {
 325     int i, n;
 326     x_list *node, *item;
 327
 328     assert (h != NULL);
 329
 330     n = hash_table_total_buckets (h);
 331
 332     for (i = 0; i < n; i++)
 333     {
 334         for (node = h->buckets[i]; node != 0; node = node->next)
 335         {
 336             item = node->data;
 337             (*fun) (ITEM_KEY (item), ITEM_VALUE (item), data);
 338         }
 339     }
 340 }