1770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick/* 2770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * Copyright © 2008 Intel Corporation 3770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 4770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * Permission is hereby granted, free of charge, to any person obtaining a 5770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * copy of this software and associated documentation files (the "Software"), 6770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * to deal in the Software without restriction, including without limitation 7770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * and/or sell copies of the Software, and to permit persons to whom the 9770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * Software is furnished to do so, subject to the following conditions: 10770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 11770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * The above copyright notice and this permission notice (including the next 12770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * paragraph) shall be included in all copies or substantial portions of the 13770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * Software. 14770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 15770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * DEALINGS IN THE SOFTWARE. 22770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick */ 23770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 24770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick/** 25770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \file hash_table.c 26770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \brief Implementation of a generic, opaque hash table data type. 27770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 28770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \author Ian Romanick <ian.d.romanick@intel.com> 29770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick */ 30770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 31523cb80d0f28d8dbb7b53b4d798e63baacc0ca35Luo Jinghua#include "main/imports.h" 32770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick#include "main/simple_list.h" 33770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick#include "hash_table.h" 34770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 35770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickstruct node { 36770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick struct node *next; 37770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick struct node *prev; 38770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick}; 39770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 40770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickstruct hash_table { 41770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick hash_func_t hash; 42770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick hash_compare_func_t compare; 43770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 44770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick unsigned num_buckets; 45770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick struct node buckets[1]; 46770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick}; 47770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 48770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 49770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickstruct hash_node { 50770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick struct node link; 51770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick const void *key; 52770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick void *data; 53770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick}; 54770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 55770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 56770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickstruct hash_table * 57770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickhash_table_ctor(unsigned num_buckets, hash_func_t hash, 58770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick hash_compare_func_t compare) 59770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick{ 60770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick struct hash_table *ht; 61770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick unsigned i; 62770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 63770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 64770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick if (num_buckets < 16) { 65770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick num_buckets = 16; 66770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick } 67770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 6832f2fd1c5d6088692551c80352b7d6fa35b0cd09Kristian Høgsberg ht = malloc(sizeof(*ht) + ((num_buckets - 1) 690044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick * sizeof(ht->buckets[0]))); 70770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick if (ht != NULL) { 71770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick ht->hash = hash; 72770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick ht->compare = compare; 73770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick ht->num_buckets = num_buckets; 74770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 75770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick for (i = 0; i < num_buckets; i++) { 76770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick make_empty_list(& ht->buckets[i]); 77770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick } 78770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick } 79770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 80770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick return ht; 81770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick} 82770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 83770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 84770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickvoid 850044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanickhash_table_dtor(struct hash_table *ht) 860044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick{ 870044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick hash_table_clear(ht); 8832f2fd1c5d6088692551c80352b7d6fa35b0cd09Kristian Høgsberg free(ht); 890044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick} 900044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick 910044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick 920044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanickvoid 93770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickhash_table_clear(struct hash_table *ht) 94770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick{ 95770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick struct node *node; 96770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick struct node *temp; 97770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick unsigned i; 98770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 99770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 100770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick for (i = 0; i < ht->num_buckets; i++) { 101770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick foreach_s(node, temp, & ht->buckets[i]) { 102770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick remove_from_list(node); 10332f2fd1c5d6088692551c80352b7d6fa35b0cd09Kristian Høgsberg free(node); 104770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick } 105770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 106770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick assert(is_empty_list(& ht->buckets[i])); 107770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick } 108770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick} 109770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 110770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 1111f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanickstatic struct hash_node * 1121f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanickget_node(struct hash_table *ht, const void *key) 113770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick{ 114770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick const unsigned hash_value = (*ht->hash)(key); 115770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick const unsigned bucket = hash_value % ht->num_buckets; 116770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick struct node *node; 117770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 118770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick foreach(node, & ht->buckets[bucket]) { 119770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick struct hash_node *hn = (struct hash_node *) node; 120770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 121770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick if ((*ht->compare)(hn->key, key) == 0) { 1221f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanick return hn; 123770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick } 124770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick } 125770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 126770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick return NULL; 127770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick} 128770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 1291f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanickvoid * 1301f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanickhash_table_find(struct hash_table *ht, const void *key) 1311f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanick{ 1321f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanick struct hash_node *hn = get_node(ht, key); 1331f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanick 1341f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanick return (hn == NULL) ? NULL : hn->data; 1351f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanick} 136770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 137770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickvoid 138770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickhash_table_insert(struct hash_table *ht, void *data, const void *key) 139770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick{ 140770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick const unsigned hash_value = (*ht->hash)(key); 141770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick const unsigned bucket = hash_value % ht->num_buckets; 142770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick struct hash_node *node; 143770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 14432f2fd1c5d6088692551c80352b7d6fa35b0cd09Kristian Høgsberg node = calloc(1, sizeof(*node)); 145770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 146770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick node->data = data; 147770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick node->key = key; 148770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 149770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick insert_at_head(& ht->buckets[bucket], & node->link); 150770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick} 151770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 1523c9fab88226af8360817c01ecde38348284e6ce7Antoine Labourbool 153acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanickhash_table_replace(struct hash_table *ht, void *data, const void *key) 154acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick{ 155acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick const unsigned hash_value = (*ht->hash)(key); 156acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick const unsigned bucket = hash_value % ht->num_buckets; 157acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick struct node *node; 158acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick struct hash_node *hn; 159acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick 160acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick foreach(node, & ht->buckets[bucket]) { 161acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick hn = (struct hash_node *) node; 162acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick 163acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick if ((*ht->compare)(hn->key, key) == 0) { 164acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick hn->data = data; 1653c9fab88226af8360817c01ecde38348284e6ce7Antoine Labour return true; 166acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick } 167acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick } 168acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick 169acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick hn = calloc(1, sizeof(*hn)); 170acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick 171acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick hn->data = data; 172acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick hn->key = key; 173acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick 174acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick insert_at_head(& ht->buckets[bucket], & hn->link); 1753c9fab88226af8360817c01ecde38348284e6ce7Antoine Labour return false; 176acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick} 177acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick 178acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanickvoid 179d4f239de6e988a59d4ba3783ea325aa1552c3f5aCarl Worthhash_table_remove(struct hash_table *ht, const void *key) 180d4f239de6e988a59d4ba3783ea325aa1552c3f5aCarl Worth{ 1811f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanick struct node *node = (struct node *) get_node(ht, key); 1821f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanick if (node != NULL) { 1831f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanick remove_from_list(node); 1841f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanick free(node); 1851f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanick return; 1861f8f8aef7f30156bbd906be36cdda2e05d8b0a7fIan Romanick } 187d4f239de6e988a59d4ba3783ea325aa1552c3f5aCarl Worth} 188770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 189b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholtvoid 190b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholthash_table_call_foreach(struct hash_table *ht, 191b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt void (*callback)(const void *key, 192b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt void *data, 193b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt void *closure), 194b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt void *closure) 195b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt{ 196b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt int bucket; 197b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt 198b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt for (bucket = 0; bucket < ht->num_buckets; bucket++) { 199b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt struct node *node, *temp; 200b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt foreach_s(node, temp, &ht->buckets[bucket]) { 201b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt struct hash_node *hn = (struct hash_node *) node; 202b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt 203b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt callback(hn->key, hn->data, closure); 204b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt } 205b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt } 206b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt} 207b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt 208770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickunsigned 209770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickhash_table_string_hash(const void *key) 210770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick{ 211770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick const char *str = (const char *) key; 212770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick unsigned hash = 5381; 213770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 214770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 215770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick while (*str != '\0') { 216770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick hash = (hash * 33) + *str; 217770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick str++; 218770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick } 219770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 220770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick return hash; 221770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick} 222d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick 223d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick 224d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanickunsigned 225d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanickhash_table_pointer_hash(const void *key) 226d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick{ 227d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick return (unsigned)((uintptr_t) key / sizeof(void *)); 228d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick} 229d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick 230d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick 231d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanickint 232d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanickhash_table_pointer_compare(const void *key1, const void *key2) 233d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick{ 234d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick return key1 == key2 ? 0 : 1; 235d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick} 236