FD.io VPP  v16.09
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 
81  /* key comparison function */
83 
84  /* Hook for user's data. Used to parameterize sum/equal functions. */
86 
87  /* Format a (k,v) pair */
89 
90  /* Format function arg */
92 
93  /* Bit i is set if pair i is a user object (as opposed to being
94  either zero or an indirect array of pairs). */
96 } hash_t;
97 
98 /* Hash header size in bytes */
101 {
102  hash_t *h;
103  uword is_user_bytes =
104  (sizeof (h->is_user[0]) * vec_len (v)) / BITS (h->is_user[0]);
105  return sizeof (h[0]) + is_user_bytes;
106 }
107 
108 /* Returns a pointer to the hash header given the vector pointer */
110 hash_header (void *v)
111 {
112  return vec_header (v, hash_header_bytes (v));
113 }
114 
115 /* Number of elements in the hash table */
117 hash_elts (void *v)
118 {
119  hash_t *h = hash_header (v);
120  return v ? h->elts : 0;
121 }
122 
123 /* Number of elements the hash table can hold */
125 hash_capacity (void *v)
126 {
127  return vec_len (v);
128 }
129 
130 /* Returns 1 if the hash pair contains user data */
132 hash_is_user (void *v, uword i)
133 {
134  hash_t *h = hash_header (v);
135  uword i0 = i / BITS (h->is_user[0]);
136  uword i1 = i % BITS (h->is_user[0]);
137  return (h->is_user[i0] & ((uword) 1 << i1)) != 0;
138 }
139 
140 /* Set the format function and format argument for a hash table */
141 always_inline void
144 {
145  hash_t *h = hash_header (v);
148 }
149 
150 /* Set hash table flags */
151 always_inline void
153 {
154  hash_header (v)->flags |= flags;
155 }
156 
157 /* Key value pairs. */
158 typedef struct
159 {
160  /* The Key */
162 
163  /* The Value. Length is 2^log2_pair_size - 1. */
164  uword value[0];
165 } hash_pair_t;
166 
167 /* The indirect pair structure
168 
169  If log2_pair_size > 0 we overload hash pairs
170  with indirect pairs for buckets with more than one
171  pair. */
172 typedef struct
173 {
174  /* pair vector */
176  /* padding */
177  u8 pad[sizeof (uword) - sizeof (hash_pair_t *)];
178  /* allocated length */
180 }
182 
183 /* Direct / Indirect pair union */
184 typedef union
185 {
189 
190 #define LOG2_ALLOC_BITS (5)
191 #define PAIR_BITS (BITS (uword) - LOG2_ALLOC_BITS)
192 
193 /* Log2 number of bytes allocated in pairs array. */
196 {
197  return p->alloc_len >> PAIR_BITS;
198 }
199 
200 /* Get the length of an indirect pair */
203 {
204  if (!p->pairs)
205  return 0;
206  else
207  return p->alloc_len & (((uword) 1 << PAIR_BITS) - 1);
208 }
209 
210 /* Set the length of an indirect pair */
211 always_inline void
213 {
214  ASSERT (len < ((uword) 1 << PAIR_BITS));
215  ASSERT (log2_alloc < ((uword) 1 << LOG2_ALLOC_BITS));
216  p->alloc_len = (log2_alloc << PAIR_BITS) | len;
217 }
218 
219 /* internal routine to fetch value for given key */
220 uword *_hash_get (void *v, uword key);
221 
222 /* internal routine to fetch value (key, value) pair for given key */
223 hash_pair_t *_hash_get_pair (void *v, uword key);
224 
225 /* internal routine to unset a (key, value) pair */
226 void *_hash_unset (void *v, uword key, void *old_value);
227 
228 /* internal routine to set a (key, value) pair, return the old value */
229 void *_hash_set3 (void *v, uword key, void *value, void *old_value);
230 
231 /* Resize a hash table */
232 void *hash_resize (void *old, uword new_size);
233 
234 /* duplicate a hash table */
235 void *hash_dup (void *old);
236 
237 /* Returns the number of bytes used by a hash table */
238 uword hash_bytes (void *v);
239 
240 /* Public macro to set a (key, value) pair, return the old value */
241 #define hash_set3(h,key,value,old_value) \
242 ({ \
243  uword _v = (uword) (value); \
244  (h) = _hash_set3 ((h), (uword) (key), (void *) &_v, (old_value)); \
245 })
246 
247 /* Public macro to fetch value for given key */
248 #define hash_get(h,key) _hash_get ((h), (uword) (key))
249 
250 /* Public macro to fetch value (key, value) pair for given key */
251 #define hash_get_pair(h,key) _hash_get_pair ((h), (uword) (key))
252 
253 /* Public macro to set a (key, value) pair */
254 #define hash_set(h,key,value) hash_set3(h,key,value,0)
255 
256 /* Public macro to set (key, 0) pair */
257 #define hash_set1(h,key) (h) = _hash_set3(h,(uword) (key),0,0)
258 
259 /* Public macro to unset a (key, value) pair */
260 #define hash_unset(h,key) ((h) = _hash_unset ((h), (uword) (key),0))
261 
262 /* Public macro to unset a (key, value) pair, return the old value */
263 #define hash_unset3(h,key,old_value) ((h) = _hash_unset ((h), (uword) (key), (void *) (old_value)))
264 
265 /* get/set/unset for pointer keys. */
266 
267 /* Public macro to fetch value for given pointer key */
268 #define hash_get_mem(h,key) _hash_get ((h), pointer_to_uword (key))
269 
270 /* Public macro to fetch (key, value) for given pointer key */
271 #define hash_get_pair_mem(h,key) _hash_get_pair ((h), pointer_to_uword (key))
272 
273 /* Public macro to set (key, value) for pointer key */
274 #define hash_set_mem(h,key,value) hash_set3 (h, pointer_to_uword (key), (value), 0)
275 
276 /* Public macro to set (key, 0) for pointer key */
277 #define hash_set1_mem(h,key) hash_set3 ((h), pointer_to_uword (key), 0, 0)
278 
279 /* Public macro to unset (key, value) for pointer key */
280 #define hash_unset_mem(h,key) ((h) = _hash_unset ((h), pointer_to_uword (key),0))
281 
282 /* internal routine to free a hash table */
283 extern void *_hash_free (void *v);
284 
285 /* Public macro to free a hash table */
286 #define hash_free(h) (h) = _hash_free ((h))
287 
288 clib_error_t *hash_validate (void *v);
289 
290 /* Public inline funcion to get the number of value bytes for a hash table */
293 {
294  hash_pair_t *p;
295  return (sizeof (p->value[0]) << h->log2_pair_size) - sizeof (p->key);
296 }
297 
298 /* Public inline funcion to get log2(size of a (key,value) pair) */
301 {
302  uword log2_bytes = h->log2_pair_size;
303  ASSERT (BITS (hash_pair_t) == 32 || BITS (hash_pair_t) == 64);
304  if (BITS (hash_pair_t) == 32)
305  log2_bytes += 2;
306  else if (BITS (hash_pair_t) == 64)
307  log2_bytes += 3;
308  return log2_bytes;
309 }
310 
311 /* Public inline funcion to get size of a (key,value) pair */
314 {
315  return (uword) 1 << hash_pair_log2_bytes (h);
316 }
317 
318 /* Public inline funcion to advance a pointer past one (key,value) pair */
319 always_inline void *
320 hash_forward1 (hash_t * h, void *v)
321 {
322  return (u8 *) v + hash_pair_bytes (h);
323 }
324 
325 /* Public inline funcion to advance a pointer past N (key,value) pairs */
326 always_inline void *
327 hash_forward (hash_t * h, void *v, uword n)
328 {
329  return (u8 *) v + ((n * sizeof (hash_pair_t)) << h->log2_pair_size);
330 }
331 
332 /* Iterate over hash pairs
333  @param p the current (key,value) pair
334  @param v the hash table to iterate
335  @param body the operation to perform on each (key,value) pair.
336  executes body with each active hash pair
337 */
338 #define hash_foreach_pair(p,v,body) \
339 do { \
340  __label__ _hash_foreach_done; \
341  hash_t * _h = hash_header (v); \
342  hash_pair_union_t * _p; \
343  hash_pair_t * _q, * _q_end; \
344  uword _i, _i1, _id, _pair_increment; \
345  \
346  _p = (hash_pair_union_t *) (v); \
347  _i = 0; \
348  _pair_increment = 1; \
349  if ((v)) \
350  _pair_increment = 1 << _h->log2_pair_size; \
351  while (_i < hash_capacity (v)) \
352  { \
353  _id = _h->is_user[_i / BITS (_h->is_user[0])]; \
354  _i1 = _i + BITS (_h->is_user[0]); \
355  \
356  do { \
357  if (_id & 1) \
358  { \
359  _q = &_p->direct; \
360  _q_end = _q + _pair_increment; \
361  } \
362  else \
363  { \
364  hash_pair_indirect_t * _pi = &_p->indirect; \
365  _q = _pi->pairs; \
366  if (_h->log2_pair_size > 0) \
367  _q_end = hash_forward (_h, _q, indirect_pair_get_len (_pi)); \
368  else \
369  _q_end = vec_end (_q); \
370  } \
371  \
372  /* Loop through all elements in bucket. \
373  Bucket may have 0 1 or more (indirect case) pairs. */ \
374  while (_q < _q_end) \
375  { \
376  uword _break_in_body = 1; \
377  (p) = _q; \
378  do { \
379  body; \
380  _break_in_body = 0; \
381  } while (0); \
382  if (_break_in_body) \
383  goto _hash_foreach_done; \
384  _q += _pair_increment; \
385  } \
386  \
387  _p = (hash_pair_union_t *) (&_p->direct + _pair_increment); \
388  _id = _id / 2; \
389  _i++; \
390  } while (_i < _i1); \
391  } \
392  _hash_foreach_done: \
393  /* Be silent Mr. Compiler-Warning. */ \
394  ; \
395  } while (0)
396 
397 /* Iterate over key/value pairs
398 
399  @param key_var the current key
400  @param value_var the current value
401  @param h the hash table to iterate across
402  @param body the operation to perform on each (key_var,value_var) pair.
403 
404  calls body with each active hash pair
405 */
406 /* Iteratate over key/value pairs. */
407 #define hash_foreach(key_var,value_var,h,body) \
408 do { \
409  hash_pair_t * _r; \
410  hash_foreach_pair (_r, (h), { \
411  (key_var) = (__typeof__ (key_var)) _r->key; \
412  (value_var) = (__typeof__ (value_var)) _r->value[0]; \
413  do { body; } while (0); \
414  }); \
415 } while (0)
416 
417 /* Iterate over key/value pairs for pointer key hash tables
418 
419  @param key_var the current key
420  @param value_var the current value
421  @param h the hash table to iterate across
422  @param body the operation to perform on each (key_var,value_var) pair.
423 
424  calls body with each active hash pair
425 */
426 #define hash_foreach_mem(key_var,value_var,h,body) \
427 do { \
428  hash_pair_t * _r; \
429  hash_foreach_pair (_r, (h), { \
430  (key_var) = (__typeof__ (key_var)) uword_to_pointer (_r->key, void *); \
431  (value_var) = (__typeof__ (value_var)) _r->value[0]; \
432  do { body; } while (0); \
433  }); \
434 } while (0)
435 
436 /* Support for iteration through hash table. */
437 
438 /* This struct saves iteration state for hash_next.
439  None of these fields are meant to be visible to the user.
440  Hence, the cryptic short-hand names. */
441 typedef struct
442 {
443  uword i, j, f;
444 } hash_next_t;
445 
446 hash_pair_t *hash_next (void *v, hash_next_t * hn);
447 
448 void *_hash_create (uword elts, hash_t * h);
449 
450 always_inline void
452 {
453  hash_pair_t *p;
454  h->log2_pair_size =
455  max_log2 ((sizeof (p->key) + value_bytes + sizeof (p->key) -
456  1) / sizeof (p->key));
457 }
458 
459 #define hash_create2(_elts,_user,_value_bytes, \
460  _key_sum,_key_equal, \
461  _format_pair,_format_pair_arg) \
462 ({ \
463  hash_t _h; \
464  memset (&_h, 0, sizeof (_h)); \
465  _h.user = (_user); \
466  _h.key_sum = (hash_key_sum_function_t *) (_key_sum); \
467  _h.key_equal = (_key_equal); \
468  hash_set_value_bytes (&_h, (_value_bytes)); \
469  _h.format_pair = (format_function_t *) (_format_pair); \
470  _h.format_pair_arg = (_format_pair_arg); \
471  _hash_create ((_elts), &_h); \
472 })
473 
474 /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
475  Public domain per: http://www.burtleburtle.net/bob/hash/doobs.html
476  Thanks, Bob. */
477 
478 #define hash_mix_step(a,b,c,s0,s1,s2) \
479 do { \
480  (a) -= (b) + (c); (a) ^= (c) >> (s0); \
481  (b) -= (c) + (a); (b) ^= (a) << (s1); \
482  (c) -= (a) + (b); (c) ^= (b) >> (s2); \
483 } while (0)
484 
485 #define hash_mix32_step_1(a,b,c) hash_mix_step(a,b,c,13,8,13)
486 #define hash_mix32_step_2(a,b,c) hash_mix_step(a,b,c,12,16,5)
487 #define hash_mix32_step_3(a,b,c) hash_mix_step(a,b,c,3,10,15)
488 
489 #define hash_mix64_step_1(a,b,c) hash_mix_step(a,b,c,43,9,8)
490 #define hash_mix64_step_2(a,b,c) hash_mix_step(a,b,c,38,23,5)
491 #define hash_mix64_step_3(a,b,c) hash_mix_step(a,b,c,35,49,11)
492 #define hash_mix64_step_4(a,b,c) hash_mix_step(a,b,c,12,18,22)
493 
494 /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
495  Thanks, Bob. */
496 #define hash_mix64(a0,b0,c0) \
497 do { \
498  hash_mix64_step_1 (a0, b0, c0); \
499  hash_mix64_step_2 (a0, b0, c0); \
500  hash_mix64_step_3 (a0, b0, c0); \
501  hash_mix64_step_4 (a0, b0, c0); \
502 } while (0) \
503 
504 #define hash_mix32(a0,b0,c0) \
505 do { \
506  hash_mix32_step_1 (a0, b0, c0); \
507  hash_mix32_step_2 (a0, b0, c0); \
508  hash_mix32_step_3 (a0, b0, c0); \
509 } while (0) \
510 
511 /* Finalize from Bob Jenkins lookup3.c */
512 
515 {
516  return (x << i) | (x >> (BITS (i) - i));
517 }
518 
519 #define hash_v3_mix32(a,b,c) \
520 do { \
521  (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b); \
522  (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c); \
523  (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a); \
524  (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b); \
525  (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c); \
526  (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a); \
527 } while (0)
528 
529 #define hash_v3_finalize32(a,b,c) \
530 do { \
531  (c) ^= (b); (c) -= hash32_rotate_left ((b), 14); \
532  (a) ^= (c); (a) -= hash32_rotate_left ((c), 11); \
533  (b) ^= (a); (b) -= hash32_rotate_left ((a), 25); \
534  (c) ^= (b); (c) -= hash32_rotate_left ((b), 16); \
535  (a) ^= (c); (a) -= hash32_rotate_left ((c), 4); \
536  (b) ^= (a); (b) -= hash32_rotate_left ((a), 14); \
537  (c) ^= (b); (c) -= hash32_rotate_left ((b), 24); \
538 } while (0)
539 
540 /* 32 bit mixing/finalize in steps. */
541 
542 #define hash_v3_mix32_step1(a,b,c) \
543 do { \
544  (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b); \
545  (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c); \
546 } while (0)
547 
548 #define hash_v3_mix32_step2(a,b,c) \
549 do { \
550  (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a); \
551  (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b); \
552 } while (0)
553 
554 #define hash_v3_mix32_step3(a,b,c) \
555 do { \
556  (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c); \
557  (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a); \
558 } while (0)
559 
560 #define hash_v3_finalize32_step1(a,b,c) \
561 do { \
562  (c) ^= (b); (c) -= hash32_rotate_left ((b), 14); \
563  (a) ^= (c); (a) -= hash32_rotate_left ((c), 11); \
564 } while (0)
565 
566 #define hash_v3_finalize32_step2(a,b,c) \
567 do { \
568  (b) ^= (a); (b) -= hash32_rotate_left ((a), 25); \
569  (c) ^= (b); (c) -= hash32_rotate_left ((b), 16); \
570 } while (0)
571 
572 #define hash_v3_finalize32_step3(a,b,c) \
573 do { \
574  (a) ^= (c); (a) -= hash32_rotate_left ((c), 4); \
575  (b) ^= (a); (b) -= hash32_rotate_left ((a), 14); \
576  (c) ^= (b); (c) -= hash32_rotate_left ((b), 24); \
577 } while (0)
578 
579 /* Vector v3 mixing/finalize. */
580 #define hash_v3_mix_step_1_u32x(a,b,c) \
581 do { \
582  (a) -= (c); (a) ^= u32x_irotate_left ((c), 4); (c) += (b); \
583  (b) -= (a); (b) ^= u32x_irotate_left ((a), 6); (a) += (c); \
584  (c) -= (b); (c) ^= u32x_irotate_left ((b), 8); (b) += (a); \
585 } while (0)
586 
587 #define hash_v3_mix_step_2_u32x(a,b,c) \
588 do { \
589  (a) -= (c); (a) ^= u32x_irotate_left ((c),16); (c) += (b); \
590  (b) -= (a); (b) ^= u32x_irotate_left ((a),19); (a) += (c); \
591  (c) -= (b); (c) ^= u32x_irotate_left ((b), 4); (b) += (a); \
592 } while (0)
593 
594 #define hash_v3_finalize_step_1_u32x(a,b,c) \
595 do { \
596  (c) ^= (b); (c) -= u32x_irotate_left ((b), 14); \
597  (a) ^= (c); (a) -= u32x_irotate_left ((c), 11); \
598  (b) ^= (a); (b) -= u32x_irotate_left ((a), 25); \
599 } while (0)
600 
601 #define hash_v3_finalize_step_2_u32x(a,b,c) \
602 do { \
603  (c) ^= (b); (c) -= u32x_irotate_left ((b), 16); \
604  (a) ^= (c); (a) -= u32x_irotate_left ((c), 4); \
605  (b) ^= (a); (b) -= u32x_irotate_left ((a), 14); \
606  (c) ^= (b); (c) -= u32x_irotate_left ((b), 24); \
607 } while (0)
608 
609 #define hash_v3_mix_u32x(a,b,c) \
610 do { \
611  hash_v3_mix_step_1_u32x(a,b,c); \
612  hash_v3_mix_step_2_u32x(a,b,c); \
613 } while (0)
614 
615 #define hash_v3_finalize_u32x(a,b,c) \
616 do { \
617  hash_v3_finalize_step_1_u32x(a,b,c); \
618  hash_v3_finalize_step_2_u32x(a,b,c); \
619 } while (0)
620 
621 extern uword hash_memory (void *p, word n_bytes, uword state);
622 
623 extern uword mem_key_sum (hash_t * h, uword key);
624 extern uword mem_key_equal (hash_t * h, uword key1, uword key2);
625 
626 #define hash_create_mem(elts,key_bytes,value_bytes) \
627  hash_create2((elts),(key_bytes),(value_bytes),mem_key_sum,mem_key_equal,0,0)
628 
629 extern uword vec_key_sum (hash_t * h, uword key);
630 extern uword vec_key_equal (hash_t * h, uword key1, uword key2);
631 extern u8 *vec_key_format_pair (u8 * s, va_list * args);
632 
633 #define hash_create_vec(elts,key_bytes,value_bytes) \
634  hash_create2((elts),(key_bytes),(value_bytes),\
635  vec_key_sum,vec_key_equal,vec_key_format_pair,0)
636 
637 extern uword string_key_sum (hash_t * h, uword key);
638 extern uword string_key_equal (hash_t * h, uword key1, uword key2);
639 extern u8 *string_key_format_pair (u8 * s, va_list * args);
640 
641 #define hash_create_string(elts,value_bytes) \
642  hash_create2((elts),0,(value_bytes), \
643  (hash_key_sum_function_t *) KEY_FUNC_STRING, \
644  (hash_key_equal_function_t *)KEY_FUNC_STRING, \
645  0, 0)
646 
647 #define hash_create(elts,value_bytes) \
648  hash_create2((elts),0,(value_bytes), \
649  (hash_key_sum_function_t *) KEY_FUNC_NONE, \
650  (hash_key_equal_function_t *) KEY_FUNC_NONE, \
651  0,0)
652 
653 #define hash_create_uword(elts,value_bytes) \
654  hash_create2((elts),0,(value_bytes), \
655  (hash_key_sum_function_t *) KEY_FUNC_POINTER_UWORD, \
656  (hash_key_equal_function_t *) KEY_FUNC_POINTER_UWORD, \
657  0,0)
658 
659 #define hash_create_u32(elts,value_bytes) \
660  hash_create2((elts),0,(value_bytes), \
661  (hash_key_sum_function_t *) KEY_FUNC_POINTER_U32, \
662  (hash_key_equal_function_t *) KEY_FUNC_POINTER_U32, \
663  0,0)
664 
665 u8 *format_hash (u8 * s, va_list * va);
666 
667 /* Looks up input in hash table indexed by either vec string or
668  c string (null terminated). */
671 
672 /* Main test routine. */
673 int test_hash_main (unformat_input_t * input);
674 
675 #endif /* included_hash_h */
676 
677 /*
678  * fd.io coding-style-patch-verification: ON
679  *
680  * Local Variables:
681  * eval: (c-set-style "gnu")
682  * End:
683  */
any user
Definition: hash.h:85
clib_error_t * hash_validate(void *v)
Definition: hash.c:1045
u8 pad[3]
log2 (size of the packing page block)
Definition: bihash_doc.h:61
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
uword hash_bytes(void *v)
Definition: hash.c:925
uword( unformat_function_t)(unformat_input_t *input, va_list *args)
Definition: format.h:231
static uword indirect_pair_get_len(hash_pair_indirect_t *p)
Definition: hash.h:202
void * format_pair_arg
Definition: hash.h:91
unformat_function_t unformat_hash_string
Definition: hash.h:670
uword hash_memory(void *p, word n_bytes, uword state)
Definition: hash.c:214
#define LOG2_ALLOC_BITS
Definition: hash.h:190
hash_pair_t * pairs
Definition: hash.h:175
u8 * format_hash(u8 *s, va_list *va)
Definition: hash.c:950
uword mem_key_sum(hash_t *h, uword key)
Definition: hash.c:860
uword j
Definition: hash.h:443
static void hash_set_value_bytes(hash_t *h, uword value_bytes)
Definition: hash.h:451
int test_hash_main(unformat_input_t *input)
static void indirect_pair_set(hash_pair_indirect_t *p, uword log2_alloc, uword len)
Definition: hash.h:212
uword vec_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:799
uword( hash_key_equal_function_t)(struct hash_header *, uword key1, uword key2)
Definition: hash.h:50
static uword hash_header_bytes(void *v)
Definition: hash.h:100
uword value[0]
Definition: hash.h:164
uword elts
Definition: hash.h:56
u32 log2_pair_size
Definition: hash.h:68
#define always_inline
Definition: clib.h:84
hash_key_equal_function_t * key_equal
Definition: hash.h:82
static void hash_set_flags(void *v, uword flags)
Definition: hash.h:152
static uword hash_value_bytes(hash_t *h)
Definition: hash.h:292
static hash_t * hash_header(void *v)
Definition: hash.h:110
static uword hash_capacity(void *v)
Definition: hash.h:125
void * hash_dup(void *old)
Definition: hash.c:765
static uword hash_is_user(void *v, uword i)
Definition: hash.h:132
static uword hash_pair_bytes(hash_t *h)
Definition: hash.h:313
uword string_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:882
void * hash_resize(void *old, uword new_size)
Definition: hash.c:759
#define PAIR_BITS
Definition: hash.h:191
unformat_function_t unformat_hash_vec_string
Definition: hash.h:669
u32 flags
Definition: hash.h:59
word any
Definition: types.h:139
format_function_t * format_pair
Definition: hash.h:88
static uword hash_pair_log2_bytes(hash_t *h)
Definition: hash.h:300
hash_pair_indirect_t indirect
Definition: hash.h:187
static void * hash_forward1(hash_t *h, void *v)
Definition: hash.h:320
static void hash_set_pair_format(void *v, format_function_t *format_pair, void *format_pair_arg)
Definition: hash.h:142
static uword hash32_rotate_left(u32 x, u32 i)
Definition: hash.h:514
u8 * string_key_format_pair(u8 *s, va_list *args)
Definition: hash.c:890
uword mem_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:867
static uword indirect_pair_get_log2_bytes(hash_pair_indirect_t *p)
Definition: hash.h:195
#define ASSERT(truth)
static uword hash_elts(void *v)
Definition: hash.h:117
unsigned int u32
Definition: types.h:88
static void * hash_forward(hash_t *h, void *v, uword n)
Definition: hash.h:327
vhost_vring_state_t state
Definition: vhost-user.h:81
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
u64 uword
Definition: types.h:112
hash_pair_t * hash_next(void *v, hash_next_t *hn)
Definition: hash.c:588
uword( hash_key_sum_function_t)(struct hash_header *, uword key)
Definition: hash.h:48
i64 word
Definition: types.h:111
hash_pair_t direct
Definition: hash.h:186
u8 * vec_key_format_pair(u8 *s, va_list *args)
Definition: hash.c:809
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
unsigned char u8
Definition: types.h:56
struct hash_header hash_t
static uword max_log2(uword x)
Definition: clib.h:222
static void * vec_header(void *v, uword header_bytes)
Find a user vector header.
Definition: vec_bootstrap.h:92
struct _unformat_input_t unformat_input_t
uword string_key_sum(hash_t *h, uword key)
Definition: hash.c:875
#define BITS(x)
Definition: clib.h:58
uword vec_key_sum(hash_t *h, uword key)
Definition: hash.c:792
uword is_user[0]
Definition: hash.h:95
hash_key_sum_function_t * key_sum
Definition: hash.h:73
uword key
Definition: hash.h:161
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".