FD.io VPP  v18.04-17-g3a0d853
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 inline funcion allocate and copy key to use in hash for pointer key */
277 always_inline void
278 hash_set_mem_alloc (uword ** h, void *key, uword v)
279 {
280  size_t ksz = hash_header (*h)->user;
281  void *copy = clib_mem_alloc (ksz);
282  clib_memcpy (copy, key, ksz);
283  hash_set_mem (*h, copy, v);
284 }
285 
286 /* Public macro to set (key, 0) for pointer key */
287 #define hash_set1_mem(h,key) hash_set3 ((h), pointer_to_uword (key), 0, 0)
288 
289 /* Public macro to unset (key, value) for pointer key */
290 #define hash_unset_mem(h,key) ((h) = _hash_unset ((h), pointer_to_uword (key),0))
291 
292 /* Public inline funcion to unset pointer key and then free the key memory */
293 always_inline void
294 hash_unset_mem_free (uword ** h, void *key)
295 {
296  hash_pair_t *hp = hash_get_pair_mem (*h, key);
297  if (PREDICT_TRUE (hp != NULL))
298  {
299  key = uword_to_pointer (hp->key, void *);
300  hash_unset_mem (*h, key);
301  clib_mem_free (key);
302  }
303 }
304 
305 /* internal routine to free a hash table */
306 extern void *_hash_free (void *v);
307 
308 /* Public macro to free a hash table */
309 #define hash_free(h) (h) = _hash_free ((h))
310 
311 clib_error_t *hash_validate (void *v);
312 
313 /* Public inline funcion to get the number of value bytes for a hash table */
316 {
317  hash_pair_t *p;
318  return (sizeof (p->value[0]) << h->log2_pair_size) - sizeof (p->key);
319 }
320 
321 /* Public inline funcion to get log2(size of a (key,value) pair) */
324 {
325  uword log2_bytes = h->log2_pair_size;
326  ASSERT (BITS (hash_pair_t) == 32 || BITS (hash_pair_t) == 64);
327  if (BITS (hash_pair_t) == 32)
328  log2_bytes += 2;
329  else if (BITS (hash_pair_t) == 64)
330  log2_bytes += 3;
331  return log2_bytes;
332 }
333 
334 /* Public inline funcion to get size of a (key,value) pair */
337 {
338  return (uword) 1 << hash_pair_log2_bytes (h);
339 }
340 
341 /* Public inline funcion to advance a pointer past one (key,value) pair */
342 always_inline void *
343 hash_forward1 (hash_t * h, void *v)
344 {
345  return (u8 *) v + hash_pair_bytes (h);
346 }
347 
348 /* Public inline funcion to advance a pointer past N (key,value) pairs */
349 always_inline void *
350 hash_forward (hash_t * h, void *v, uword n)
351 {
352  return (u8 *) v + ((n * sizeof (hash_pair_t)) << h->log2_pair_size);
353 }
354 
355 /** Iterate over hash pairs.
356 
357  @param p The current (key,value) pair. This should be of type
358  <code>(hash_pair_t *)</code>.
359  @param v The hash table to iterate.
360  @param body The operation to perform on each (key,value) pair.
361 
362  Executes the expression or code block @c body with each active hash pair.
363 */
364 /* A previous version of this macro made use of the hash_pair_union_t
365  * structure; this version does not since that approach mightily upset
366  * the static analysis tool. In the rare chance someone is reading this
367  * code, pretend that _p below is of type hash_pair_union_t and that when
368  * used as an rvalue it's really using one of the union members as the
369  * rvalue. If you were confused before you might be marginally less
370  * confused after.
371  */
372 #define hash_foreach_pair(p,v,body) \
373 do { \
374  __label__ _hash_foreach_done; \
375  hash_t * _h = hash_header (v); \
376  void * _p; \
377  hash_pair_t * _q, * _q_end; \
378  uword _i, _i1, _id, _pair_increment; \
379  \
380  _p = (v); \
381  _i = 0; \
382  _pair_increment = 1; \
383  if ((v)) \
384  _pair_increment = 1 << _h->log2_pair_size; \
385  while (_i < hash_capacity (v)) \
386  { \
387  _id = _h->is_user[_i / BITS (_h->is_user[0])]; \
388  _i1 = _i + BITS (_h->is_user[0]); \
389  \
390  do { \
391  if (_id & 1) \
392  { \
393  _q = _p; \
394  _q_end = _q + _pair_increment; \
395  } \
396  else \
397  { \
398  hash_pair_indirect_t * _pi = _p; \
399  _q = _pi->pairs; \
400  if (_h->log2_pair_size > 0) \
401  _q_end = hash_forward (_h, _q, indirect_pair_get_len (_pi)); \
402  else \
403  _q_end = vec_end (_q); \
404  } \
405  \
406  /* Loop through all elements in bucket. \
407  Bucket may have 0 1 or more (indirect case) pairs. */ \
408  while (_q < _q_end) \
409  { \
410  uword _break_in_body = 1; \
411  (p) = _q; \
412  do { \
413  body; \
414  _break_in_body = 0; \
415  } while (0); \
416  if (_break_in_body) \
417  goto _hash_foreach_done; \
418  _q += _pair_increment; \
419  } \
420  \
421  _p = (hash_pair_t *)_p + _pair_increment; \
422  _id = _id / 2; \
423  _i++; \
424  } while (_i < _i1); \
425  } \
426  _hash_foreach_done: \
427  /* Be silent Mr. Compiler-Warning. */ \
428  ; \
429  } while (0)
430 
431 /* Iterate over key/value pairs
432 
433  @param key_var the current key
434  @param value_var the current value
435  @param h the hash table to iterate across
436  @param body the operation to perform on each (key_var,value_var) pair.
437 
438  calls body with each active hash pair
439 */
440 /* Iteratate over key/value pairs. */
441 #define hash_foreach(key_var,value_var,h,body) \
442 do { \
443  hash_pair_t * _r; \
444  hash_foreach_pair (_r, (h), { \
445  (key_var) = (__typeof__ (key_var)) _r->key; \
446  (value_var) = (__typeof__ (value_var)) _r->value[0]; \
447  do { body; } while (0); \
448  }); \
449 } while (0)
450 
451 /* Iterate over key/value pairs for pointer key hash tables
452 
453  @param key_var the current key
454  @param value_var the current value
455  @param h the hash table to iterate across
456  @param body the operation to perform on each (key_var,value_var) pair.
457 
458  calls body with each active hash pair
459 */
460 #define hash_foreach_mem(key_var,value_var,h,body) \
461 do { \
462  hash_pair_t * _r; \
463  hash_foreach_pair (_r, (h), { \
464  (key_var) = (__typeof__ (key_var)) uword_to_pointer (_r->key, void *); \
465  (value_var) = (__typeof__ (value_var)) _r->value[0]; \
466  do { body; } while (0); \
467  }); \
468 } while (0)
469 
470 /* Support for iteration through hash table. */
471 
472 /* This struct saves iteration state for hash_next.
473  None of these fields are meant to be visible to the user.
474  Hence, the cryptic short-hand names. */
475 typedef struct
476 {
477  uword i, j, f;
478 } hash_next_t;
479 
480 hash_pair_t *hash_next (void *v, hash_next_t * hn);
481 
482 void *_hash_create (uword elts, hash_t * h);
483 
484 always_inline void
486 {
487  hash_pair_t *p;
488  h->log2_pair_size =
489  max_log2 ((sizeof (p->key) + value_bytes + sizeof (p->key) -
490  1) / sizeof (p->key));
491 }
492 
493 #define hash_create2(_elts,_user,_value_bytes, \
494  _key_sum,_key_equal, \
495  _format_pair,_format_pair_arg) \
496 ({ \
497  hash_t _h; \
498  memset (&_h, 0, sizeof (_h)); \
499  _h.user = (_user); \
500  _h.key_sum = (hash_key_sum_function_t *) (_key_sum); \
501  _h.key_equal = (_key_equal); \
502  hash_set_value_bytes (&_h, (_value_bytes)); \
503  _h.format_pair = (format_function_t *) (_format_pair); \
504  _h.format_pair_arg = (_format_pair_arg); \
505  _hash_create ((_elts), &_h); \
506 })
507 
508 /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
509  Public domain per: http://www.burtleburtle.net/bob/hash/doobs.html
510  Thanks, Bob. */
511 
512 #define hash_mix_step(a,b,c,s0,s1,s2) \
513 do { \
514  (a) -= (b) + (c); (a) ^= (c) >> (s0); \
515  (b) -= (c) + (a); (b) ^= (a) << (s1); \
516  (c) -= (a) + (b); (c) ^= (b) >> (s2); \
517 } while (0)
518 
519 #define hash_mix32_step_1(a,b,c) hash_mix_step(a,b,c,13,8,13)
520 #define hash_mix32_step_2(a,b,c) hash_mix_step(a,b,c,12,16,5)
521 #define hash_mix32_step_3(a,b,c) hash_mix_step(a,b,c,3,10,15)
522 
523 #define hash_mix64_step_1(a,b,c) hash_mix_step(a,b,c,43,9,8)
524 #define hash_mix64_step_2(a,b,c) hash_mix_step(a,b,c,38,23,5)
525 #define hash_mix64_step_3(a,b,c) hash_mix_step(a,b,c,35,49,11)
526 #define hash_mix64_step_4(a,b,c) hash_mix_step(a,b,c,12,18,22)
527 
528 /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
529  Thanks, Bob. */
530 #define hash_mix64(a0,b0,c0) \
531 do { \
532  hash_mix64_step_1 (a0, b0, c0); \
533  hash_mix64_step_2 (a0, b0, c0); \
534  hash_mix64_step_3 (a0, b0, c0); \
535  hash_mix64_step_4 (a0, b0, c0); \
536 } while (0) \
537 
538 #define hash_mix32(a0,b0,c0) \
539 do { \
540  hash_mix32_step_1 (a0, b0, c0); \
541  hash_mix32_step_2 (a0, b0, c0); \
542  hash_mix32_step_3 (a0, b0, c0); \
543 } while (0) \
544 
545 /* Finalize from Bob Jenkins lookup3.c */
546 
549 {
550  return (x << i) | (x >> (BITS (i) - i));
551 }
552 
553 #define hash_v3_mix32(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  (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a); \
558  (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b); \
559  (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c); \
560  (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a); \
561 } while (0)
562 
563 #define hash_v3_finalize32(a,b,c) \
564 do { \
565  (c) ^= (b); (c) -= hash32_rotate_left ((b), 14); \
566  (a) ^= (c); (a) -= hash32_rotate_left ((c), 11); \
567  (b) ^= (a); (b) -= hash32_rotate_left ((a), 25); \
568  (c) ^= (b); (c) -= hash32_rotate_left ((b), 16); \
569  (a) ^= (c); (a) -= hash32_rotate_left ((c), 4); \
570  (b) ^= (a); (b) -= hash32_rotate_left ((a), 14); \
571  (c) ^= (b); (c) -= hash32_rotate_left ((b), 24); \
572 } while (0)
573 
574 /* 32 bit mixing/finalize in steps. */
575 
576 #define hash_v3_mix32_step1(a,b,c) \
577 do { \
578  (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b); \
579  (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c); \
580 } while (0)
581 
582 #define hash_v3_mix32_step2(a,b,c) \
583 do { \
584  (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a); \
585  (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b); \
586 } while (0)
587 
588 #define hash_v3_mix32_step3(a,b,c) \
589 do { \
590  (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c); \
591  (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a); \
592 } while (0)
593 
594 #define hash_v3_finalize32_step1(a,b,c) \
595 do { \
596  (c) ^= (b); (c) -= hash32_rotate_left ((b), 14); \
597  (a) ^= (c); (a) -= hash32_rotate_left ((c), 11); \
598 } while (0)
599 
600 #define hash_v3_finalize32_step2(a,b,c) \
601 do { \
602  (b) ^= (a); (b) -= hash32_rotate_left ((a), 25); \
603  (c) ^= (b); (c) -= hash32_rotate_left ((b), 16); \
604 } while (0)
605 
606 #define hash_v3_finalize32_step3(a,b,c) \
607 do { \
608  (a) ^= (c); (a) -= hash32_rotate_left ((c), 4); \
609  (b) ^= (a); (b) -= hash32_rotate_left ((a), 14); \
610  (c) ^= (b); (c) -= hash32_rotate_left ((b), 24); \
611 } while (0)
612 
613 /* Vector v3 mixing/finalize. */
614 #define hash_v3_mix_step_1_u32x(a,b,c) \
615 do { \
616  (a) -= (c); (a) ^= u32x_irotate_left ((c), 4); (c) += (b); \
617  (b) -= (a); (b) ^= u32x_irotate_left ((a), 6); (a) += (c); \
618  (c) -= (b); (c) ^= u32x_irotate_left ((b), 8); (b) += (a); \
619 } while (0)
620 
621 #define hash_v3_mix_step_2_u32x(a,b,c) \
622 do { \
623  (a) -= (c); (a) ^= u32x_irotate_left ((c),16); (c) += (b); \
624  (b) -= (a); (b) ^= u32x_irotate_left ((a),19); (a) += (c); \
625  (c) -= (b); (c) ^= u32x_irotate_left ((b), 4); (b) += (a); \
626 } while (0)
627 
628 #define hash_v3_finalize_step_1_u32x(a,b,c) \
629 do { \
630  (c) ^= (b); (c) -= u32x_irotate_left ((b), 14); \
631  (a) ^= (c); (a) -= u32x_irotate_left ((c), 11); \
632  (b) ^= (a); (b) -= u32x_irotate_left ((a), 25); \
633 } while (0)
634 
635 #define hash_v3_finalize_step_2_u32x(a,b,c) \
636 do { \
637  (c) ^= (b); (c) -= u32x_irotate_left ((b), 16); \
638  (a) ^= (c); (a) -= u32x_irotate_left ((c), 4); \
639  (b) ^= (a); (b) -= u32x_irotate_left ((a), 14); \
640  (c) ^= (b); (c) -= u32x_irotate_left ((b), 24); \
641 } while (0)
642 
643 #define hash_v3_mix_u32x(a,b,c) \
644 do { \
645  hash_v3_mix_step_1_u32x(a,b,c); \
646  hash_v3_mix_step_2_u32x(a,b,c); \
647 } while (0)
648 
649 #define hash_v3_finalize_u32x(a,b,c) \
650 do { \
651  hash_v3_finalize_step_1_u32x(a,b,c); \
652  hash_v3_finalize_step_2_u32x(a,b,c); \
653 } while (0)
654 
655 extern uword hash_memory (void *p, word n_bytes, uword state);
656 
657 extern uword mem_key_sum (hash_t * h, uword key);
658 extern uword mem_key_equal (hash_t * h, uword key1, uword key2);
659 
660 #define hash_create_mem(elts,key_bytes,value_bytes) \
661  hash_create2((elts),(key_bytes),(value_bytes),mem_key_sum,mem_key_equal,0,0)
662 
663 extern uword vec_key_sum (hash_t * h, uword key);
664 extern uword vec_key_equal (hash_t * h, uword key1, uword key2);
665 extern u8 *vec_key_format_pair (u8 * s, va_list * args);
666 
667 #define hash_create_vec(elts,key_bytes,value_bytes) \
668  hash_create2((elts),(key_bytes),(value_bytes),\
669  vec_key_sum,vec_key_equal,vec_key_format_pair,0)
670 
671 extern uword string_key_sum (hash_t * h, uword key);
672 extern uword string_key_equal (hash_t * h, uword key1, uword key2);
673 extern u8 *string_key_format_pair (u8 * s, va_list * args);
674 
675 #define hash_create_string(elts,value_bytes) \
676  hash_create2((elts),0,(value_bytes), \
677  (hash_key_sum_function_t *) KEY_FUNC_STRING, \
678  (hash_key_equal_function_t *)KEY_FUNC_STRING, \
679  0, 0)
680 
681 #define hash_create(elts,value_bytes) \
682  hash_create2((elts),0,(value_bytes), \
683  (hash_key_sum_function_t *) KEY_FUNC_NONE, \
684  (hash_key_equal_function_t *) KEY_FUNC_NONE, \
685  0,0)
686 
687 #define hash_create_uword(elts,value_bytes) \
688  hash_create2((elts),0,(value_bytes), \
689  (hash_key_sum_function_t *) KEY_FUNC_POINTER_UWORD, \
690  (hash_key_equal_function_t *) KEY_FUNC_POINTER_UWORD, \
691  0,0)
692 
693 #define hash_create_u32(elts,value_bytes) \
694  hash_create2((elts),0,(value_bytes), \
695  (hash_key_sum_function_t *) KEY_FUNC_POINTER_U32, \
696  (hash_key_equal_function_t *) KEY_FUNC_POINTER_U32, \
697  0,0)
698 
699 u8 *format_hash (u8 * s, va_list * va);
700 
701 /* Looks up input in hash table indexed by either vec string or
702  c string (null terminated). */
705 
706 /* Main test routine. */
707 int test_hash_main (unformat_input_t * input);
708 
709 #endif /* included_hash_h */
710 
711 /*
712  * fd.io coding-style-patch-verification: ON
713  *
714  * Local Variables:
715  * eval: (c-set-style "gnu")
716  * End:
717  */
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:1055
u8 pad[3]
log2 (size of the packing page block)
Definition: bihash_doc.h:61
uword hash_bytes(void *v)
Definition: hash.c:935
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:704
#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:190
#define NULL
Definition: clib.h:55
hash_pair_t * pairs
Definition: hash.h:175
u8 * format_hash(u8 *s, va_list *va)
Definition: hash.c:960
uword mem_key_sum(hash_t *h, uword key)
Definition: hash.c:870
uword j
Definition: hash.h:477
static void hash_set_value_bytes(hash_t *h, uword value_bytes)
Definition: hash.h:485
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:212
#define hash_set_mem(h, key, value)
Definition: hash.h:274
uword vec_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:809
#define hash_get_pair_mem(h, key)
Definition: hash.h:271
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:92
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:315
static hash_t * hash_header(void *v)
Definition: hash.h:110
#define hash_unset_mem(h, key)
Definition: hash.h:290
static uword hash_capacity(void *v)
Definition: hash.h:125
void * hash_dup(void *old)
Definition: hash.c:775
static uword hash_is_user(void *v, uword i)
Definition: hash.h:132
static uword hash_pair_bytes(hash_t *h)
Definition: hash.h:336
struct _unformat_input_t unformat_input_t
uword string_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:892
void * hash_resize(void *old, uword new_size)
Definition: hash.c:769
#define PAIR_BITS
Definition: hash.h:191
unformat_function_t unformat_hash_vec_string
Definition: hash.h:703
u32 flags
Definition: hash.h:59
word any
Definition: types.h:139
#define uword_to_pointer(u, type)
Definition: types.h:136
format_function_t * format_pair
Definition: hash.h:88
static uword hash_pair_log2_bytes(hash_t *h)
Definition: hash.h:323
hash_pair_indirect_t indirect
Definition: hash.h:187
static void * hash_forward1(hash_t *h, void *v)
Definition: hash.h:343
static void hash_set_pair_format(void *v, format_function_t *format_pair, void *format_pair_arg)
Definition: hash.h:142
#define clib_memcpy(a, b, c)
Definition: string.h:75
static uword hash32_rotate_left(u32 x, u32 i)
Definition: hash.h:548
u8 * string_key_format_pair(u8 *s, va_list *args)
Definition: hash.c:900
uword mem_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:877
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:350
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
u64 uword
Definition: types.h:112
hash_pair_t * hash_next(void *v, hash_next_t *hn)
Definition: hash.c:598
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:819
#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:236
static void hash_set_mem_alloc(uword **h, void *key, uword v)
Definition: hash.h:278
static void hash_unset_mem_free(uword **h, void *key)
Definition: hash.h:294
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:885
#define BITS(x)
Definition: clib.h:58
uword vec_key_sum(hash_t *h, uword key)
Definition: hash.c:802
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".