FD.io VPP  v17.07-30-g839fa73
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 
334  @param p The current (key,value) pair. This should be of type
335  <code>(hash_pair_t *)</code>.
336  @param v The hash table to iterate.
337  @param body The operation to perform on each (key,value) pair.
338 
339  Executes the expression or code block @c body with each active hash pair.
340 */
341 /* A previous version of this macro made use of the hash_pair_union_t
342  * structure; this version does not since that approach mightily upset
343  * the static analysis tool. In the rare chance someone is reading this
344  * code, pretend that _p below is of type hash_pair_union_t and that when
345  * used as an rvalue it's really using one of the union members as the
346  * rvalue. If you were confused before you might be marginally less
347  * confused after.
348  */
349 #define hash_foreach_pair(p,v,body) \
350 do { \
351  __label__ _hash_foreach_done; \
352  hash_t * _h = hash_header (v); \
353  void * _p; \
354  hash_pair_t * _q, * _q_end; \
355  uword _i, _i1, _id, _pair_increment; \
356  \
357  _p = (v); \
358  _i = 0; \
359  _pair_increment = 1; \
360  if ((v)) \
361  _pair_increment = 1 << _h->log2_pair_size; \
362  while (_i < hash_capacity (v)) \
363  { \
364  _id = _h->is_user[_i / BITS (_h->is_user[0])]; \
365  _i1 = _i + BITS (_h->is_user[0]); \
366  \
367  do { \
368  if (_id & 1) \
369  { \
370  _q = _p; \
371  _q_end = _q + _pair_increment; \
372  } \
373  else \
374  { \
375  hash_pair_indirect_t * _pi = _p; \
376  _q = _pi->pairs; \
377  if (_h->log2_pair_size > 0) \
378  _q_end = hash_forward (_h, _q, indirect_pair_get_len (_pi)); \
379  else \
380  _q_end = vec_end (_q); \
381  } \
382  \
383  /* Loop through all elements in bucket. \
384  Bucket may have 0 1 or more (indirect case) pairs. */ \
385  while (_q < _q_end) \
386  { \
387  uword _break_in_body = 1; \
388  (p) = _q; \
389  do { \
390  body; \
391  _break_in_body = 0; \
392  } while (0); \
393  if (_break_in_body) \
394  goto _hash_foreach_done; \
395  _q += _pair_increment; \
396  } \
397  \
398  _p = (hash_pair_t *)_p + _pair_increment; \
399  _id = _id / 2; \
400  _i++; \
401  } while (_i < _i1); \
402  } \
403  _hash_foreach_done: \
404  /* Be silent Mr. Compiler-Warning. */ \
405  ; \
406  } while (0)
407 
408 /* Iterate over key/value pairs
409 
410  @param key_var the current key
411  @param value_var the current value
412  @param h the hash table to iterate across
413  @param body the operation to perform on each (key_var,value_var) pair.
414 
415  calls body with each active hash pair
416 */
417 /* Iteratate over key/value pairs. */
418 #define hash_foreach(key_var,value_var,h,body) \
419 do { \
420  hash_pair_t * _r; \
421  hash_foreach_pair (_r, (h), { \
422  (key_var) = (__typeof__ (key_var)) _r->key; \
423  (value_var) = (__typeof__ (value_var)) _r->value[0]; \
424  do { body; } while (0); \
425  }); \
426 } while (0)
427 
428 /* Iterate over key/value pairs for pointer key hash tables
429 
430  @param key_var the current key
431  @param value_var the current value
432  @param h the hash table to iterate across
433  @param body the operation to perform on each (key_var,value_var) pair.
434 
435  calls body with each active hash pair
436 */
437 #define hash_foreach_mem(key_var,value_var,h,body) \
438 do { \
439  hash_pair_t * _r; \
440  hash_foreach_pair (_r, (h), { \
441  (key_var) = (__typeof__ (key_var)) uword_to_pointer (_r->key, void *); \
442  (value_var) = (__typeof__ (value_var)) _r->value[0]; \
443  do { body; } while (0); \
444  }); \
445 } while (0)
446 
447 /* Support for iteration through hash table. */
448 
449 /* This struct saves iteration state for hash_next.
450  None of these fields are meant to be visible to the user.
451  Hence, the cryptic short-hand names. */
452 typedef struct
453 {
454  uword i, j, f;
455 } hash_next_t;
456 
457 hash_pair_t *hash_next (void *v, hash_next_t * hn);
458 
459 void *_hash_create (uword elts, hash_t * h);
460 
461 always_inline void
463 {
464  hash_pair_t *p;
465  h->log2_pair_size =
466  max_log2 ((sizeof (p->key) + value_bytes + sizeof (p->key) -
467  1) / sizeof (p->key));
468 }
469 
470 #define hash_create2(_elts,_user,_value_bytes, \
471  _key_sum,_key_equal, \
472  _format_pair,_format_pair_arg) \
473 ({ \
474  hash_t _h; \
475  memset (&_h, 0, sizeof (_h)); \
476  _h.user = (_user); \
477  _h.key_sum = (hash_key_sum_function_t *) (_key_sum); \
478  _h.key_equal = (_key_equal); \
479  hash_set_value_bytes (&_h, (_value_bytes)); \
480  _h.format_pair = (format_function_t *) (_format_pair); \
481  _h.format_pair_arg = (_format_pair_arg); \
482  _hash_create ((_elts), &_h); \
483 })
484 
485 /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
486  Public domain per: http://www.burtleburtle.net/bob/hash/doobs.html
487  Thanks, Bob. */
488 
489 #define hash_mix_step(a,b,c,s0,s1,s2) \
490 do { \
491  (a) -= (b) + (c); (a) ^= (c) >> (s0); \
492  (b) -= (c) + (a); (b) ^= (a) << (s1); \
493  (c) -= (a) + (b); (c) ^= (b) >> (s2); \
494 } while (0)
495 
496 #define hash_mix32_step_1(a,b,c) hash_mix_step(a,b,c,13,8,13)
497 #define hash_mix32_step_2(a,b,c) hash_mix_step(a,b,c,12,16,5)
498 #define hash_mix32_step_3(a,b,c) hash_mix_step(a,b,c,3,10,15)
499 
500 #define hash_mix64_step_1(a,b,c) hash_mix_step(a,b,c,43,9,8)
501 #define hash_mix64_step_2(a,b,c) hash_mix_step(a,b,c,38,23,5)
502 #define hash_mix64_step_3(a,b,c) hash_mix_step(a,b,c,35,49,11)
503 #define hash_mix64_step_4(a,b,c) hash_mix_step(a,b,c,12,18,22)
504 
505 /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
506  Thanks, Bob. */
507 #define hash_mix64(a0,b0,c0) \
508 do { \
509  hash_mix64_step_1 (a0, b0, c0); \
510  hash_mix64_step_2 (a0, b0, c0); \
511  hash_mix64_step_3 (a0, b0, c0); \
512  hash_mix64_step_4 (a0, b0, c0); \
513 } while (0) \
514 
515 #define hash_mix32(a0,b0,c0) \
516 do { \
517  hash_mix32_step_1 (a0, b0, c0); \
518  hash_mix32_step_2 (a0, b0, c0); \
519  hash_mix32_step_3 (a0, b0, c0); \
520 } while (0) \
521 
522 /* Finalize from Bob Jenkins lookup3.c */
523 
526 {
527  return (x << i) | (x >> (BITS (i) - i));
528 }
529 
530 #define hash_v3_mix32(a,b,c) \
531 do { \
532  (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b); \
533  (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c); \
534  (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a); \
535  (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b); \
536  (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c); \
537  (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a); \
538 } while (0)
539 
540 #define hash_v3_finalize32(a,b,c) \
541 do { \
542  (c) ^= (b); (c) -= hash32_rotate_left ((b), 14); \
543  (a) ^= (c); (a) -= hash32_rotate_left ((c), 11); \
544  (b) ^= (a); (b) -= hash32_rotate_left ((a), 25); \
545  (c) ^= (b); (c) -= hash32_rotate_left ((b), 16); \
546  (a) ^= (c); (a) -= hash32_rotate_left ((c), 4); \
547  (b) ^= (a); (b) -= hash32_rotate_left ((a), 14); \
548  (c) ^= (b); (c) -= hash32_rotate_left ((b), 24); \
549 } while (0)
550 
551 /* 32 bit mixing/finalize in steps. */
552 
553 #define hash_v3_mix32_step1(a,b,c) \
554 do { \
555  (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b); \
556  (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c); \
557 } while (0)
558 
559 #define hash_v3_mix32_step2(a,b,c) \
560 do { \
561  (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a); \
562  (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b); \
563 } while (0)
564 
565 #define hash_v3_mix32_step3(a,b,c) \
566 do { \
567  (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c); \
568  (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a); \
569 } while (0)
570 
571 #define hash_v3_finalize32_step1(a,b,c) \
572 do { \
573  (c) ^= (b); (c) -= hash32_rotate_left ((b), 14); \
574  (a) ^= (c); (a) -= hash32_rotate_left ((c), 11); \
575 } while (0)
576 
577 #define hash_v3_finalize32_step2(a,b,c) \
578 do { \
579  (b) ^= (a); (b) -= hash32_rotate_left ((a), 25); \
580  (c) ^= (b); (c) -= hash32_rotate_left ((b), 16); \
581 } while (0)
582 
583 #define hash_v3_finalize32_step3(a,b,c) \
584 do { \
585  (a) ^= (c); (a) -= hash32_rotate_left ((c), 4); \
586  (b) ^= (a); (b) -= hash32_rotate_left ((a), 14); \
587  (c) ^= (b); (c) -= hash32_rotate_left ((b), 24); \
588 } while (0)
589 
590 /* Vector v3 mixing/finalize. */
591 #define hash_v3_mix_step_1_u32x(a,b,c) \
592 do { \
593  (a) -= (c); (a) ^= u32x_irotate_left ((c), 4); (c) += (b); \
594  (b) -= (a); (b) ^= u32x_irotate_left ((a), 6); (a) += (c); \
595  (c) -= (b); (c) ^= u32x_irotate_left ((b), 8); (b) += (a); \
596 } while (0)
597 
598 #define hash_v3_mix_step_2_u32x(a,b,c) \
599 do { \
600  (a) -= (c); (a) ^= u32x_irotate_left ((c),16); (c) += (b); \
601  (b) -= (a); (b) ^= u32x_irotate_left ((a),19); (a) += (c); \
602  (c) -= (b); (c) ^= u32x_irotate_left ((b), 4); (b) += (a); \
603 } while (0)
604 
605 #define hash_v3_finalize_step_1_u32x(a,b,c) \
606 do { \
607  (c) ^= (b); (c) -= u32x_irotate_left ((b), 14); \
608  (a) ^= (c); (a) -= u32x_irotate_left ((c), 11); \
609  (b) ^= (a); (b) -= u32x_irotate_left ((a), 25); \
610 } while (0)
611 
612 #define hash_v3_finalize_step_2_u32x(a,b,c) \
613 do { \
614  (c) ^= (b); (c) -= u32x_irotate_left ((b), 16); \
615  (a) ^= (c); (a) -= u32x_irotate_left ((c), 4); \
616  (b) ^= (a); (b) -= u32x_irotate_left ((a), 14); \
617  (c) ^= (b); (c) -= u32x_irotate_left ((b), 24); \
618 } while (0)
619 
620 #define hash_v3_mix_u32x(a,b,c) \
621 do { \
622  hash_v3_mix_step_1_u32x(a,b,c); \
623  hash_v3_mix_step_2_u32x(a,b,c); \
624 } while (0)
625 
626 #define hash_v3_finalize_u32x(a,b,c) \
627 do { \
628  hash_v3_finalize_step_1_u32x(a,b,c); \
629  hash_v3_finalize_step_2_u32x(a,b,c); \
630 } while (0)
631 
632 extern uword hash_memory (void *p, word n_bytes, uword state);
633 
634 extern uword mem_key_sum (hash_t * h, uword key);
635 extern uword mem_key_equal (hash_t * h, uword key1, uword key2);
636 
637 #define hash_create_mem(elts,key_bytes,value_bytes) \
638  hash_create2((elts),(key_bytes),(value_bytes),mem_key_sum,mem_key_equal,0,0)
639 
640 extern uword vec_key_sum (hash_t * h, uword key);
641 extern uword vec_key_equal (hash_t * h, uword key1, uword key2);
642 extern u8 *vec_key_format_pair (u8 * s, va_list * args);
643 
644 #define hash_create_vec(elts,key_bytes,value_bytes) \
645  hash_create2((elts),(key_bytes),(value_bytes),\
646  vec_key_sum,vec_key_equal,vec_key_format_pair,0)
647 
648 extern uword string_key_sum (hash_t * h, uword key);
649 extern uword string_key_equal (hash_t * h, uword key1, uword key2);
650 extern u8 *string_key_format_pair (u8 * s, va_list * args);
651 
652 #define hash_create_string(elts,value_bytes) \
653  hash_create2((elts),0,(value_bytes), \
654  (hash_key_sum_function_t *) KEY_FUNC_STRING, \
655  (hash_key_equal_function_t *)KEY_FUNC_STRING, \
656  0, 0)
657 
658 #define hash_create(elts,value_bytes) \
659  hash_create2((elts),0,(value_bytes), \
660  (hash_key_sum_function_t *) KEY_FUNC_NONE, \
661  (hash_key_equal_function_t *) KEY_FUNC_NONE, \
662  0,0)
663 
664 #define hash_create_uword(elts,value_bytes) \
665  hash_create2((elts),0,(value_bytes), \
666  (hash_key_sum_function_t *) KEY_FUNC_POINTER_UWORD, \
667  (hash_key_equal_function_t *) KEY_FUNC_POINTER_UWORD, \
668  0,0)
669 
670 #define hash_create_u32(elts,value_bytes) \
671  hash_create2((elts),0,(value_bytes), \
672  (hash_key_sum_function_t *) KEY_FUNC_POINTER_U32, \
673  (hash_key_equal_function_t *) KEY_FUNC_POINTER_U32, \
674  0,0)
675 
676 u8 *format_hash (u8 * s, va_list * va);
677 
678 /* Looks up input in hash table indexed by either vec string or
679  c string (null terminated). */
682 
683 /* Main test routine. */
684 int test_hash_main (unformat_input_t * input);
685 
686 #endif /* included_hash_h */
687 
688 /*
689  * fd.io coding-style-patch-verification: ON
690  *
691  * Local Variables:
692  * eval: (c-set-style "gnu")
693  * End:
694  */
uword( unformat_function_t)(unformat_input_t *input, va_list *args)
Definition: format.h:231
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:337
uword hash_bytes(void *v)
Definition: hash.c:925
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:681
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:454
static void hash_set_value_bytes(hash_t *h, uword value_bytes)
Definition: hash.h:462
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
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
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
struct _unformat_input_t unformat_input_t
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:680
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:525
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
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:228
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: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".