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),
94 return x & masks_big_endian[n];
96 return x & masks_little_endian[n];
109 static inline u64 __attribute__ ((no_sanitize_address))
115 a = b = 0x9e3779b97f4a7c13LL;
119 while (n >= 3 *
sizeof (
u64))
125 n -= 3 *
sizeof (
u64);
130 switch (n /
sizeof (
u64))
135 if (n %
sizeof (
u64))
141 if (n %
sizeof (
u64))
146 if (n %
sizeof (
u64))
161 #define _(n) (((u32) 1 << (u32) (8*(n))) - (u32) 1) 162 static u32 masks_little_endian[] = {
165 static u32 masks_big_endian[] = {
166 0, ~_(3), ~_(2), ~_(1),
170 return x & masks_big_endian[n];
172 return x & masks_little_endian[n];
185 while (n >= 3 *
sizeof (
u32))
191 n -= 3 *
sizeof (
u32);
196 switch (n /
sizeof (
u32))
201 if (n %
sizeof (
u32))
207 if (n %
sizeof (
u32))
212 if (n %
sizeof (
u32))
229 return hash_memory64 (q, n_bytes, state);
241 a = b = 0x9e3779b97f4a7c13LL;
326 uword e = key1 == key2;
327 if (CLIB_DEBUG > 0 && key1 == key2)
362 uword log2_bytes = 0;
405 uword len, new_len, log2_bytes;
414 1ULL << (log2_bytes + 1),
472 _vec_len (pi->
pairs) -= 1;
487 void *new_value,
void *old_value)
497 i =
key_sum (h, key) & (_vec_len (v) - 1);
540 if (found_key && op ==
UNSET)
555 if (op ==
SET && p != 0)
558 if (old_value && found_key)
564 h->
elts += !found_key;
566 h->
elts -= found_key;
573 _hash_get (
void *
v,
uword key)
579 if (!
v || h->
elts == 0)
592 _hash_get_pair (
void *
v,
uword key)
605 if (hn->
i == 0 && hn->
j == 0)
619 memset (hn, 0,
sizeof (hn[0]));
652 _hash_unset (
void *
v,
uword key,
void *old_value)
676 uword log2_pair_size;
755 new = _hash_create (new_size, h);
758 new = _hash_set3 (
new, p->
key, &p->
value[0], 0);
781 _hash_set3 (
void *
v,
uword key,
void *value,
void *old_value)
789 (void)
lookup (
v, key,
SET, value, old_value);
815 return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->
user);
821 void *
CLIB_UNUSED (user_arg) = va_arg (*args,
void *);
822 void *
v = va_arg (*args,
void *);
837 for (i = 0; i <
vec_len (w); i++)
838 s =
format (s,
"0x%x, ", w[i]);
845 for (i = 0; i <
vec_len (w); i++)
846 s =
format (s,
"0x%x, ", w[i]);
853 for (i = 0; i <
vec_len (w); i++)
854 s =
format (s,
"0x%Lx, ", w[i]);
881 return v1 && v2 && 0 == memcmp (v1, v2, h->
user);
896 return v1 && v2 && 0 == strcmp (v1, v2);
902 void *
CLIB_UNUSED (user_arg) = va_arg (*args,
void *);
903 void *
v = va_arg (*args,
void *);
921 void *
CLIB_UNUSED (user_arg) = va_arg (*args,
void *);
922 void *
v = va_arg (*args,
void *);
962 void *
v = va_arg (*va,
void *);
963 int verbose = va_arg (*va,
int);
968 s =
format (s,
"hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
972 uword *occupancy = 0;
996 s =
format (s,
" profile ");
997 for (i = 0; i <
vec_len (occupancy); i++)
998 s =
format (s,
"%wd%c", occupancy[i],
999 i + 1 == vec_len (occupancy) ?
'\n' :
' ');
1001 s =
format (s,
" lookup # of compares: ");
1002 for (i = 1; i <
vec_len (occupancy); i++)
1003 s =
format (s,
"%wd: .%03d%c", i,
1004 (1000 * i * occupancy[i]) /
hash_elts (v),
1005 i + 1 ==
vec_len (occupancy) ?
'\n' :
' ');
1024 va_list * va,
int is_vec)
1027 int *result = va_arg (*va,
int *);
1031 if (!
unformat (input, is_vec ?
"%v%_" :
"%s%_", &
string))
1062 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done; 1085 for (j = 0; j <
vec_len (keys); j++)
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
u8 * string_key_format_pair(u8 *s, va_list *args)
sll srl srl sll sra u16x4 i
static void unset_indirect(void *v, uword i, hash_pair_t *q)
static void init_pair(hash_t *h, hash_pair_t *p)
uword mem_key_equal(hash_t *h, uword key1, uword key2)
static uword indirect_pair_get_len(hash_pair_indirect_t *p)
void * hash_resize(void *old, uword new_size)
#define KEY_FUNC_POINTER_UWORD
static void * clib_mem_realloc(void *p, uword new_size, uword old_size)
#define HASH_FLAG_NO_AUTO_GROW
#define vec_free_header(h)
Free vector user header (syntactic sugar)
static hash_pair_union_t * get_indirect(void *v, hash_pair_indirect_t *pi, uword key)
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
static void zero_pair(hash_t *h, hash_pair_t *p)
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
static void indirect_pair_set(hash_pair_indirect_t *p, uword log2_alloc, uword len)
static uword hash_header_bytes(void *v)
static u32 zap32(u32 x, word n)
#define KEY_FUNC_POINTER_U32
#define vec_new(T, N)
Create new vector of given type and length (unspecified alignment, no header).
static void set_is_user(void *v, uword i, uword is_user)
static uword key_equal1(hash_t *h, uword key1, uword key2, uword e)
static uword key_sum(hash_t *h, uword key)
uword vec_key_sum(hash_t *h, uword key)
u8 * format_hash(u8 *s, va_list *va)
static uword hash_value_bytes(hash_t *h)
static uword pointer_to_uword(const void *p)
u8 * vec_key_format_pair(u8 *s, va_list *args)
static hash_pair_union_t * set_indirect(void *v, hash_pair_indirect_t *pi, uword key, uword *found_key)
static hash_t * hash_header(void *v)
static uword hash_capacity(void *v)
clib_error_t * hash_validate(void *v)
static uword hash_is_user(void *v, uword i)
static u8 * hash_format_pair_default(u8 *s, va_list *args)
static uword hash_pair_bytes(hash_t *h)
uword hash_bytes(void *v)
#define uword_to_pointer(u, type)
static uword hash_pair_log2_bytes(hash_t *h)
hash_pair_t * hash_next(void *v, hash_next_t *hn)
static void * hash_resize_internal(void *old, uword new_size, uword free_old)
static hash_pair_t * lookup(void *v, uword key, enum lookup_opcode op, void *new_value, void *old_value)
hash_pair_indirect_t indirect
#define clib_arch_is_big_endian
#define hash_mix64(a0, b0, c0)
#define vec_free(V)
Free vector's memory (no header).
static void * hash_forward1(hash_t *h, void *v)
#define clib_memcpy(a, b, c)
#define hash_mix32(a0, b0, c0)
static uword hash_uword(uword x)
#define HASH_FLAG_HASH_NEXT_IN_PROGRESS
#define vec_capacity(v, b)
Total number of bytes that can fit in vector with current allocation.
static uword indirect_pair_get_log2_bytes(hash_pair_indirect_t *p)
static uword unformat_hash_string_internal(unformat_input_t *input, va_list *va, int is_vec)
static hash_pair_union_t * get_pair(void *v, uword i)
void * hash_dup(void *old)
#define hash_create(elts, value_bytes)
static hash_pair_union_t * set_indirect_is_user(void *v, uword i, hash_pair_union_t *p, uword key)
static uword hash_elts(void *v)
static void * hash_forward(hash_t *h, void *v, uword n)
uword string_key_sum(hash_t *h, uword key)
uword hash_memory(void *p, word n_bytes, uword state)
vhost_vring_state_t state
static void clib_mem_free(void *p)
static void * clib_mem_alloc(uword size)
uword unformat_hash_string(unformat_input_t *input, va_list *va)
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
#define hash_foreach_pair(p, v, body)
Iterate over hash pairs.
static uword max_log2(uword x)
#define clib_mem_unaligned(pointer, type)
#define hash_get_mem(h, key)
uword string_key_equal(hash_t *h, uword key1, uword key2)
uword unformat_hash_vec_string(unformat_input_t *input, va_list *va)
uword mem_key_sum(hash_t *h, uword key)
#define HASH_FLAG_NO_AUTO_SHRINK
static uword key_equal(hash_t *h, uword key1, uword key2)
uword vec_key_equal(hash_t *h, uword key1, uword key2)
static u32 hash_memory32(void *p, word n_bytes, u32 state)