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