src/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 #include <stdint.h>
  37
  38 #include "hash.h"
  39
  40 struct hash_entry {
  41         uint32_t hash;
  42         void *data;
  43 };
  44
  45 struct hash_table {
  46         struct hash_entry *table;
  47         uint32_t size;
  48         uint32_t rehash;
  49         uint32_t max_entries;
  50         uint32_t size_index;
  51         uint32_t entries;
  52         uint32_t deleted_entries;
  53 };
  54
  55 #define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0]))
  56
  57 /*
  58  * From Knuth -- a good choice for hash/rehash values is p, p-2 where
  59  * p and p-2 are both prime.  These tables are sized to have an extra 10%
  60  * free to avoid exponential performance degradation as the hash table fills
  61  */
  62
  63 static const uint32_t deleted_data;
  64
  65 static const struct {
  66    uint32_t max_entries, size, rehash;
  67 } hash_sizes[] = {
  68     { 2,                5,              3         },
  69     { 4,                7,              5         },
  70     { 8,                13,             11        },
  71     { 16,               19,             17        },
  72     { 32,               43,             41        },
  73     { 64,               73,             71        },
  74     { 128,              151,            149       },
  75     { 256,              283,            281       },
  76     { 512,              571,            569       },
  77     { 1024,             1153,           1151      },
  78     { 2048,             2269,           2267      },
  79     { 4096,             4519,           4517      },
  80     { 8192,             9013,           9011      },
  81     { 16384,            18043,          18041     },
  82     { 32768,            36109,          36107     },
  83     { 65536,            72091,          72089     },
  84     { 131072,           144409,         144407    },
  85     { 262144,           288361,         288359    },
  86     { 524288,           576883,         576881    },
  87     { 1048576,          1153459,        1153457   },
  88     { 2097152,          2307163,        2307161   },
  89     { 4194304,          4613893,        4613891   },
  90     { 8388608,          9227641,        9227639   },
  91     { 16777216,         18455029,       18455027  },
  92     { 33554432,         36911011,       36911009  },
  93     { 67108864,         73819861,       73819859  },
  94     { 134217728,        147639589,      147639587 },
  95     { 268435456,        295279081,      295279079 },
  96     { 536870912,        590559793,      590559791 },
  97     { 1073741824,       1181116273,     1181116271},
  98     { 2147483648ul,     2362232233ul,   2362232231ul}
  99 };
 100
 101 static int
 102 entry_is_free(struct hash_entry *entry)
 103 {
 104         return entry->data == NULL;
 105 }
 106
 107 static int
 108 entry_is_deleted(struct hash_entry *entry)
 109 {
 110         return entry->data == &deleted_data;
 111 }
 112
 113 static int
 114 entry_is_present(struct hash_entry *entry)
 115 {
 116         return entry->data != NULL && entry->data != &deleted_data;
 117 }
 118
 119 struct hash_table *
 120 hash_table_create(void)
 121 {
 122         struct hash_table *ht;
 123
 124         ht = malloc(sizeof(*ht));
 125         if (ht == NULL)
 126                 return NULL;
 127
 128         ht->size_index = 0;
 129         ht->size = hash_sizes[ht->size_index].size;
 130         ht->rehash = hash_sizes[ht->size_index].rehash;
 131         ht->max_entries = hash_sizes[ht->size_index].max_entries;
 132         ht->table = calloc(ht->size, sizeof(*ht->table));
 133         ht->entries = 0;
 134         ht->deleted_entries = 0;
 135
 136         if (ht->table == NULL) {
 137                 free(ht);
 138                 return NULL;
 139         }
 140
 141         return ht;
 142 }
 143
 144 /**
 145  * Frees the given hash table.
 146  */
 147 void
 148 hash_table_destroy(struct hash_table *ht)
 149 {
 150         if (!ht)
 151                 return;
 152
 153         free(ht->table);
 154         free(ht);
 155 }
 156
 157 /**
 158  * Finds a hash table entry with the given key and hash of that key.
 159  *
 160  * Returns NULL if no entry is found.  Note that the data pointer may be
 161  * modified by the user.
 162  */
 163 static void *
 164 hash_table_search(struct hash_table *ht, uint32_t hash)
 165 {
 166         uint32_t hash_address;
 167
 168         hash_address = hash % ht->size;
 169         do {
 170                 uint32_t double_hash;
 171
 172                 struct hash_entry *entry = ht->table + hash_address;
 173
 174                 if (entry_is_free(entry)) {
 175                         return NULL;
 176                 } else if (entry_is_present(entry) && entry->hash == hash) {
 177                         return entry;
 178                 }
 179
 180                 double_hash = 1 + hash % ht->rehash;
 181
 182                 hash_address = (hash_address + double_hash) % ht->size;
 183         } while (hash_address != hash % ht->size);
 184
 185         return NULL;
 186 }
 187
 188 void
 189 hash_table_for_each(struct hash_table *ht,
 190                     hash_table_iterator_func_t func, void *data)
 191 {
 192         struct hash_entry *entry;
 193         uint32_t i;
 194
 195         for (i = 0; i < ht->size; i++) {
 196                 entry = ht->table + i;
 197                 if (entry_is_present(entry))
 198                         func(entry->data, data);
 199         }
 200 }
 201
 202 void *
 203 hash_table_lookup(struct hash_table *ht, uint32_t hash)
 204 {
 205         struct hash_entry *entry;
 206
 207         entry = hash_table_search(ht, hash);
 208         if (entry != NULL)
 209                 return entry->data;
 210
 211         return NULL;
 212 }
 213
 214 static void
 215 hash_table_rehash(struct hash_table *ht, int new_size_index)
 216 {
 217         struct hash_table old_ht;
 218         struct hash_entry *table, *entry;
 219
 220         if (new_size_index >= ARRAY_SIZE(hash_sizes))
 221                 return;
 222
 223         table = calloc(hash_sizes[new_size_index].size, sizeof(*ht->table));
 224         if (table == NULL)
 225                 return;
 226
 227         old_ht = *ht;
 228
 229         ht->table = table;
 230         ht->size_index = new_size_index;
 231         ht->size = hash_sizes[ht->size_index].size;
 232         ht->rehash = hash_sizes[ht->size_index].rehash;
 233         ht->max_entries = hash_sizes[ht->size_index].max_entries;
 234         ht->entries = 0;
 235         ht->deleted_entries = 0;
 236
 237         for (entry = old_ht.table;
 238              entry != old_ht.table + old_ht.size;
 239              entry++) {
 240                 if (entry_is_present(entry)) {
 241                         hash_table_insert(ht, entry->hash, entry->data);
 242                 }
 243         }
 244
 245         free(old_ht.table);
 246 }
 247
 248 /**
 249  * Inserts the data with the given hash into the table.
 250  *
 251  * Note that insertion may rearrange the table on a resize or rehash,
 252  * so previously found hash_entries are no longer valid after this function.
 253  */
 254 int
 255 hash_table_insert(struct hash_table *ht, uint32_t hash, void *data)
 256 {
 257         uint32_t hash_address;
 258
 259         if (ht->entries >= ht->max_entries) {
 260                 hash_table_rehash(ht, ht->size_index + 1);
 261         } else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
 262                 hash_table_rehash(ht, ht->size_index);
 263         }
 264
 265         hash_address = hash % ht->size;
 266         do {
 267                 struct hash_entry *entry = ht->table + hash_address;
 268                 uint32_t double_hash;
 269
 270                 if (!entry_is_present(entry)) {
 271                         if (entry_is_deleted(entry))
 272                                 ht->deleted_entries--;
 273                         entry->hash = hash;
 274                         entry->data = data;
 275                         ht->entries++;
 276                         return 0;
 277                 }
 278
 279                 double_hash = 1 + hash % ht->rehash;
 280
 281                 hash_address = (hash_address + double_hash) % ht->size;
 282         } while (hash_address != hash % ht->size);
 283
 284         /* We could hit here if a required resize failed. An unchecked-malloc
 285          * application could ignore this result.
 286          */
 287         return -1;
 288 }
 289
 290 /**
 291  * This function deletes the given hash table entry.
 292  *
 293  * Note that deletion doesn't otherwise modify the table, so an iteration over
 294  * the table deleting entries is safe.
 295  */
 296 void
 297 hash_table_remove(struct hash_table *ht, uint32_t hash)
 298 {
 299         struct hash_entry *entry;
 300
 301         entry = hash_table_search(ht, hash);
 302         if (entry != NULL) {
 303                 entry->data = (void *) &deleted_data;
 304                 ht->entries--;
 305                 ht->deleted_entries++;
 306         }
 307 }