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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 Copyright (c) 2001-2005 Eliot Dresselhaus
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:
26 The above copyright notice and this permission notice shall be
27 included in all copies or substantial portions of the Software.
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.
38 #include <vppinfra/hash.h>
39 #include <vppinfra/error.h>
40 #include <vppinfra/mem.h>
41 #include <vppinfra/byte_order.h> /* for clib_arch_is_big_endian */
44 zero_pair (hash_t * h, hash_pair_t * p)
46 clib_memset (p, 0, hash_pair_bytes (h));
50 init_pair (hash_t * h, hash_pair_t * p)
52 clib_memset (p->value, ~0, hash_value_bytes (h));
55 always_inline hash_pair_union_t *
56 get_pair (void *v, uword i)
58 hash_t *h = hash_header (v);
60 ASSERT (i < vec_len (v));
62 p += i << h->log2_pair_size;
63 return (hash_pair_union_t *) p;
67 set_is_user (void *v, uword i, uword is_user)
69 hash_t *h = hash_header (v);
70 uword i0 = i / BITS (h->is_user[0]);
71 uword i1 = (uword) 1 << (i % BITS (h->is_user[0]));
75 h->is_user[i0] &= ~i1;
78 static u8 *hash_format_pair_default (u8 * s, va_list * args);
85 #define _(n) (((u64) 1 << (u64) (8*(n))) - (u64) 1)
86 static u64 masks_little_endian[] = {
87 0, _(1), _(2), _(3), _(4), _(5), _(6), _(7),
89 static u64 masks_big_endian[] = {
90 0, ~_(7), ~_(6), ~_(5), ~_(4), ~_(3), ~_(2), ~_(1),
93 if (clib_arch_is_big_endian)
94 return x & masks_big_endian[n];
96 return x & masks_little_endian[n];
100 * make address-sanitizer skip this:
101 * clib_mem_unaligned + zap64 casts its input as u64, computes a mask
102 * according to the input length, and returns the casted maked value.
103 * Therefore all the 8 Bytes of the u64 are systematically read, which
104 * rightfully causes address-sanitizer to raise an error on smaller inputs.
106 * However the invalid Bytes are discarded within zap64(), which is why
107 * this can be silenced safely.
109 * The above is true *unless* the extra bytes cross a page boundary
110 * into unmapped or no-access space, hence the boundary crossing check.
113 hash_memory64 (void *p, word n_bytes, u64 state)
117 int page_boundary_crossing;
118 u64 start_addr, end_addr;
126 * If the request crosses a 4k boundary, it's not OK to assume
127 * that the zap64 game is safe. 4k is the minimum known page size.
129 start_addr = (u64) p;
130 end_addr = start_addr + n_bytes + 7;
131 page_boundary_crossing = (start_addr >> 12) != (end_addr >> 12);
133 a = b = 0x9e3779b97f4a7c13LL;
137 while (n >= 3 * sizeof (u64))
139 a += clib_mem_unaligned (q + 0, u64);
140 b += clib_mem_unaligned (q + 1, u64);
141 c += clib_mem_unaligned (q + 2, u64);
142 hash_mix64 (a, b, c);
143 n -= 3 * sizeof (u64);
148 switch (n / sizeof (u64))
151 a += clib_mem_unaligned (q + 0, u64);
152 b += clib_mem_unaligned (q + 1, u64);
153 if (n % sizeof (u64))
155 if (PREDICT_TRUE (page_boundary_crossing == 0))
157 CLIB_MEM_OVERFLOW_PUSH (q + 2, sizeof (u64));
158 c += zap64 (clib_mem_unaligned (q + 2, u64), n % sizeof (u64))
160 CLIB_MEM_OVERFLOW_POP ();
164 clib_memcpy_fast (tmp.as_u8, q + 2, n % sizeof (u64));
165 c += zap64 (tmp.as_u64, n % sizeof (u64)) << 8;
171 a += clib_mem_unaligned (q + 0, u64);
172 if (n % sizeof (u64))
174 if (PREDICT_TRUE (page_boundary_crossing == 0))
176 CLIB_MEM_OVERFLOW_PUSH (q + 1, sizeof (u64));
177 b += zap64 (clib_mem_unaligned (q + 1, u64), n % sizeof (u64));
178 CLIB_MEM_OVERFLOW_POP ();
182 clib_memcpy_fast (tmp.as_u8, q + 1, n % sizeof (u64));
183 b += zap64 (tmp.as_u64, n % sizeof (u64));
189 if (n % sizeof (u64))
191 if (PREDICT_TRUE (page_boundary_crossing == 0))
193 CLIB_MEM_OVERFLOW_PUSH (q + 0, sizeof (u64));
194 a += zap64 (clib_mem_unaligned (q + 0, u64), n % sizeof (u64));
195 CLIB_MEM_OVERFLOW_POP ();
199 clib_memcpy_fast (tmp.as_u8, q, n % sizeof (u64));
200 a += zap64 (tmp.as_u64, n % sizeof (u64));
206 hash_mix64 (a, b, c);
211 #else /* if uword_bits == 64 */
214 zap32 (u32 x, word n)
216 #define _(n) (((u32) 1 << (u32) (8*(n))) - (u32) 1)
217 static u32 masks_little_endian[] = {
220 static u32 masks_big_endian[] = {
221 0, ~_(3), ~_(2), ~_(1),
224 if (clib_arch_is_big_endian)
225 return x & masks_big_endian[n];
227 return x & masks_little_endian[n];
231 hash_memory32 (void *p, word n_bytes, u32 state)
240 while (n >= 3 * sizeof (u32))
242 a += clib_mem_unaligned (q + 0, u32);
243 b += clib_mem_unaligned (q + 1, u32);
244 c += clib_mem_unaligned (q + 2, u32);
245 hash_mix32 (a, b, c);
246 n -= 3 * sizeof (u32);
251 switch (n / sizeof (u32))
254 a += clib_mem_unaligned (q + 0, u32);
255 b += clib_mem_unaligned (q + 1, u32);
256 if (n % sizeof (u32))
257 c += zap32 (clib_mem_unaligned (q + 2, u32), n % sizeof (u32)) << 8;
261 a += clib_mem_unaligned (q + 0, u32);
262 if (n % sizeof (u32))
263 b += zap32 (clib_mem_unaligned (q + 1, u32), n % sizeof (u32));
267 if (n % sizeof (u32))
268 a += zap32 (clib_mem_unaligned (q + 0, u32), n % sizeof (u32));
272 hash_mix32 (a, b, c);
279 hash_memory (void *p, word n_bytes, uword state)
284 return hash_memory64 (q, n_bytes, state);
286 return hash_memory32 (q, n_bytes, state);
296 a = b = 0x9e3779b97f4a7c13LL;
299 hash_mix64 (a, b, c);
311 hash_mix32 (a, b, c);
316 /* Call sum function. Hash code will be sum function value
317 modulo the prime length of the hash table. */
319 key_sum (hash_t * h, uword key)
322 switch (pointer_to_uword ((void *) h->key_sum))
325 sum = hash_uword (key);
328 case KEY_FUNC_POINTER_UWORD:
329 sum = hash_uword (*uword_to_pointer (key, uword *));
332 case KEY_FUNC_POINTER_U32:
333 sum = hash_uword (*uword_to_pointer (key, u32 *));
336 case KEY_FUNC_STRING:
337 sum = string_key_sum (h, key);
341 sum = mem_key_sum (h, key);
345 sum = h->key_sum (h, key);
353 key_equal1 (hash_t * h, uword key1, uword key2, uword e)
355 switch (pointer_to_uword ((void *) h->key_equal))
360 case KEY_FUNC_POINTER_UWORD:
362 *uword_to_pointer (key1, uword *) == *uword_to_pointer (key2,
366 case KEY_FUNC_POINTER_U32:
367 e = *uword_to_pointer (key1, u32 *) == *uword_to_pointer (key2, u32 *);
370 case KEY_FUNC_STRING:
371 e = string_key_equal (h, key1, key2);
375 e = mem_key_equal (h, key1, key2);
379 e = h->key_equal (h, key1, key2);
385 /* Compares two keys: returns 1 if equal, 0 if not. */
387 key_equal (hash_t * h, uword key1, uword key2)
389 uword e = key1 == key2;
390 if (CLIB_DEBUG > 0 && key1 == key2)
391 ASSERT (key_equal1 (h, key1, key2, e));
393 e = key_equal1 (h, key1, key2, e);
397 static hash_pair_union_t *
398 get_indirect (void *v, hash_pair_indirect_t * pi, uword key)
400 hash_t *h = hash_header (v);
401 hash_pair_t *p0, *p1;
404 if (h->log2_pair_size > 0)
405 p1 = hash_forward (h, p0, indirect_pair_get_len (pi));
411 if (key_equal (h, p0->key, key))
412 return (hash_pair_union_t *) p0;
413 p0 = hash_forward1 (h, p0);
416 return (hash_pair_union_t *) 0;
419 static hash_pair_union_t *
420 set_indirect_is_user (void *v, uword i, hash_pair_union_t * p, uword key)
422 hash_t *h = hash_header (v);
424 hash_pair_indirect_t *pi = &p->indirect;
425 uword log2_bytes = 0;
427 if (h->log2_pair_size == 0)
428 q = vec_new (hash_pair_t, 2);
431 log2_bytes = 1 + hash_pair_log2_bytes (h);
432 q = clib_mem_alloc (1ULL << log2_bytes);
434 clib_memcpy_fast (q, &p->direct, hash_pair_bytes (h));
437 if (h->log2_pair_size > 0)
438 indirect_pair_set (pi, log2_bytes, 2);
440 set_is_user (v, i, 0);
442 /* First element is used by existing pair, second will be used by caller. */
443 q = hash_forward1 (h, q);
446 return (hash_pair_union_t *) q;
449 static hash_pair_union_t *
450 set_indirect (void *v, hash_pair_indirect_t * pi, uword key,
453 hash_t *h = hash_header (v);
454 hash_pair_t *new_pair;
455 hash_pair_union_t *q;
457 q = get_indirect (v, pi, key);
464 if (h->log2_pair_size == 0)
465 vec_add2 (pi->pairs, new_pair, 1);
468 uword len, new_len, log2_bytes;
470 len = indirect_pair_get_len (pi);
471 log2_bytes = indirect_pair_get_log2_bytes (pi);
474 if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes))
476 pi->pairs = clib_mem_realloc (pi->pairs,
477 1ULL << (log2_bytes + 1),
482 indirect_pair_set (pi, log2_bytes, new_len);
483 new_pair = pi->pairs + (len << h->log2_pair_size);
486 init_pair (h, new_pair);
488 return (hash_pair_union_t *) new_pair;
492 unset_indirect (void *v, uword i, hash_pair_t * q)
494 hash_t *h = hash_header (v);
495 hash_pair_union_t *p = get_pair (v, i);
497 hash_pair_indirect_t *pi = &p->indirect;
500 is_vec = h->log2_pair_size == 0;
502 ASSERT (!hash_is_user (v, i));
503 len = is_vec ? vec_len (pi->pairs) : indirect_pair_get_len (pi);
504 e = hash_forward (h, pi->pairs, len - 1);
505 ASSERT (q >= pi->pairs && q <= e);
507 /* We have two or fewer pairs and we are delete one pair.
508 Make indirect pointer direct and free indirect memory. */
511 hash_pair_t *r = pi->pairs;
515 clib_memcpy_fast (p, q == r ? hash_forward1 (h, r) : r,
516 hash_pair_bytes (h));
517 set_is_user (v, i, 1);
520 zero_pair (h, &p->direct);
529 /* If deleting a pair we need to keep non-null pairs together. */
531 clib_memcpy_fast (q, e, hash_pair_bytes (h));
535 _vec_len (pi->pairs) -= 1;
537 indirect_pair_set (pi, indirect_pair_get_log2_bytes (pi), len - 1);
549 lookup (void *v, uword key, enum lookup_opcode op,
550 void *new_value, void *old_value)
552 hash_t *h = hash_header (v);
553 hash_pair_union_t *p = 0;
561 i = key_sum (h, key) & (_vec_len (v) - 1);
563 value_bytes = hash_value_bytes (h);
565 if (hash_is_user (v, i))
567 found_key = key_equal (h, p->direct.key, key);
572 set_is_user (v, i, 0);
573 if (old_value && value_bytes)
574 clib_memcpy_fast (old_value, p->direct.value, value_bytes);
575 zero_pair (h, &p->direct);
581 p = set_indirect_is_user (v, i, p, key);
588 hash_pair_indirect_t *pi = &p->indirect;
595 set_is_user (v, i, 1);
598 p = set_indirect (v, pi, key, &found_key);
602 p = get_indirect (v, pi, key);
604 if (found_key && op == UNSET)
606 if (old_value && value_bytes)
607 clib_memcpy_fast (old_value, &p->direct.value, value_bytes);
609 unset_indirect (v, i, &p->direct);
611 /* Nullify p (since it's just been deleted).
612 Otherwise we might be tempted to play with it. */
618 if (op == SET && p != 0 && value_bytes)
620 /* Save away old value for caller. */
621 if (old_value && found_key)
622 clib_memcpy_fast (old_value, &p->direct.value, value_bytes);
623 clib_memcpy_fast (&p->direct.value, new_value, value_bytes);
627 h->elts += !found_key;
629 h->elts -= found_key;
634 /* Fetch value of key. */
635 __clib_export uword *
636 _hash_get (void *v, uword key)
638 hash_t *h = hash_header (v);
641 /* Don't even search table if its empty. */
642 if (!v || h->elts == 0)
645 p = lookup (v, key, GET, 0, 0);
648 if (h->log2_pair_size == 0)
654 __clib_export hash_pair_t *
655 _hash_get_pair (void *v, uword key)
657 return lookup (v, key, GET, 0, 0);
660 __clib_export hash_pair_t *
661 hash_next (void *v, hash_next_t *hn)
663 hash_t *h = hash_header (v);
668 if (hn->i == 0 && hn->j == 0)
673 /* Prevent others from re-sizing hash table. */
675 (HASH_FLAG_NO_AUTO_GROW
676 | HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_HASH_NEXT_IN_PROGRESS);
678 else if (hn->i >= hash_capacity (v))
682 clib_memset (hn, 0, sizeof (hn[0]));
686 p = hash_forward (h, v, hn->i);
687 if (hash_is_user (v, hn->i))
694 hash_pair_indirect_t *pi = (void *) p;
697 if (h->log2_pair_size > 0)
698 n = indirect_pair_get_len (pi);
700 n = vec_len (pi->pairs);
708 return hash_forward (h, pi->pairs, hn->j++);
713 /* Remove key from table. */
715 _hash_unset (void *v, uword key, void *old_value)
722 (void) lookup (v, key, UNSET, 0, old_value);
725 if (!(h->flags & HASH_FLAG_NO_AUTO_SHRINK))
727 /* Resize when 1/4 full. */
728 if (h->elts > 32 && 4 * (h->elts + 1) < vec_len (v))
729 v = hash_resize (v, vec_len (v) / 2);
736 _hash_create (uword elts, hash_t * h_user)
739 uword log2_pair_size;
742 /* Size of hash is power of 2 >= ELTS and larger than
743 number of bits in is_user bitmap elements. */
744 elts = clib_max (elts, BITS (h->is_user[0]));
745 elts = 1ULL << max_log2 (elts);
749 log2_pair_size = h_user->log2_pair_size;
751 v = _vec_resize ((void *) 0,
754 (elts << log2_pair_size) * sizeof (hash_pair_t),
757 /* alignment */ sizeof (hash_pair_t));
766 vec_validate_aligned (
767 h->is_user, ((elts / BITS (h->is_user[0])) * sizeof (h->is_user[0])) - 1,
768 CLIB_CACHE_LINE_BYTES);
769 h->log2_pair_size = log2_pair_size;
772 /* Default flags to never shrinking hash tables.
773 Shrinking tables can cause "jackpot" cases. */
775 h->flags = HASH_FLAG_NO_AUTO_SHRINK;
779 h->format_pair = hash_format_pair_default;
780 h->format_pair_arg = 0;
789 hash_t *h = hash_header (v);
790 hash_pair_union_t *p;
796 /* We zero all freed memory in case user would be tempted to use it. */
797 for (i = 0; i < hash_capacity (v); i++)
799 if (hash_is_user (v, i))
802 if (h->log2_pair_size == 0)
803 vec_free (p->indirect.pairs);
804 else if (p->indirect.pairs)
805 clib_mem_free (p->indirect.pairs);
808 vec_free (h->is_user);
815 hash_resize_internal (void *old, uword new_size, uword free_old)
823 hash_t *h = old ? hash_header (old) : 0;
824 new = _hash_create (new_size, h);
826 hash_foreach_pair (p, old, {
827 new = _hash_set3 (new, p->key, &p->value[0], 0);
838 hash_resize (void *old, uword new_size)
840 return hash_resize_internal (old, new_size, 1);
846 return hash_resize_internal (old, vec_len (old), 0);
850 _hash_set3 (void *v, uword key, void *value, void *old_value)
855 v = hash_create (0, sizeof (uword));
858 (void) lookup (v, key, SET, value, old_value);
860 if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
862 /* Resize when 3/4 full. */
863 if (4 * (h->elts + 1) > 3 * vec_len (v))
864 v = hash_resize (v, 2 * vec_len (v));
871 vec_key_sum (hash_t * h, uword key)
873 void *v = uword_to_pointer (key, void *);
874 return hash_memory (v, vec_len (v) * h->user, 0);
878 vec_key_equal (hash_t * h, uword key1, uword key2)
880 void *v1 = uword_to_pointer (key1, void *);
881 void *v2 = uword_to_pointer (key2, void *);
882 uword l1 = vec_len (v1);
883 uword l2 = vec_len (v2);
884 return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user);
888 vec_key_format_pair (u8 * s, va_list * args)
890 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
891 void *v = va_arg (*args, void *);
892 hash_pair_t *p = va_arg (*args, hash_pair_t *);
893 hash_t *h = hash_header (v);
894 void *u = uword_to_pointer (p->key, void *);
900 s = format (s, "%v", u);
906 for (i = 0; i < vec_len (w); i++)
907 s = format (s, "0x%x, ", w[i]);
914 for (i = 0; i < vec_len (w); i++)
915 s = format (s, "0x%x, ", w[i]);
922 for (i = 0; i < vec_len (w); i++)
923 s = format (s, "0x%Lx, ", w[i]);
928 s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
932 if (hash_value_bytes (h) > 0)
933 s = format (s, " -> 0x%wx", p->value[0]);
939 mem_key_sum (hash_t * h, uword key)
941 uword *v = uword_to_pointer (key, void *);
942 return hash_memory (v, h->user, 0);
946 mem_key_equal (hash_t * h, uword key1, uword key2)
948 void *v1 = uword_to_pointer (key1, void *);
949 void *v2 = uword_to_pointer (key2, void *);
950 return v1 && v2 && 0 == memcmp (v1, v2, h->user);
954 string_key_sum (hash_t * h, uword key)
956 char *v = uword_to_pointer (key, char *);
957 return hash_memory (v, strlen (v), 0);
961 string_key_equal (hash_t * h, uword key1, uword key2)
963 void *v1 = uword_to_pointer (key1, void *);
964 void *v2 = uword_to_pointer (key2, void *);
965 return v1 && v2 && 0 == strcmp (v1, v2);
969 string_key_format_pair (u8 * s, va_list * args)
971 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
972 void *v = va_arg (*args, void *);
973 hash_pair_t *p = va_arg (*args, hash_pair_t *);
974 hash_t *h = hash_header (v);
975 void *u = uword_to_pointer (p->key, void *);
977 s = format (s, "%s", u);
979 if (hash_value_bytes (h) > 0)
981 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
982 hash_value_bytes (h));
988 hash_format_pair_default (u8 * s, va_list * args)
990 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
991 void *v = va_arg (*args, void *);
992 hash_pair_t *p = va_arg (*args, hash_pair_t *);
993 hash_t *h = hash_header (v);
995 s = format (s, "0x%08x", p->key);
996 if (hash_value_bytes (h) > 0)
998 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
999 hash_value_bytes (h));
1004 hash_bytes (void *v)
1007 hash_t *h = hash_header (v);
1012 bytes = vec_mem_size (v, hash_header_bytes (v));
1014 for (i = 0; i < hash_capacity (v); i++)
1016 if (!hash_is_user (v, i))
1018 hash_pair_union_t *p = get_pair (v, i);
1019 if (h->log2_pair_size > 0)
1020 bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect);
1022 bytes += vec_mem_size (p->indirect.pairs, 0);
1029 format_hash (u8 *s, va_list *va)
1031 void *v = va_arg (*va, void *);
1032 int verbose = va_arg (*va, int);
1034 hash_t *h = hash_header (v);
1037 s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
1038 v, hash_elts (v), hash_capacity (v), hash_bytes (v));
1041 uword *occupancy = 0;
1043 /* Count number of buckets with each occupancy. */
1044 for (i = 0; i < hash_capacity (v); i++)
1048 if (hash_is_user (v, i))
1054 hash_pair_union_t *p = get_pair (v, i);
1055 if (h->log2_pair_size > 0)
1056 j = indirect_pair_get_len (&p->indirect);
1058 j = vec_len (p->indirect.pairs);
1061 vec_validate (occupancy, j);
1065 s = format (s, " profile ");
1066 for (i = 0; i < vec_len (occupancy); i++)
1067 s = format (s, "%wd%c", occupancy[i],
1068 i + 1 == vec_len (occupancy) ? '\n' : ' ');
1070 s = format (s, " lookup # of compares: ");
1071 for (i = 1; i < vec_len (occupancy); i++)
1072 s = format (s, "%wd: .%03d%c", i,
1073 (1000 * i * occupancy[i]) / hash_elts (v),
1074 i + 1 == vec_len (occupancy) ? '\n' : ' ');
1076 vec_free (occupancy);
1082 hash_foreach_pair (p, v, {
1083 s = format (s, " %U\n", h->format_pair, h->format_pair_arg, v, p);
1092 unformat_hash_string_internal (unformat_input_t * input,
1093 va_list * va, int is_vec)
1095 uword *hash = va_arg (*va, uword *);
1096 int *result = va_arg (*va, int *);
1100 if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
1103 p = hash_get_mem (hash, string);
1112 unformat_hash_vec_string (unformat_input_t * input, va_list * va)
1114 return unformat_hash_string_internal (input, va, /* is_vec */ 1);
1118 unformat_hash_string (unformat_input_t * input, va_list * va)
1120 return unformat_hash_string_internal (input, va, /* is_vec */ 0);
1123 __clib_export clib_error_t *
1124 hash_validate (void *v)
1126 hash_t *h = hash_header (v);
1129 clib_error_t *error = 0;
1131 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
1133 for (i = 0; i < hash_capacity (v); i++)
1135 hash_pair_union_t *pu = get_pair (v, i);
1137 if (hash_is_user (v, i))
1139 CHECK (pu->direct.key != 0);
1140 vec_add1 (keys, pu->direct.key);
1145 hash_pair_indirect_t *pi = &pu->indirect;
1148 n = h->log2_pair_size > 0
1149 ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
1151 for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
1153 /* Assert key uniqueness. */
1154 for (j = 0; j < vec_len (keys); j++)
1155 CHECK (keys[j] != p->key);
1156 vec_add1 (keys, p->key);
1161 CHECK (vec_len (keys) == h->elts);
1169 * fd.io coding-style-patch-verification: ON
1172 * eval: (c-set-style "gnu")