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