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 void * 112 hash_table_find(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->data; 123 } 124 } 125 126 return NULL; 127 } 128 129 130 void 131 hash_table_insert(struct hash_table *ht, void *data, const void *key) 132 { 133 const unsigned hash_value = (*ht->hash)(key); 134 const unsigned bucket = hash_value % ht->num_buckets; 135 struct hash_node *node; 136 137 node = calloc(1, sizeof(*node)); 138 139 node->data = data; 140 node->key = key; 141 142 insert_at_head(& ht->buckets[bucket], & node->link); 143 } 144 145 void 146 hash_table_remove(struct hash_table *ht, const void *key) 147 { 148 const unsigned hash_value = (*ht->hash)(key); 149 const unsigned bucket = hash_value % ht->num_buckets; 150 struct node *node; 151 152 foreach(node, & ht->buckets[bucket]) { 153 struct hash_node *hn = (struct hash_node *) node; 154 155 if ((*ht->compare)(hn->key, key) == 0) { 156 remove_from_list(node); 157 free(node); 158 return; 159 } 160 } 161 } 162 163 unsigned 164 hash_table_string_hash(const void *key) 165 { 166 const char *str = (const char *) key; 167 unsigned hash = 5381; 168 169 170 while (*str != '\0') { 171 hash = (hash * 33) + *str; 172 str++; 173 } 174 175 return hash; 176 } 177 178 179 unsigned 180 hash_table_pointer_hash(const void *key) 181 { 182 return (unsigned)((uintptr_t) key / sizeof(void *)); 183 } 184 185 186 int 187 hash_table_pointer_compare(const void *key1, const void *key2) 188 { 189 return key1 == key2 ? 0 : 1; 190 } 191
