FD.io VPP  v18.07-rc0-415-g6c78436
Vector Packet Processing
hash.h
Go to the documentation of this file.
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);
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. */
57 
58  /* Flags as follows. */
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 
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)). */
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 */
84 
85  /* Hook for user's data. Used to parameterize sum/equal functions. */
87 
88  /* Format a (k,v) pair */
90 
91  /* Format function 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). */
97 } hash_t;
98 
99 /* Hash header size in bytes */
102 {
103  hash_t *h;
104  uword is_user_bytes =
105  (sizeof (h->is_user[0]) * vec_len (v)) / BITS (h->is_user[0]);
106  return sizeof (h[0]) + is_user_bytes;
107 }
108 
109 /* Returns a pointer to the hash header given the vector pointer */
111 hash_header (void *v)
112 {
113  return vec_header (v, hash_header_bytes (v));
114 }
115 
116 /* Number of elements in the hash table */
118 hash_elts (void *v)
119 {
120  hash_t *h = hash_header (v);
121  return v ? h->elts : 0;
122 }
123 
124 /* Number of elements the hash table can hold */
126 hash_capacity (void *v)
127 {
128  return vec_len (v);
129 }
130 
131 /* Returns 1 if the hash pair contains user data */
133 hash_is_user (void *v, uword i)
134 {
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]);
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
145 {
146  hash_t *h = hash_header (v);
149 }
150 
151 /* Set hash table flags */
152 always_inline void
154 {
155  hash_header (v)->flags |= flags;
156 }
157 
158 /* Key value pairs. */
159 typedef struct
160 {
161  /* The 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. */
173 typedef struct
174 {
175  /* pair vector */
177  /* padding */
178  u8 pad[sizeof (uword) - sizeof (hash_pair_t *)];
179  /* allocated length */
181 }
183 
184 /* Direct / Indirect pair union */
185 typedef union
186 {
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. */
197 {
198  return p->alloc_len >> PAIR_BITS;
199 }
200 
201 /* Get the length of an indirect pair */
204 {
205  if (!p->pairs)
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
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 */
221 uword *_hash_get (void *v, uword key);
222 
223 /* internal routine to fetch value (key, value) pair for given key */
224 hash_pair_t *_hash_get_pair (void *v, uword key);
225 
226 /* internal routine to unset a (key, value) pair */
227 void *_hash_unset (void *v, uword key, void *old_value);
228 
229 /* internal routine to set a (key, value) pair, return the old value */
230 void *_hash_set3 (void *v, uword key, void *value, void *old_value);
231 
232 /* Resize a hash table */
233 void *hash_resize (void *old, uword new_size);
234 
235 /* duplicate a hash table */
236 void *hash_dup (void *old);
237 
238 /* Returns the number of bytes used by a hash table */
239 uword hash_bytes (void *v);
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 
277 /* Public inline funcion allocate and copy key to use in hash for pointer key */
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 
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 
293 /* Public inline funcion to unset pointer key and then free the key memory */
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);
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  }
304 }
305 
306 /* internal routine to free a hash table */
307 extern void *_hash_free (void *v);
308 
309 /* Public macro to free a hash table */
310 #define hash_free(h) (h) = _hash_free ((h))
311 
312 clib_error_t *hash_validate (void *v);
313 
314 /* Public inline funcion to get the number of value bytes for a hash table */
317 {
318  hash_pair_t *p;
319  return (sizeof (p->value[0]) << h->log2_pair_size) - sizeof (p->key);
320 }
321 
322 /* Public inline funcion to get log2(size of a (key,value) pair) */
325 {
326  uword log2_bytes = h->log2_pair_size;
327  ASSERT (BITS (hash_pair_t) == 32 || BITS (hash_pair_t) == 64);
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 
335 /* Public inline funcion to get size of a (key,value) pair */
338 {
339  return (uword) 1 << hash_pair_log2_bytes (h);
340 }
341 
342 /* Public inline funcion to advance a pointer past one (key,value) pair */
343 always_inline void *
344 hash_forward1 (hash_t * h, void *v)
345 {
346  return (u8 *) v + hash_pair_bytes (h);
347 }
348 
349 /* Public inline funcion to advance a pointer past N (key,value) pairs */
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 }
355 
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.
364 */
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  */
373 #define hash_foreach_pair(p,v,body) \
374 do { \
375  __label__ _hash_foreach_done; \
376  hash_t * _h = hash_header (v); \
377  void * _p; \
378  hash_pair_t * _q, * _q_end; \
379  uword _i, _i1, _id, _pair_increment; \
380  \
381  _p = (v); \
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  { \
394  _q = _p; \
395  _q_end = _q + _pair_increment; \
396  } \
397  else \
398  { \
399  hash_pair_indirect_t * _pi = _p; \
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  \
422  _p = (hash_pair_t *)_p + _pair_increment; \
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
437  @param body the operation to perform on each (key_var,value_var) pair.
438 
439  calls body with each active hash pair
440 */
441 /* Iteratate over key/value pairs. */
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
457  @param body the operation to perform on each (key_var,value_var) pair.
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. */
476 typedef struct
477 {
478  uword i, j, f;
479 } hash_next_t;
480 
481 hash_pair_t *hash_next (void *v, hash_next_t * hn);
482 
483 void *_hash_create (uword elts, hash_t * h);
484 
485 always_inline void
487 {
488  hash_pair_t *p;
489  h->log2_pair_size =
490  max_log2 ((sizeof (p->key) + value_bytes + sizeof (p->key) -
491  1) / sizeof (p->key));
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; \
499  memset (&_h, 0, sizeof (_h)); \
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 
550 {
551  return (x << i) | (x >> (BITS (i) - i));
552 }
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 
656 extern uword hash_memory (void *p, word n_bytes, uword state);
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);
666 extern u8 *vec_key_format_pair (u8 * s, va_list * args);
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);
674 extern u8 *string_key_format_pair (u8 * s, va_list * args);
675 
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 
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 
714 u8 *format_hash (u8 * s, va_list * va);
715 
716 /* Looks up input in hash table indexed by either vec string or
717  c string (null terminated). */
720 
721 /* Main test routine. */
722 int test_hash_main (unformat_input_t * input);
723 
724 #endif /* included_hash_h */
725 
726 /*
727  * fd.io coding-style-patch-verification: ON
728  *
729  * Local Variables:
730  * eval: (c-set-style "gnu")
731  * End:
732  */
uword( unformat_function_t)(unformat_input_t *input, va_list *args)
Definition: format.h:231
any user
Definition: hash.h:86
clib_error_t * hash_validate(void *v)
Definition: hash.c:1063
u8 pad[3]
log2 (size of the packing page block)
Definition: bihash_doc.h:61
uword hash_bytes(void *v)
Definition: hash.c:943
static uword indirect_pair_get_len(hash_pair_indirect_t *p)
Definition: hash.h:203
void * format_pair_arg
Definition: hash.h:92
unformat_function_t unformat_hash_string
Definition: hash.h:719
#define PREDICT_TRUE(x)
Definition: clib.h:106
uword hash_memory(void *p, word n_bytes, uword state)
Definition: hash.c:224
#define LOG2_ALLOC_BITS
Definition: hash.h:191
#define NULL
Definition: clib.h:55
hash_pair_t * pairs
Definition: hash.h:176
u8 * format_hash(u8 *s, va_list *va)
Definition: hash.c:968
uword mem_key_sum(hash_t *h, uword key)
Definition: hash.c:878
uword j
Definition: hash.h:478
static void hash_set_value_bytes(hash_t *h, uword value_bytes)
Definition: hash.h:486
word any
Definition: types.h:139
int test_hash_main(unformat_input_t *input)
int i
static void indirect_pair_set(hash_pair_indirect_t *p, uword log2_alloc, uword len)
Definition: hash.h:213
#define hash_set_mem(h, key, value)
Definition: hash.h:275
uword vec_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:817
#define hash_get_pair_mem(h, key)
Definition: hash.h:272
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
uword( hash_key_equal_function_t)(struct hash_header *, uword key1, uword key2)
Definition: hash.h:50
unsigned char u8
Definition: types.h:56
static uword hash_header_bytes(void *v)
Definition: hash.h:101
uword value[0]
Definition: hash.h:165
uword elts
Definition: hash.h:56
u32 log2_pair_size
Definition: hash.h:68
i64 word
Definition: types.h:111
#define always_inline
Definition: clib.h:92
hash_key_equal_function_t * key_equal
Definition: hash.h:83
unsigned int u32
Definition: types.h:88
static void hash_set_flags(void *v, uword flags)
Definition: hash.h:153
static uword hash_value_bytes(hash_t *h)
Definition: hash.h:316
static hash_t * hash_header(void *v)
Definition: hash.h:111
#define hash_unset_mem(h, key)
Definition: hash.h:291
static uword hash_capacity(void *v)
Definition: hash.h:126
void * hash_dup(void *old)
Definition: hash.c:783
static uword hash_is_user(void *v, uword i)
Definition: hash.h:133
static uword hash_pair_bytes(hash_t *h)
Definition: hash.h:337
struct _unformat_input_t unformat_input_t
uword string_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:900
void * hash_resize(void *old, uword new_size)
Definition: hash.c:777
#define PAIR_BITS
Definition: hash.h:192
unformat_function_t unformat_hash_vec_string
Definition: hash.h:718
u32 flags
Definition: hash.h:59
format_function_t * format_pair
Definition: hash.h:89
static uword hash_pair_log2_bytes(hash_t *h)
Definition: hash.h:324
hash_pair_indirect_t indirect
Definition: hash.h:188
static void * hash_forward1(hash_t *h, void *v)
Definition: hash.h:344
static void hash_set_pair_format(void *v, format_function_t *format_pair, void *format_pair_arg)
Definition: hash.h:143
#define clib_memcpy(a, b, c)
Definition: string.h:75
static uword hash32_rotate_left(u32 x, u32 i)
Definition: hash.h:549
u8 * string_key_format_pair(u8 *s, va_list *args)
Definition: hash.c:908
uword mem_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:885
static uword indirect_pair_get_log2_bytes(hash_pair_indirect_t *p)
Definition: hash.h:196
#define uword_to_pointer(u, type)
Definition: types.h:136
#define ASSERT(truth)
static uword hash_elts(void *v)
Definition: hash.h:118
static void * hash_forward(hash_t *h, void *v, uword n)
Definition: hash.h:351
vhost_vring_state_t state
Definition: vhost-user.h:82
static void clib_mem_free(void *p)
Definition: mem.h:179
static void * clib_mem_alloc(uword size)
Definition: mem.h:112
hash_pair_t * hash_next(void *v, hash_next_t *hn)
Definition: hash.c:606
uword( hash_key_sum_function_t)(struct hash_header *, uword key)
Definition: hash.h:48
hash_pair_t direct
Definition: hash.h:187
u8 * vec_key_format_pair(u8 *s, va_list *args)
Definition: hash.c:827
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
struct hash_header hash_t
static uword max_log2(uword x)
Definition: clib.h:185
u64 uword
Definition: types.h:112
static void hash_set_mem_alloc(uword **h, void *key, uword v)
Definition: hash.h:279
static void hash_unset_mem_free(uword **h, void *key)
Definition: hash.h:295
static void * vec_header(void *v, uword header_bytes)
Find a user vector header.
Definition: vec_bootstrap.h:92
uword string_key_sum(hash_t *h, uword key)
Definition: hash.c:893
#define BITS(x)
Definition: clib.h:58
uword vec_key_sum(hash_t *h, uword key)
Definition: hash.c:810
uword is_user[0]
Definition: hash.h:96
hash_key_sum_function_t * key_sum
Definition: hash.h:73
uword key
Definition: hash.h:162
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".