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 zap64 (CLIB_MEM_OVERFLOW
158 (clib_mem_unaligned (q + 2, u64), q + 2, sizeof (u64)),
159 n % sizeof (u64)) << 8;
162 clib_memcpy_fast (tmp.as_u8, q + 2, n % sizeof (u64));
163 c += zap64 (tmp.as_u64, n % sizeof (u64)) << 8;
169 a += clib_mem_unaligned (q + 0, u64);
170 if (n % sizeof (u64))
172 if (PREDICT_TRUE (page_boundary_crossing == 0))
174 zap64 (CLIB_MEM_OVERFLOW
175 (clib_mem_unaligned (q + 1, u64), q + 1, sizeof (u64)),
179 clib_memcpy_fast (tmp.as_u8, q + 1, n % sizeof (u64));
180 b += zap64 (tmp.as_u64, n % sizeof (u64));
186 if (n % sizeof (u64))
188 if (PREDICT_TRUE (page_boundary_crossing == 0))
190 zap64 (CLIB_MEM_OVERFLOW
191 (clib_mem_unaligned (q + 0, u64), q + 0, sizeof (u64)),
195 clib_memcpy_fast (tmp.as_u8, q, n % sizeof (u64));
196 a += zap64 (tmp.as_u64, n % sizeof (u64));
202 hash_mix64 (a, b, c);
207 #else /* if uword_bits == 64 */
210 zap32 (u32 x, word n)
212 #define _(n) (((u32) 1 << (u32) (8*(n))) - (u32) 1)
213 static u32 masks_little_endian[] = {
216 static u32 masks_big_endian[] = {
217 0, ~_(3), ~_(2), ~_(1),
220 if (clib_arch_is_big_endian)
221 return x & masks_big_endian[n];
223 return x & masks_little_endian[n];
227 hash_memory32 (void *p, word n_bytes, u32 state)
236 while (n >= 3 * sizeof (u32))
238 a += clib_mem_unaligned (q + 0, u32);
239 b += clib_mem_unaligned (q + 1, u32);
240 c += clib_mem_unaligned (q + 2, u32);
241 hash_mix32 (a, b, c);
242 n -= 3 * sizeof (u32);
247 switch (n / sizeof (u32))
250 a += clib_mem_unaligned (q + 0, u32);
251 b += clib_mem_unaligned (q + 1, u32);
252 if (n % sizeof (u32))
253 c += zap32 (clib_mem_unaligned (q + 2, u32), n % sizeof (u32)) << 8;
257 a += clib_mem_unaligned (q + 0, u32);
258 if (n % sizeof (u32))
259 b += zap32 (clib_mem_unaligned (q + 1, u32), n % sizeof (u32));
263 if (n % sizeof (u32))
264 a += zap32 (clib_mem_unaligned (q + 0, u32), n % sizeof (u32));
268 hash_mix32 (a, b, c);
275 hash_memory (void *p, word n_bytes, uword state)
280 return hash_memory64 (q, n_bytes, state);
282 return hash_memory32 (q, n_bytes, state);
292 a = b = 0x9e3779b97f4a7c13LL;
295 hash_mix64 (a, b, c);
307 hash_mix32 (a, b, c);
312 /* Call sum function. Hash code will be sum function value
313 modulo the prime length of the hash table. */
315 key_sum (hash_t * h, uword key)
318 switch (pointer_to_uword ((void *) h->key_sum))
321 sum = hash_uword (key);
324 case KEY_FUNC_POINTER_UWORD:
325 sum = hash_uword (*uword_to_pointer (key, uword *));
328 case KEY_FUNC_POINTER_U32:
329 sum = hash_uword (*uword_to_pointer (key, u32 *));
332 case KEY_FUNC_STRING:
333 sum = string_key_sum (h, key);
337 sum = mem_key_sum (h, key);
341 sum = h->key_sum (h, key);
349 key_equal1 (hash_t * h, uword key1, uword key2, uword e)
351 switch (pointer_to_uword ((void *) h->key_equal))
356 case KEY_FUNC_POINTER_UWORD:
358 *uword_to_pointer (key1, uword *) == *uword_to_pointer (key2,
362 case KEY_FUNC_POINTER_U32:
363 e = *uword_to_pointer (key1, u32 *) == *uword_to_pointer (key2, u32 *);
366 case KEY_FUNC_STRING:
367 e = string_key_equal (h, key1, key2);
371 e = mem_key_equal (h, key1, key2);
375 e = h->key_equal (h, key1, key2);
381 /* Compares two keys: returns 1 if equal, 0 if not. */
383 key_equal (hash_t * h, uword key1, uword key2)
385 uword e = key1 == key2;
386 if (CLIB_DEBUG > 0 && key1 == key2)
387 ASSERT (key_equal1 (h, key1, key2, e));
389 e = key_equal1 (h, key1, key2, e);
393 static hash_pair_union_t *
394 get_indirect (void *v, hash_pair_indirect_t * pi, uword key)
396 hash_t *h = hash_header (v);
397 hash_pair_t *p0, *p1;
400 if (h->log2_pair_size > 0)
401 p1 = hash_forward (h, p0, indirect_pair_get_len (pi));
407 if (key_equal (h, p0->key, key))
408 return (hash_pair_union_t *) p0;
409 p0 = hash_forward1 (h, p0);
412 return (hash_pair_union_t *) 0;
415 static hash_pair_union_t *
416 set_indirect_is_user (void *v, uword i, hash_pair_union_t * p, uword key)
418 hash_t *h = hash_header (v);
420 hash_pair_indirect_t *pi = &p->indirect;
421 uword log2_bytes = 0;
423 if (h->log2_pair_size == 0)
424 q = vec_new (hash_pair_t, 2);
427 log2_bytes = 1 + hash_pair_log2_bytes (h);
428 q = clib_mem_alloc (1ULL << log2_bytes);
430 clib_memcpy_fast (q, &p->direct, hash_pair_bytes (h));
433 if (h->log2_pair_size > 0)
434 indirect_pair_set (pi, log2_bytes, 2);
436 set_is_user (v, i, 0);
438 /* First element is used by existing pair, second will be used by caller. */
439 q = hash_forward1 (h, q);
442 return (hash_pair_union_t *) q;
445 static hash_pair_union_t *
446 set_indirect (void *v, hash_pair_indirect_t * pi, uword key,
449 hash_t *h = hash_header (v);
450 hash_pair_t *new_pair;
451 hash_pair_union_t *q;
453 q = get_indirect (v, pi, key);
460 if (h->log2_pair_size == 0)
461 vec_add2 (pi->pairs, new_pair, 1);
464 uword len, new_len, log2_bytes;
466 len = indirect_pair_get_len (pi);
467 log2_bytes = indirect_pair_get_log2_bytes (pi);
470 if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes))
472 pi->pairs = clib_mem_realloc (pi->pairs,
473 1ULL << (log2_bytes + 1),
478 indirect_pair_set (pi, log2_bytes, new_len);
479 new_pair = pi->pairs + (len << h->log2_pair_size);
482 init_pair (h, new_pair);
484 return (hash_pair_union_t *) new_pair;
488 unset_indirect (void *v, uword i, hash_pair_t * q)
490 hash_t *h = hash_header (v);
491 hash_pair_union_t *p = get_pair (v, i);
493 hash_pair_indirect_t *pi = &p->indirect;
496 is_vec = h->log2_pair_size == 0;
498 ASSERT (!hash_is_user (v, i));
499 len = is_vec ? vec_len (pi->pairs) : indirect_pair_get_len (pi);
500 e = hash_forward (h, pi->pairs, len - 1);
501 ASSERT (q >= pi->pairs && q <= e);
503 /* We have two or fewer pairs and we are delete one pair.
504 Make indirect pointer direct and free indirect memory. */
507 hash_pair_t *r = pi->pairs;
511 clib_memcpy_fast (p, q == r ? hash_forward1 (h, r) : r,
512 hash_pair_bytes (h));
513 set_is_user (v, i, 1);
516 zero_pair (h, &p->direct);
525 /* If deleting a pair we need to keep non-null pairs together. */
527 clib_memcpy_fast (q, e, hash_pair_bytes (h));
531 _vec_len (pi->pairs) -= 1;
533 indirect_pair_set (pi, indirect_pair_get_log2_bytes (pi), len - 1);
545 lookup (void *v, uword key, enum lookup_opcode op,
546 void *new_value, void *old_value)
548 hash_t *h = hash_header (v);
549 hash_pair_union_t *p = 0;
556 i = key_sum (h, key) & (_vec_len (v) - 1);
559 if (hash_is_user (v, i))
561 found_key = key_equal (h, p->direct.key, key);
566 set_is_user (v, i, 0);
568 clib_memcpy_fast (old_value, p->direct.value,
569 hash_value_bytes (h));
570 zero_pair (h, &p->direct);
576 p = set_indirect_is_user (v, i, p, key);
583 hash_pair_indirect_t *pi = &p->indirect;
590 set_is_user (v, i, 1);
593 p = set_indirect (v, pi, key, &found_key);
597 p = get_indirect (v, pi, key);
599 if (found_key && op == UNSET)
602 clib_memcpy_fast (old_value, &p->direct.value,
603 hash_value_bytes (h));
605 unset_indirect (v, i, &p->direct);
607 /* Nullify p (since it's just been deleted).
608 Otherwise we might be tempted to play with it. */
614 if (op == SET && p != 0)
616 /* Save away old value for caller. */
617 if (old_value && found_key)
618 clib_memcpy_fast (old_value, &p->direct.value, hash_value_bytes (h));
619 clib_memcpy_fast (&p->direct.value, new_value, hash_value_bytes (h));
623 h->elts += !found_key;
625 h->elts -= found_key;
630 /* Fetch value of key. */
632 _hash_get (void *v, uword key)
634 hash_t *h = hash_header (v);
637 /* Don't even search table if its empty. */
638 if (!v || h->elts == 0)
641 p = lookup (v, key, GET, 0, 0);
644 if (h->log2_pair_size == 0)
651 _hash_get_pair (void *v, uword key)
653 return lookup (v, key, GET, 0, 0);
657 hash_next (void *v, hash_next_t * hn)
659 hash_t *h = hash_header (v);
664 if (hn->i == 0 && hn->j == 0)
669 /* Prevent others from re-sizing hash table. */
671 (HASH_FLAG_NO_AUTO_GROW
672 | HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_HASH_NEXT_IN_PROGRESS);
674 else if (hn->i >= hash_capacity (v))
678 clib_memset (hn, 0, sizeof (hn[0]));
682 p = hash_forward (h, v, hn->i);
683 if (hash_is_user (v, hn->i))
690 hash_pair_indirect_t *pi = (void *) p;
693 if (h->log2_pair_size > 0)
694 n = indirect_pair_get_len (pi);
696 n = vec_len (pi->pairs);
704 return hash_forward (h, pi->pairs, hn->j++);
709 /* Remove key from table. */
711 _hash_unset (void *v, uword key, void *old_value)
718 (void) lookup (v, key, UNSET, 0, old_value);
721 if (!(h->flags & HASH_FLAG_NO_AUTO_SHRINK))
723 /* Resize when 1/4 full. */
724 if (h->elts > 32 && 4 * (h->elts + 1) < vec_len (v))
725 v = hash_resize (v, vec_len (v) / 2);
732 _hash_create (uword elts, hash_t * h_user)
735 uword log2_pair_size;
738 /* Size of hash is power of 2 >= ELTS and larger than
739 number of bits in is_user bitmap elements. */
740 elts = clib_max (elts, BITS (h->is_user[0]));
741 elts = 1ULL << max_log2 (elts);
745 log2_pair_size = h_user->log2_pair_size;
747 v = _vec_resize ((void *) 0,
750 (elts << log2_pair_size) * sizeof (hash_pair_t),
753 (elts / BITS (h->is_user[0])) * sizeof (h->is_user[0]),
754 /* alignment */ sizeof (hash_pair_t));
760 h->log2_pair_size = log2_pair_size;
763 /* Default flags to never shrinking hash tables.
764 Shrinking tables can cause "jackpot" cases. */
766 h->flags = HASH_FLAG_NO_AUTO_SHRINK;
770 h->format_pair = hash_format_pair_default;
771 h->format_pair_arg = 0;
780 hash_t *h = hash_header (v);
781 hash_pair_union_t *p;
787 /* We zero all freed memory in case user would be tempted to use it. */
788 for (i = 0; i < hash_capacity (v); i++)
790 if (hash_is_user (v, i))
793 if (h->log2_pair_size == 0)
794 vec_free (p->indirect.pairs);
795 else if (p->indirect.pairs)
796 clib_mem_free (p->indirect.pairs);
805 hash_resize_internal (void *old, uword new_size, uword free_old)
813 hash_t *h = old ? hash_header (old) : 0;
814 new = _hash_create (new_size, h);
816 hash_foreach_pair (p, old, {
817 new = _hash_set3 (new, p->key, &p->value[0], 0);
828 hash_resize (void *old, uword new_size)
830 return hash_resize_internal (old, new_size, 1);
836 return hash_resize_internal (old, vec_len (old), 0);
840 _hash_set3 (void *v, uword key, void *value, void *old_value)
845 v = hash_create (0, sizeof (uword));
848 (void) lookup (v, key, SET, value, old_value);
850 if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
852 /* Resize when 3/4 full. */
853 if (4 * (h->elts + 1) > 3 * vec_len (v))
854 v = hash_resize (v, 2 * vec_len (v));
861 vec_key_sum (hash_t * h, uword key)
863 void *v = uword_to_pointer (key, void *);
864 return hash_memory (v, vec_len (v) * h->user, 0);
868 vec_key_equal (hash_t * h, uword key1, uword key2)
870 void *v1 = uword_to_pointer (key1, void *);
871 void *v2 = uword_to_pointer (key2, void *);
872 uword l1 = vec_len (v1);
873 uword l2 = vec_len (v2);
874 return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user);
878 vec_key_format_pair (u8 * s, va_list * args)
880 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
881 void *v = va_arg (*args, void *);
882 hash_pair_t *p = va_arg (*args, hash_pair_t *);
883 hash_t *h = hash_header (v);
884 void *u = uword_to_pointer (p->key, void *);
890 s = format (s, "%v", u);
896 for (i = 0; i < vec_len (w); i++)
897 s = format (s, "0x%x, ", w[i]);
904 for (i = 0; i < vec_len (w); i++)
905 s = format (s, "0x%x, ", w[i]);
912 for (i = 0; i < vec_len (w); i++)
913 s = format (s, "0x%Lx, ", w[i]);
918 s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
922 if (hash_value_bytes (h) > 0)
923 s = format (s, " -> 0x%wx", p->value[0]);
929 mem_key_sum (hash_t * h, uword key)
931 uword *v = uword_to_pointer (key, void *);
932 return hash_memory (v, h->user, 0);
936 mem_key_equal (hash_t * h, uword key1, uword key2)
938 void *v1 = uword_to_pointer (key1, void *);
939 void *v2 = uword_to_pointer (key2, void *);
940 return v1 && v2 && 0 == memcmp (v1, v2, h->user);
944 string_key_sum (hash_t * h, uword key)
946 char *v = uword_to_pointer (key, char *);
947 return hash_memory (v, strlen (v), 0);
951 string_key_equal (hash_t * h, uword key1, uword key2)
953 void *v1 = uword_to_pointer (key1, void *);
954 void *v2 = uword_to_pointer (key2, void *);
955 return v1 && v2 && 0 == strcmp (v1, v2);
959 string_key_format_pair (u8 * s, va_list * args)
961 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
962 void *v = va_arg (*args, void *);
963 hash_pair_t *p = va_arg (*args, hash_pair_t *);
964 hash_t *h = hash_header (v);
965 void *u = uword_to_pointer (p->key, void *);
967 s = format (s, "%s", u);
969 if (hash_value_bytes (h) > 0)
971 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
972 hash_value_bytes (h));
978 hash_format_pair_default (u8 * s, va_list * args)
980 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
981 void *v = va_arg (*args, void *);
982 hash_pair_t *p = va_arg (*args, hash_pair_t *);
983 hash_t *h = hash_header (v);
985 s = format (s, "0x%08x", p->key);
986 if (hash_value_bytes (h) > 0)
988 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
989 hash_value_bytes (h));
997 hash_t *h = hash_header (v);
1002 bytes = vec_capacity (v, hash_header_bytes (v));
1004 for (i = 0; i < hash_capacity (v); i++)
1006 if (!hash_is_user (v, i))
1008 hash_pair_union_t *p = get_pair (v, i);
1009 if (h->log2_pair_size > 0)
1010 bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect);
1012 bytes += vec_capacity (p->indirect.pairs, 0);
1019 format_hash (u8 * s, va_list * va)
1021 void *v = va_arg (*va, void *);
1022 int verbose = va_arg (*va, int);
1024 hash_t *h = hash_header (v);
1027 s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
1028 v, hash_elts (v), hash_capacity (v), hash_bytes (v));
1031 uword *occupancy = 0;
1033 /* Count number of buckets with each occupancy. */
1034 for (i = 0; i < hash_capacity (v); i++)
1038 if (hash_is_user (v, i))
1044 hash_pair_union_t *p = get_pair (v, i);
1045 if (h->log2_pair_size > 0)
1046 j = indirect_pair_get_len (&p->indirect);
1048 j = vec_len (p->indirect.pairs);
1051 vec_validate (occupancy, j);
1055 s = format (s, " profile ");
1056 for (i = 0; i < vec_len (occupancy); i++)
1057 s = format (s, "%wd%c", occupancy[i],
1058 i + 1 == vec_len (occupancy) ? '\n' : ' ');
1060 s = format (s, " lookup # of compares: ");
1061 for (i = 1; i < vec_len (occupancy); i++)
1062 s = format (s, "%wd: .%03d%c", i,
1063 (1000 * i * occupancy[i]) / hash_elts (v),
1064 i + 1 == vec_len (occupancy) ? '\n' : ' ');
1066 vec_free (occupancy);
1072 hash_foreach_pair (p, v, {
1073 s = format (s, " %U\n", h->format_pair, h->format_pair_arg, v, p);
1082 unformat_hash_string_internal (unformat_input_t * input,
1083 va_list * va, int is_vec)
1085 uword *hash = va_arg (*va, uword *);
1086 int *result = va_arg (*va, int *);
1090 if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
1093 p = hash_get_mem (hash, string);
1102 unformat_hash_vec_string (unformat_input_t * input, va_list * va)
1104 return unformat_hash_string_internal (input, va, /* is_vec */ 1);
1108 unformat_hash_string (unformat_input_t * input, va_list * va)
1110 return unformat_hash_string_internal (input, va, /* is_vec */ 0);
1114 hash_validate (void *v)
1116 hash_t *h = hash_header (v);
1119 clib_error_t *error = 0;
1121 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
1123 for (i = 0; i < hash_capacity (v); i++)
1125 hash_pair_union_t *pu = get_pair (v, i);
1127 if (hash_is_user (v, i))
1129 CHECK (pu->direct.key != 0);
1130 vec_add1 (keys, pu->direct.key);
1135 hash_pair_indirect_t *pi = &pu->indirect;
1138 n = h->log2_pair_size > 0
1139 ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
1141 for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
1143 /* Assert key uniqueness. */
1144 for (j = 0; j < vec_len (keys); j++)
1145 CHECK (keys[j] != p->key);
1146 vec_add1 (keys, p->key);
1151 CHECK (vec_len (keys) == h->elts);
1159 * fd.io coding-style-patch-verification: ON
1162 * eval: (c-set-style "gnu")