hash_table_impl.h (6069B)
1 /* 2 * The MIT License (MIT) 3 * 4 * Copyright (c) 2015 Mikkel F. Jørgensen, dvide.com 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a copy 7 * of this software and associated documentation files (the "Software"), to deal 8 * in the Software without restriction, including without limitation the rights 9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 10 * copies of the Software, and to permit persons to whom the Software is 11 * furnished to do so, subject to the following conditions: 12 * 13 * The above copyright notice and this permission notice shall be included in all 14 * copies or substantial portions of the 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 THE 19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 22 * SOFTWARE. 23 */ 24 25 26 /* 27 * This file implements a generic hash interface such that different 28 * instances have the same name, but hidden from each other. 29 * The interface maps the local names to a public specific type. 30 * 31 * This implementations implements a hash table with linear or quadratic 32 * probing. 33 */ 34 35 #ifdef HASH_TABLE_IMPL 36 #error "cannot have multiple implementations in same compilation unit" 37 #endif 38 #define HASH_TABLE_IMPL 39 /* Open Addressing */ 40 #define HT_OA 41 42 #if defined(_MSC_VER) 43 #pragma warning(disable: 4127) /* conditional expression is constant */ 44 #endif 45 46 #include <stdlib.h> 47 #include <assert.h> 48 49 #ifndef HT_PROBE 50 #ifdef HT_PROBE_QUADRATIC 51 #define HT_PROBE(k, i, N) ((k + (i + i * i) / 2) & N) 52 #else 53 #define HT_PROBE(k, i, N) ((k + i) & N) 54 #endif 55 #endif 56 57 static int ht_init(hash_table_t *ht, size_t count) 58 { 59 size_t buckets = 4; 60 61 if ((HT_LOAD_FACTOR_FRAC) > 256 || (HT_LOAD_FACTOR_FRAC) < 1) { 62 /* 63 * 100% is bad but still the users choice. 64 * 101% will never terminate insertion. 65 */ 66 HT_PANIC("hash table failed with impossible load factor"); 67 return -1; 68 } 69 while (count > buckets * (HT_LOAD_FACTOR_FRAC) / 256) { 70 buckets *= 2; 71 } 72 ht->table = calloc(buckets, sizeof(ht_item_t)); 73 if (ht->table == 0) { 74 return -1; 75 } 76 ht->offsets = 0; 77 ht->buckets = buckets; 78 ht->count = 0; 79 return 0; 80 } 81 82 static int ht_resize(hash_table_t *ht, size_t count) 83 { 84 size_t i; 85 hash_table_t ht2; 86 ht_item_t *T = ht->table; 87 void *item; 88 89 if (count < ht->count) { 90 count = ht->count; 91 } 92 if (ht_init(&ht2, count)) { 93 return -1; 94 } 95 for (i = 0; i < ht->buckets; ++i) { 96 item = T[i]; 97 if ((item && item != HT_DELETED)) { 98 ht_insert(&ht2, ht_key(item), ht_key_len(item), item, ht_multi); 99 } 100 } 101 ht_clear(ht); 102 memcpy(ht, &ht2, sizeof(*ht)); 103 return 0; 104 } 105 106 static ht_item_t ht_insert(hash_table_t *ht, 107 const void *key, size_t len, ht_item_t new_item, int mode) 108 { 109 ht_item_t *T; 110 size_t N, i, j, k; 111 ht_item_t item, *vacant = 0; 112 113 assert(new_item != HT_MISSING); 114 assert(new_item != HT_DELETED); 115 assert(new_item != HT_NOMEM); 116 117 if (ht->count >= ht->buckets * (HT_LOAD_FACTOR_FRAC) / 256) { 118 if (ht_resize(ht, ht->count * 2)) { 119 HT_PANIC("hash table failed to allocate memory during resize"); 120 return HT_NOMEM; 121 } 122 } 123 T = ht->table; 124 N = ht->buckets - 1; 125 k = HT_HASH_FUNCTION(key, len); 126 i = 0; 127 j = HT_PROBE(k, i, N); 128 if (mode == ht_unique || mode == ht_multi) { 129 ++ht->count; 130 while (T[j] && T[j] != HT_DELETED) { 131 ++i; 132 j = HT_PROBE(k, i, N); 133 } 134 T[j] = new_item; 135 return 0; 136 } 137 while ((item = T[j])) { 138 if (item == HT_DELETED) { 139 if (vacant == 0) { 140 /* 141 * If a tombstone was found, use the first available, 142 * but continue search for possible match. 143 */ 144 vacant = &T[j]; 145 } 146 } else if (ht_match(key, len, item)) { 147 if (mode == ht_replace) { 148 T[j] = new_item; 149 } 150 return item; 151 } 152 ++i; 153 j = HT_PROBE(k, i, N); 154 } 155 if (vacant == 0) { 156 vacant = &T[j]; 157 } 158 ++ht->count; 159 *vacant = new_item; 160 return 0; 161 } 162 163 static ht_item_t ht_find(hash_table_t *ht, const void *key, size_t len) 164 { 165 ht_item_t *T = ht->table; 166 size_t N, i, j, k; 167 ht_item_t item; 168 169 if (T == 0) { 170 return 0; 171 } 172 N = ht->buckets - 1; 173 k = HT_HASH_FUNCTION(key, len); 174 i = 0; 175 j = HT_PROBE(k, i, N); 176 while ((item = T[j])) { 177 if ((item != HT_DELETED) && 178 ht_match(key, len, item)) { 179 return item; 180 } 181 ++i; 182 j = HT_PROBE(k, i, N); 183 } 184 return 0; 185 } 186 187 static ht_item_t ht_remove(hash_table_t *ht, const void *key, size_t len) 188 { 189 ht_item_t *T = ht->table; 190 size_t N, i, j, k; 191 ht_item_t item; 192 193 if (T == 0) { 194 return 0; 195 } 196 N = ht->buckets - 1; 197 k = HT_HASH_FUNCTION(key, len); 198 i = 0; 199 j = HT_PROBE(k, i, N); 200 while ((item = T[j])) { 201 if (item != HT_DELETED && 202 ht_match(key, len, item)) { 203 T[j] = HT_DELETED; 204 --ht->count; 205 return item; 206 } 207 ++i; 208 j = HT_PROBE(k, i, N); 209 } 210 return 0; 211 } 212 213 static void ht_visit(hash_table_t *ht, ht_visitor_f *visitor, void *context) 214 { 215 size_t i; 216 ht_item_t *T = ht->table; 217 ht_item_t item; 218 219 for (i = 0; i < ht->buckets; ++i) { 220 item = T[i]; 221 if (item && item != HT_DELETED) { 222 visitor(context, item); 223 } 224 } 225 } 226 227 static void ht_clear(hash_table_t *ht) 228 { 229 if (ht->table) { 230 free(ht->table); 231 } 232 memset(ht, 0, sizeof(*ht)); 233 }