xorg-server-1.4/hw/darwin/quartz/xpr/x-hash.c

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