1 /* 2 * Copyright (c) 2017, NVIDIA CORPORATION. All rights reserved. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 * 16 */ 17 18 #ifndef __SHARED_HASH_H__ 19 #define __SHARED_HASH_H__ 20 21 /** \file 22 * \brief General-Purpose Hash Tables. 23 * 24 * These two hash table implementations store void pointers as keys, using 25 * user-provided functions for hashing and equality testing. The void pointers 26 * are not interpreted by the hash table implementation, except: 27 * 28 * - The void pointers are passed to the provided hash() and equals() functions. 29 * 30 * - The sentinel values NULL and (void*)~0UL have special meanings and cannot 31 * be used as keys. 32 * 33 * The equality function should return non-zero for equal hash keys. At a 34 * minimum, the provided functions must satisfy: 35 * 36 * equals(a, b) ==> hash(a) = hash(b) 37 * 38 * The hash() function should avoid clustering in the low bits of the hash 39 * value. 40 * 41 * A NULL equals() function is equivalent to a function returning a == b, but 42 * faster. 43 */ 44 45 typedef unsigned hash_value_t; 46 typedef const void *hash_key_t; 47 48 typedef hash_value_t (*hash_function_t)(hash_key_t); 49 typedef int (*hash_equality_t)(hash_key_t, hash_key_t); 50 51 typedef struct hash_functions_ { 52 hash_function_t hash; 53 hash_equality_t equals; 54 } hash_functions_t; 55 56 /** \brief Predefined hash functions for strings. 57 * 58 * The hash keys are interpreted as pointers to NUL-terminated strings. 59 */ 60 extern const hash_functions_t hash_functions_strings; 61 62 /** \brief Predefined hash functions for directly hashed keys. 63 * 64 * The pointers are compared by value with no indirection. These hash functions 65 * can also be used for integer keys. Just cast the integers to hash_key_t. 66 */ 67 extern const hash_functions_t hash_functions_direct; 68 69 #define INT2HKEY(i) (hash_key_t)(long)(i) 70 #define HKEY2INT(k) (int)(long)(k) 71 72 /** \brief Hash Set. 73 * 74 * A hashset_t is a hash table that stores a set of keys with no associated 75 * information. 76 */ 77 typedef struct hashset_ *hashset_t; 78 79 /** \brief Allocate a hashset which uses the provided functions to interpret 80 * keys. 81 * 82 * The returned hashset_t handle should be passed to hashset_free() to 83 * deallocate 84 * memory. 85 */ 86 hashset_t hashset_alloc(hash_functions_t); 87 88 /** \brief Free all memory used by a hashset. 89 * 90 * Note that any memory referenced by keys in the set is not freed. 91 */ 92 void hashset_free(hashset_t); 93 94 /** \brief Erase all keys in the set. 95 */ 96 void hashset_clear(hashset_t); 97 98 /** \brief Get the number of keys in the set. 99 */ 100 unsigned hashset_size(hashset_t); 101 102 /** \brief Look up a key and return the equivalent stored key, or NULL. 103 */ 104 hash_key_t hashset_lookup(hashset_t, hash_key_t); 105 106 /** \brief Insert a new key. 107 * 108 * Note that this function assumes that no equivalent key is present in the 109 * set, i.e. hashset_lookup() would return false. 110 * 111 * Use hashset_replace() if an equivalent key may be in the set already. 112 * 113 * The key cannot be NULL or (hash_key_t)~0UL. 114 */ 115 void hashset_insert(hashset_t, hash_key_t); 116 117 /** \brief Insert a new key or replace an existing key. 118 * 119 * If an equivalent key already exists, replace it with the new key and return 120 * the old one. If no equivalent key is in the set, insert the new key and 121 * return NULL. 122 */ 123 hash_key_t hashset_replace(hashset_t, hash_key_t); 124 125 /** \brief Erase a key from the set and return it. 126 * 127 * Return NULL if no equivalent key was found. 128 */ 129 hash_key_t hashset_erase(hashset_t, hash_key_t); 130 131 /** \brief Call f with every key in the hash set. 132 * 133 * Note that the iteration order is a function of both the hash function and 134 * the sequence of hashset_* calls leading up to this one. If pointers are 135 * directly hashed, address space layout randomization can cause different 136 * iteration orders in otherwise identical executions. 137 * 138 * The function f must not modify the hash table. 139 */ 140 void hashset_iterate(hashset_t, void (*f)(hash_key_t, void *context), 141 void *context); 142 143 /** \brief Hash Map. 144 * 145 * A hashmap_t is a hash table that maps a set of keys to data pointers. 146 * 147 * The keys are treated exactly the same as for a hashset_t, and have the same 148 * restrictions (i.e., no NULL and ~0UL keys allowed). The data pointers can 149 * have any value. 150 */ 151 typedef struct hashmap_ *hashmap_t; 152 typedef const void *hash_data_t; 153 154 /** \brief Allocate a hashmap. 155 * 156 * The returned handle must be freed with hashmap_free(). 157 */ 158 hashmap_t hashmap_alloc(hash_functions_t); 159 160 /** \brief Free all memory used by a hashmap. 161 * 162 * Note that any memory referenced by keys and data pointers in the map is not 163 * freed. 164 */ 165 void hashmap_free(hashmap_t); 166 167 /** \brief Erase all (key, data) entries in the map. 168 */ 169 void hashmap_clear(hashmap_t); 170 171 /** \brief Return the number of (key, data) pairs in the map. 172 */ 173 unsigned hashmap_size(hashmap_t); 174 175 /** \brief Look up a key and return the equivalent stored key, or NULL. 176 * 177 * If if a key was found and data is not NULL, *data will be set to the 178 * corresponding data value, otherwise it is not changed. 179 */ 180 hash_key_t hashmap_lookup(hashmap_t, hash_key_t, hash_data_t *data); 181 182 /** \brief Insert a new (key, data) pair. 183 * 184 * This function assumes that no equivalent key is present in the map, i.e. 185 * hashmap_lookup() would return NULL. 186 * 187 * Use hashmap_replace() if an equivalent key may exist in the map already. 188 */ 189 void hashmap_insert(hashmap_t, hash_key_t, hash_data_t); 190 191 /** \brief Insert or replace a (key, data) pair. 192 * 193 * If an equivalent key already exists, replace it with the new key and *data, 194 * and return the old key. On return, *data is set to the old data. 195 * 196 * If no equivalent key is present, insert the new key and *data and return 197 * NULL. The *data value is not updated. 198 */ 199 hash_key_t hashmap_replace(hashmap_t, hash_key_t, hash_data_t *data); 200 201 /** \brief Erase a key from the map and return it. 202 * 203 * If a (key, data) pair was erased and data is not NULL, update *data with the 204 * erased data value. 205 * 206 * If no key was erased, return NULL and leave *data unchanged. 207 */ 208 hash_key_t hashmap_erase(hashmap_t, hash_key_t, hash_data_t *data); 209 210 /** \brief Call f with every (key, data) pair in the hash map. 211 * 212 * The function f must not modify the hash table. 213 */ 214 void hashmap_iterate(hashmap_t, 215 void (*f)(hash_key_t, hash_data_t, void *context), 216 void *context); 217 218 /* 219 * Helpers for computing hash values for composite data structures, using a 220 * hash accumulator. These macros implement parts of the Jenkins hash function. 221 * 222 * See also the functions string_hash() and direct_hash() in hash.c. 223 * 224 * hash_value_T hash_function(const struct foo *data) 225 * { 226 * hash_accu_t hacc = HASH_ACCU_INIT; 227 * 228 * HASH_ACCU_ADD(hacc, data->int_member); 229 * HASH_ACCU_ADD(hacc, data->pointer_member); 230 * HASH_ACCU_FINISH(accu); 231 * return HASH_ACCU_VALUE(accu); 232 * } 233 * 234 */ 235 236 typedef struct hash_accu_ { 237 hash_value_t a; 238 } hash_accu_t; 239 240 #define HASH_ACCU_INIT \ 241 { \ 242 0 \ 243 } 244 245 #define HASH_ACCU_ADD(accu, data) \ 246 do { \ 247 (accu).a += (hash_value_t)(data); \ 248 (accu).a += (accu).a << 10; \ 249 (accu).a ^= (accu).a >> 6; \ 250 } while (0) 251 252 #define HASH_ACCU_FINISH(accu) \ 253 do { \ 254 (accu).a += (accu).a << 3; \ 255 (accu).a ^= (accu).a >> 11; \ 256 (accu).a += (accu).a << 15; \ 257 } while (0) 258 259 #define HASH_ACCU_VALUE(accu) ((accu).a + 0) 260 261 #endif /* __SHARED_HASH_H__ */ 262