X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=vppinfra%2Fvppinfra%2Fhash.c;h=062ad8823e1669635850952dc4013739070b35cd;hb=e2e95ce6550a28a6ba5870c9c550acb619883f1a;hp=9e038b4fd8c57e8e5d848b703e6df4c44c695646;hpb=cb9cadad578297ffd78fa8a33670bdf1ab669e7e;p=vpp.git diff --git a/vppinfra/vppinfra/hash.c b/vppinfra/vppinfra/hash.c index 9e038b4fd8c..062ad8823e1 100644 --- a/vppinfra/vppinfra/hash.c +++ b/vppinfra/vppinfra/hash.c @@ -40,42 +40,50 @@ #include #include /* 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 +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 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) +get_pair (void *v, uword i) { - hash_t * h = hash_header (v); - hash_pair_t * p; + 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) +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])); + 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); +static u8 *hash_format_pair_default (u8 * s, va_list * args); #if uword_bits == 64 -static inline u64 zap64 (u64 x, word n) +static inline u64 +zap64 (u64 x, word n) { #define _(n) (((u64) 1 << (u64) (8*(n))) - (u64) 1) - static u64 masks_little_endian[] = { + static u64 masks_little_endian[] = { 0, _(1), _(2), _(3), _(4), _(5), _(6), _(7), }; static u64 masks_big_endian[] = { @@ -88,22 +96,23 @@ static inline u64 zap64 (u64 x, word n) return x & masks_little_endian[n]; } -u64 hash_memory64 (void * p, word n_bytes, u64 state) +static inline u64 +hash_memory64 (void *p, word n_bytes, u64 state) { - u64 * q = p; + u64 *q = p; u64 a, b, c, n; a = b = 0x9e3779b97f4a7c13LL; c = state; n = n_bytes; - while (n >= 3 * sizeof(u64)) + 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); + n -= 3 * sizeof (u64); q += 3; } @@ -114,32 +123,30 @@ u64 hash_memory64 (void * p, word n_bytes, u64 state) 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; + 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)); + 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)); + 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) +static inline u32 +zap32 (u32 x, word n) { #define _(n) (((u32) 1 << (u32) (8*(n))) - (u32) 1) static u32 masks_little_endian[] = { @@ -155,22 +162,23 @@ static inline u32 zap32 (u32 x, word n) return x & masks_little_endian[n]; } -u32 hash_memory32 (void * p, word n_bytes, u32 state) +static inline u32 +hash_memory32 (void *p, word n_bytes, u32 state) { - u32 * q = p; + u32 *q = p; u32 a, b, c, n; a = b = 0x9e3779b9; c = state; n = n_bytes; - while (n >= 3 * sizeof(u32)) + 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); + n -= 3 * sizeof (u32); q += 3; } @@ -181,33 +189,31 @@ u32 hash_memory32 (void * p, word n_bytes, u32 state) 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; + 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)); + 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)); + 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 +hash_memory (void *p, word n_bytes, uword state) { - uword * q = p; + uword *q = p; #if uword_bits == 64 return hash_memory64 (q, n_bytes, state); @@ -217,7 +223,8 @@ uword hash_memory (void * p, word n_bytes, uword state) } #if uword_bits == 64 -always_inline uword hash_uword (uword x) +always_inline uword +hash_uword (uword x) { u64 a, b, c; @@ -228,7 +235,8 @@ always_inline uword hash_uword (uword x) return c; } #else -always_inline uword hash_uword (uword x) +always_inline uword +hash_uword (uword x) { u32 a, b, c; @@ -242,7 +250,8 @@ always_inline uword hash_uword (uword x) /* 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) +always_inline uword +key_sum (hash_t * h, uword key) { uword sum; switch (pointer_to_uword ((void *) h->key_sum)) @@ -252,15 +261,15 @@ always_inline uword key_sum (hash_t * h, uword key) break; case KEY_FUNC_POINTER_UWORD: - sum = hash_uword (* uword_to_pointer (key, uword *)); + sum = hash_uword (*uword_to_pointer (key, uword *)); break; case KEY_FUNC_POINTER_U32: - sum = hash_uword (* uword_to_pointer (key, u32 *)); + sum = hash_uword (*uword_to_pointer (key, u32 *)); break; case KEY_FUNC_STRING: - sum = string_key_sum (h, key); + sum = string_key_sum (h, key); break; default: @@ -271,7 +280,8 @@ always_inline uword key_sum (hash_t * h, uword key) return sum; } -always_inline uword key_equal1 (hash_t * h, uword key1, uword key2, uword e) +always_inline uword +key_equal1 (hash_t * h, uword key1, uword key2, uword e) { switch (pointer_to_uword ((void *) h->key_equal)) { @@ -279,15 +289,17 @@ always_inline uword key_equal1 (hash_t * h, uword key1, uword key2, uword e) break; case KEY_FUNC_POINTER_UWORD: - e = * uword_to_pointer (key1, uword *) == * uword_to_pointer (key2, 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 *); + e = *uword_to_pointer (key1, u32 *) == *uword_to_pointer (key2, u32 *); break; case KEY_FUNC_STRING: - e = string_key_equal (h, key1, key2); + e = string_key_equal (h, key1, key2); break; default: @@ -298,21 +310,22 @@ always_inline uword key_equal1 (hash_t * h, uword key1, uword key2, uword e) } /* Compares two keys: returns 1 if equal, 0 if not. */ -always_inline uword key_equal (hash_t * h, uword key1, uword key2) +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) + 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) +get_indirect (void *v, hash_pair_indirect_t * pi, uword key) { - hash_t * h = hash_header (v); - hash_pair_t * p0, * p1; + hash_t *h = hash_header (v); + hash_pair_t *p0, *p1; p0 = p1 = pi->pairs; if (h->log2_pair_size > 0) @@ -331,14 +344,11 @@ get_indirect (void * v, hash_pair_indirect_t * pi, uword key) } static hash_pair_union_t * -set_indirect_is_user (void * v, - uword i, - hash_pair_union_t * p, - uword key) +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; + 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) @@ -346,9 +356,9 @@ set_indirect_is_user (void * v, else { log2_bytes = 1 + hash_pair_log2_bytes (h); - q = clib_mem_alloc (1 << log2_bytes); + q = clib_mem_alloc (1ULL << log2_bytes); } - memcpy (q, &p->direct, hash_pair_bytes (h)); + clib_memcpy (q, &p->direct, hash_pair_bytes (h)); pi->pairs = q; if (h->log2_pair_size > 0) @@ -364,12 +374,12 @@ set_indirect_is_user (void * v, } static hash_pair_union_t * -set_indirect (void * v, hash_pair_indirect_t * pi, uword key, +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; + hash_t *h = hash_header (v); + hash_pair_t *new_pair; + hash_pair_union_t *q; q = get_indirect (v, pi, key); if (q) @@ -388,11 +398,11 @@ set_indirect (void * v, hash_pair_indirect_t * pi, uword key, log2_bytes = indirect_pair_get_log2_bytes (pi); new_len = len + 1; - if (new_len * hash_pair_bytes (h) > (1 << log2_bytes)) + if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes)) { pi->pairs = clib_mem_realloc (pi->pairs, - 1 << (log2_bytes + 1), - 1 << log2_bytes); + 1ULL << (log2_bytes + 1), + 1ULL << log2_bytes); log2_bytes++; } @@ -405,17 +415,18 @@ set_indirect (void * v, hash_pair_indirect_t * pi, uword key, return (hash_pair_union_t *) new_pair; } -static void unset_indirect (void * v, uword i, hash_pair_t * q) +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; + 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)); + 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); @@ -424,11 +435,12 @@ static void unset_indirect (void * v, uword i, hash_pair_t * q) Make indirect pointer direct and free indirect memory. */ if (len <= 2) { - hash_pair_t * r = pi->pairs; + hash_pair_t *r = pi->pairs; if (len == 2) { - memcpy (p, q == r ? hash_forward1 (h, r) : r, hash_pair_bytes (h)); + clib_memcpy (p, q == r ? hash_forward1 (h, r) : r, + hash_pair_bytes (h)); set_is_user (v, i, 1); } else @@ -443,33 +455,33 @@ static void unset_indirect (void * v, uword i, hash_pair_t * q) { /* If deleting a pair we need to keep non-null pairs together. */ if (q < e) - memcpy (q, e, hash_pair_bytes (h)); + 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); + indirect_pair_set (pi, indirect_pair_get_log2_bytes (pi), len - 1); } } -enum lookup_opcode { +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) +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; + hash_t *h = hash_header (v); + hash_pair_union_t *p = 0; uword found_key = 0; uword i; - if (! v) + if (!v) return 0; i = key_sum (h, key) & (_vec_len (v) - 1); @@ -484,7 +496,8 @@ static hash_pair_t * lookup (void * v, uword key, enum lookup_opcode op, { set_is_user (v, i, 0); if (old_value) - memcpy (old_value, p->direct.value, hash_value_bytes (h)); + clib_memcpy (old_value, p->direct.value, + hash_value_bytes (h)); zero_pair (h, &p->direct); } } @@ -498,11 +511,11 @@ static hash_pair_t * lookup (void * v, uword key, enum lookup_opcode op, } else { - hash_pair_indirect_t * pi = &p->indirect; + hash_pair_indirect_t *pi = &p->indirect; if (op == SET) { - if (! pi->pairs) + if (!pi->pairs) { p->direct.key = key; set_is_user (v, i, 1); @@ -517,12 +530,13 @@ static hash_pair_t * lookup (void * v, uword key, enum lookup_opcode op, if (found_key && op == UNSET) { if (old_value) - memcpy (old_value, &p->direct.value, hash_value_bytes (h)); + 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. */ + Otherwise we might be tempted to play with it. */ p = 0; } } @@ -532,8 +546,8 @@ static hash_pair_t * lookup (void * v, uword key, enum lookup_opcode op, { /* Save away old value for caller. */ if (old_value && found_key) - memcpy (old_value, &p->direct.value, hash_value_bytes (h)); - memcpy (&p->direct.value, new_value, hash_value_bytes (h)); + 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) @@ -545,17 +559,18 @@ static hash_pair_t * lookup (void * v, uword key, enum lookup_opcode op, } /* Fetch value of key. */ -uword * _hash_get (void * v, uword key) +uword * +_hash_get (void *v, uword key) { - hash_t * h = hash_header (v); - hash_pair_t * p; + hash_t *h = hash_header (v); + hash_pair_t *p; /* Don't even search table if its empty. */ - if (! v || h->elts == 0) + if (!v || h->elts == 0) return 0; p = lookup (v, key, GET, 0, 0); - if (! p) + if (!p) return 0; if (h->log2_pair_size == 0) return &p->key; @@ -563,13 +578,17 @@ uword * _hash_get (void * v, uword key) 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_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_pair_t * +hash_next (void *v, hash_next_t * hn) { - hash_t * h = hash_header (v); - hash_pair_t * p; + hash_t *h = hash_header (v); + hash_pair_t *p; while (1) { @@ -580,9 +599,8 @@ hash_pair_t * hash_next (void * v, hash_next_t * hn) /* 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); + (HASH_FLAG_NO_AUTO_GROW + | HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_HASH_NEXT_IN_PROGRESS); } else if (hn->i >= hash_capacity (v)) { @@ -600,7 +618,7 @@ hash_pair_t * hash_next (void * v, hash_next_t * hn) } else { - hash_pair_indirect_t * pi = (void *) p; + hash_pair_indirect_t *pi = (void *) p; uword n; if (h->log2_pair_size > 0) @@ -620,17 +638,18 @@ hash_pair_t * hash_next (void * v, hash_next_t * hn) } /* Remove key from table. */ -void * _hash_unset (void * v, uword key, void * old_value) +void * +_hash_unset (void *v, uword key, void *old_value) { - hash_t * h; + hash_t *h; - if (! v) + if (!v) return v; (void) lookup (v, key, UNSET, 0, old_value); h = hash_header (v); - if (! (h->flags & HASH_FLAG_NO_AUTO_SHRINK)) + if (!(h->flags & HASH_FLAG_NO_AUTO_SHRINK)) { /* Resize when 1/4 full. */ if (h->elts > 32 && 4 * (h->elts + 1) < vec_len (v)) @@ -640,25 +659,29 @@ void * _hash_unset (void * v, uword key, void * old_value) return v; } -void * _hash_create (uword elts, hash_t * h_user) +void * +_hash_create (uword elts, hash_t * h_user) { - hash_t * h; + hash_t *h; uword log2_pair_size; - void * v; + 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 = 1 << max_log2 (elts); + 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]), + /* 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); @@ -670,10 +693,10 @@ void * _hash_create (uword elts, hash_t * h_user) /* 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_user) + h->flags = HASH_FLAG_NO_AUTO_SHRINK; - if (! h->format_pair) + if (!h->format_pair) { h->format_pair = hash_format_pair_default; h->format_pair_arg = 0; @@ -682,13 +705,14 @@ void * _hash_create (uword elts, hash_t * h_user) return v; } -void * _hash_free (void * v) +void * +_hash_free (void *v) { - hash_t * h = hash_header (v); - hash_pair_union_t * p; + hash_t *h = hash_header (v); + hash_pair_union_t *p; uword i; - if (! v) + if (!v) return v; /* We zero all freed memory in case user would be tempted to use it. */ @@ -708,19 +732,22 @@ void * _hash_free (void * v) return 0; } -static void * hash_resize_internal (void * old, uword new_size, uword free_old) +static void * +hash_resize_internal (void *old, uword new_size, uword free_old) { - void * new; - hash_pair_t * p; + void *new; + hash_pair_t *p; new = 0; if (new_size > 0) { - hash_t * h = old ? hash_header (old) : 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) @@ -728,23 +755,30 @@ static void * hash_resize_internal (void * old, uword new_size, uword free_old) return new; } -void * hash_resize (void * old, uword new_size) -{ return hash_resize_internal (old, new_size, 1); } +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_dup (void *old) +{ + return hash_resize_internal (old, vec_len (old), 0); +} -void * _hash_set3 (void * v, uword key, void * value, void * old_value) +void * +_hash_set3 (void *v, uword key, void *value, void *old_value) { - hash_t * h; + hash_t *h; - if (! v) + 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)) + if (!(h->flags & HASH_FLAG_NO_AUTO_GROW)) { /* Resize when 3/4 full. */ if (4 * (h->elts + 1) > 3 * vec_len (v)) @@ -754,63 +788,67 @@ void * _hash_set3 (void * v, uword key, void * value, void * old_value) return v; } -uword vec_key_sum (hash_t * h, uword key) +uword +vec_key_sum (hash_t * h, uword key) { - void * v = uword_to_pointer (key, void *); + 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) +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 *); + 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) +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 *); + 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: + 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 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 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; - } + case 8: + { + u64 *w = u; + for (i = 0; i < vec_len (w); i++) + s = format (s, "0x%Lx, ", w[i]); + break; + } - default: + 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]); @@ -818,78 +856,89 @@ u8 * vec_key_format_pair (u8 * s, va_list * args) return s; } -uword mem_key_sum (hash_t * h, uword key) +uword +mem_key_sum (hash_t * h, uword key) { - uword * v = uword_to_pointer (key, void *); + 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) +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 *); + 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) +uword +string_key_sum (hash_t * h, uword key) { - char * v = uword_to_pointer (key, char *); + 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) +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 *); + 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) +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 *); + 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)); + 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) +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); + 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)); + s = + format (s, " -> 0x%8U", format_hex_bytes, &p->value[0], + hash_value_bytes (h)); return s; } -uword hash_bytes (void * v) +uword +hash_bytes (void *v) { uword i, bytes; - hash_t * h = hash_header (v); + hash_t *h = hash_header (v); - if (! 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)) + if (!hash_is_user (v, i)) { - hash_pair_union_t * p = get_pair (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); + bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect); else bytes += vec_capacity (p->indirect.pairs, 0); } @@ -897,20 +946,20 @@ uword hash_bytes (void * v) return bytes; } -u8 * format_hash (u8 * s, va_list * va) +u8 * +format_hash (u8 * s, va_list * va) { - void * v = va_arg (*va, void *); + void *v = va_arg (*va, void *); int verbose = va_arg (*va, int); - hash_pair_t * p; - hash_t * h = hash_header (v); + 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)); + v, hash_elts (v), hash_capacity (v), hash_bytes (v)); { - uword * occupancy = 0; + uword *occupancy = 0; /* Count number of buckets with each occupancy. */ for (i = 0; i < hash_capacity (v); i++) @@ -923,7 +972,7 @@ u8 * format_hash (u8 * s, va_list * va) } else { - hash_pair_union_t * p = get_pair (v, i); + hash_pair_union_t *p = get_pair (v, i); if (h->log2_pair_size > 0) j = indirect_pair_get_len (&p->indirect); else @@ -950,9 +999,11 @@ u8 * format_hash (u8 * s, va_list * va) 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; @@ -960,15 +1011,14 @@ u8 * format_hash (u8 * s, va_list * va) static uword unformat_hash_string_internal (unformat_input_t * input, - va_list * va, - int is_vec) + va_list * va, int is_vec) { - uword * hash = va_arg (*va, uword *); - int * result = va_arg (*va, int *); - u8 * string = 0; - uword * p; + 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)) + if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string)) return 0; p = hash_get_mem (hash, string); @@ -981,24 +1031,29 @@ unformat_hash_string_internal (unformat_input_t * input, uword unformat_hash_vec_string (unformat_input_t * input, va_list * va) -{ return unformat_hash_string_internal (input, va, /* is_vec */ 1); } +{ + 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); } +{ + return unformat_hash_string_internal (input, va, /* is_vec */ 0); +} -clib_error_t * hash_validate (void * v) +clib_error_t * +hash_validate (void *v) { - hash_t * h = hash_header (v); + hash_t *h = hash_header (v); uword i, j; - uword * keys = 0; - clib_error_t * error = 0; + 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); + hash_pair_union_t *pu = get_pair (v, i); if (hash_is_user (v, i)) { @@ -1007,13 +1062,12 @@ clib_error_t * hash_validate (void * v) } else { - hash_pair_t * p; - hash_pair_indirect_t * pi = &pu->indirect; + 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); + ? indirect_pair_get_len (pi) : vec_len (pi->pairs); for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p)) { @@ -1028,6 +1082,14 @@ clib_error_t * hash_validate (void * v) CHECK (vec_len (keys) == h->elts); vec_free (keys); - done: +done: return error; } + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */