Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (c) 2015 Cisco and/or its affiliates. |
| 3 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 | * you may not use this file except in compliance with the License. |
| 5 | * You may obtain a copy of the License at: |
| 6 | * |
| 7 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 8 | * |
| 9 | * Unless required by applicable law or agreed to in writing, software |
| 10 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 11 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 | * See the License for the specific language governing permissions and |
| 13 | * limitations under the License. |
| 14 | */ |
| 15 | /* |
| 16 | Copyright (c) 2001-2005 Eliot Dresselhaus |
| 17 | |
| 18 | Permission is hereby granted, free of charge, to any person obtaining |
| 19 | a copy of this software and associated documentation files (the |
| 20 | "Software"), to deal in the Software without restriction, including |
| 21 | without limitation the rights to use, copy, modify, merge, publish, |
| 22 | distribute, sublicense, and/or sell copies of the Software, and to |
| 23 | permit persons to whom the Software is furnished to do so, subject to |
| 24 | the following conditions: |
| 25 | |
| 26 | The above copyright notice and this permission notice shall be |
| 27 | included in all copies or substantial portions of the Software. |
| 28 | |
| 29 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
| 30 | EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
| 31 | MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
| 32 | NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE |
| 33 | LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION |
| 34 | OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION |
| 35 | WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| 36 | */ |
| 37 | |
| 38 | #ifndef included_hash_h |
| 39 | #define included_hash_h |
| 40 | |
| 41 | #include <vppinfra/error.h> |
| 42 | #include <vppinfra/format.h> |
| 43 | #include <vppinfra/vec.h> |
| 44 | #include <vppinfra/vector.h> |
| 45 | |
| 46 | struct hash_header; |
| 47 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 48 | typedef uword (hash_key_sum_function_t) (struct hash_header *, uword key); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 49 | typedef uword (hash_key_equal_function_t) |
| 50 | (struct hash_header *, uword key1, uword key2); |
| 51 | |
| 52 | /* Vector header for hash tables. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 53 | typedef struct hash_header |
| 54 | { |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 55 | /* Number of elements in hash table. */ |
| 56 | uword elts; |
| 57 | |
| 58 | /* Flags as follows. */ |
| 59 | u32 flags; |
| 60 | |
| 61 | /* Set if user does not want table to auto-resize when sufficiently full. */ |
| 62 | #define HASH_FLAG_NO_AUTO_GROW (1 << 0) |
| 63 | /* Set if user does not want table to auto-resize when sufficiently empty. */ |
| 64 | #define HASH_FLAG_NO_AUTO_SHRINK (1 << 1) |
| 65 | /* Set when hash_next is in the process of iterating through this hash table. */ |
| 66 | #define HASH_FLAG_HASH_NEXT_IN_PROGRESS (1 << 2) |
| 67 | |
| 68 | u32 log2_pair_size; |
| 69 | |
| 70 | /* Function to compute the "sum" of a hash key. |
| 71 | Hash function is this sum modulo the prime size of |
| 72 | the hash table (vec_len (v)). */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 73 | hash_key_sum_function_t *key_sum; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 74 | |
| 75 | /* Special values for key_sum "function". */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 76 | #define KEY_FUNC_NONE (0) /*< sum = key */ |
| 77 | #define KEY_FUNC_POINTER_UWORD (1) /*< sum = *(uword *) key */ |
| 78 | #define KEY_FUNC_POINTER_U32 (2) /*< sum = *(u32 *) key */ |
| 79 | #define KEY_FUNC_STRING (3) /*< sum = string_key_sum, etc. */ |
Ole Troan | 73710c7 | 2018-06-04 22:27:49 +0200 | [diff] [blame] | 80 | #define KEY_FUNC_MEM (4) /*< sum = mem_key_sum */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 81 | |
| 82 | /* key comparison function */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 83 | hash_key_equal_function_t *key_equal; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 84 | |
| 85 | /* Hook for user's data. Used to parameterize sum/equal functions. */ |
| 86 | any user; |
| 87 | |
| 88 | /* Format a (k,v) pair */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 89 | format_function_t *format_pair; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 90 | |
| 91 | /* Format function arg */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 92 | void *format_pair_arg; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 93 | |
| 94 | /* Bit i is set if pair i is a user object (as opposed to being |
| 95 | either zero or an indirect array of pairs). */ |
| 96 | uword is_user[0]; |
| 97 | } hash_t; |
| 98 | |
| 99 | /* Hash header size in bytes */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 100 | always_inline uword |
| 101 | hash_header_bytes (void *v) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 102 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 103 | hash_t *h; |
| 104 | uword is_user_bytes = |
| 105 | (sizeof (h->is_user[0]) * vec_len (v)) / BITS (h->is_user[0]); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 106 | return sizeof (h[0]) + is_user_bytes; |
| 107 | } |
| 108 | |
| 109 | /* Returns a pointer to the hash header given the vector pointer */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 110 | always_inline hash_t * |
| 111 | hash_header (void *v) |
| 112 | { |
| 113 | return vec_header (v, hash_header_bytes (v)); |
| 114 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 115 | |
| 116 | /* Number of elements in the hash table */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 117 | always_inline uword |
| 118 | hash_elts (void *v) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 119 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 120 | hash_t *h = hash_header (v); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 121 | return v ? h->elts : 0; |
| 122 | } |
| 123 | |
| 124 | /* Number of elements the hash table can hold */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 125 | always_inline uword |
| 126 | hash_capacity (void *v) |
| 127 | { |
| 128 | return vec_len (v); |
| 129 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 130 | |
| 131 | /* Returns 1 if the hash pair contains user data */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 132 | always_inline uword |
| 133 | hash_is_user (void *v, uword i) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 134 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 135 | hash_t *h = hash_header (v); |
| 136 | uword i0 = i / BITS (h->is_user[0]); |
| 137 | uword i1 = i % BITS (h->is_user[0]); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 138 | return (h->is_user[i0] & ((uword) 1 << i1)) != 0; |
| 139 | } |
| 140 | |
| 141 | /* Set the format function and format argument for a hash table */ |
| 142 | always_inline void |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 143 | hash_set_pair_format (void *v, |
| 144 | format_function_t * format_pair, void *format_pair_arg) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 145 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 146 | hash_t *h = hash_header (v); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 147 | h->format_pair = format_pair; |
| 148 | h->format_pair_arg = format_pair_arg; |
| 149 | } |
| 150 | |
| 151 | /* Set hash table flags */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 152 | always_inline void |
| 153 | hash_set_flags (void *v, uword flags) |
| 154 | { |
| 155 | hash_header (v)->flags |= flags; |
| 156 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 157 | |
| 158 | /* Key value pairs. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 159 | typedef struct |
| 160 | { |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 161 | /* The Key */ |
| 162 | uword key; |
| 163 | |
| 164 | /* The Value. Length is 2^log2_pair_size - 1. */ |
| 165 | uword value[0]; |
| 166 | } hash_pair_t; |
| 167 | |
| 168 | /* The indirect pair structure |
| 169 | |
| 170 | If log2_pair_size > 0 we overload hash pairs |
| 171 | with indirect pairs for buckets with more than one |
| 172 | pair. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 173 | typedef struct |
| 174 | { |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 175 | /* pair vector */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 176 | hash_pair_t *pairs; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 177 | /* padding */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 178 | u8 pad[sizeof (uword) - sizeof (hash_pair_t *)]; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 179 | /* allocated length */ |
| 180 | uword alloc_len; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 181 | } |
| 182 | hash_pair_indirect_t; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 183 | |
| 184 | /* Direct / Indirect pair union */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 185 | typedef union |
| 186 | { |
| 187 | hash_pair_t direct; |
| 188 | hash_pair_indirect_t indirect; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 189 | } hash_pair_union_t; |
| 190 | |
| 191 | #define LOG2_ALLOC_BITS (5) |
| 192 | #define PAIR_BITS (BITS (uword) - LOG2_ALLOC_BITS) |
| 193 | |
| 194 | /* Log2 number of bytes allocated in pairs array. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 195 | always_inline uword |
| 196 | indirect_pair_get_log2_bytes (hash_pair_indirect_t * p) |
| 197 | { |
| 198 | return p->alloc_len >> PAIR_BITS; |
| 199 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 200 | |
| 201 | /* Get the length of an indirect pair */ |
| 202 | always_inline uword |
| 203 | indirect_pair_get_len (hash_pair_indirect_t * p) |
| 204 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 205 | if (!p->pairs) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 206 | return 0; |
| 207 | else |
| 208 | return p->alloc_len & (((uword) 1 << PAIR_BITS) - 1); |
| 209 | } |
| 210 | |
| 211 | /* Set the length of an indirect pair */ |
| 212 | always_inline void |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 213 | indirect_pair_set (hash_pair_indirect_t * p, uword log2_alloc, uword len) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 214 | { |
| 215 | ASSERT (len < ((uword) 1 << PAIR_BITS)); |
| 216 | ASSERT (log2_alloc < ((uword) 1 << LOG2_ALLOC_BITS)); |
| 217 | p->alloc_len = (log2_alloc << PAIR_BITS) | len; |
| 218 | } |
| 219 | |
| 220 | /* internal routine to fetch value for given key */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 221 | uword *_hash_get (void *v, uword key); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 222 | |
| 223 | /* internal routine to fetch value (key, value) pair for given key */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 224 | hash_pair_t *_hash_get_pair (void *v, uword key); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 225 | |
| 226 | /* internal routine to unset a (key, value) pair */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 227 | void *_hash_unset (void *v, uword key, void *old_value); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 228 | |
| 229 | /* internal routine to set a (key, value) pair, return the old value */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 230 | void *_hash_set3 (void *v, uword key, void *value, void *old_value); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 231 | |
| 232 | /* Resize a hash table */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 233 | void *hash_resize (void *old, uword new_size); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 234 | |
| 235 | /* duplicate a hash table */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 236 | void *hash_dup (void *old); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 237 | |
| 238 | /* Returns the number of bytes used by a hash table */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 239 | uword hash_bytes (void *v); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 240 | |
| 241 | /* Public macro to set a (key, value) pair, return the old value */ |
| 242 | #define hash_set3(h,key,value,old_value) \ |
| 243 | ({ \ |
| 244 | uword _v = (uword) (value); \ |
| 245 | (h) = _hash_set3 ((h), (uword) (key), (void *) &_v, (old_value)); \ |
| 246 | }) |
| 247 | |
| 248 | /* Public macro to fetch value for given key */ |
| 249 | #define hash_get(h,key) _hash_get ((h), (uword) (key)) |
| 250 | |
| 251 | /* Public macro to fetch value (key, value) pair for given key */ |
| 252 | #define hash_get_pair(h,key) _hash_get_pair ((h), (uword) (key)) |
| 253 | |
| 254 | /* Public macro to set a (key, value) pair */ |
| 255 | #define hash_set(h,key,value) hash_set3(h,key,value,0) |
| 256 | |
| 257 | /* Public macro to set (key, 0) pair */ |
| 258 | #define hash_set1(h,key) (h) = _hash_set3(h,(uword) (key),0,0) |
| 259 | |
| 260 | /* Public macro to unset a (key, value) pair */ |
| 261 | #define hash_unset(h,key) ((h) = _hash_unset ((h), (uword) (key),0)) |
| 262 | |
| 263 | /* Public macro to unset a (key, value) pair, return the old value */ |
| 264 | #define hash_unset3(h,key,old_value) ((h) = _hash_unset ((h), (uword) (key), (void *) (old_value))) |
| 265 | |
| 266 | /* get/set/unset for pointer keys. */ |
| 267 | |
| 268 | /* Public macro to fetch value for given pointer key */ |
| 269 | #define hash_get_mem(h,key) _hash_get ((h), pointer_to_uword (key)) |
| 270 | |
| 271 | /* Public macro to fetch (key, value) for given pointer key */ |
| 272 | #define hash_get_pair_mem(h,key) _hash_get_pair ((h), pointer_to_uword (key)) |
| 273 | |
| 274 | /* Public macro to set (key, value) for pointer key */ |
| 275 | #define hash_set_mem(h,key,value) hash_set3 (h, pointer_to_uword (key), (value), 0) |
| 276 | |
Paul Vinciguerra | ec11b13 | 2018-09-24 05:25:00 -0700 | [diff] [blame] | 277 | /* Public inline function allocate and copy key to use in hash for pointer key */ |
John Lo | e6bfeab | 2018-01-04 16:39:42 -0500 | [diff] [blame] | 278 | always_inline void |
| 279 | hash_set_mem_alloc (uword ** h, void *key, uword v) |
| 280 | { |
| 281 | size_t ksz = hash_header (*h)->user; |
| 282 | void *copy = clib_mem_alloc (ksz); |
| 283 | clib_memcpy (copy, key, ksz); |
| 284 | hash_set_mem (*h, copy, v); |
| 285 | } |
| 286 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 287 | /* Public macro to set (key, 0) for pointer key */ |
| 288 | #define hash_set1_mem(h,key) hash_set3 ((h), pointer_to_uword (key), 0, 0) |
| 289 | |
| 290 | /* Public macro to unset (key, value) for pointer key */ |
| 291 | #define hash_unset_mem(h,key) ((h) = _hash_unset ((h), pointer_to_uword (key),0)) |
| 292 | |
Paul Vinciguerra | ec11b13 | 2018-09-24 05:25:00 -0700 | [diff] [blame] | 293 | /* Public inline function to unset pointer key and then free the key memory */ |
John Lo | e6bfeab | 2018-01-04 16:39:42 -0500 | [diff] [blame] | 294 | always_inline void |
| 295 | hash_unset_mem_free (uword ** h, void *key) |
| 296 | { |
| 297 | hash_pair_t *hp = hash_get_pair_mem (*h, key); |
John Lo | 5957a14 | 2018-01-18 12:44:50 -0500 | [diff] [blame] | 298 | if (PREDICT_TRUE (hp != NULL)) |
| 299 | { |
| 300 | key = uword_to_pointer (hp->key, void *); |
| 301 | hash_unset_mem (*h, key); |
| 302 | clib_mem_free (key); |
| 303 | } |
John Lo | e6bfeab | 2018-01-04 16:39:42 -0500 | [diff] [blame] | 304 | } |
| 305 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 306 | /* internal routine to free a hash table */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 307 | extern void *_hash_free (void *v); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 308 | |
| 309 | /* Public macro to free a hash table */ |
| 310 | #define hash_free(h) (h) = _hash_free ((h)) |
| 311 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 312 | clib_error_t *hash_validate (void *v); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 313 | |
Paul Vinciguerra | ec11b13 | 2018-09-24 05:25:00 -0700 | [diff] [blame] | 314 | /* Public inline function to get the number of value bytes for a hash table */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 315 | always_inline uword |
| 316 | hash_value_bytes (hash_t * h) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 317 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 318 | hash_pair_t *p; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 319 | return (sizeof (p->value[0]) << h->log2_pair_size) - sizeof (p->key); |
| 320 | } |
| 321 | |
Paul Vinciguerra | ec11b13 | 2018-09-24 05:25:00 -0700 | [diff] [blame] | 322 | /* Public inline function to get log2(size of a (key,value) pair) */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 323 | always_inline uword |
| 324 | hash_pair_log2_bytes (hash_t * h) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 325 | { |
| 326 | uword log2_bytes = h->log2_pair_size; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 327 | ASSERT (BITS (hash_pair_t) == 32 || BITS (hash_pair_t) == 64); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 328 | if (BITS (hash_pair_t) == 32) |
| 329 | log2_bytes += 2; |
| 330 | else if (BITS (hash_pair_t) == 64) |
| 331 | log2_bytes += 3; |
| 332 | return log2_bytes; |
| 333 | } |
| 334 | |
Paul Vinciguerra | ec11b13 | 2018-09-24 05:25:00 -0700 | [diff] [blame] | 335 | /* Public inline function to get size of a (key,value) pair */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 336 | always_inline uword |
| 337 | hash_pair_bytes (hash_t * h) |
| 338 | { |
| 339 | return (uword) 1 << hash_pair_log2_bytes (h); |
| 340 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 341 | |
Paul Vinciguerra | ec11b13 | 2018-09-24 05:25:00 -0700 | [diff] [blame] | 342 | /* Public inline function to advance a pointer past one (key,value) pair */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 343 | always_inline void * |
| 344 | hash_forward1 (hash_t * h, void *v) |
| 345 | { |
| 346 | return (u8 *) v + hash_pair_bytes (h); |
| 347 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 348 | |
Paul Vinciguerra | ec11b13 | 2018-09-24 05:25:00 -0700 | [diff] [blame] | 349 | /* Public inline function to advance a pointer past N (key,value) pairs */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 350 | always_inline void * |
| 351 | hash_forward (hash_t * h, void *v, uword n) |
| 352 | { |
| 353 | return (u8 *) v + ((n * sizeof (hash_pair_t)) << h->log2_pair_size); |
| 354 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 355 | |
Chris Luke | 5cdaf63 | 2016-07-30 15:05:07 -0400 | [diff] [blame] | 356 | /** Iterate over hash pairs. |
| 357 | |
| 358 | @param p The current (key,value) pair. This should be of type |
| 359 | <code>(hash_pair_t *)</code>. |
| 360 | @param v The hash table to iterate. |
| 361 | @param body The operation to perform on each (key,value) pair. |
| 362 | |
| 363 | Executes the expression or code block @c body with each active hash pair. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 364 | */ |
Chris Luke | 5cdaf63 | 2016-07-30 15:05:07 -0400 | [diff] [blame] | 365 | /* A previous version of this macro made use of the hash_pair_union_t |
| 366 | * structure; this version does not since that approach mightily upset |
| 367 | * the static analysis tool. In the rare chance someone is reading this |
| 368 | * code, pretend that _p below is of type hash_pair_union_t and that when |
| 369 | * used as an rvalue it's really using one of the union members as the |
| 370 | * rvalue. If you were confused before you might be marginally less |
| 371 | * confused after. |
| 372 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 373 | #define hash_foreach_pair(p,v,body) \ |
| 374 | do { \ |
| 375 | __label__ _hash_foreach_done; \ |
| 376 | hash_t * _h = hash_header (v); \ |
Chris Luke | 5cdaf63 | 2016-07-30 15:05:07 -0400 | [diff] [blame] | 377 | void * _p; \ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 378 | hash_pair_t * _q, * _q_end; \ |
| 379 | uword _i, _i1, _id, _pair_increment; \ |
| 380 | \ |
Chris Luke | 5cdaf63 | 2016-07-30 15:05:07 -0400 | [diff] [blame] | 381 | _p = (v); \ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 382 | _i = 0; \ |
| 383 | _pair_increment = 1; \ |
| 384 | if ((v)) \ |
| 385 | _pair_increment = 1 << _h->log2_pair_size; \ |
| 386 | while (_i < hash_capacity (v)) \ |
| 387 | { \ |
| 388 | _id = _h->is_user[_i / BITS (_h->is_user[0])]; \ |
| 389 | _i1 = _i + BITS (_h->is_user[0]); \ |
| 390 | \ |
| 391 | do { \ |
| 392 | if (_id & 1) \ |
| 393 | { \ |
Chris Luke | 5cdaf63 | 2016-07-30 15:05:07 -0400 | [diff] [blame] | 394 | _q = _p; \ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 395 | _q_end = _q + _pair_increment; \ |
| 396 | } \ |
| 397 | else \ |
| 398 | { \ |
Chris Luke | 5cdaf63 | 2016-07-30 15:05:07 -0400 | [diff] [blame] | 399 | hash_pair_indirect_t * _pi = _p; \ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 400 | _q = _pi->pairs; \ |
| 401 | if (_h->log2_pair_size > 0) \ |
| 402 | _q_end = hash_forward (_h, _q, indirect_pair_get_len (_pi)); \ |
| 403 | else \ |
| 404 | _q_end = vec_end (_q); \ |
| 405 | } \ |
| 406 | \ |
| 407 | /* Loop through all elements in bucket. \ |
| 408 | Bucket may have 0 1 or more (indirect case) pairs. */ \ |
| 409 | while (_q < _q_end) \ |
| 410 | { \ |
| 411 | uword _break_in_body = 1; \ |
| 412 | (p) = _q; \ |
| 413 | do { \ |
| 414 | body; \ |
| 415 | _break_in_body = 0; \ |
| 416 | } while (0); \ |
| 417 | if (_break_in_body) \ |
| 418 | goto _hash_foreach_done; \ |
| 419 | _q += _pair_increment; \ |
| 420 | } \ |
| 421 | \ |
Chris Luke | 5cdaf63 | 2016-07-30 15:05:07 -0400 | [diff] [blame] | 422 | _p = (hash_pair_t *)_p + _pair_increment; \ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 423 | _id = _id / 2; \ |
| 424 | _i++; \ |
| 425 | } while (_i < _i1); \ |
| 426 | } \ |
| 427 | _hash_foreach_done: \ |
| 428 | /* Be silent Mr. Compiler-Warning. */ \ |
| 429 | ; \ |
| 430 | } while (0) |
| 431 | |
| 432 | /* Iterate over key/value pairs |
| 433 | |
| 434 | @param key_var the current key |
| 435 | @param value_var the current value |
| 436 | @param h the hash table to iterate across |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 437 | @param body the operation to perform on each (key_var,value_var) pair. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 438 | |
| 439 | calls body with each active hash pair |
| 440 | */ |
Paul Vinciguerra | ec11b13 | 2018-09-24 05:25:00 -0700 | [diff] [blame] | 441 | /* Iterate over key/value pairs. */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 442 | #define hash_foreach(key_var,value_var,h,body) \ |
| 443 | do { \ |
| 444 | hash_pair_t * _r; \ |
| 445 | hash_foreach_pair (_r, (h), { \ |
| 446 | (key_var) = (__typeof__ (key_var)) _r->key; \ |
| 447 | (value_var) = (__typeof__ (value_var)) _r->value[0]; \ |
| 448 | do { body; } while (0); \ |
| 449 | }); \ |
| 450 | } while (0) |
| 451 | |
| 452 | /* Iterate over key/value pairs for pointer key hash tables |
| 453 | |
| 454 | @param key_var the current key |
| 455 | @param value_var the current value |
| 456 | @param h the hash table to iterate across |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 457 | @param body the operation to perform on each (key_var,value_var) pair. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 458 | |
| 459 | calls body with each active hash pair |
| 460 | */ |
| 461 | #define hash_foreach_mem(key_var,value_var,h,body) \ |
| 462 | do { \ |
| 463 | hash_pair_t * _r; \ |
| 464 | hash_foreach_pair (_r, (h), { \ |
| 465 | (key_var) = (__typeof__ (key_var)) uword_to_pointer (_r->key, void *); \ |
| 466 | (value_var) = (__typeof__ (value_var)) _r->value[0]; \ |
| 467 | do { body; } while (0); \ |
| 468 | }); \ |
| 469 | } while (0) |
| 470 | |
| 471 | /* Support for iteration through hash table. */ |
| 472 | |
| 473 | /* This struct saves iteration state for hash_next. |
| 474 | None of these fields are meant to be visible to the user. |
| 475 | Hence, the cryptic short-hand names. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 476 | typedef struct |
| 477 | { |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 478 | uword i, j, f; |
| 479 | } hash_next_t; |
| 480 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 481 | hash_pair_t *hash_next (void *v, hash_next_t * hn); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 482 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 483 | void *_hash_create (uword elts, hash_t * h); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 484 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 485 | always_inline void |
| 486 | hash_set_value_bytes (hash_t * h, uword value_bytes) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 487 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 488 | hash_pair_t *p; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 489 | h->log2_pair_size = |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 490 | max_log2 ((sizeof (p->key) + value_bytes + sizeof (p->key) - |
| 491 | 1) / sizeof (p->key)); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 492 | } |
| 493 | |
| 494 | #define hash_create2(_elts,_user,_value_bytes, \ |
| 495 | _key_sum,_key_equal, \ |
| 496 | _format_pair,_format_pair_arg) \ |
| 497 | ({ \ |
| 498 | hash_t _h; \ |
Dave Barach | b7b9299 | 2018-10-17 10:38:51 -0400 | [diff] [blame] | 499 | clib_memset (&_h, 0, sizeof (_h)); \ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 500 | _h.user = (_user); \ |
| 501 | _h.key_sum = (hash_key_sum_function_t *) (_key_sum); \ |
| 502 | _h.key_equal = (_key_equal); \ |
| 503 | hash_set_value_bytes (&_h, (_value_bytes)); \ |
| 504 | _h.format_pair = (format_function_t *) (_format_pair); \ |
| 505 | _h.format_pair_arg = (_format_pair_arg); \ |
| 506 | _hash_create ((_elts), &_h); \ |
| 507 | }) |
| 508 | |
| 509 | /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com). |
| 510 | Public domain per: http://www.burtleburtle.net/bob/hash/doobs.html |
| 511 | Thanks, Bob. */ |
| 512 | |
| 513 | #define hash_mix_step(a,b,c,s0,s1,s2) \ |
| 514 | do { \ |
| 515 | (a) -= (b) + (c); (a) ^= (c) >> (s0); \ |
| 516 | (b) -= (c) + (a); (b) ^= (a) << (s1); \ |
| 517 | (c) -= (a) + (b); (c) ^= (b) >> (s2); \ |
| 518 | } while (0) |
| 519 | |
| 520 | #define hash_mix32_step_1(a,b,c) hash_mix_step(a,b,c,13,8,13) |
| 521 | #define hash_mix32_step_2(a,b,c) hash_mix_step(a,b,c,12,16,5) |
| 522 | #define hash_mix32_step_3(a,b,c) hash_mix_step(a,b,c,3,10,15) |
| 523 | |
| 524 | #define hash_mix64_step_1(a,b,c) hash_mix_step(a,b,c,43,9,8) |
| 525 | #define hash_mix64_step_2(a,b,c) hash_mix_step(a,b,c,38,23,5) |
| 526 | #define hash_mix64_step_3(a,b,c) hash_mix_step(a,b,c,35,49,11) |
| 527 | #define hash_mix64_step_4(a,b,c) hash_mix_step(a,b,c,12,18,22) |
| 528 | |
| 529 | /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com). |
| 530 | Thanks, Bob. */ |
| 531 | #define hash_mix64(a0,b0,c0) \ |
| 532 | do { \ |
| 533 | hash_mix64_step_1 (a0, b0, c0); \ |
| 534 | hash_mix64_step_2 (a0, b0, c0); \ |
| 535 | hash_mix64_step_3 (a0, b0, c0); \ |
| 536 | hash_mix64_step_4 (a0, b0, c0); \ |
| 537 | } while (0) \ |
| 538 | |
| 539 | #define hash_mix32(a0,b0,c0) \ |
| 540 | do { \ |
| 541 | hash_mix32_step_1 (a0, b0, c0); \ |
| 542 | hash_mix32_step_2 (a0, b0, c0); \ |
| 543 | hash_mix32_step_3 (a0, b0, c0); \ |
| 544 | } while (0) \ |
| 545 | |
| 546 | /* Finalize from Bob Jenkins lookup3.c */ |
| 547 | |
| 548 | always_inline uword |
| 549 | hash32_rotate_left (u32 x, u32 i) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 550 | { |
| 551 | return (x << i) | (x >> (BITS (i) - i)); |
| 552 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 553 | |
| 554 | #define hash_v3_mix32(a,b,c) \ |
| 555 | do { \ |
| 556 | (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b); \ |
| 557 | (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c); \ |
| 558 | (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a); \ |
| 559 | (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b); \ |
| 560 | (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c); \ |
| 561 | (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a); \ |
| 562 | } while (0) |
| 563 | |
| 564 | #define hash_v3_finalize32(a,b,c) \ |
| 565 | do { \ |
| 566 | (c) ^= (b); (c) -= hash32_rotate_left ((b), 14); \ |
| 567 | (a) ^= (c); (a) -= hash32_rotate_left ((c), 11); \ |
| 568 | (b) ^= (a); (b) -= hash32_rotate_left ((a), 25); \ |
| 569 | (c) ^= (b); (c) -= hash32_rotate_left ((b), 16); \ |
| 570 | (a) ^= (c); (a) -= hash32_rotate_left ((c), 4); \ |
| 571 | (b) ^= (a); (b) -= hash32_rotate_left ((a), 14); \ |
| 572 | (c) ^= (b); (c) -= hash32_rotate_left ((b), 24); \ |
| 573 | } while (0) |
| 574 | |
| 575 | /* 32 bit mixing/finalize in steps. */ |
| 576 | |
| 577 | #define hash_v3_mix32_step1(a,b,c) \ |
| 578 | do { \ |
| 579 | (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b); \ |
| 580 | (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c); \ |
| 581 | } while (0) |
| 582 | |
| 583 | #define hash_v3_mix32_step2(a,b,c) \ |
| 584 | do { \ |
| 585 | (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a); \ |
| 586 | (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b); \ |
| 587 | } while (0) |
| 588 | |
| 589 | #define hash_v3_mix32_step3(a,b,c) \ |
| 590 | do { \ |
| 591 | (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c); \ |
| 592 | (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a); \ |
| 593 | } while (0) |
| 594 | |
| 595 | #define hash_v3_finalize32_step1(a,b,c) \ |
| 596 | do { \ |
| 597 | (c) ^= (b); (c) -= hash32_rotate_left ((b), 14); \ |
| 598 | (a) ^= (c); (a) -= hash32_rotate_left ((c), 11); \ |
| 599 | } while (0) |
| 600 | |
| 601 | #define hash_v3_finalize32_step2(a,b,c) \ |
| 602 | do { \ |
| 603 | (b) ^= (a); (b) -= hash32_rotate_left ((a), 25); \ |
| 604 | (c) ^= (b); (c) -= hash32_rotate_left ((b), 16); \ |
| 605 | } while (0) |
| 606 | |
| 607 | #define hash_v3_finalize32_step3(a,b,c) \ |
| 608 | do { \ |
| 609 | (a) ^= (c); (a) -= hash32_rotate_left ((c), 4); \ |
| 610 | (b) ^= (a); (b) -= hash32_rotate_left ((a), 14); \ |
| 611 | (c) ^= (b); (c) -= hash32_rotate_left ((b), 24); \ |
| 612 | } while (0) |
| 613 | |
| 614 | /* Vector v3 mixing/finalize. */ |
| 615 | #define hash_v3_mix_step_1_u32x(a,b,c) \ |
| 616 | do { \ |
| 617 | (a) -= (c); (a) ^= u32x_irotate_left ((c), 4); (c) += (b); \ |
| 618 | (b) -= (a); (b) ^= u32x_irotate_left ((a), 6); (a) += (c); \ |
| 619 | (c) -= (b); (c) ^= u32x_irotate_left ((b), 8); (b) += (a); \ |
| 620 | } while (0) |
| 621 | |
| 622 | #define hash_v3_mix_step_2_u32x(a,b,c) \ |
| 623 | do { \ |
| 624 | (a) -= (c); (a) ^= u32x_irotate_left ((c),16); (c) += (b); \ |
| 625 | (b) -= (a); (b) ^= u32x_irotate_left ((a),19); (a) += (c); \ |
| 626 | (c) -= (b); (c) ^= u32x_irotate_left ((b), 4); (b) += (a); \ |
| 627 | } while (0) |
| 628 | |
| 629 | #define hash_v3_finalize_step_1_u32x(a,b,c) \ |
| 630 | do { \ |
| 631 | (c) ^= (b); (c) -= u32x_irotate_left ((b), 14); \ |
| 632 | (a) ^= (c); (a) -= u32x_irotate_left ((c), 11); \ |
| 633 | (b) ^= (a); (b) -= u32x_irotate_left ((a), 25); \ |
| 634 | } while (0) |
| 635 | |
| 636 | #define hash_v3_finalize_step_2_u32x(a,b,c) \ |
| 637 | do { \ |
| 638 | (c) ^= (b); (c) -= u32x_irotate_left ((b), 16); \ |
| 639 | (a) ^= (c); (a) -= u32x_irotate_left ((c), 4); \ |
| 640 | (b) ^= (a); (b) -= u32x_irotate_left ((a), 14); \ |
| 641 | (c) ^= (b); (c) -= u32x_irotate_left ((b), 24); \ |
| 642 | } while (0) |
| 643 | |
| 644 | #define hash_v3_mix_u32x(a,b,c) \ |
| 645 | do { \ |
| 646 | hash_v3_mix_step_1_u32x(a,b,c); \ |
| 647 | hash_v3_mix_step_2_u32x(a,b,c); \ |
| 648 | } while (0) |
| 649 | |
| 650 | #define hash_v3_finalize_u32x(a,b,c) \ |
| 651 | do { \ |
| 652 | hash_v3_finalize_step_1_u32x(a,b,c); \ |
| 653 | hash_v3_finalize_step_2_u32x(a,b,c); \ |
| 654 | } while (0) |
| 655 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 656 | extern uword hash_memory (void *p, word n_bytes, uword state); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 657 | |
| 658 | extern uword mem_key_sum (hash_t * h, uword key); |
| 659 | extern uword mem_key_equal (hash_t * h, uword key1, uword key2); |
| 660 | |
| 661 | #define hash_create_mem(elts,key_bytes,value_bytes) \ |
| 662 | hash_create2((elts),(key_bytes),(value_bytes),mem_key_sum,mem_key_equal,0,0) |
| 663 | |
| 664 | extern uword vec_key_sum (hash_t * h, uword key); |
| 665 | extern uword vec_key_equal (hash_t * h, uword key1, uword key2); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 666 | extern u8 *vec_key_format_pair (u8 * s, va_list * args); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 667 | |
| 668 | #define hash_create_vec(elts,key_bytes,value_bytes) \ |
| 669 | hash_create2((elts),(key_bytes),(value_bytes),\ |
| 670 | vec_key_sum,vec_key_equal,vec_key_format_pair,0) |
| 671 | |
| 672 | extern uword string_key_sum (hash_t * h, uword key); |
| 673 | extern uword string_key_equal (hash_t * h, uword key1, uword key2); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 674 | extern u8 *string_key_format_pair (u8 * s, va_list * args); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 675 | |
Ole Troan | 73710c7 | 2018-06-04 22:27:49 +0200 | [diff] [blame] | 676 | /* |
| 677 | * Note: if you plan to put a hash into shared memory, |
| 678 | * the key sum and key equal functions MUST be set to magic constants! |
| 679 | * PIC means that whichever process sets up the hash won't have |
| 680 | * the actual key sum functions at the same place, leading to |
| 681 | * very hard-to-find bugs... |
| 682 | */ |
| 683 | |
| 684 | #define hash_create_shmem(elts,key_bytes,value_bytes) \ |
| 685 | hash_create2((elts),(key_bytes),(value_bytes), \ |
| 686 | (hash_key_sum_function_t *) KEY_FUNC_MEM, \ |
| 687 | (hash_key_equal_function_t *)KEY_FUNC_MEM, \ |
| 688 | 0, 0) |
| 689 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 690 | #define hash_create_string(elts,value_bytes) \ |
| 691 | hash_create2((elts),0,(value_bytes), \ |
| 692 | (hash_key_sum_function_t *) KEY_FUNC_STRING, \ |
| 693 | (hash_key_equal_function_t *)KEY_FUNC_STRING, \ |
| 694 | 0, 0) |
| 695 | |
| 696 | #define hash_create(elts,value_bytes) \ |
| 697 | hash_create2((elts),0,(value_bytes), \ |
| 698 | (hash_key_sum_function_t *) KEY_FUNC_NONE, \ |
| 699 | (hash_key_equal_function_t *) KEY_FUNC_NONE, \ |
| 700 | 0,0) |
| 701 | |
| 702 | #define hash_create_uword(elts,value_bytes) \ |
| 703 | hash_create2((elts),0,(value_bytes), \ |
| 704 | (hash_key_sum_function_t *) KEY_FUNC_POINTER_UWORD, \ |
| 705 | (hash_key_equal_function_t *) KEY_FUNC_POINTER_UWORD, \ |
| 706 | 0,0) |
| 707 | |
| 708 | #define hash_create_u32(elts,value_bytes) \ |
| 709 | hash_create2((elts),0,(value_bytes), \ |
| 710 | (hash_key_sum_function_t *) KEY_FUNC_POINTER_U32, \ |
| 711 | (hash_key_equal_function_t *) KEY_FUNC_POINTER_U32, \ |
| 712 | 0,0) |
| 713 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 714 | u8 *format_hash (u8 * s, va_list * va); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 715 | |
| 716 | /* Looks up input in hash table indexed by either vec string or |
| 717 | c string (null terminated). */ |
| 718 | unformat_function_t unformat_hash_vec_string; |
| 719 | unformat_function_t unformat_hash_string; |
| 720 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 721 | /* Main test routine. */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 722 | int test_hash_main (unformat_input_t * input); |
| 723 | |
| 724 | #endif /* included_hash_h */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 725 | |
| 726 | /* |
| 727 | * fd.io coding-style-patch-verification: ON |
| 728 | * |
| 729 | * Local Variables: |
| 730 | * eval: (c-set-style "gnu") |
| 731 | * End: |
| 732 | */ |