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.h 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 31770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick#ifndef HASH_TABLE_H 32770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick#define HASH_TABLE_H 33770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 343ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick#include <string.h> 35a74c4fb89dee398a955415f0b5641bd9c5888c75Stéphane Marchesin#include <stdbool.h> 36f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick#include <stdlib.h> 373ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick#include <stdint.h> 383ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick#include <limits.h> 393ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick#include <assert.h> 403ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick 413ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanickstruct string_to_uint_map; 42770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 43e45a982313e02dbc186b51cf0935e0bec18dc61aIan Romanick#ifdef __cplusplus 44e45a982313e02dbc186b51cf0935e0bec18dc61aIan Romanickextern "C" { 45e45a982313e02dbc186b51cf0935e0bec18dc61aIan Romanick#endif 46e45a982313e02dbc186b51cf0935e0bec18dc61aIan Romanick 4763e7a4c6e5bf51d8090046ebc5adcb4207448565José Fonsecastruct hash_table; 4863e7a4c6e5bf51d8090046ebc5adcb4207448565José Fonseca 4963e7a4c6e5bf51d8090046ebc5adcb4207448565José Fonsecatypedef unsigned (*hash_func_t)(const void *key); 5063e7a4c6e5bf51d8090046ebc5adcb4207448565José Fonsecatypedef int (*hash_compare_func_t)(const void *key1, const void *key2); 5163e7a4c6e5bf51d8090046ebc5adcb4207448565José Fonseca 52770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick/** 53770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * Hash table constructor 54770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 55770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * Creates a hash table with the specified number of buckets. The supplied 56770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \c hash and \c compare routines are used when adding elements to the table 57770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * and when searching for elements in the table. 58770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 59770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \param num_buckets Number of buckets (bins) in the hash table. 60770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \param hash Function used to compute hash value of input keys. 61770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \param compare Function used to compare keys. 62770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick */ 63770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickextern struct hash_table *hash_table_ctor(unsigned num_buckets, 64770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick hash_func_t hash, hash_compare_func_t compare); 65770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 66770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 67770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick/** 680044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick * Release all memory associated with a hash table 690044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick * 700044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick * \warning 710044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick * This function cannot release memory occupied either by keys or data. 720044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick */ 730044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanickextern void hash_table_dtor(struct hash_table *ht); 740044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick 750044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick 760044d3ba94f9041492ea90cf8961fd8b55daefdaIan Romanick/** 77770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * Flush all entries from a hash table 78770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 79770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \param ht Table to be cleared of its entries. 80770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick */ 81770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickextern void hash_table_clear(struct hash_table *ht); 82770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 83770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 84770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick/** 85770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * Search a hash table for a specific element 86770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 87770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \param ht Table to be searched 88770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \param key Key of the desired element 89770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 90770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \return 91770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * The \c data value supplied to \c hash_table_insert when the element with 92770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * the matching key was added. If no matching key exists in the table, 93770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \c NULL is returned. 94770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick */ 95770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickextern void *hash_table_find(struct hash_table *ht, const void *key); 96770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 97770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 98770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick/** 99770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * Add an element to a hash table 10016f7bdf5556e739d5a0b6c4c2e2a30bb731f8fc9Ian Romanick * 10116f7bdf5556e739d5a0b6c4c2e2a30bb731f8fc9Ian Romanick * \warning 10216f7bdf5556e739d5a0b6c4c2e2a30bb731f8fc9Ian Romanick * If \c key is already in the hash table, it will be added again. Future 10316f7bdf5556e739d5a0b6c4c2e2a30bb731f8fc9Ian Romanick * calls to \c hash_table_find and \c hash_table_remove will return or remove, 10416f7bdf5556e739d5a0b6c4c2e2a30bb731f8fc9Ian Romanick * repsectively, the most recently added instance of \c key. 105acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick * 106f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick * \warning 107f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick * The value passed by \c key is kept in the hash table and is used by later 108f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick * calls to \c hash_table_find. 109f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick * 110acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick * \sa hash_table_replace 111770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick */ 112770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickextern void hash_table_insert(struct hash_table *ht, void *data, 113770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick const void *key); 114770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 115d4f239de6e988a59d4ba3783ea325aa1552c3f5aCarl Worth/** 116acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick * Add an element to a hash table with replacement 117acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick * 1183c9fab88226af8360817c01ecde38348284e6ce7Antoine Labour * \return 1193c9fab88226af8360817c01ecde38348284e6ce7Antoine Labour * 1 if it did replace the the value (in which case the old key is kept), 0 if 1203c9fab88226af8360817c01ecde38348284e6ce7Antoine Labour * it did not replace the value (in which case the new key is kept). 1213c9fab88226af8360817c01ecde38348284e6ce7Antoine Labour * 122acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick * \warning 123acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick * If \c key is already in the hash table, \c data will \b replace the most 124acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick * recently inserted \c data (see the warning in \c hash_table_insert) for 125acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick * that key. 126acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick * 127acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick * \sa hash_table_insert 128acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick */ 129a74c4fb89dee398a955415f0b5641bd9c5888c75Stéphane Marchesinextern bool hash_table_replace(struct hash_table *ht, void *data, 130acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick const void *key); 131acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick 132acd834fde2e604173985be5d44cb2cf2b0cd5673Ian Romanick/** 133d4f239de6e988a59d4ba3783ea325aa1552c3f5aCarl Worth * Remove a specific element from a hash table. 134d4f239de6e988a59d4ba3783ea325aa1552c3f5aCarl Worth */ 135d4f239de6e988a59d4ba3783ea325aa1552c3f5aCarl Worthextern void hash_table_remove(struct hash_table *ht, const void *key); 136770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 137770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick/** 138770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * Compute hash value of a string 139770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 140770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * Computes the hash value of a string using the DJB2 algorithm developed by 141770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * Professor Daniel J. Bernstein. It was published on comp.lang.c once upon 142770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * a time. I was unable to find the original posting in the archives. 143770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 144770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \param key Pointer to a NUL terminated string to be hashed. 145770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 146770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \sa hash_table_string_compare 147770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick */ 148770cebbc29863ae944a31463ee4bdeb789105abaIan Romanickextern unsigned hash_table_string_hash(const void *key); 149770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 150770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 151770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick/** 152770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * Compare two strings used as keys 153770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 154770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * This is just a macro wrapper around \c strcmp. 155770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * 156770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick * \sa hash_table_string_hash 157770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick */ 158770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick#define hash_table_string_compare ((hash_compare_func_t) strcmp) 159770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick 160d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick 161d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick/** 162d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick * Compute hash value of a pointer 163d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick * 164d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick * \param key Pointer to be used as a hash key 165d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick * 166d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick * \note 167d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick * The memory pointed to by \c key is \b never accessed. The value of \c key 168d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick * itself is used as the hash key 169d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick * 170d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick * \sa hash_table_pointer_compare 171d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick */ 172d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanickunsigned 173d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanickhash_table_pointer_hash(const void *key); 174d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick 175d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick 176d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick/** 177d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick * Compare two pointers used as keys 178d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick * 179d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick * \sa hash_table_pointer_hash 180d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick */ 181d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanickint 182d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanickhash_table_pointer_compare(const void *key1, const void *key2); 183d1a1ee583e7e8338243b3e9768d2fc5312a1145dIan Romanick 184b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholtvoid 185b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholthash_table_call_foreach(struct hash_table *ht, 186b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt void (*callback)(const void *key, 187b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt void *data, 188b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt void *closure), 189b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt void *closure); 190b061b5ffb055c64ffc45e506bad877f47942ba01Eric Anholt 1913ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanickstruct string_to_uint_map * 1923ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanickstring_to_uint_map_ctor(); 1933ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick 1943ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanickvoid 1953ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanickstring_to_uint_map_dtor(struct string_to_uint_map *); 1963ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick 1973ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick 198e45a982313e02dbc186b51cf0935e0bec18dc61aIan Romanick#ifdef __cplusplus 19930d083903f28965122800cc6ba3dc1ad08aff47fBrian Paul} 2003ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick 2013ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick/** 2023ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * Map from a string (name) to an unsigned integer value 2033ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * 2043ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * \note 2053ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * Because of the way this class interacts with the \c hash_table 2063ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * implementation, values of \c UINT_MAX cannot be stored in the map. 2073ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick */ 2083ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanickstruct string_to_uint_map { 2093ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanickpublic: 2103ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick string_to_uint_map() 2113ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick { 2123ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick this->ht = hash_table_ctor(0, hash_table_string_hash, 2133ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick hash_table_string_compare); 2143ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick } 2153ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick 2163ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick ~string_to_uint_map() 2173ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick { 218f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick hash_table_call_foreach(this->ht, delete_key, NULL); 2193ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick hash_table_dtor(this->ht); 2203ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick } 2213ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick 2223ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick /** 223017346f4038671bd6725b857f6daeba821a8306bIan Romanick * Remove all mappings from this map. 224017346f4038671bd6725b857f6daeba821a8306bIan Romanick */ 225017346f4038671bd6725b857f6daeba821a8306bIan Romanick void clear() 226017346f4038671bd6725b857f6daeba821a8306bIan Romanick { 2273c9fab88226af8360817c01ecde38348284e6ce7Antoine Labour hash_table_call_foreach(this->ht, delete_key, NULL); 228017346f4038671bd6725b857f6daeba821a8306bIan Romanick hash_table_clear(this->ht); 229017346f4038671bd6725b857f6daeba821a8306bIan Romanick } 230017346f4038671bd6725b857f6daeba821a8306bIan Romanick 231017346f4038671bd6725b857f6daeba821a8306bIan Romanick /** 2323ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * Get the value associated with a particular key 2333ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * 2343ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * \return 2353ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * If \c key is found in the map, \c true is returned. Otherwise \c false 2363ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * is returned. 2373ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * 2383ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * \note 2393ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * If \c key is not found in the table, \c value is not modified. 2403ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick */ 2413ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick bool get(unsigned &value, const char *key) 2423ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick { 2433ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick const intptr_t v = 2443ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick (intptr_t) hash_table_find(this->ht, (const void *) key); 2453ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick 2463ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick if (v == 0) 2473ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick return false; 2483ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick 2493ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick value = (unsigned)(v - 1); 2503ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick return true; 2513ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick } 2523ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick 2533ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick void put(unsigned value, const char *key) 2543ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick { 2553ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick /* The low-level hash table structure returns NULL if key is not in the 2563ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * hash table. However, users of this map might want to store zero as a 2573ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * valid value in the table. Bias the value by +1 so that a 2583ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * user-specified zero is stored as 1. This enables ::get to tell the 2593ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * difference between a user-specified zero (returned as 1 by 2603ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * hash_table_find) and the key not in the table (returned as 0 by 2613ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * hash_table_find). 2623ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * 2633ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * The net effect is that we can't store UINT_MAX in the table. This is 2643ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick * because UINT_MAX+1 = 0. 2653ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick */ 2663ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick assert(value != UINT_MAX); 2673c9fab88226af8360817c01ecde38348284e6ce7Antoine Labour char *dup_key = strdup(key); 268a74c4fb89dee398a955415f0b5641bd9c5888c75Stéphane Marchesin bool result = hash_table_replace(this->ht, 269a74c4fb89dee398a955415f0b5641bd9c5888c75Stéphane Marchesin (void *) (intptr_t) (value + 1), 270a74c4fb89dee398a955415f0b5641bd9c5888c75Stéphane Marchesin dup_key); 2713c9fab88226af8360817c01ecde38348284e6ce7Antoine Labour if (result) 2723c9fab88226af8360817c01ecde38348284e6ce7Antoine Labour free(dup_key); 2733ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick } 2743ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick 2753ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanickprivate: 276f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick static void delete_key(const void *key, void *data, void *closure) 277f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick { 278f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick (void) data; 279f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick (void) closure; 280f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick 281f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick free((char *)key); 282f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick } 283f3650b05cf4e37066d0f142a4c14fcc650de8d8dIan Romanick 2843ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick struct hash_table *ht; 2853ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick}; 2863ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick 2873ea297bdc47848e80c3b5a7d2143aca8a982b7a5Ian Romanick#endif /* __cplusplus */ 288770cebbc29863ae944a31463ee4bdeb789105abaIan Romanick#endif /* HASH_TABLE_H */ 289