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];
117 int page_boundary_crossing;
118 u64 start_addr, end_addr;
129 start_addr = (
u64) p;
130 end_addr = start_addr + n_bytes + 7;
131 page_boundary_crossing = (start_addr >> 12) != (end_addr >> 12);
133 a = b = 0x9e3779b97f4a7c13LL;
137 while (n >= 3 *
sizeof (
u64))
143 n -= 3 *
sizeof (
u64);
148 switch (n /
sizeof (
u64))
153 if (n %
sizeof (
u64))
159 n %
sizeof (
u64)) << 8;
163 c += zap64 (tmp.as_u64, n % sizeof (
u64)) << 8;
170 if (n %
sizeof (
u64))
180 b += zap64 (tmp.as_u64, n % sizeof (
u64));
186 if (n %
sizeof (
u64))
196 a += zap64 (tmp.as_u64, n % sizeof (
u64));
212 #define _(n) (((u32) 1 << (u32) (8*(n))) - (u32) 1) 213 static u32 masks_little_endian[] = {
216 static u32 masks_big_endian[] = {
217 0, ~_(3), ~_(2), ~_(1),
221 return x & masks_big_endian[n];
223 return x & masks_little_endian[n];
236 while (n >= 3 *
sizeof (
u32))
242 n -= 3 *
sizeof (
u32);
247 switch (n /
sizeof (
u32))
252 if (n %
sizeof (
u32))
258 if (n %
sizeof (
u32))
263 if (n %
sizeof (
u32))
280 return hash_memory64 (q, n_bytes, state);
292 a = b = 0x9e3779b97f4a7c13LL;
385 uword e = key1 == key2;
386 if (CLIB_DEBUG > 0 && key1 == key2)
421 uword log2_bytes = 0;
473 1ULL << (log2_bytes + 1),
531 _vec_len (pi->
pairs) -= 1;
546 void *new_value,
void *old_value)
556 i =
key_sum (h, key) & (_vec_len (v) - 1);
599 if (found_key && op ==
UNSET)
614 if (op ==
SET && p != 0)
617 if (old_value && found_key)
623 h->
elts += !found_key;
625 h->
elts -= found_key;
638 if (!v || h->
elts == 0)
664 if (hn->
i == 0 && hn->
j == 0)
711 _hash_unset (
void *v,
uword key,
void *old_value)
735 uword log2_pair_size;
747 v = _vec_resize ((
void *) 0,
814 new = _hash_create (new_size, h);
817 new = _hash_set3 (
new, p->
key, &p->
value[0], 0);
840 _hash_set3 (
void *v,
uword key,
void *
value,
void *old_value)
874 return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->
user);
880 void *
CLIB_UNUSED (user_arg) = va_arg (*args,
void *);
881 void *v = va_arg (*args,
void *);
896 for (i = 0; i <
vec_len (w); i++)
897 s =
format (s,
"0x%x, ", w[i]);
904 for (i = 0; i <
vec_len (w); i++)
905 s =
format (s,
"0x%x, ", w[i]);
912 for (i = 0; i <
vec_len (w); i++)
913 s =
format (s,
"0x%Lx, ", w[i]);
940 return v1 && v2 && 0 == memcmp (v1, v2, h->
user);
955 return v1 && v2 && 0 == strcmp (v1, v2);
961 void *
CLIB_UNUSED (user_arg) = va_arg (*args,
void *);
962 void *v = va_arg (*args,
void *);
980 void *
CLIB_UNUSED (user_arg) = va_arg (*args,
void *);
981 void *v = va_arg (*args,
void *);
1021 void *v = va_arg (*va,
void *);
1022 int verbose = va_arg (*va,
int);
1027 s =
format (s,
"hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
1031 uword *occupancy = 0;
1055 s =
format (s,
" profile ");
1056 for (i = 0; i <
vec_len (occupancy); i++)
1057 s =
format (s,
"%wd%c", occupancy[i],
1058 i + 1 == vec_len (occupancy) ?
'\n' :
' ');
1060 s =
format (s,
" lookup # of compares: ");
1061 for (i = 1; i <
vec_len (occupancy); i++)
1062 s =
format (s,
"%wd: .%03d%c", i,
1063 (1000 * i * occupancy[i]) /
hash_elts (v),
1064 i + 1 ==
vec_len (occupancy) ?
'\n' :
' ');
1083 va_list * va,
int is_vec)
1086 int *result = va_arg (*va,
int *);
1090 if (!
unformat (input, is_vec ?
"%v%_" :
"%s%_", &
string))
1121 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done; 1144 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)
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
#define clib_memcpy_fast(a, b, c)
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
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)
#define CLIB_MEM_OVERFLOW(a, b, c)
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)
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)
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)
sll srl srl sll sra u16x4 i
#define vec_free(V)
Free vector's memory (no header).
static void * hash_forward1(hash_t *h, void *v)
#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)
#define uword_to_pointer(u, type)
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)
static void clib_mem_free(void *p)
#define clib_mem_unaligned(pointer, type)
static void * clib_mem_alloc(uword size)
uword unformat_hash_string(unformat_input_t *input, va_list *va)
static uword pointer_to_uword(const void *p)
#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 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)
vl_api_dhcp_client_state_t state
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)