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 memset (p, 0, hash_pair_bytes (h));
50 init_pair (hash_t * h, hash_pair_t * p)
52 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 hash_memory64 (void *p, word n_bytes, u64 state)
105 a = b = 0x9e3779b97f4a7c13LL;
109 while (n >= 3 * sizeof (u64))
111 a += clib_mem_unaligned (q + 0, u64);
112 b += clib_mem_unaligned (q + 1, u64);
113 c += clib_mem_unaligned (q + 2, u64);
114 hash_mix64 (a, b, c);
115 n -= 3 * sizeof (u64);
120 switch (n / sizeof (u64))
123 a += clib_mem_unaligned (q + 0, u64);
124 b += clib_mem_unaligned (q + 1, u64);
125 if (n % sizeof (u64))
126 c += zap64 (clib_mem_unaligned (q + 2, u64), n % sizeof (u64)) << 8;
130 a += clib_mem_unaligned (q + 0, u64);
131 if (n % sizeof (u64))
132 b += zap64 (clib_mem_unaligned (q + 1, u64), n % sizeof (u64));
136 if (n % sizeof (u64))
137 a += zap64 (clib_mem_unaligned (q + 0, u64), n % sizeof (u64));
141 hash_mix64 (a, b, c);
146 #else /* if uword_bits == 64 */
149 zap32 (u32 x, word n)
151 #define _(n) (((u32) 1 << (u32) (8*(n))) - (u32) 1)
152 static u32 masks_little_endian[] = {
155 static u32 masks_big_endian[] = {
156 0, ~_(3), ~_(2), ~_(1),
159 if (clib_arch_is_big_endian)
160 return x & masks_big_endian[n];
162 return x & masks_little_endian[n];
166 hash_memory32 (void *p, word n_bytes, u32 state)
175 while (n >= 3 * sizeof (u32))
177 a += clib_mem_unaligned (q + 0, u32);
178 b += clib_mem_unaligned (q + 1, u32);
179 c += clib_mem_unaligned (q + 2, u32);
180 hash_mix32 (a, b, c);
181 n -= 3 * sizeof (u32);
186 switch (n / sizeof (u32))
189 a += clib_mem_unaligned (q + 0, u32);
190 b += clib_mem_unaligned (q + 1, u32);
191 if (n % sizeof (u32))
192 c += zap32 (clib_mem_unaligned (q + 2, u32), n % sizeof (u32)) << 8;
196 a += clib_mem_unaligned (q + 0, u32);
197 if (n % sizeof (u32))
198 b += zap32 (clib_mem_unaligned (q + 1, u32), n % sizeof (u32));
202 if (n % sizeof (u32))
203 a += zap32 (clib_mem_unaligned (q + 0, u32), n % sizeof (u32));
207 hash_mix32 (a, b, c);
214 hash_memory (void *p, word n_bytes, uword state)
219 return hash_memory64 (q, n_bytes, state);
221 return hash_memory32 (q, n_bytes, state);
231 a = b = 0x9e3779b97f4a7c13LL;
234 hash_mix64 (a, b, c);
246 hash_mix32 (a, b, c);
251 /* Call sum function. Hash code will be sum function value
252 modulo the prime length of the hash table. */
254 key_sum (hash_t * h, uword key)
257 switch (pointer_to_uword ((void *) h->key_sum))
260 sum = hash_uword (key);
263 case KEY_FUNC_POINTER_UWORD:
264 sum = hash_uword (*uword_to_pointer (key, uword *));
267 case KEY_FUNC_POINTER_U32:
268 sum = hash_uword (*uword_to_pointer (key, u32 *));
271 case KEY_FUNC_STRING:
272 sum = string_key_sum (h, key);
276 sum = h->key_sum (h, key);
284 key_equal1 (hash_t * h, uword key1, uword key2, uword e)
286 switch (pointer_to_uword ((void *) h->key_equal))
291 case KEY_FUNC_POINTER_UWORD:
293 *uword_to_pointer (key1, uword *) == *uword_to_pointer (key2,
297 case KEY_FUNC_POINTER_U32:
298 e = *uword_to_pointer (key1, u32 *) == *uword_to_pointer (key2, u32 *);
301 case KEY_FUNC_STRING:
302 e = string_key_equal (h, key1, key2);
306 e = h->key_equal (h, key1, key2);
312 /* Compares two keys: returns 1 if equal, 0 if not. */
314 key_equal (hash_t * h, uword key1, uword key2)
316 uword e = key1 == key2;
317 if (CLIB_DEBUG > 0 && key1 == key2)
318 ASSERT (key_equal1 (h, key1, key2, e));
320 e = key_equal1 (h, key1, key2, e);
324 static hash_pair_union_t *
325 get_indirect (void *v, hash_pair_indirect_t * pi, uword key)
327 hash_t *h = hash_header (v);
328 hash_pair_t *p0, *p1;
331 if (h->log2_pair_size > 0)
332 p1 = hash_forward (h, p0, indirect_pair_get_len (pi));
338 if (key_equal (h, p0->key, key))
339 return (hash_pair_union_t *) p0;
340 p0 = hash_forward1 (h, p0);
343 return (hash_pair_union_t *) 0;
346 static hash_pair_union_t *
347 set_indirect_is_user (void *v, uword i, hash_pair_union_t * p, uword key)
349 hash_t *h = hash_header (v);
351 hash_pair_indirect_t *pi = &p->indirect;
352 uword log2_bytes = 0;
354 if (h->log2_pair_size == 0)
355 q = vec_new (hash_pair_t, 2);
358 log2_bytes = 1 + hash_pair_log2_bytes (h);
359 q = clib_mem_alloc (1ULL << log2_bytes);
361 clib_memcpy (q, &p->direct, hash_pair_bytes (h));
364 if (h->log2_pair_size > 0)
365 indirect_pair_set (pi, log2_bytes, 2);
367 set_is_user (v, i, 0);
369 /* First element is used by existing pair, second will be used by caller. */
370 q = hash_forward1 (h, q);
373 return (hash_pair_union_t *) q;
376 static hash_pair_union_t *
377 set_indirect (void *v, hash_pair_indirect_t * pi, uword key,
380 hash_t *h = hash_header (v);
381 hash_pair_t *new_pair;
382 hash_pair_union_t *q;
384 q = get_indirect (v, pi, key);
391 if (h->log2_pair_size == 0)
392 vec_add2 (pi->pairs, new_pair, 1);
395 uword len, new_len, log2_bytes;
397 len = indirect_pair_get_len (pi);
398 log2_bytes = indirect_pair_get_log2_bytes (pi);
401 if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes))
403 pi->pairs = clib_mem_realloc (pi->pairs,
404 1ULL << (log2_bytes + 1),
409 indirect_pair_set (pi, log2_bytes, new_len);
410 new_pair = pi->pairs + (len << h->log2_pair_size);
413 init_pair (h, new_pair);
415 return (hash_pair_union_t *) new_pair;
419 unset_indirect (void *v, uword i, hash_pair_t * q)
421 hash_t *h = hash_header (v);
422 hash_pair_union_t *p = get_pair (v, i);
424 hash_pair_indirect_t *pi = &p->indirect;
427 is_vec = h->log2_pair_size == 0;
429 ASSERT (!hash_is_user (v, i));
430 len = is_vec ? vec_len (pi->pairs) : indirect_pair_get_len (pi);
431 e = hash_forward (h, pi->pairs, len - 1);
432 ASSERT (q >= pi->pairs && q <= e);
434 /* We have two or fewer pairs and we are delete one pair.
435 Make indirect pointer direct and free indirect memory. */
438 hash_pair_t *r = pi->pairs;
442 clib_memcpy (p, q == r ? hash_forward1 (h, r) : r,
443 hash_pair_bytes (h));
444 set_is_user (v, i, 1);
447 zero_pair (h, &p->direct);
456 /* If deleting a pair we need to keep non-null pairs together. */
458 clib_memcpy (q, e, hash_pair_bytes (h));
462 _vec_len (pi->pairs) -= 1;
464 indirect_pair_set (pi, indirect_pair_get_log2_bytes (pi), len - 1);
476 lookup (void *v, uword key, enum lookup_opcode op,
477 void *new_value, void *old_value)
479 hash_t *h = hash_header (v);
480 hash_pair_union_t *p = 0;
487 i = key_sum (h, key) & (_vec_len (v) - 1);
490 if (hash_is_user (v, i))
492 found_key = key_equal (h, p->direct.key, key);
497 set_is_user (v, i, 0);
499 clib_memcpy (old_value, p->direct.value,
500 hash_value_bytes (h));
501 zero_pair (h, &p->direct);
507 p = set_indirect_is_user (v, i, p, key);
514 hash_pair_indirect_t *pi = &p->indirect;
521 set_is_user (v, i, 1);
524 p = set_indirect (v, pi, key, &found_key);
528 p = get_indirect (v, pi, key);
530 if (found_key && op == UNSET)
533 clib_memcpy (old_value, &p->direct.value,
534 hash_value_bytes (h));
536 unset_indirect (v, i, &p->direct);
538 /* Nullify p (since it's just been deleted).
539 Otherwise we might be tempted to play with it. */
545 if (op == SET && p != 0)
547 /* Save away old value for caller. */
548 if (old_value && found_key)
549 clib_memcpy (old_value, &p->direct.value, hash_value_bytes (h));
550 clib_memcpy (&p->direct.value, new_value, hash_value_bytes (h));
554 h->elts += !found_key;
556 h->elts -= found_key;
561 /* Fetch value of key. */
563 _hash_get (void *v, uword key)
565 hash_t *h = hash_header (v);
568 /* Don't even search table if its empty. */
569 if (!v || h->elts == 0)
572 p = lookup (v, key, GET, 0, 0);
575 if (h->log2_pair_size == 0)
582 _hash_get_pair (void *v, uword key)
584 return lookup (v, key, GET, 0, 0);
588 hash_next (void *v, hash_next_t * hn)
590 hash_t *h = hash_header (v);
595 if (hn->i == 0 && hn->j == 0)
600 /* Prevent others from re-sizing hash table. */
602 (HASH_FLAG_NO_AUTO_GROW
603 | HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_HASH_NEXT_IN_PROGRESS);
605 else if (hn->i >= hash_capacity (v))
609 memset (hn, 0, sizeof (hn[0]));
613 p = hash_forward (h, v, hn->i);
614 if (hash_is_user (v, hn->i))
621 hash_pair_indirect_t *pi = (void *) p;
624 if (h->log2_pair_size > 0)
625 n = indirect_pair_get_len (pi);
627 n = vec_len (pi->pairs);
635 return hash_forward (h, pi->pairs, hn->j++);
640 /* Remove key from table. */
642 _hash_unset (void *v, uword key, void *old_value)
649 (void) lookup (v, key, UNSET, 0, old_value);
652 if (!(h->flags & HASH_FLAG_NO_AUTO_SHRINK))
654 /* Resize when 1/4 full. */
655 if (h->elts > 32 && 4 * (h->elts + 1) < vec_len (v))
656 v = hash_resize (v, vec_len (v) / 2);
663 _hash_create (uword elts, hash_t * h_user)
666 uword log2_pair_size;
669 /* Size of hash is power of 2 >= ELTS and larger than
670 number of bits in is_user bitmap elements. */
671 elts = clib_max (elts, BITS (h->is_user[0]));
672 elts = 1ULL << max_log2 (elts);
676 log2_pair_size = h_user->log2_pair_size;
681 (elts << log2_pair_size) * sizeof (hash_pair_t),
684 (elts / BITS (h->is_user[0])) * sizeof (h->is_user[0]),
685 /* alignment */ sizeof (hash_pair_t));
691 h->log2_pair_size = log2_pair_size;
694 /* Default flags to never shrinking hash tables.
695 Shrinking tables can cause "jackpot" cases. */
697 h->flags = HASH_FLAG_NO_AUTO_SHRINK;
701 h->format_pair = hash_format_pair_default;
702 h->format_pair_arg = 0;
711 hash_t *h = hash_header (v);
712 hash_pair_union_t *p;
718 /* We zero all freed memory in case user would be tempted to use it. */
719 for (i = 0; i < hash_capacity (v); i++)
721 if (hash_is_user (v, i))
724 if (h->log2_pair_size == 0)
725 vec_free (p->indirect.pairs);
726 else if (p->indirect.pairs)
727 clib_mem_free (p->indirect.pairs);
736 hash_resize_internal (void *old, uword new_size, uword free_old)
744 hash_t *h = old ? hash_header (old) : 0;
745 new = _hash_create (new_size, h);
747 hash_foreach_pair (p, old, {
748 new = _hash_set3 (new, p->key, &p->value[0], 0);
759 hash_resize (void *old, uword new_size)
761 return hash_resize_internal (old, new_size, 1);
767 return hash_resize_internal (old, vec_len (old), 0);
771 _hash_set3 (void *v, uword key, void *value, void *old_value)
776 v = hash_create (0, sizeof (uword));
779 (void) lookup (v, key, SET, value, old_value);
781 if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
783 /* Resize when 3/4 full. */
784 if (4 * (h->elts + 1) > 3 * vec_len (v))
785 v = hash_resize (v, 2 * vec_len (v));
792 vec_key_sum (hash_t * h, uword key)
794 void *v = uword_to_pointer (key, void *);
795 return hash_memory (v, vec_len (v) * h->user, 0);
799 vec_key_equal (hash_t * h, uword key1, uword key2)
801 void *v1 = uword_to_pointer (key1, void *);
802 void *v2 = uword_to_pointer (key2, void *);
803 uword l1 = vec_len (v1);
804 uword l2 = vec_len (v2);
805 return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user);
809 vec_key_format_pair (u8 * s, va_list * args)
811 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
812 void *v = va_arg (*args, void *);
813 hash_pair_t *p = va_arg (*args, hash_pair_t *);
814 hash_t *h = hash_header (v);
815 void *u = uword_to_pointer (p->key, void *);
821 s = format (s, "%v", u);
827 for (i = 0; i < vec_len (w); i++)
828 s = format (s, "0x%x, ", w[i]);
835 for (i = 0; i < vec_len (w); i++)
836 s = format (s, "0x%x, ", w[i]);
843 for (i = 0; i < vec_len (w); i++)
844 s = format (s, "0x%Lx, ", w[i]);
849 s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
853 if (hash_value_bytes (h) > 0)
854 s = format (s, " -> 0x%wx", p->value[0]);
860 mem_key_sum (hash_t * h, uword key)
862 uword *v = uword_to_pointer (key, void *);
863 return hash_memory (v, h->user, 0);
867 mem_key_equal (hash_t * h, uword key1, uword key2)
869 void *v1 = uword_to_pointer (key1, void *);
870 void *v2 = uword_to_pointer (key2, void *);
871 return v1 && v2 && 0 == memcmp (v1, v2, h->user);
875 string_key_sum (hash_t * h, uword key)
877 char *v = uword_to_pointer (key, char *);
878 return hash_memory (v, strlen (v), 0);
882 string_key_equal (hash_t * h, uword key1, uword key2)
884 void *v1 = uword_to_pointer (key1, void *);
885 void *v2 = uword_to_pointer (key2, void *);
886 return v1 && v2 && 0 == strcmp (v1, v2);
890 string_key_format_pair (u8 * s, va_list * args)
892 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
893 void *v = va_arg (*args, void *);
894 hash_pair_t *p = va_arg (*args, hash_pair_t *);
895 hash_t *h = hash_header (v);
896 void *u = uword_to_pointer (p->key, void *);
898 s = format (s, "%s", u);
900 if (hash_value_bytes (h) > 0)
902 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
903 hash_value_bytes (h));
909 hash_format_pair_default (u8 * s, va_list * args)
911 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
912 void *v = va_arg (*args, void *);
913 hash_pair_t *p = va_arg (*args, hash_pair_t *);
914 hash_t *h = hash_header (v);
916 s = format (s, "0x%08x", p->key);
917 if (hash_value_bytes (h) > 0)
919 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
920 hash_value_bytes (h));
928 hash_t *h = hash_header (v);
933 bytes = vec_capacity (v, hash_header_bytes (v));
935 for (i = 0; i < hash_capacity (v); i++)
937 if (!hash_is_user (v, i))
939 hash_pair_union_t *p = get_pair (v, i);
940 if (h->log2_pair_size > 0)
941 bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect);
943 bytes += vec_capacity (p->indirect.pairs, 0);
950 format_hash (u8 * s, va_list * va)
952 void *v = va_arg (*va, void *);
953 int verbose = va_arg (*va, int);
955 hash_t *h = hash_header (v);
958 s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
959 v, hash_elts (v), hash_capacity (v), hash_bytes (v));
962 uword *occupancy = 0;
964 /* Count number of buckets with each occupancy. */
965 for (i = 0; i < hash_capacity (v); i++)
969 if (hash_is_user (v, i))
975 hash_pair_union_t *p = get_pair (v, i);
976 if (h->log2_pair_size > 0)
977 j = indirect_pair_get_len (&p->indirect);
979 j = vec_len (p->indirect.pairs);
982 vec_validate (occupancy, j);
986 s = format (s, " profile ");
987 for (i = 0; i < vec_len (occupancy); i++)
988 s = format (s, "%wd%c", occupancy[i],
989 i + 1 == vec_len (occupancy) ? '\n' : ' ');
991 s = format (s, " lookup # of compares: ");
992 for (i = 1; i < vec_len (occupancy); i++)
993 s = format (s, "%wd: .%03d%c", i,
994 (1000 * i * occupancy[i]) / hash_elts (v),
995 i + 1 == vec_len (occupancy) ? '\n' : ' ');
997 vec_free (occupancy);
1003 hash_foreach_pair (p, v, {
1004 s = format (s, " %U\n", h->format_pair, h->format_pair_arg, v, p);
1013 unformat_hash_string_internal (unformat_input_t * input,
1014 va_list * va, int is_vec)
1016 uword *hash = va_arg (*va, uword *);
1017 int *result = va_arg (*va, int *);
1021 if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
1024 p = hash_get_mem (hash, string);
1033 unformat_hash_vec_string (unformat_input_t * input, va_list * va)
1035 return unformat_hash_string_internal (input, va, /* is_vec */ 1);
1039 unformat_hash_string (unformat_input_t * input, va_list * va)
1041 return unformat_hash_string_internal (input, va, /* is_vec */ 0);
1045 hash_validate (void *v)
1047 hash_t *h = hash_header (v);
1050 clib_error_t *error = 0;
1052 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
1054 for (i = 0; i < hash_capacity (v); i++)
1056 hash_pair_union_t *pu = get_pair (v, i);
1058 if (hash_is_user (v, i))
1060 CHECK (pu->direct.key != 0);
1061 vec_add1 (keys, pu->direct.key);
1066 hash_pair_indirect_t *pi = &pu->indirect;
1069 n = h->log2_pair_size > 0
1070 ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
1072 for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
1074 /* Assert key uniqueness. */
1075 for (j = 0; j < vec_len (keys); j++)
1076 CHECK (keys[j] != p->key);
1077 vec_add1 (keys, p->key);
1082 CHECK (vec_len (keys) == h->elts);
1090 * fd.io coding-style-patch-verification: ON
1093 * eval: (c-set-style "gnu")