wayland/wayland-hash.c

   1 /*
   2  * Copyright © 2009 Intel Corporation
   3  * Copyright © 1988-2004 Keith Packard and Bart Massey.
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice (including the next
  13  * paragraph) shall be included in all copies or substantial portions of the
  14  * Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  19  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  22  * IN THE SOFTWARE.
  23  *
  24  * Except as contained in this notice, the names of the authors
  25  * or their institutions shall not be used in advertising or
  26  * otherwise to promote the sale, use or other dealings in this
  27  * Software without prior written authorization from the
  28  * authors.
  29  *
  30  * Authors:
  31  *    Eric Anholt <eric@anholt.net>
  32  *    Keith Packard <keithp@keithp.com>
  33  */
  34
  35 #include <stdlib.h>
  36
  37 #include "wayland-util.h"
  38
  39 struct hash_entry {
  40         uint32_t hash;
  41         void *data;
  42 };
  43
  44 struct wl_hash_table {
  45         struct hash_entry *table;
  46         uint32_t size;
  47         uint32_t rehash;
  48         uint32_t max_entries;
  49         uint32_t size_index;
  50         uint32_t entries;
  51         uint32_t deleted_entries;
  52 };
  53
  54 #define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0]))
  55
  56 /*
  57  * From Knuth -- a good choice for hash/rehash values is p, p-2 where
  58  * p and p-2 are both prime.  These tables are sized to have an extra 10%
  59  * free to avoid exponential performance degradation as the hash table fills
  60  */
  61
  62 static const uint32_t deleted_data;
  63
  64 static const struct {
  65    uint32_t max_entries, size, rehash;
  66 } hash_sizes[] = {
  67     { 2,                5,              3         },
  68     { 4,                7,              5         },
  69     { 8,                13,             11        },
  70     { 16,               19,             17        },
  71     { 32,               43,             41        },
  72     { 64,               73,             71        },
  73     { 128,              151,            149       },
  74     { 256,              283,            281       },
  75     { 512,              571,            569       },
  76     { 1024,             1153,           1151      },
  77     { 2048,             2269,           2267      },
  78     { 4096,             4519,           4517      },
  79     { 8192,             9013,           9011      },
  80     { 16384,            18043,          18041     },
  81     { 32768,            36109,          36107     },
  82     { 65536,            72091,          72089     },
  83     { 131072,           144409,         144407    },
  84     { 262144,           288361,         288359    },
  85     { 524288,           576883,         576881    },
  86     { 1048576,          1153459,        1153457   },
  87     { 2097152,          2307163,        2307161   },
  88     { 4194304,          4613893,        4613891   },
  89     { 8388608,          9227641,        9227639   },
  90     { 16777216,         18455029,       18455027  },
  91     { 33554432,         36911011,       36911009  },
  92     { 67108864,         73819861,       73819859  },
  93     { 134217728,        147639589,      147639587 },
  94     { 268435456,        295279081,      295279079 },
  95     { 536870912,        590559793,      590559791 },
  96     { 1073741824,       1181116273,     1181116271},
  97     { 2147483648ul,     2362232233ul,   2362232231ul}
  98 };
  99
 100 static int
 101 entry_is_free(struct hash_entry *entry)
 102 {
 103         return entry->data == NULL;
 104 }
 105
 106 static int
 107 entry_is_deleted(struct hash_entry *entry)
 108 {
 109         return entry->data == &deleted_data;
 110 }
 111
 112 static int
 113 entry_is_present(struct hash_entry *entry)
 114 {
 115         return entry->data != NULL && entry->data != &deleted_data;
 116 }
 117
 118 WL_EXPORT struct wl_hash_table *
 119 wl_hash_table_create(void)
 120 {
 121         struct wl_hash_table *ht;
 122
 123         ht = malloc(sizeof(*ht));
 124         if (ht == NULL)
 125                 return NULL;
 126
 127         ht->size_index = 0;
 128         ht->size = hash_sizes[ht->size_index].size;
 129         ht->rehash = hash_sizes[ht->size_index].rehash;
 130         ht->max_entries = hash_sizes[ht->size_index].max_entries;
 131         ht->table = calloc(ht->size, sizeof(*ht->table));
 132         ht->entries = 0;
 133         ht->deleted_entries = 0;
 134
 135         if (ht->table == NULL) {
 136                 free(ht);
 137                 return NULL;
 138         }
 139
 140         return ht;
 141 }
 142
 143 /**
 144  * Frees the given hash table.
 145  */
 146 WL_EXPORT void
 147 wl_hash_table_destroy(struct wl_hash_table *ht)
 148 {
 149         if (!ht)
 150                 return;
 151
 152         free(ht->table);
 153         free(ht);
 154 }
 155
 156 /**
 157  * Finds a hash table entry with the given key and hash of that key.
 158  *
 159  * Returns NULL if no entry is found.  Note that the data pointer may be
 160  * modified by the user.
 161  */
 162 static void *
 163 hash_table_search(struct wl_hash_table *ht, uint32_t hash)
 164 {
 165         uint32_t hash_address;
 166
 167         hash_address = hash % ht->size;
 168         do {
 169                 uint32_t double_hash;
 170
 171                 struct hash_entry *entry = ht->table + hash_address;
 172
 173                 if (entry_is_free(entry)) {
 174                         return NULL;
 175                 } else if (entry_is_present(entry) && entry->hash == hash) {
 176                         return entry;
 177                 }
 178
 179                 double_hash = hash % ht->rehash;
 180                 if (double_hash == 0)
 181                         double_hash = 1;
 182
 183                 hash_address = (hash_address + double_hash) % ht->size;
 184         } while (hash_address != hash % ht->size);
 185
 186         return NULL;
 187 }
 188
 189 WL_EXPORT void *
 190 wl_hash_table_lookup(struct wl_hash_table *ht, uint32_t hash)
 191 {
 192         struct hash_entry *entry;
 193
 194         entry = hash_table_search(ht, hash);
 195         if (entry != NULL)
 196                 return entry->data;
 197
 198         return NULL;
 199 }
 200
 201 static void
 202 hash_table_rehash(struct wl_hash_table *ht, int new_size_index)
 203 {
 204         struct wl_hash_table old_ht;
 205         struct hash_entry *table, *entry;
 206
 207         if (new_size_index >= ARRAY_SIZE(hash_sizes))
 208                 return;
 209
 210         table = calloc(hash_sizes[new_size_index].size, sizeof(*ht->table));
 211         if (table == NULL)
 212                 return;
 213
 214         old_ht = *ht;
 215
 216         ht->table = table;
 217         ht->size_index = new_size_index;
 218         ht->size = hash_sizes[ht->size_index].size;
 219         ht->rehash = hash_sizes[ht->size_index].rehash;
 220         ht->max_entries = hash_sizes[ht->size_index].max_entries;
 221         ht->entries = 0;
 222         ht->deleted_entries = 0;
 223
 224         for (entry = old_ht.table;
 225              entry != old_ht.table + old_ht.size;
 226              entry++) {
 227                 if (entry_is_present(entry)) {
 228                         wl_hash_table_insert(ht, entry->hash, entry->data);
 229                 }
 230         }
 231
 232         free(old_ht.table);
 233 }
 234
 235 /**
 236  * Inserts the data with the given hash into the table.
 237  *
 238  * Note that insertion may rearrange the table on a resize or rehash,
 239  * so previously found hash_entries are no longer valid after this function.
 240  */
 241 WL_EXPORT int
 242 wl_hash_table_insert(struct wl_hash_table *ht, uint32_t hash, void *data)
 243 {
 244         uint32_t hash_address;
 245
 246         if (ht->entries >= ht->max_entries) {
 247                 hash_table_rehash(ht, ht->size_index + 1);
 248         } else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
 249                 hash_table_rehash(ht, ht->size_index);
 250         }
 251
 252         hash_address = hash % ht->size;
 253         do {
 254                 struct hash_entry *entry = ht->table + hash_address;
 255                 uint32_t double_hash;
 256
 257                 if (!entry_is_present(entry)) {
 258                         if (entry_is_deleted(entry))
 259                                 ht->deleted_entries--;
 260                         entry->hash = hash;
 261                         entry->data = data;
 262                         ht->entries++;
 263                         return 0;
 264                 }
 265
 266                 double_hash = hash % ht->rehash;
 267                 if (double_hash == 0)
 268                         double_hash = 1;
 269
 270                 hash_address = (hash_address + double_hash) % ht->size;
 271         } while (hash_address != hash % ht->size);
 272
 273         /* We could hit here if a required resize failed. An unchecked-malloc
 274          * application could ignore this result.
 275          */
 276         return -1;
 277 }
 278
 279 /**
 280  * This function deletes the given hash table entry.
 281  *
 282  * Note that deletion doesn't otherwise modify the table, so an iteration over
 283  * the table deleting entries is safe.
 284  */
 285 WL_EXPORT void
 286 wl_hash_table_remove(struct wl_hash_table *ht, uint32_t hash)
 287 {
 288         struct hash_entry *entry;
 289
 290         entry = hash_table_search(ht, hash);
 291         if (entry != NULL) {
 292                 entry->data = (void *) &deleted_data;
 293                 ht->entries--;
 294                 ht->deleted_entries++;
 295         }
 296 }