1 /* 2 * Copyright 2008 Intel Corporation 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21 * DEALINGS IN THE SOFTWARE. 22 */ 23 24 /** 25 * \file hash_table.c 26 * \brief Implementation of a generic, opaque hash table data type. 27 * 28 * \author Ian Romanick <ian.d.romanick (at) intel.com> 29 */ 30 31 #include "main/imports.h" 32 #include "main/simple_list.h" 33 #include "hash_table.h" 34 35 struct node { 36 struct node *next; 37 struct node *prev; 38 }; 39 40 struct hash_table { 41 hash_func_t hash; 42 hash_compare_func_t compare; 43 44 unsigned num_buckets; 45 struct node buckets[1]; 46 }; 47 48 49 struct hash_node { 50 struct node link; 51 const void *key; 52 void *data; 53 }; 54 55 56 struct hash_table * 57 hash_table_ctor(unsigned num_buckets, hash_func_t hash, 58 hash_compare_func_t compare) 59 { 60 struct hash_table *ht; 61 unsigned i; 62 63 64 if (num_buckets < 16) { 65 num_buckets = 16; 66 } 67 68 ht = malloc(sizeof(*ht) + ((num_buckets - 1) 69 * sizeof(ht->buckets[0]))); 70 if (ht != NULL) { 71 ht->hash = hash; 72 ht->compare = compare; 73 ht->num_buckets = num_buckets; 74 75 for (i = 0; i < num_buckets; i++) { 76 make_empty_list(& ht->buckets[i]); 77 } 78 } 79 80 return ht; 81 } 82 83 84 void 85 hash_table_dtor(struct hash_table *ht) 86 { 87 hash_table_clear(ht); 88 free(ht); 89 } 90 91 92 void 93 hash_table_clear(struct hash_table *ht) 94 { 95 struct node *node; 96 struct node *temp; 97 unsigned i; 98 99 100 for (i = 0; i < ht->num_buckets; i++) { 101 foreach_s(node, temp, & ht->buckets[i]) { 102 remove_from_list(node); 103 free(node); 104 } 105 106 assert(is_empty_list(& ht->buckets[i])); 107 } 108 } 109 110 111 static struct hash_node * 112 get_node(struct hash_table *ht, const void *key) 113 { 114 const unsigned hash_value = (*ht->hash)(key); 115 const unsigned bucket = hash_value % ht->num_buckets; 116 struct node *node; 117 118 foreach(node, & ht->buckets[bucket]) { 119 struct hash_node *hn = (struct hash_node *) node; 120 121 if ((*ht->compare)(hn->key, key) == 0) { 122 return hn; 123 } 124 } 125 126 return NULL; 127 } 128 129 void * 130 hash_table_find(struct hash_table *ht, const void *key) 131 { 132 struct hash_node *hn = get_node(ht, key); 133 134 return (hn == NULL) ? NULL : hn->data; 135 } 136 137 void 138 hash_table_insert(struct hash_table *ht, void *data, const void *key) 139 { 140 const unsigned hash_value = (*ht->hash)(key); 141 const unsigned bucket = hash_value % ht->num_buckets; 142 struct hash_node *node; 143 144 node = calloc(1, sizeof(*node)); 145 146 node->data = data; 147 node->key = key; 148 149 insert_at_head(& ht->buckets[bucket], & node->link); 150 } 151 152 bool 153 hash_table_replace(struct hash_table *ht, void *data, const void *key) 154 { 155 const unsigned hash_value = (*ht->hash)(key); 156 const unsigned bucket = hash_value % ht->num_buckets; 157 struct node *node; 158 struct hash_node *hn; 159 160 foreach(node, & ht->buckets[bucket]) { 161 hn = (struct hash_node *) node; 162 163 if ((*ht->compare)(hn->key, key) == 0) { 164 hn->data = data; 165 return true; 166 } 167 } 168 169 hn = calloc(1, sizeof(*hn)); 170 171 hn->data = data; 172 hn->key = key; 173 174 insert_at_head(& ht->buckets[bucket], & hn->link); 175 return false; 176 } 177 178 void 179 hash_table_remove(struct hash_table *ht, const void *key) 180 { 181 struct node *node = (struct node *) get_node(ht, key); 182 if (node != NULL) { 183 remove_from_list(node); 184 free(node); 185 return; 186 } 187 } 188 189 void 190 hash_table_call_foreach(struct hash_table *ht, 191 void (*callback)(const void *key, 192 void *data, 193 void *closure), 194 void *closure) 195 { 196 int bucket; 197 198 for (bucket = 0; bucket < ht->num_buckets; bucket++) { 199 struct node *node, *temp; 200 foreach_s(node, temp, &ht->buckets[bucket]) { 201 struct hash_node *hn = (struct hash_node *) node; 202 203 callback(hn->key, hn->data, closure); 204 } 205 } 206 } 207 208 unsigned 209 hash_table_string_hash(const void *key) 210 { 211 const char *str = (const char *) key; 212 unsigned hash = 5381; 213 214 215 while (*str != '\0') { 216 hash = (hash * 33) + *str; 217 str++; 218 } 219 220 return hash; 221 } 222 223 224 unsigned 225 hash_table_pointer_hash(const void *key) 226 { 227 return (unsigned)((uintptr_t) key / sizeof(void *)); 228 } 229 230 231 int 232 hash_table_pointer_compare(const void *key1, const void *key2) 233 { 234 return key1 == key2 ? 0 : 1; 235 } 236
