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);
631 hash_foreach_pair (p, old, {
632 new = _hash_set3 (new, p->key, &p->value[0], 0);
642 hash_resize (void *old, uword new_size)
644 return hash_resize_internal (old, new_size, 1);
650 return hash_resize_internal (old, vec_len (old), 0);
654 _hash_set3 (void *v, uword key, void *value, void *old_value)
659 v = hash_create (0, sizeof (uword));
662 (void) lookup (v, key, SET, value, old_value);
664 if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
666 /* Resize when 3/4 full. */
667 if (4 * (h->elts + 1) > 3 * vec_len (v))
668 v = hash_resize (v, 2 * vec_len (v));
675 vec_key_sum (hash_t * h, uword key)
677 void *v = uword_to_pointer (key, void *);
678 return hash_memory (v, vec_len (v) * h->user, 0);
682 vec_key_equal (hash_t * h, uword key1, uword key2)
684 void *v1 = uword_to_pointer (key1, void *);
685 void *v2 = uword_to_pointer (key2, void *);
686 uword l1 = vec_len (v1);
687 uword l2 = vec_len (v2);
688 return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user);
692 vec_key_format_pair (u8 * s, va_list * args)
694 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
695 void *v = va_arg (*args, void *);
696 hash_pair_t *p = va_arg (*args, hash_pair_t *);
697 hash_t *h = hash_header (v);
698 void *u = uword_to_pointer (p->key, void *);
704 s = format (s, "%v", u);
710 for (i = 0; i < vec_len (w); i++)
711 s = format (s, "0x%x, ", w[i]);
718 for (i = 0; i < vec_len (w); i++)
719 s = format (s, "0x%x, ", w[i]);
726 for (i = 0; i < vec_len (w); i++)
727 s = format (s, "0x%Lx, ", w[i]);
732 s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
736 if (hash_value_bytes (h) > 0)
737 s = format (s, " -> 0x%wx", p->value[0]);
743 mem_key_sum (hash_t * h, uword key)
745 uword *v = uword_to_pointer (key, void *);
746 return hash_memory (v, h->user, 0);
750 mem_key_equal (hash_t * h, uword key1, uword key2)
752 void *v1 = uword_to_pointer (key1, void *);
753 void *v2 = uword_to_pointer (key2, void *);
754 return v1 && v2 && 0 == memcmp (v1, v2, h->user);
758 string_key_sum (hash_t * h, uword key)
760 char *v = uword_to_pointer (key, char *);
761 return hash_memory (v, strlen (v), 0);
765 string_key_equal (hash_t * h, uword key1, uword key2)
767 void *v1 = uword_to_pointer (key1, void *);
768 void *v2 = uword_to_pointer (key2, void *);
769 return v1 && v2 && 0 == strcmp (v1, v2);
773 string_key_format_pair (u8 * s, va_list * args)
775 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
776 void *v = va_arg (*args, void *);
777 hash_pair_t *p = va_arg (*args, hash_pair_t *);
778 hash_t *h = hash_header (v);
779 void *u = uword_to_pointer (p->key, void *);
781 s = format (s, "%s", u);
783 if (hash_value_bytes (h) > 0)
785 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
786 hash_value_bytes (h));
792 hash_format_pair_default (u8 * s, va_list * args)
794 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
795 void *v = va_arg (*args, void *);
796 hash_pair_t *p = va_arg (*args, hash_pair_t *);
797 hash_t *h = hash_header (v);
799 s = format (s, "0x%08x", p->key);
800 if (hash_value_bytes (h) > 0)
802 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
803 hash_value_bytes (h));
811 hash_t *h = hash_header (v);
816 bytes = vec_mem_size (v);
818 for (i = 0; i < hash_capacity (v); i++)
820 if (!hash_is_user (v, i))
822 hash_pair_union_t *p = get_pair (v, i);
823 if (h->log2_pair_size > 0)
824 bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect);
826 bytes += vec_mem_size (p->indirect.pairs);
833 format_hash (u8 *s, va_list *va)
835 void *v = va_arg (*va, void *);
836 int verbose = va_arg (*va, int);
838 hash_t *h = hash_header (v);
841 s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
842 v, hash_elts (v), hash_capacity (v), hash_bytes (v));
845 uword *occupancy = 0;
847 /* Count number of buckets with each occupancy. */
848 for (i = 0; i < hash_capacity (v); i++)
852 if (hash_is_user (v, i))
858 hash_pair_union_t *p = get_pair (v, i);
859 if (h->log2_pair_size > 0)
860 j = indirect_pair_get_len (&p->indirect);
862 j = vec_len (p->indirect.pairs);
865 vec_validate (occupancy, j);
869 s = format (s, " profile ");
870 for (i = 0; i < vec_len (occupancy); i++)
871 s = format (s, "%wd%c", occupancy[i],
872 i + 1 == vec_len (occupancy) ? '\n' : ' ');
874 s = format (s, " lookup # of compares: ");
875 for (i = 1; i < vec_len (occupancy); i++)
876 s = format (s, "%wd: .%03d%c", i,
877 (1000 * i * occupancy[i]) / hash_elts (v),
878 i + 1 == vec_len (occupancy) ? '\n' : ' ');
880 vec_free (occupancy);
885 hash_foreach_pair (p, v, {
886 s = format (s, " %U\n", h->format_pair, h->format_pair_arg, v, p);
894 unformat_hash_string_internal (unformat_input_t * input,
895 va_list * va, int is_vec)
897 uword *hash = va_arg (*va, uword *);
898 int *result = va_arg (*va, int *);
902 if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
905 p = hash_get_mem (hash, string);
914 unformat_hash_vec_string (unformat_input_t * input, va_list * va)
916 return unformat_hash_string_internal (input, va, /* is_vec */ 1);
920 unformat_hash_string (unformat_input_t * input, va_list * va)
922 return unformat_hash_string_internal (input, va, /* is_vec */ 0);
925 __clib_export clib_error_t *
926 hash_validate (void *v)
928 hash_t *h = hash_header (v);
931 clib_error_t *error = 0;
933 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
935 for (i = 0; i < hash_capacity (v); i++)
937 hash_pair_union_t *pu = get_pair (v, i);
939 if (hash_is_user (v, i))
941 CHECK (pu->direct.key != 0);
942 vec_add1 (keys, pu->direct.key);
947 hash_pair_indirect_t *pi = &pu->indirect;
950 n = h->log2_pair_size > 0
951 ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
953 for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
955 /* Assert key uniqueness. */
956 for (j = 0; j < vec_len (keys); j++)
957 CHECK (keys[j] != p->key);
958 vec_add1 (keys, p->key);
963 CHECK (vec_len (keys) == h->elts);
971 * fd.io coding-style-patch-verification: ON
974 * eval: (c-set-style "gnu")