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