diff options
Diffstat (limited to 'vppinfra/vppinfra/hash.c')
-rw-r--r-- | vppinfra/vppinfra/hash.c | 1095 |
1 files changed, 0 insertions, 1095 deletions
diff --git a/vppinfra/vppinfra/hash.c b/vppinfra/vppinfra/hash.c deleted file mode 100644 index 062ad8823e1..00000000000 --- a/vppinfra/vppinfra/hash.c +++ /dev/null @@ -1,1095 +0,0 @@ -/* - * Copyright (c) 2015 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -/* - Copyright (c) 2001-2005 Eliot Dresselhaus - - Permission is hereby granted, free of charge, to any person obtaining - a copy of this software and associated documentation files (the - "Software"), to deal in the Software without restriction, including - without limitation the rights to use, copy, modify, merge, publish, - distribute, sublicense, and/or sell copies of the Software, and to - permit persons to whom the Software is furnished to do so, subject to - the following conditions: - - The above copyright notice and this permission notice shall be - included in all copies or substantial portions of the Software. - - THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND - NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE - LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION - OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION - WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -*/ - -#include <vppinfra/hash.h> -#include <vppinfra/error.h> -#include <vppinfra/mem.h> -#include <vppinfra/byte_order.h> /* for clib_arch_is_big_endian */ - -always_inline void -zero_pair (hash_t * h, hash_pair_t * p) -{ - memset (p, 0, hash_pair_bytes (h)); -} - -always_inline void -init_pair (hash_t * h, hash_pair_t * p) -{ - memset (p->value, ~0, hash_value_bytes (h)); -} - -always_inline hash_pair_union_t * -get_pair (void *v, uword i) -{ - hash_t *h = hash_header (v); - hash_pair_t *p; - ASSERT (i < vec_len (v)); - p = v; - p += i << h->log2_pair_size; - return (hash_pair_union_t *) p; -} - -always_inline void -set_is_user (void *v, uword i, uword is_user) -{ - hash_t *h = hash_header (v); - uword i0 = i / BITS (h->is_user[0]); - uword i1 = (uword) 1 << (i % BITS (h->is_user[0])); - if (is_user) - h->is_user[i0] |= i1; - else - h->is_user[i0] &= ~i1; -} - -static u8 *hash_format_pair_default (u8 * s, va_list * args); - -#if uword_bits == 64 - -static inline u64 -zap64 (u64 x, word n) -{ -#define _(n) (((u64) 1 << (u64) (8*(n))) - (u64) 1) - static u64 masks_little_endian[] = { - 0, _(1), _(2), _(3), _(4), _(5), _(6), _(7), - }; - static u64 masks_big_endian[] = { - 0, ~_(7), ~_(6), ~_(5), ~_(4), ~_(3), ~_(2), ~_(1), - }; -#undef _ - if (clib_arch_is_big_endian) - return x & masks_big_endian[n]; - else - return x & masks_little_endian[n]; -} - -static inline u64 -hash_memory64 (void *p, word n_bytes, u64 state) -{ - u64 *q = p; - u64 a, b, c, n; - - a = b = 0x9e3779b97f4a7c13LL; - c = state; - n = n_bytes; - - while (n >= 3 * sizeof (u64)) - { - a += clib_mem_unaligned (q + 0, u64); - b += clib_mem_unaligned (q + 1, u64); - c += clib_mem_unaligned (q + 2, u64); - hash_mix64 (a, b, c); - n -= 3 * sizeof (u64); - q += 3; - } - - c += n_bytes; - switch (n / sizeof (u64)) - { - case 2: - a += clib_mem_unaligned (q + 0, u64); - b += clib_mem_unaligned (q + 1, u64); - if (n % sizeof (u64)) - c += zap64 (clib_mem_unaligned (q + 2, u64), n % sizeof (u64)) << 8; - break; - - case 1: - a += clib_mem_unaligned (q + 0, u64); - if (n % sizeof (u64)) - b += zap64 (clib_mem_unaligned (q + 1, u64), n % sizeof (u64)); - break; - - case 0: - if (n % sizeof (u64)) - a += zap64 (clib_mem_unaligned (q + 0, u64), n % sizeof (u64)); - break; - } - - hash_mix64 (a, b, c); - - return c; -} - -#else /* if uword_bits == 64 */ - -static inline u32 -zap32 (u32 x, word n) -{ -#define _(n) (((u32) 1 << (u32) (8*(n))) - (u32) 1) - static u32 masks_little_endian[] = { - 0, _(1), _(2), _(3), - }; - static u32 masks_big_endian[] = { - 0, ~_(3), ~_(2), ~_(1), - }; -#undef _ - if (clib_arch_is_big_endian) - return x & masks_big_endian[n]; - else - return x & masks_little_endian[n]; -} - -static inline u32 -hash_memory32 (void *p, word n_bytes, u32 state) -{ - u32 *q = p; - u32 a, b, c, n; - - a = b = 0x9e3779b9; - c = state; - n = n_bytes; - - while (n >= 3 * sizeof (u32)) - { - a += clib_mem_unaligned (q + 0, u32); - b += clib_mem_unaligned (q + 1, u32); - c += clib_mem_unaligned (q + 2, u32); - hash_mix32 (a, b, c); - n -= 3 * sizeof (u32); - q += 3; - } - - c += n_bytes; - switch (n / sizeof (u32)) - { - case 2: - a += clib_mem_unaligned (q + 0, u32); - b += clib_mem_unaligned (q + 1, u32); - if (n % sizeof (u32)) - c += zap32 (clib_mem_unaligned (q + 2, u32), n % sizeof (u32)) << 8; - break; - - case 1: - a += clib_mem_unaligned (q + 0, u32); - if (n % sizeof (u32)) - b += zap32 (clib_mem_unaligned (q + 1, u32), n % sizeof (u32)); - break; - - case 0: - if (n % sizeof (u32)) - a += zap32 (clib_mem_unaligned (q + 0, u32), n % sizeof (u32)); - break; - } - - hash_mix32 (a, b, c); - - return c; -} -#endif - -uword -hash_memory (void *p, word n_bytes, uword state) -{ - uword *q = p; - -#if uword_bits == 64 - return hash_memory64 (q, n_bytes, state); -#else - return hash_memory32 (q, n_bytes, state); -#endif -} - -#if uword_bits == 64 -always_inline uword -hash_uword (uword x) -{ - u64 a, b, c; - - a = b = 0x9e3779b97f4a7c13LL; - c = 0; - a += x; - hash_mix64 (a, b, c); - return c; -} -#else -always_inline uword -hash_uword (uword x) -{ - u32 a, b, c; - - a = b = 0x9e3779b9; - c = 0; - a += x; - hash_mix32 (a, b, c); - return c; -} -#endif - -/* Call sum function. Hash code will be sum function value - modulo the prime length of the hash table. */ -always_inline uword -key_sum (hash_t * h, uword key) -{ - uword sum; - switch (pointer_to_uword ((void *) h->key_sum)) - { - case KEY_FUNC_NONE: - sum = hash_uword (key); - break; - - case KEY_FUNC_POINTER_UWORD: - sum = hash_uword (*uword_to_pointer (key, uword *)); - break; - - case KEY_FUNC_POINTER_U32: - sum = hash_uword (*uword_to_pointer (key, u32 *)); - break; - - case KEY_FUNC_STRING: - sum = string_key_sum (h, key); - break; - - default: - sum = h->key_sum (h, key); - break; - } - - return sum; -} - -always_inline uword -key_equal1 (hash_t * h, uword key1, uword key2, uword e) -{ - switch (pointer_to_uword ((void *) h->key_equal)) - { - case KEY_FUNC_NONE: - break; - - case KEY_FUNC_POINTER_UWORD: - e = - *uword_to_pointer (key1, uword *) == *uword_to_pointer (key2, - uword *); - break; - - case KEY_FUNC_POINTER_U32: - e = *uword_to_pointer (key1, u32 *) == *uword_to_pointer (key2, u32 *); - break; - - case KEY_FUNC_STRING: - e = string_key_equal (h, key1, key2); - break; - - default: - e = h->key_equal (h, key1, key2); - break; - } - return e; -} - -/* Compares two keys: returns 1 if equal, 0 if not. */ -always_inline uword -key_equal (hash_t * h, uword key1, uword key2) -{ - uword e = key1 == key2; - if (CLIB_DEBUG > 0 && key1 == key2) - ASSERT (key_equal1 (h, key1, key2, e)); - if (!e) - e = key_equal1 (h, key1, key2, e); - return e; -} - -static hash_pair_union_t * -get_indirect (void *v, hash_pair_indirect_t * pi, uword key) -{ - hash_t *h = hash_header (v); - hash_pair_t *p0, *p1; - - p0 = p1 = pi->pairs; - if (h->log2_pair_size > 0) - p1 = hash_forward (h, p0, indirect_pair_get_len (pi)); - else - p1 += vec_len (p0); - - while (p0 < p1) - { - if (key_equal (h, p0->key, key)) - return (hash_pair_union_t *) p0; - p0 = hash_forward1 (h, p0); - } - - return (hash_pair_union_t *) 0; -} - -static hash_pair_union_t * -set_indirect_is_user (void *v, uword i, hash_pair_union_t * p, uword key) -{ - hash_t *h = hash_header (v); - hash_pair_t *q; - hash_pair_indirect_t *pi = &p->indirect; - uword log2_bytes = 0; - - if (h->log2_pair_size == 0) - q = vec_new (hash_pair_t, 2); - else - { - log2_bytes = 1 + hash_pair_log2_bytes (h); - q = clib_mem_alloc (1ULL << log2_bytes); - } - clib_memcpy (q, &p->direct, hash_pair_bytes (h)); - - pi->pairs = q; - if (h->log2_pair_size > 0) - indirect_pair_set (pi, log2_bytes, 2); - - set_is_user (v, i, 0); - - /* First element is used by existing pair, second will be used by caller. */ - q = hash_forward1 (h, q); - q->key = key; - init_pair (h, q); - return (hash_pair_union_t *) q; -} - -static hash_pair_union_t * -set_indirect (void *v, hash_pair_indirect_t * pi, uword key, - uword * found_key) -{ - hash_t *h = hash_header (v); - hash_pair_t *new_pair; - hash_pair_union_t *q; - - q = get_indirect (v, pi, key); - if (q) - { - *found_key = 1; - return q; - } - - if (h->log2_pair_size == 0) - vec_add2 (pi->pairs, new_pair, 1); - else - { - uword len, new_len, log2_bytes; - - len = indirect_pair_get_len (pi); - log2_bytes = indirect_pair_get_log2_bytes (pi); - - new_len = len + 1; - if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes)) - { - pi->pairs = clib_mem_realloc (pi->pairs, - 1ULL << (log2_bytes + 1), - 1ULL << log2_bytes); - log2_bytes++; - } - - indirect_pair_set (pi, log2_bytes, new_len); - new_pair = pi->pairs + (len << h->log2_pair_size); - } - new_pair->key = key; - init_pair (h, new_pair); - *found_key = 0; - return (hash_pair_union_t *) new_pair; -} - -static void -unset_indirect (void *v, uword i, hash_pair_t * q) -{ - hash_t *h = hash_header (v); - hash_pair_union_t *p = get_pair (v, i); - hash_pair_t *e; - hash_pair_indirect_t *pi = &p->indirect; - uword len, is_vec; - - is_vec = h->log2_pair_size == 0; - - ASSERT (!hash_is_user (v, i)); - len = is_vec ? vec_len (pi->pairs) : indirect_pair_get_len (pi); - e = hash_forward (h, pi->pairs, len - 1); - ASSERT (q >= pi->pairs && q <= e); - - /* We have two or fewer pairs and we are delete one pair. - Make indirect pointer direct and free indirect memory. */ - if (len <= 2) - { - hash_pair_t *r = pi->pairs; - - if (len == 2) - { - clib_memcpy (p, q == r ? hash_forward1 (h, r) : r, - hash_pair_bytes (h)); - set_is_user (v, i, 1); - } - else - zero_pair (h, &p->direct); - - if (is_vec) - vec_free (r); - else if (r) - clib_mem_free (r); - } - else - { - /* If deleting a pair we need to keep non-null pairs together. */ - if (q < e) - clib_memcpy (q, e, hash_pair_bytes (h)); - else - zero_pair (h, q); - if (is_vec) - _vec_len (pi->pairs) -= 1; - else - indirect_pair_set (pi, indirect_pair_get_log2_bytes (pi), len - 1); - } -} - -enum lookup_opcode -{ - GET = 1, - SET = 2, - UNSET = 3, -}; - -static hash_pair_t * -lookup (void *v, uword key, enum lookup_opcode op, - void *new_value, void *old_value) -{ - hash_t *h = hash_header (v); - hash_pair_union_t *p = 0; - uword found_key = 0; - uword i; - - if (!v) - return 0; - - i = key_sum (h, key) & (_vec_len (v) - 1); - p = get_pair (v, i); - - if (hash_is_user (v, i)) - { - found_key = key_equal (h, p->direct.key, key); - if (found_key) - { - if (op == UNSET) - { - set_is_user (v, i, 0); - if (old_value) - clib_memcpy (old_value, p->direct.value, - hash_value_bytes (h)); - zero_pair (h, &p->direct); - } - } - else - { - if (op == SET) - p = set_indirect_is_user (v, i, p, key); - else - p = 0; - } - } - else - { - hash_pair_indirect_t *pi = &p->indirect; - - if (op == SET) - { - if (!pi->pairs) - { - p->direct.key = key; - set_is_user (v, i, 1); - } - else - p = set_indirect (v, pi, key, &found_key); - } - else - { - p = get_indirect (v, pi, key); - found_key = p != 0; - if (found_key && op == UNSET) - { - if (old_value) - clib_memcpy (old_value, &p->direct.value, - hash_value_bytes (h)); - - unset_indirect (v, i, &p->direct); - - /* Nullify p (since it's just been deleted). - Otherwise we might be tempted to play with it. */ - p = 0; - } - } - } - - if (op == SET && p != 0) - { - /* Save away old value for caller. */ - if (old_value && found_key) - clib_memcpy (old_value, &p->direct.value, hash_value_bytes (h)); - clib_memcpy (&p->direct.value, new_value, hash_value_bytes (h)); - } - - if (op == SET) - h->elts += !found_key; - if (op == UNSET) - h->elts -= found_key; - - return &p->direct; -} - -/* Fetch value of key. */ -uword * -_hash_get (void *v, uword key) -{ - hash_t *h = hash_header (v); - hash_pair_t *p; - - /* Don't even search table if its empty. */ - if (!v || h->elts == 0) - return 0; - - p = lookup (v, key, GET, 0, 0); - if (!p) - return 0; - if (h->log2_pair_size == 0) - return &p->key; - else - return &p->value[0]; -} - -hash_pair_t * -_hash_get_pair (void *v, uword key) -{ - return lookup (v, key, GET, 0, 0); -} - -hash_pair_t * -hash_next (void *v, hash_next_t * hn) -{ - hash_t *h = hash_header (v); - hash_pair_t *p; - - while (1) - { - if (hn->i == 0 && hn->j == 0) - { - /* Save flags. */ - hn->f = h->flags; - - /* Prevent others from re-sizing hash table. */ - h->flags |= - (HASH_FLAG_NO_AUTO_GROW - | HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_HASH_NEXT_IN_PROGRESS); - } - else if (hn->i >= hash_capacity (v)) - { - /* Restore flags. */ - h->flags = hn->f; - memset (hn, 0, sizeof (hn[0])); - return 0; - } - - p = hash_forward (h, v, hn->i); - if (hash_is_user (v, hn->i)) - { - hn->i++; - return p; - } - else - { - hash_pair_indirect_t *pi = (void *) p; - uword n; - - if (h->log2_pair_size > 0) - n = indirect_pair_get_len (pi); - else - n = vec_len (pi->pairs); - - if (hn->j >= n) - { - hn->i++; - hn->j = 0; - } - else - return hash_forward (h, pi->pairs, hn->j++); - } - } -} - -/* Remove key from table. */ -void * -_hash_unset (void *v, uword key, void *old_value) -{ - hash_t *h; - - if (!v) - return v; - - (void) lookup (v, key, UNSET, 0, old_value); - - h = hash_header (v); - if (!(h->flags & HASH_FLAG_NO_AUTO_SHRINK)) - { - /* Resize when 1/4 full. */ - if (h->elts > 32 && 4 * (h->elts + 1) < vec_len (v)) - v = hash_resize (v, vec_len (v) / 2); - } - - return v; -} - -void * -_hash_create (uword elts, hash_t * h_user) -{ - hash_t *h; - uword log2_pair_size; - void *v; - - /* Size of hash is power of 2 >= ELTS and larger than - number of bits in is_user bitmap elements. */ - elts = clib_max (elts, BITS (h->is_user[0])); - elts = 1ULL << max_log2 (elts); - - log2_pair_size = 1; - if (h_user) - log2_pair_size = h_user->log2_pair_size; - - v = _vec_resize (0, - /* vec len: */ elts, - /* data bytes: */ - (elts << log2_pair_size) * sizeof (hash_pair_t), - /* header bytes: */ - sizeof (h[0]) + - (elts / BITS (h->is_user[0])) * sizeof (h->is_user[0]), - /* alignment */ sizeof (hash_pair_t)); - h = hash_header (v); - - if (h_user) - h[0] = h_user[0]; - - h->log2_pair_size = log2_pair_size; - h->elts = 0; - - /* Default flags to never shrinking hash tables. - Shrinking tables can cause "jackpot" cases. */ - if (!h_user) - h->flags = HASH_FLAG_NO_AUTO_SHRINK; - - if (!h->format_pair) - { - h->format_pair = hash_format_pair_default; - h->format_pair_arg = 0; - } - - return v; -} - -void * -_hash_free (void *v) -{ - hash_t *h = hash_header (v); - hash_pair_union_t *p; - uword i; - - if (!v) - return v; - - /* We zero all freed memory in case user would be tempted to use it. */ - for (i = 0; i < hash_capacity (v); i++) - { - if (hash_is_user (v, i)) - continue; - p = get_pair (v, i); - if (h->log2_pair_size == 0) - vec_free (p->indirect.pairs); - else if (p->indirect.pairs) - clib_mem_free (p->indirect.pairs); - } - - vec_free_header (h); - - return 0; -} - -static void * -hash_resize_internal (void *old, uword new_size, uword free_old) -{ - void *new; - hash_pair_t *p; - - new = 0; - if (new_size > 0) - { - hash_t *h = old ? hash_header (old) : 0; - new = _hash_create (new_size, h); - /* *INDENT-OFF* */ - hash_foreach_pair (p, old, { - new = _hash_set3 (new, p->key, &p->value[0], 0); - }); - /* *INDENT-ON* */ - } - - if (free_old) - hash_free (old); - return new; -} - -void * -hash_resize (void *old, uword new_size) -{ - return hash_resize_internal (old, new_size, 1); -} - -void * -hash_dup (void *old) -{ - return hash_resize_internal (old, vec_len (old), 0); -} - -void * -_hash_set3 (void *v, uword key, void *value, void *old_value) -{ - hash_t *h; - - if (!v) - v = hash_create (0, sizeof (uword)); - - h = hash_header (v); - (void) lookup (v, key, SET, value, old_value); - - if (!(h->flags & HASH_FLAG_NO_AUTO_GROW)) - { - /* Resize when 3/4 full. */ - if (4 * (h->elts + 1) > 3 * vec_len (v)) - v = hash_resize (v, 2 * vec_len (v)); - } - - return v; -} - -uword -vec_key_sum (hash_t * h, uword key) -{ - void *v = uword_to_pointer (key, void *); - return hash_memory (v, vec_len (v) * h->user, 0); -} - -uword -vec_key_equal (hash_t * h, uword key1, uword key2) -{ - void *v1 = uword_to_pointer (key1, void *); - void *v2 = uword_to_pointer (key2, void *); - uword l1 = vec_len (v1); - uword l2 = vec_len (v2); - return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user); -} - -u8 * -vec_key_format_pair (u8 * s, va_list * args) -{ - void *CLIB_UNUSED (user_arg) = va_arg (*args, void *); - void *v = va_arg (*args, void *); - hash_pair_t *p = va_arg (*args, hash_pair_t *); - hash_t *h = hash_header (v); - void *u = uword_to_pointer (p->key, void *); - int i; - - switch (h->user) - { - case 1: - s = format (s, "%v", u); - break; - - case 2: - { - u16 *w = u; - for (i = 0; i < vec_len (w); i++) - s = format (s, "0x%x, ", w[i]); - break; - } - - case 4: - { - u32 *w = u; - for (i = 0; i < vec_len (w); i++) - s = format (s, "0x%x, ", w[i]); - break; - } - - case 8: - { - u64 *w = u; - for (i = 0; i < vec_len (w); i++) - s = format (s, "0x%Lx, ", w[i]); - break; - } - - default: - s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user); - break; - } - - if (hash_value_bytes (h) > 0) - s = format (s, " -> 0x%wx", p->value[0]); - - return s; -} - -uword -mem_key_sum (hash_t * h, uword key) -{ - uword *v = uword_to_pointer (key, void *); - return hash_memory (v, h->user, 0); -} - -uword -mem_key_equal (hash_t * h, uword key1, uword key2) -{ - void *v1 = uword_to_pointer (key1, void *); - void *v2 = uword_to_pointer (key2, void *); - return v1 && v2 && 0 == memcmp (v1, v2, h->user); -} - -uword -string_key_sum (hash_t * h, uword key) -{ - char *v = uword_to_pointer (key, char *); - return hash_memory (v, strlen (v), 0); -} - -uword -string_key_equal (hash_t * h, uword key1, uword key2) -{ - void *v1 = uword_to_pointer (key1, void *); - void *v2 = uword_to_pointer (key2, void *); - return v1 && v2 && 0 == strcmp (v1, v2); -} - -u8 * -string_key_format_pair (u8 * s, va_list * args) -{ - void *CLIB_UNUSED (user_arg) = va_arg (*args, void *); - void *v = va_arg (*args, void *); - hash_pair_t *p = va_arg (*args, hash_pair_t *); - hash_t *h = hash_header (v); - void *u = uword_to_pointer (p->key, void *); - - s = format (s, "%s", u); - - if (hash_value_bytes (h) > 0) - s = - format (s, " -> 0x%8U", format_hex_bytes, &p->value[0], - hash_value_bytes (h)); - - return s; -} - -static u8 * -hash_format_pair_default (u8 * s, va_list * args) -{ - void *CLIB_UNUSED (user_arg) = va_arg (*args, void *); - void *v = va_arg (*args, void *); - hash_pair_t *p = va_arg (*args, hash_pair_t *); - hash_t *h = hash_header (v); - - s = format (s, "0x%08x", p->key); - if (hash_value_bytes (h) > 0) - s = - format (s, " -> 0x%8U", format_hex_bytes, &p->value[0], - hash_value_bytes (h)); - return s; -} - -uword -hash_bytes (void *v) -{ - uword i, bytes; - hash_t *h = hash_header (v); - - if (!v) - return 0; - - bytes = vec_capacity (v, hash_header_bytes (v)); - - for (i = 0; i < hash_capacity (v); i++) - { - if (!hash_is_user (v, i)) - { - hash_pair_union_t *p = get_pair (v, i); - if (h->log2_pair_size > 0) - bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect); - else - bytes += vec_capacity (p->indirect.pairs, 0); - } - } - return bytes; -} - -u8 * -format_hash (u8 * s, va_list * va) -{ - void *v = va_arg (*va, void *); - int verbose = va_arg (*va, int); - hash_pair_t *p; - hash_t *h = hash_header (v); - uword i; - - s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n", - v, hash_elts (v), hash_capacity (v), hash_bytes (v)); - - { - uword *occupancy = 0; - - /* Count number of buckets with each occupancy. */ - for (i = 0; i < hash_capacity (v); i++) - { - uword j; - - if (hash_is_user (v, i)) - { - j = 1; - } - else - { - hash_pair_union_t *p = get_pair (v, i); - if (h->log2_pair_size > 0) - j = indirect_pair_get_len (&p->indirect); - else - j = vec_len (p->indirect.pairs); - } - - vec_validate (occupancy, j); - occupancy[j]++; - } - - s = format (s, " profile "); - for (i = 0; i < vec_len (occupancy); i++) - s = format (s, "%wd%c", occupancy[i], - i + 1 == vec_len (occupancy) ? '\n' : ' '); - - s = format (s, " lookup # of compares: "); - for (i = 1; i < vec_len (occupancy); i++) - s = format (s, "%wd: .%03d%c", i, - (1000 * i * occupancy[i]) / hash_elts (v), - i + 1 == vec_len (occupancy) ? '\n' : ' '); - - vec_free (occupancy); - } - - if (verbose) - { - /* *INDENT-OFF* */ - hash_foreach_pair (p, v, { - s = format (s, " %U\n", h->format_pair, h->format_pair_arg, v, p); - }); - /* *INDENT-ON* */ - } - - return s; -} - -static uword -unformat_hash_string_internal (unformat_input_t * input, - va_list * va, int is_vec) -{ - uword *hash = va_arg (*va, uword *); - int *result = va_arg (*va, int *); - u8 *string = 0; - uword *p; - - if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string)) - return 0; - - p = hash_get_mem (hash, string); - if (p) - *result = *p; - - vec_free (string); - return p ? 1 : 0; -} - -uword -unformat_hash_vec_string (unformat_input_t * input, va_list * va) -{ - return unformat_hash_string_internal (input, va, /* is_vec */ 1); -} - -uword -unformat_hash_string (unformat_input_t * input, va_list * va) -{ - return unformat_hash_string_internal (input, va, /* is_vec */ 0); -} - -clib_error_t * -hash_validate (void *v) -{ - hash_t *h = hash_header (v); - uword i, j; - uword *keys = 0; - clib_error_t *error = 0; - -#define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done; - - for (i = 0; i < hash_capacity (v); i++) - { - hash_pair_union_t *pu = get_pair (v, i); - - if (hash_is_user (v, i)) - { - CHECK (pu->direct.key != 0); - vec_add1 (keys, pu->direct.key); - } - else - { - hash_pair_t *p; - hash_pair_indirect_t *pi = &pu->indirect; - uword n; - - n = h->log2_pair_size > 0 - ? indirect_pair_get_len (pi) : vec_len (pi->pairs); - - for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p)) - { - /* Assert key uniqueness. */ - for (j = 0; j < vec_len (keys); j++) - CHECK (keys[j] != p->key); - vec_add1 (keys, p->key); - } - } - } - - CHECK (vec_len (keys) == h->elts); - - vec_free (keys); -done: - return error; -} - -/* - * fd.io coding-style-patch-verification: ON - * - * Local Variables: - * eval: (c-set-style "gnu") - * End: - */ |