11591693c7b415e9869157c711fe11263c95d74eDavid Li/* 21591693c7b415e9869157c711fe11263c95d74eDavid Li * Copyright © 2008 Intel Corporation 31591693c7b415e9869157c711fe11263c95d74eDavid Li * 41591693c7b415e9869157c711fe11263c95d74eDavid Li * Permission is hereby granted, free of charge, to any person obtaining a 51591693c7b415e9869157c711fe11263c95d74eDavid Li * copy of this software and associated documentation files (the "Software"), 61591693c7b415e9869157c711fe11263c95d74eDavid Li * to deal in the Software without restriction, including without limitation 71591693c7b415e9869157c711fe11263c95d74eDavid Li * the rights to use, copy, modify, merge, publish, distribute, sublicense, 81591693c7b415e9869157c711fe11263c95d74eDavid Li * and/or sell copies of the Software, and to permit persons to whom the 91591693c7b415e9869157c711fe11263c95d74eDavid Li * Software is furnished to do so, subject to the following conditions: 101591693c7b415e9869157c711fe11263c95d74eDavid Li * 111591693c7b415e9869157c711fe11263c95d74eDavid Li * The above copyright notice and this permission notice (including the next 121591693c7b415e9869157c711fe11263c95d74eDavid Li * paragraph) shall be included in all copies or substantial portions of the 131591693c7b415e9869157c711fe11263c95d74eDavid Li * Software. 141591693c7b415e9869157c711fe11263c95d74eDavid Li * 151591693c7b415e9869157c711fe11263c95d74eDavid Li * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 161591693c7b415e9869157c711fe11263c95d74eDavid Li * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 171591693c7b415e9869157c711fe11263c95d74eDavid Li * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 181591693c7b415e9869157c711fe11263c95d74eDavid Li * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 191591693c7b415e9869157c711fe11263c95d74eDavid Li * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 201591693c7b415e9869157c711fe11263c95d74eDavid Li * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 211591693c7b415e9869157c711fe11263c95d74eDavid Li * DEALINGS IN THE SOFTWARE. 221591693c7b415e9869157c711fe11263c95d74eDavid Li */ 231591693c7b415e9869157c711fe11263c95d74eDavid Li 241591693c7b415e9869157c711fe11263c95d74eDavid Li/** 251591693c7b415e9869157c711fe11263c95d74eDavid Li * \file hash_table.c 261591693c7b415e9869157c711fe11263c95d74eDavid Li * \brief Implementation of a generic, opaque hash table data type. 271591693c7b415e9869157c711fe11263c95d74eDavid Li * 281591693c7b415e9869157c711fe11263c95d74eDavid Li * \author Ian Romanick <ian.d.romanick@intel.com> 291591693c7b415e9869157c711fe11263c95d74eDavid Li */ 301591693c7b415e9869157c711fe11263c95d74eDavid Li 311591693c7b415e9869157c711fe11263c95d74eDavid Li#include "main/imports.h" 321591693c7b415e9869157c711fe11263c95d74eDavid Li#include "main/simple_list.h" 331591693c7b415e9869157c711fe11263c95d74eDavid Li#include "hash_table.h" 341591693c7b415e9869157c711fe11263c95d74eDavid Li 351591693c7b415e9869157c711fe11263c95d74eDavid Listruct node { 361591693c7b415e9869157c711fe11263c95d74eDavid Li struct node *next; 371591693c7b415e9869157c711fe11263c95d74eDavid Li struct node *prev; 381591693c7b415e9869157c711fe11263c95d74eDavid Li}; 391591693c7b415e9869157c711fe11263c95d74eDavid Li 401591693c7b415e9869157c711fe11263c95d74eDavid Listruct hash_table { 411591693c7b415e9869157c711fe11263c95d74eDavid Li hash_func_t hash; 421591693c7b415e9869157c711fe11263c95d74eDavid Li hash_compare_func_t compare; 431591693c7b415e9869157c711fe11263c95d74eDavid Li 441591693c7b415e9869157c711fe11263c95d74eDavid Li unsigned num_buckets; 451591693c7b415e9869157c711fe11263c95d74eDavid Li struct node buckets[1]; 461591693c7b415e9869157c711fe11263c95d74eDavid Li}; 471591693c7b415e9869157c711fe11263c95d74eDavid Li 481591693c7b415e9869157c711fe11263c95d74eDavid Li 491591693c7b415e9869157c711fe11263c95d74eDavid Listruct hash_node { 501591693c7b415e9869157c711fe11263c95d74eDavid Li struct node link; 511591693c7b415e9869157c711fe11263c95d74eDavid Li const void *key; 521591693c7b415e9869157c711fe11263c95d74eDavid Li void *data; 531591693c7b415e9869157c711fe11263c95d74eDavid Li}; 541591693c7b415e9869157c711fe11263c95d74eDavid Li 551591693c7b415e9869157c711fe11263c95d74eDavid Li 561591693c7b415e9869157c711fe11263c95d74eDavid Listruct hash_table * 571591693c7b415e9869157c711fe11263c95d74eDavid Lihash_table_ctor(unsigned num_buckets, hash_func_t hash, 581591693c7b415e9869157c711fe11263c95d74eDavid Li hash_compare_func_t compare) 591591693c7b415e9869157c711fe11263c95d74eDavid Li{ 601591693c7b415e9869157c711fe11263c95d74eDavid Li struct hash_table *ht; 611591693c7b415e9869157c711fe11263c95d74eDavid Li unsigned i; 621591693c7b415e9869157c711fe11263c95d74eDavid Li 631591693c7b415e9869157c711fe11263c95d74eDavid Li 641591693c7b415e9869157c711fe11263c95d74eDavid Li if (num_buckets < 16) { 651591693c7b415e9869157c711fe11263c95d74eDavid Li num_buckets = 16; 661591693c7b415e9869157c711fe11263c95d74eDavid Li } 671591693c7b415e9869157c711fe11263c95d74eDavid Li 681591693c7b415e9869157c711fe11263c95d74eDavid Li ht = malloc(sizeof(*ht) + ((num_buckets - 1) 691591693c7b415e9869157c711fe11263c95d74eDavid Li * sizeof(ht->buckets[0]))); 701591693c7b415e9869157c711fe11263c95d74eDavid Li if (ht != NULL) { 711591693c7b415e9869157c711fe11263c95d74eDavid Li ht->hash = hash; 721591693c7b415e9869157c711fe11263c95d74eDavid Li ht->compare = compare; 731591693c7b415e9869157c711fe11263c95d74eDavid Li ht->num_buckets = num_buckets; 741591693c7b415e9869157c711fe11263c95d74eDavid Li 751591693c7b415e9869157c711fe11263c95d74eDavid Li for (i = 0; i < num_buckets; i++) { 761591693c7b415e9869157c711fe11263c95d74eDavid Li make_empty_list(& ht->buckets[i]); 771591693c7b415e9869157c711fe11263c95d74eDavid Li } 781591693c7b415e9869157c711fe11263c95d74eDavid Li } 791591693c7b415e9869157c711fe11263c95d74eDavid Li 801591693c7b415e9869157c711fe11263c95d74eDavid Li return ht; 811591693c7b415e9869157c711fe11263c95d74eDavid Li} 821591693c7b415e9869157c711fe11263c95d74eDavid Li 831591693c7b415e9869157c711fe11263c95d74eDavid Li 841591693c7b415e9869157c711fe11263c95d74eDavid Livoid 851591693c7b415e9869157c711fe11263c95d74eDavid Lihash_table_dtor(struct hash_table *ht) 861591693c7b415e9869157c711fe11263c95d74eDavid Li{ 871591693c7b415e9869157c711fe11263c95d74eDavid Li hash_table_clear(ht); 881591693c7b415e9869157c711fe11263c95d74eDavid Li free(ht); 891591693c7b415e9869157c711fe11263c95d74eDavid Li} 901591693c7b415e9869157c711fe11263c95d74eDavid Li 911591693c7b415e9869157c711fe11263c95d74eDavid Li 921591693c7b415e9869157c711fe11263c95d74eDavid Livoid 931591693c7b415e9869157c711fe11263c95d74eDavid Lihash_table_clear(struct hash_table *ht) 941591693c7b415e9869157c711fe11263c95d74eDavid Li{ 951591693c7b415e9869157c711fe11263c95d74eDavid Li struct node *node; 961591693c7b415e9869157c711fe11263c95d74eDavid Li struct node *temp; 971591693c7b415e9869157c711fe11263c95d74eDavid Li unsigned i; 981591693c7b415e9869157c711fe11263c95d74eDavid Li 991591693c7b415e9869157c711fe11263c95d74eDavid Li 1001591693c7b415e9869157c711fe11263c95d74eDavid Li for (i = 0; i < ht->num_buckets; i++) { 1011591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_s(node, temp, & ht->buckets[i]) { 1021591693c7b415e9869157c711fe11263c95d74eDavid Li remove_from_list(node); 1031591693c7b415e9869157c711fe11263c95d74eDavid Li free(node); 1041591693c7b415e9869157c711fe11263c95d74eDavid Li } 1051591693c7b415e9869157c711fe11263c95d74eDavid Li 1061591693c7b415e9869157c711fe11263c95d74eDavid Li assert(is_empty_list(& ht->buckets[i])); 1071591693c7b415e9869157c711fe11263c95d74eDavid Li } 1081591693c7b415e9869157c711fe11263c95d74eDavid Li} 1091591693c7b415e9869157c711fe11263c95d74eDavid Li 1101591693c7b415e9869157c711fe11263c95d74eDavid Li 1111591693c7b415e9869157c711fe11263c95d74eDavid Livoid * 1121591693c7b415e9869157c711fe11263c95d74eDavid Lihash_table_find(struct hash_table *ht, const void *key) 1131591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1141591693c7b415e9869157c711fe11263c95d74eDavid Li const unsigned hash_value = (*ht->hash)(key); 1151591693c7b415e9869157c711fe11263c95d74eDavid Li const unsigned bucket = hash_value % ht->num_buckets; 1161591693c7b415e9869157c711fe11263c95d74eDavid Li struct node *node; 1171591693c7b415e9869157c711fe11263c95d74eDavid Li 1181591693c7b415e9869157c711fe11263c95d74eDavid Li foreach(node, & ht->buckets[bucket]) { 1191591693c7b415e9869157c711fe11263c95d74eDavid Li struct hash_node *hn = (struct hash_node *) node; 1201591693c7b415e9869157c711fe11263c95d74eDavid Li 1211591693c7b415e9869157c711fe11263c95d74eDavid Li if ((*ht->compare)(hn->key, key) == 0) { 1221591693c7b415e9869157c711fe11263c95d74eDavid Li return hn->data; 1231591693c7b415e9869157c711fe11263c95d74eDavid Li } 1241591693c7b415e9869157c711fe11263c95d74eDavid Li } 1251591693c7b415e9869157c711fe11263c95d74eDavid Li 1261591693c7b415e9869157c711fe11263c95d74eDavid Li return NULL; 1271591693c7b415e9869157c711fe11263c95d74eDavid Li} 1281591693c7b415e9869157c711fe11263c95d74eDavid Li 1291591693c7b415e9869157c711fe11263c95d74eDavid Li 1301591693c7b415e9869157c711fe11263c95d74eDavid Livoid 1311591693c7b415e9869157c711fe11263c95d74eDavid Lihash_table_insert(struct hash_table *ht, void *data, const void *key) 1321591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1331591693c7b415e9869157c711fe11263c95d74eDavid Li const unsigned hash_value = (*ht->hash)(key); 1341591693c7b415e9869157c711fe11263c95d74eDavid Li const unsigned bucket = hash_value % ht->num_buckets; 1351591693c7b415e9869157c711fe11263c95d74eDavid Li struct hash_node *node; 1361591693c7b415e9869157c711fe11263c95d74eDavid Li 1371591693c7b415e9869157c711fe11263c95d74eDavid Li node = calloc(1, sizeof(*node)); 1381591693c7b415e9869157c711fe11263c95d74eDavid Li 1391591693c7b415e9869157c711fe11263c95d74eDavid Li node->data = data; 1401591693c7b415e9869157c711fe11263c95d74eDavid Li node->key = key; 1411591693c7b415e9869157c711fe11263c95d74eDavid Li 1421591693c7b415e9869157c711fe11263c95d74eDavid Li insert_at_head(& ht->buckets[bucket], & node->link); 1431591693c7b415e9869157c711fe11263c95d74eDavid Li} 1441591693c7b415e9869157c711fe11263c95d74eDavid Li 1451591693c7b415e9869157c711fe11263c95d74eDavid Livoid 1461591693c7b415e9869157c711fe11263c95d74eDavid Lihash_table_remove(struct hash_table *ht, const void *key) 1471591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1481591693c7b415e9869157c711fe11263c95d74eDavid Li const unsigned hash_value = (*ht->hash)(key); 1491591693c7b415e9869157c711fe11263c95d74eDavid Li const unsigned bucket = hash_value % ht->num_buckets; 1501591693c7b415e9869157c711fe11263c95d74eDavid Li struct node *node; 1511591693c7b415e9869157c711fe11263c95d74eDavid Li 1521591693c7b415e9869157c711fe11263c95d74eDavid Li foreach(node, & ht->buckets[bucket]) { 1531591693c7b415e9869157c711fe11263c95d74eDavid Li struct hash_node *hn = (struct hash_node *) node; 1541591693c7b415e9869157c711fe11263c95d74eDavid Li 1551591693c7b415e9869157c711fe11263c95d74eDavid Li if ((*ht->compare)(hn->key, key) == 0) { 1561591693c7b415e9869157c711fe11263c95d74eDavid Li remove_from_list(node); 1571591693c7b415e9869157c711fe11263c95d74eDavid Li free(node); 1581591693c7b415e9869157c711fe11263c95d74eDavid Li return; 1591591693c7b415e9869157c711fe11263c95d74eDavid Li } 1601591693c7b415e9869157c711fe11263c95d74eDavid Li } 1611591693c7b415e9869157c711fe11263c95d74eDavid Li} 1621591693c7b415e9869157c711fe11263c95d74eDavid Li 1631591693c7b415e9869157c711fe11263c95d74eDavid Liunsigned 1641591693c7b415e9869157c711fe11263c95d74eDavid Lihash_table_string_hash(const void *key) 1651591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1661591693c7b415e9869157c711fe11263c95d74eDavid Li const char *str = (const char *) key; 1671591693c7b415e9869157c711fe11263c95d74eDavid Li unsigned hash = 5381; 1681591693c7b415e9869157c711fe11263c95d74eDavid Li 1691591693c7b415e9869157c711fe11263c95d74eDavid Li 1701591693c7b415e9869157c711fe11263c95d74eDavid Li while (*str != '\0') { 1711591693c7b415e9869157c711fe11263c95d74eDavid Li hash = (hash * 33) + *str; 1721591693c7b415e9869157c711fe11263c95d74eDavid Li str++; 1731591693c7b415e9869157c711fe11263c95d74eDavid Li } 1741591693c7b415e9869157c711fe11263c95d74eDavid Li 1751591693c7b415e9869157c711fe11263c95d74eDavid Li return hash; 1761591693c7b415e9869157c711fe11263c95d74eDavid Li} 1771591693c7b415e9869157c711fe11263c95d74eDavid Li 1781591693c7b415e9869157c711fe11263c95d74eDavid Li 1791591693c7b415e9869157c711fe11263c95d74eDavid Liunsigned 1801591693c7b415e9869157c711fe11263c95d74eDavid Lihash_table_pointer_hash(const void *key) 1811591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1821591693c7b415e9869157c711fe11263c95d74eDavid Li return (unsigned)((uintptr_t) key / sizeof(void *)); 1831591693c7b415e9869157c711fe11263c95d74eDavid Li} 1841591693c7b415e9869157c711fe11263c95d74eDavid Li 1851591693c7b415e9869157c711fe11263c95d74eDavid Li 1861591693c7b415e9869157c711fe11263c95d74eDavid Liint 1871591693c7b415e9869157c711fe11263c95d74eDavid Lihash_table_pointer_compare(const void *key1, const void *key2) 1881591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1891591693c7b415e9869157c711fe11263c95d74eDavid Li return key1 == key2 ? 0 : 1; 1901591693c7b415e9869157c711fe11263c95d74eDavid Li} 191