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);
81 hash_memory (void *p, word n_bytes, uword state)
87 a = b = (uword_bits == 64) ? 0x9e3779b97f4a7c13LL : 0x9e3779b9;
91 while (n >= 3 * sizeof (uword))
97 n -= 3 * sizeof (uword);
105 clib_memcpy_fast (&last, q, n);
121 a = b = (uword_bits == 64) ? 0x9e3779b97f4a7c13LL : 0x9e3779b9;
128 /* Call sum function. Hash code will be sum function value
129 modulo the prime length of the hash table. */
131 key_sum (hash_t * h, uword key)
134 switch (pointer_to_uword ((void *) h->key_sum))
137 sum = hash_uword (key);
140 case KEY_FUNC_POINTER_UWORD:
141 sum = hash_uword (*uword_to_pointer (key, uword *));
144 case KEY_FUNC_POINTER_U32:
145 sum = hash_uword (*uword_to_pointer (key, u32 *));
148 case KEY_FUNC_STRING:
149 sum = string_key_sum (h, key);
153 sum = mem_key_sum (h, key);
157 sum = h->key_sum (h, key);
165 key_equal1 (hash_t * h, uword key1, uword key2, uword e)
167 switch (pointer_to_uword ((void *) h->key_equal))
172 case KEY_FUNC_POINTER_UWORD:
174 *uword_to_pointer (key1, uword *) == *uword_to_pointer (key2,
178 case KEY_FUNC_POINTER_U32:
179 e = *uword_to_pointer (key1, u32 *) == *uword_to_pointer (key2, u32 *);
182 case KEY_FUNC_STRING:
183 e = string_key_equal (h, key1, key2);
187 e = mem_key_equal (h, key1, key2);
191 e = h->key_equal (h, key1, key2);
197 /* Compares two keys: returns 1 if equal, 0 if not. */
199 key_equal (hash_t * h, uword key1, uword key2)
201 uword e = key1 == key2;
202 if (CLIB_DEBUG > 0 && key1 == key2)
203 ASSERT (key_equal1 (h, key1, key2, e));
205 e = key_equal1 (h, key1, key2, e);
209 static hash_pair_union_t *
210 get_indirect (void *v, hash_pair_indirect_t * pi, uword key)
212 hash_t *h = hash_header (v);
213 hash_pair_t *p0, *p1;
216 if (h->log2_pair_size > 0)
217 p1 = hash_forward (h, p0, indirect_pair_get_len (pi));
223 if (key_equal (h, p0->key, key))
224 return (hash_pair_union_t *) p0;
225 p0 = hash_forward1 (h, p0);
228 return (hash_pair_union_t *) 0;
231 static hash_pair_union_t *
232 set_indirect_is_user (void *v, uword i, hash_pair_union_t * p, uword key)
234 hash_t *h = hash_header (v);
236 hash_pair_indirect_t *pi = &p->indirect;
237 uword log2_bytes = 0;
239 if (h->log2_pair_size == 0)
240 q = vec_new (hash_pair_t, 2);
243 log2_bytes = 1 + hash_pair_log2_bytes (h);
244 q = clib_mem_alloc (1ULL << log2_bytes);
246 clib_memcpy_fast (q, &p->direct, hash_pair_bytes (h));
249 if (h->log2_pair_size > 0)
250 indirect_pair_set (pi, log2_bytes, 2);
252 set_is_user (v, i, 0);
254 /* First element is used by existing pair, second will be used by caller. */
255 q = hash_forward1 (h, q);
258 return (hash_pair_union_t *) q;
261 static hash_pair_union_t *
262 set_indirect (void *v, hash_pair_indirect_t * pi, uword key,
265 hash_t *h = hash_header (v);
266 hash_pair_t *new_pair;
267 hash_pair_union_t *q;
269 q = get_indirect (v, pi, key);
276 if (h->log2_pair_size == 0)
277 vec_add2 (pi->pairs, new_pair, 1);
280 uword len, new_len, log2_bytes;
282 len = indirect_pair_get_len (pi);
283 log2_bytes = indirect_pair_get_log2_bytes (pi);
286 if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes))
288 pi->pairs = clib_mem_realloc (pi->pairs, 1ULL << (log2_bytes + 1));
292 indirect_pair_set (pi, log2_bytes, new_len);
293 new_pair = pi->pairs + (len << h->log2_pair_size);
296 init_pair (h, new_pair);
298 return (hash_pair_union_t *) new_pair;
302 unset_indirect (void *v, uword i, hash_pair_t * q)
304 hash_t *h = hash_header (v);
305 hash_pair_union_t *p = get_pair (v, i);
307 hash_pair_indirect_t *pi = &p->indirect;
310 is_vec = h->log2_pair_size == 0;
312 ASSERT (!hash_is_user (v, i));
313 len = is_vec ? vec_len (pi->pairs) : indirect_pair_get_len (pi);
314 e = hash_forward (h, pi->pairs, len - 1);
315 ASSERT (q >= pi->pairs && q <= e);
317 /* We have two or fewer pairs and we are delete one pair.
318 Make indirect pointer direct and free indirect memory. */
321 hash_pair_t *r = pi->pairs;
325 clib_memcpy_fast (p, q == r ? hash_forward1 (h, r) : r,
326 hash_pair_bytes (h));
327 set_is_user (v, i, 1);
330 zero_pair (h, &p->direct);
339 /* If deleting a pair we need to keep non-null pairs together. */
341 clib_memcpy_fast (q, e, hash_pair_bytes (h));
345 vec_dec_len (pi->pairs, 1);
347 indirect_pair_set (pi, indirect_pair_get_log2_bytes (pi), len - 1);
359 lookup (void *v, uword key, enum lookup_opcode op,
360 void *new_value, void *old_value)
362 hash_t *h = hash_header (v);
363 hash_pair_union_t *p = 0;
371 i = key_sum (h, key) & (_vec_len (v) - 1);
373 value_bytes = hash_value_bytes (h);
375 if (hash_is_user (v, i))
377 found_key = key_equal (h, p->direct.key, key);
382 set_is_user (v, i, 0);
383 if (old_value && value_bytes)
384 clib_memcpy_fast (old_value, p->direct.value, value_bytes);
385 zero_pair (h, &p->direct);
391 p = set_indirect_is_user (v, i, p, key);
398 hash_pair_indirect_t *pi = &p->indirect;
405 set_is_user (v, i, 1);
408 p = set_indirect (v, pi, key, &found_key);
412 p = get_indirect (v, pi, key);
414 if (found_key && op == UNSET)
416 if (old_value && value_bytes)
417 clib_memcpy_fast (old_value, &p->direct.value, value_bytes);
419 unset_indirect (v, i, &p->direct);
421 /* Nullify p (since it's just been deleted).
422 Otherwise we might be tempted to play with it. */
428 if (op == SET && p != 0 && value_bytes)
430 /* Save away old value for caller. */
431 if (old_value && found_key)
432 clib_memcpy_fast (old_value, &p->direct.value, value_bytes);
433 clib_memcpy_fast (&p->direct.value, new_value, value_bytes);
437 h->elts += !found_key;
439 h->elts -= found_key;
444 /* Fetch value of key. */
445 __clib_export uword *
446 _hash_get (void *v, uword key)
448 hash_t *h = hash_header (v);
451 /* Don't even search table if its empty. */
452 if (!v || h->elts == 0)
455 p = lookup (v, key, GET, 0, 0);
458 if (h->log2_pair_size == 0)
464 __clib_export hash_pair_t *
465 _hash_get_pair (void *v, uword key)
467 return lookup (v, key, GET, 0, 0);
470 __clib_export hash_pair_t *
471 hash_next (void *v, hash_next_t *hn)
473 hash_t *h = hash_header (v);
478 if (hn->i == 0 && hn->j == 0)
483 /* Prevent others from re-sizing hash table. */
485 (HASH_FLAG_NO_AUTO_GROW
486 | HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_HASH_NEXT_IN_PROGRESS);
488 else if (hn->i >= hash_capacity (v))
492 clib_memset (hn, 0, sizeof (hn[0]));
496 p = hash_forward (h, v, hn->i);
497 if (hash_is_user (v, hn->i))
504 hash_pair_indirect_t *pi = (void *) p;
507 if (h->log2_pair_size > 0)
508 n = indirect_pair_get_len (pi);
510 n = vec_len (pi->pairs);
518 return hash_forward (h, pi->pairs, hn->j++);
523 /* Remove key from table. */
525 _hash_unset (void *v, uword key, void *old_value)
532 (void) lookup (v, key, UNSET, 0, old_value);
535 if (!(h->flags & HASH_FLAG_NO_AUTO_SHRINK))
537 /* Resize when 1/4 full. */
538 if (h->elts > 32 && 4 * (h->elts + 1) < vec_len (v))
539 v = hash_resize (v, vec_len (v) / 2);
546 _hash_create (uword elts, hash_t * h_user)
549 uword log2_pair_size;
551 vec_attr_t va = { .hdr_sz = sizeof (h[0]), .align = sizeof (hash_pair_t) };
553 /* Size of hash is power of 2 >= ELTS and larger than
554 number of bits in is_user bitmap elements. */
555 elts = clib_max (elts, BITS (h->is_user[0]));
556 elts = 1ULL << max_log2 (elts);
560 log2_pair_size = h_user->log2_pair_size;
562 va.elt_sz = (1 << log2_pair_size) * sizeof (hash_pair_t),
563 v = _vec_alloc_internal (elts, &va);
572 vec_validate_aligned (
573 h->is_user, ((elts / BITS (h->is_user[0])) * sizeof (h->is_user[0])) - 1,
574 CLIB_CACHE_LINE_BYTES);
575 h->log2_pair_size = log2_pair_size;
578 /* Default flags to never shrinking hash tables.
579 Shrinking tables can cause "jackpot" cases. */
581 h->flags = HASH_FLAG_NO_AUTO_SHRINK;
585 h->format_pair = hash_format_pair_default;
586 h->format_pair_arg = 0;
595 hash_t *h = hash_header (v);
596 hash_pair_union_t *p;
602 /* We zero all freed memory in case user would be tempted to use it. */
603 for (i = 0; i < hash_capacity (v); i++)
605 if (hash_is_user (v, i))
608 if (h->log2_pair_size == 0)
609 vec_free (p->indirect.pairs);
610 else if (p->indirect.pairs)
611 clib_mem_free (p->indirect.pairs);
614 vec_free (h->is_user);
621 hash_resize_internal (void *old, uword new_size, uword free_old)
629 hash_t *h = old ? hash_header (old) : 0;
630 new = _hash_create (new_size, h);
632 hash_foreach_pair (p, old, {
633 new = _hash_set3 (new, p->key, &p->value[0], 0);
644 hash_resize (void *old, uword new_size)
646 return hash_resize_internal (old, new_size, 1);
652 return hash_resize_internal (old, vec_len (old), 0);
656 _hash_set3 (void *v, uword key, void *value, void *old_value)
661 v = hash_create (0, sizeof (uword));
664 (void) lookup (v, key, SET, value, old_value);
666 if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
668 /* Resize when 3/4 full. */
669 if (4 * (h->elts + 1) > 3 * vec_len (v))
670 v = hash_resize (v, 2 * vec_len (v));
677 vec_key_sum (hash_t * h, uword key)
679 void *v = uword_to_pointer (key, void *);
680 return hash_memory (v, vec_len (v) * h->user, 0);
684 vec_key_equal (hash_t * h, uword key1, uword key2)
686 void *v1 = uword_to_pointer (key1, void *);
687 void *v2 = uword_to_pointer (key2, void *);
688 uword l1 = vec_len (v1);
689 uword l2 = vec_len (v2);
690 return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user);
694 vec_key_format_pair (u8 * s, va_list * args)
696 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
697 void *v = va_arg (*args, void *);
698 hash_pair_t *p = va_arg (*args, hash_pair_t *);
699 hash_t *h = hash_header (v);
700 void *u = uword_to_pointer (p->key, void *);
706 s = format (s, "%v", u);
712 for (i = 0; i < vec_len (w); i++)
713 s = format (s, "0x%x, ", w[i]);
720 for (i = 0; i < vec_len (w); i++)
721 s = format (s, "0x%x, ", w[i]);
728 for (i = 0; i < vec_len (w); i++)
729 s = format (s, "0x%Lx, ", w[i]);
734 s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
738 if (hash_value_bytes (h) > 0)
739 s = format (s, " -> 0x%wx", p->value[0]);
745 mem_key_sum (hash_t * h, uword key)
747 uword *v = uword_to_pointer (key, void *);
748 return hash_memory (v, h->user, 0);
752 mem_key_equal (hash_t * h, uword key1, uword key2)
754 void *v1 = uword_to_pointer (key1, void *);
755 void *v2 = uword_to_pointer (key2, void *);
756 return v1 && v2 && 0 == memcmp (v1, v2, h->user);
760 string_key_sum (hash_t * h, uword key)
762 char *v = uword_to_pointer (key, char *);
763 return hash_memory (v, strlen (v), 0);
767 string_key_equal (hash_t * h, uword key1, uword key2)
769 void *v1 = uword_to_pointer (key1, void *);
770 void *v2 = uword_to_pointer (key2, void *);
771 return v1 && v2 && 0 == strcmp (v1, v2);
775 string_key_format_pair (u8 * s, va_list * args)
777 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
778 void *v = va_arg (*args, void *);
779 hash_pair_t *p = va_arg (*args, hash_pair_t *);
780 hash_t *h = hash_header (v);
781 void *u = uword_to_pointer (p->key, void *);
783 s = format (s, "%s", u);
785 if (hash_value_bytes (h) > 0)
787 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
788 hash_value_bytes (h));
794 hash_format_pair_default (u8 * s, va_list * args)
796 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
797 void *v = va_arg (*args, void *);
798 hash_pair_t *p = va_arg (*args, hash_pair_t *);
799 hash_t *h = hash_header (v);
801 s = format (s, "0x%08x", p->key);
802 if (hash_value_bytes (h) > 0)
804 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
805 hash_value_bytes (h));
813 hash_t *h = hash_header (v);
818 bytes = vec_mem_size (v);
820 for (i = 0; i < hash_capacity (v); i++)
822 if (!hash_is_user (v, i))
824 hash_pair_union_t *p = get_pair (v, i);
825 if (h->log2_pair_size > 0)
826 bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect);
828 bytes += vec_mem_size (p->indirect.pairs);
835 format_hash (u8 *s, va_list *va)
837 void *v = va_arg (*va, void *);
838 int verbose = va_arg (*va, int);
840 hash_t *h = hash_header (v);
843 s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
844 v, hash_elts (v), hash_capacity (v), hash_bytes (v));
847 uword *occupancy = 0;
849 /* Count number of buckets with each occupancy. */
850 for (i = 0; i < hash_capacity (v); i++)
854 if (hash_is_user (v, i))
860 hash_pair_union_t *p = get_pair (v, i);
861 if (h->log2_pair_size > 0)
862 j = indirect_pair_get_len (&p->indirect);
864 j = vec_len (p->indirect.pairs);
867 vec_validate (occupancy, j);
871 s = format (s, " profile ");
872 for (i = 0; i < vec_len (occupancy); i++)
873 s = format (s, "%wd%c", occupancy[i],
874 i + 1 == vec_len (occupancy) ? '\n' : ' ');
876 s = format (s, " lookup # of compares: ");
877 for (i = 1; i < vec_len (occupancy); i++)
878 s = format (s, "%wd: .%03d%c", i,
879 (1000 * i * occupancy[i]) / hash_elts (v),
880 i + 1 == vec_len (occupancy) ? '\n' : ' ');
882 vec_free (occupancy);
888 hash_foreach_pair (p, v, {
889 s = format (s, " %U\n", h->format_pair, h->format_pair_arg, v, p);
898 unformat_hash_string_internal (unformat_input_t * input,
899 va_list * va, int is_vec)
901 uword *hash = va_arg (*va, uword *);
902 int *result = va_arg (*va, int *);
906 if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
909 p = hash_get_mem (hash, string);
918 unformat_hash_vec_string (unformat_input_t * input, va_list * va)
920 return unformat_hash_string_internal (input, va, /* is_vec */ 1);
924 unformat_hash_string (unformat_input_t * input, va_list * va)
926 return unformat_hash_string_internal (input, va, /* is_vec */ 0);
929 __clib_export clib_error_t *
930 hash_validate (void *v)
932 hash_t *h = hash_header (v);
935 clib_error_t *error = 0;
937 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
939 for (i = 0; i < hash_capacity (v); i++)
941 hash_pair_union_t *pu = get_pair (v, i);
943 if (hash_is_user (v, i))
945 CHECK (pu->direct.key != 0);
946 vec_add1 (keys, pu->direct.key);
951 hash_pair_indirect_t *pi = &pu->indirect;
954 n = h->log2_pair_size > 0
955 ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
957 for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
959 /* Assert key uniqueness. */
960 for (j = 0; j < vec_len (keys); j++)
961 CHECK (keys[j] != p->key);
962 vec_add1 (keys, p->key);
967 CHECK (vec_len (keys) == h->elts);
975 * fd.io coding-style-patch-verification: ON
978 * eval: (c-set-style "gnu")