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.h 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#ifndef HASH_TABLE_H 321591693c7b415e9869157c711fe11263c95d74eDavid Li#define HASH_TABLE_H 331591693c7b415e9869157c711fe11263c95d74eDavid Li 341591693c7b415e9869157c711fe11263c95d74eDavid Listruct hash_table; 351591693c7b415e9869157c711fe11263c95d74eDavid Li 361591693c7b415e9869157c711fe11263c95d74eDavid Litypedef unsigned (*hash_func_t)(const void *key); 371591693c7b415e9869157c711fe11263c95d74eDavid Litypedef int (*hash_compare_func_t)(const void *key1, const void *key2); 381591693c7b415e9869157c711fe11263c95d74eDavid Li 391591693c7b415e9869157c711fe11263c95d74eDavid Li#ifdef __cplusplus 401591693c7b415e9869157c711fe11263c95d74eDavid Liextern "C" { 411591693c7b415e9869157c711fe11263c95d74eDavid Li#endif 421591693c7b415e9869157c711fe11263c95d74eDavid Li 431591693c7b415e9869157c711fe11263c95d74eDavid Li/** 441591693c7b415e9869157c711fe11263c95d74eDavid Li * Hash table constructor 451591693c7b415e9869157c711fe11263c95d74eDavid Li * 461591693c7b415e9869157c711fe11263c95d74eDavid Li * Creates a hash table with the specified number of buckets. The supplied 471591693c7b415e9869157c711fe11263c95d74eDavid Li * \c hash and \c compare routines are used when adding elements to the table 481591693c7b415e9869157c711fe11263c95d74eDavid Li * and when searching for elements in the table. 491591693c7b415e9869157c711fe11263c95d74eDavid Li * 501591693c7b415e9869157c711fe11263c95d74eDavid Li * \param num_buckets Number of buckets (bins) in the hash table. 511591693c7b415e9869157c711fe11263c95d74eDavid Li * \param hash Function used to compute hash value of input keys. 521591693c7b415e9869157c711fe11263c95d74eDavid Li * \param compare Function used to compare keys. 531591693c7b415e9869157c711fe11263c95d74eDavid Li */ 541591693c7b415e9869157c711fe11263c95d74eDavid Liextern struct hash_table *hash_table_ctor(unsigned num_buckets, 551591693c7b415e9869157c711fe11263c95d74eDavid Li hash_func_t hash, hash_compare_func_t compare); 561591693c7b415e9869157c711fe11263c95d74eDavid Li 571591693c7b415e9869157c711fe11263c95d74eDavid Li 581591693c7b415e9869157c711fe11263c95d74eDavid Li/** 591591693c7b415e9869157c711fe11263c95d74eDavid Li * Release all memory associated with a hash table 601591693c7b415e9869157c711fe11263c95d74eDavid Li * 611591693c7b415e9869157c711fe11263c95d74eDavid Li * \warning 621591693c7b415e9869157c711fe11263c95d74eDavid Li * This function cannot release memory occupied either by keys or data. 631591693c7b415e9869157c711fe11263c95d74eDavid Li */ 641591693c7b415e9869157c711fe11263c95d74eDavid Liextern void hash_table_dtor(struct hash_table *ht); 651591693c7b415e9869157c711fe11263c95d74eDavid Li 661591693c7b415e9869157c711fe11263c95d74eDavid Li 671591693c7b415e9869157c711fe11263c95d74eDavid Li/** 681591693c7b415e9869157c711fe11263c95d74eDavid Li * Flush all entries from a hash table 691591693c7b415e9869157c711fe11263c95d74eDavid Li * 701591693c7b415e9869157c711fe11263c95d74eDavid Li * \param ht Table to be cleared of its entries. 711591693c7b415e9869157c711fe11263c95d74eDavid Li */ 721591693c7b415e9869157c711fe11263c95d74eDavid Liextern void hash_table_clear(struct hash_table *ht); 731591693c7b415e9869157c711fe11263c95d74eDavid Li 741591693c7b415e9869157c711fe11263c95d74eDavid Li 751591693c7b415e9869157c711fe11263c95d74eDavid Li/** 761591693c7b415e9869157c711fe11263c95d74eDavid Li * Search a hash table for a specific element 771591693c7b415e9869157c711fe11263c95d74eDavid Li * 781591693c7b415e9869157c711fe11263c95d74eDavid Li * \param ht Table to be searched 791591693c7b415e9869157c711fe11263c95d74eDavid Li * \param key Key of the desired element 801591693c7b415e9869157c711fe11263c95d74eDavid Li * 811591693c7b415e9869157c711fe11263c95d74eDavid Li * \return 821591693c7b415e9869157c711fe11263c95d74eDavid Li * The \c data value supplied to \c hash_table_insert when the element with 831591693c7b415e9869157c711fe11263c95d74eDavid Li * the matching key was added. If no matching key exists in the table, 841591693c7b415e9869157c711fe11263c95d74eDavid Li * \c NULL is returned. 851591693c7b415e9869157c711fe11263c95d74eDavid Li */ 861591693c7b415e9869157c711fe11263c95d74eDavid Liextern void *hash_table_find(struct hash_table *ht, const void *key); 871591693c7b415e9869157c711fe11263c95d74eDavid Li 881591693c7b415e9869157c711fe11263c95d74eDavid Li 891591693c7b415e9869157c711fe11263c95d74eDavid Li/** 901591693c7b415e9869157c711fe11263c95d74eDavid Li * Add an element to a hash table 911591693c7b415e9869157c711fe11263c95d74eDavid Li */ 921591693c7b415e9869157c711fe11263c95d74eDavid Liextern void hash_table_insert(struct hash_table *ht, void *data, 931591693c7b415e9869157c711fe11263c95d74eDavid Li const void *key); 941591693c7b415e9869157c711fe11263c95d74eDavid Li 951591693c7b415e9869157c711fe11263c95d74eDavid Li/** 961591693c7b415e9869157c711fe11263c95d74eDavid Li * Remove a specific element from a hash table. 971591693c7b415e9869157c711fe11263c95d74eDavid Li */ 981591693c7b415e9869157c711fe11263c95d74eDavid Liextern void hash_table_remove(struct hash_table *ht, const void *key); 991591693c7b415e9869157c711fe11263c95d74eDavid Li 1001591693c7b415e9869157c711fe11263c95d74eDavid Li/** 1011591693c7b415e9869157c711fe11263c95d74eDavid Li * Compute hash value of a string 1021591693c7b415e9869157c711fe11263c95d74eDavid Li * 1031591693c7b415e9869157c711fe11263c95d74eDavid Li * Computes the hash value of a string using the DJB2 algorithm developed by 1041591693c7b415e9869157c711fe11263c95d74eDavid Li * Professor Daniel J. Bernstein. It was published on comp.lang.c once upon 1051591693c7b415e9869157c711fe11263c95d74eDavid Li * a time. I was unable to find the original posting in the archives. 1061591693c7b415e9869157c711fe11263c95d74eDavid Li * 1071591693c7b415e9869157c711fe11263c95d74eDavid Li * \param key Pointer to a NUL terminated string to be hashed. 1081591693c7b415e9869157c711fe11263c95d74eDavid Li * 1091591693c7b415e9869157c711fe11263c95d74eDavid Li * \sa hash_table_string_compare 1101591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1111591693c7b415e9869157c711fe11263c95d74eDavid Liextern unsigned hash_table_string_hash(const void *key); 1121591693c7b415e9869157c711fe11263c95d74eDavid Li 1131591693c7b415e9869157c711fe11263c95d74eDavid Li 1141591693c7b415e9869157c711fe11263c95d74eDavid Li/** 1151591693c7b415e9869157c711fe11263c95d74eDavid Li * Compare two strings used as keys 1161591693c7b415e9869157c711fe11263c95d74eDavid Li * 1171591693c7b415e9869157c711fe11263c95d74eDavid Li * This is just a macro wrapper around \c strcmp. 1181591693c7b415e9869157c711fe11263c95d74eDavid Li * 1191591693c7b415e9869157c711fe11263c95d74eDavid Li * \sa hash_table_string_hash 1201591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1211591693c7b415e9869157c711fe11263c95d74eDavid Li#define hash_table_string_compare ((hash_compare_func_t) strcmp) 1221591693c7b415e9869157c711fe11263c95d74eDavid Li 1231591693c7b415e9869157c711fe11263c95d74eDavid Li 1241591693c7b415e9869157c711fe11263c95d74eDavid Li/** 1251591693c7b415e9869157c711fe11263c95d74eDavid Li * Compute hash value of a pointer 1261591693c7b415e9869157c711fe11263c95d74eDavid Li * 1271591693c7b415e9869157c711fe11263c95d74eDavid Li * \param key Pointer to be used as a hash key 1281591693c7b415e9869157c711fe11263c95d74eDavid Li * 1291591693c7b415e9869157c711fe11263c95d74eDavid Li * \note 1301591693c7b415e9869157c711fe11263c95d74eDavid Li * The memory pointed to by \c key is \b never accessed. The value of \c key 1311591693c7b415e9869157c711fe11263c95d74eDavid Li * itself is used as the hash key 1321591693c7b415e9869157c711fe11263c95d74eDavid Li * 1331591693c7b415e9869157c711fe11263c95d74eDavid Li * \sa hash_table_pointer_compare 1341591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1351591693c7b415e9869157c711fe11263c95d74eDavid Liunsigned 1361591693c7b415e9869157c711fe11263c95d74eDavid Lihash_table_pointer_hash(const void *key); 1371591693c7b415e9869157c711fe11263c95d74eDavid Li 1381591693c7b415e9869157c711fe11263c95d74eDavid Li 1391591693c7b415e9869157c711fe11263c95d74eDavid Li/** 1401591693c7b415e9869157c711fe11263c95d74eDavid Li * Compare two pointers used as keys 1411591693c7b415e9869157c711fe11263c95d74eDavid Li * 1421591693c7b415e9869157c711fe11263c95d74eDavid Li * \sa hash_table_pointer_hash 1431591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1441591693c7b415e9869157c711fe11263c95d74eDavid Liint 1451591693c7b415e9869157c711fe11263c95d74eDavid Lihash_table_pointer_compare(const void *key1, const void *key2); 1461591693c7b415e9869157c711fe11263c95d74eDavid Li 1471591693c7b415e9869157c711fe11263c95d74eDavid Li#ifdef __cplusplus 1481591693c7b415e9869157c711fe11263c95d74eDavid Li} 1491591693c7b415e9869157c711fe11263c95d74eDavid Li#endif 1501591693c7b415e9869157c711fe11263c95d74eDavid Li#endif /* HASH_TABLE_H */ 151