Go to most recent revision | Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 1901 | serge | 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.h |
||
| 26 | * \brief Implementation of a generic, opaque hash table data type. |
||
| 27 | * |
||
| 28 | * \author Ian Romanick |
||
| 29 | */ |
||
| 30 | |||
| 31 | #ifndef HASH_TABLE_H |
||
| 32 | #define HASH_TABLE_H |
||
| 33 | |||
| 34 | struct hash_table; |
||
| 35 | |||
| 36 | typedef unsigned (*hash_func_t)(const void *key); |
||
| 37 | typedef int (*hash_compare_func_t)(const void *key1, const void *key2); |
||
| 38 | |||
| 39 | #ifdef __cplusplus |
||
| 40 | extern "C" { |
||
| 41 | #endif |
||
| 42 | |||
| 43 | /** |
||
| 44 | * Hash table constructor |
||
| 45 | * |
||
| 46 | * Creates a hash table with the specified number of buckets. The supplied |
||
| 47 | * \c hash and \c compare routines are used when adding elements to the table |
||
| 48 | * and when searching for elements in the table. |
||
| 49 | * |
||
| 50 | * \param num_buckets Number of buckets (bins) in the hash table. |
||
| 51 | * \param hash Function used to compute hash value of input keys. |
||
| 52 | * \param compare Function used to compare keys. |
||
| 53 | */ |
||
| 54 | extern struct hash_table *hash_table_ctor(unsigned num_buckets, |
||
| 55 | hash_func_t hash, hash_compare_func_t compare); |
||
| 56 | |||
| 57 | |||
| 58 | /** |
||
| 59 | * Release all memory associated with a hash table |
||
| 60 | * |
||
| 61 | * \warning |
||
| 62 | * This function cannot release memory occupied either by keys or data. |
||
| 63 | */ |
||
| 64 | extern void hash_table_dtor(struct hash_table *ht); |
||
| 65 | |||
| 66 | |||
| 67 | /** |
||
| 68 | * Flush all entries from a hash table |
||
| 69 | * |
||
| 70 | * \param ht Table to be cleared of its entries. |
||
| 71 | */ |
||
| 72 | extern void hash_table_clear(struct hash_table *ht); |
||
| 73 | |||
| 74 | |||
| 75 | /** |
||
| 76 | * Search a hash table for a specific element |
||
| 77 | * |
||
| 78 | * \param ht Table to be searched |
||
| 79 | * \param key Key of the desired element |
||
| 80 | * |
||
| 81 | * \return |
||
| 82 | * The \c data value supplied to \c hash_table_insert when the element with |
||
| 83 | * the matching key was added. If no matching key exists in the table, |
||
| 84 | * \c NULL is returned. |
||
| 85 | */ |
||
| 86 | extern void *hash_table_find(struct hash_table *ht, const void *key); |
||
| 87 | |||
| 88 | |||
| 89 | /** |
||
| 90 | * Add an element to a hash table |
||
| 91 | */ |
||
| 92 | extern void hash_table_insert(struct hash_table *ht, void *data, |
||
| 93 | const void *key); |
||
| 94 | |||
| 95 | /** |
||
| 96 | * Remove a specific element from a hash table. |
||
| 97 | */ |
||
| 98 | extern void hash_table_remove(struct hash_table *ht, const void *key); |
||
| 99 | |||
| 100 | /** |
||
| 101 | * Compute hash value of a string |
||
| 102 | * |
||
| 103 | * Computes the hash value of a string using the DJB2 algorithm developed by |
||
| 104 | * Professor Daniel J. Bernstein. It was published on comp.lang.c once upon |
||
| 105 | * a time. I was unable to find the original posting in the archives. |
||
| 106 | * |
||
| 107 | * \param key Pointer to a NUL terminated string to be hashed. |
||
| 108 | * |
||
| 109 | * \sa hash_table_string_compare |
||
| 110 | */ |
||
| 111 | extern unsigned hash_table_string_hash(const void *key); |
||
| 112 | |||
| 113 | |||
| 114 | /** |
||
| 115 | * Compare two strings used as keys |
||
| 116 | * |
||
| 117 | * This is just a macro wrapper around \c strcmp. |
||
| 118 | * |
||
| 119 | * \sa hash_table_string_hash |
||
| 120 | */ |
||
| 121 | #define hash_table_string_compare ((hash_compare_func_t) strcmp) |
||
| 122 | |||
| 123 | |||
| 124 | /** |
||
| 125 | * Compute hash value of a pointer |
||
| 126 | * |
||
| 127 | * \param key Pointer to be used as a hash key |
||
| 128 | * |
||
| 129 | * \note |
||
| 130 | * The memory pointed to by \c key is \b never accessed. The value of \c key |
||
| 131 | * itself is used as the hash key |
||
| 132 | * |
||
| 133 | * \sa hash_table_pointer_compare |
||
| 134 | */ |
||
| 135 | unsigned |
||
| 136 | hash_table_pointer_hash(const void *key); |
||
| 137 | |||
| 138 | |||
| 139 | /** |
||
| 140 | * Compare two pointers used as keys |
||
| 141 | * |
||
| 142 | * \sa hash_table_pointer_hash |
||
| 143 | */ |
||
| 144 | int |
||
| 145 | hash_table_pointer_compare(const void *key1, const void *key2); |
||
| 146 | |||
| 147 | #ifdef __cplusplus |
||
| 148 | } |
||
| 149 | #endif |
||
| 150 | #endif /* HASH_TABLE_H */ |