40 #define QHASH_ALL_VALID ((1 << QHASH_KEYS_PER_BUCKET) - 1) 43 _qhash_resize (
void *
v,
uword length,
uword elt_bytes)
51 l += ((
f64) length / (
f64) (1 << l)) < .5;
53 v = _vec_resize (0, 1 << l, elt_bytes << l,
sizeof (h[0]),
64 memset (v, ~0, elt_bytes << l);
83 for (i = 0; i < 256; i++)
103 #define _(i) ((hash_keys[i] == search_key) << i) 104 t = (_(0) | _(1) | _(2) | _(3));
106 t |= (_(4) | _(5) | _(6) | _(7));
108 t |= (_(8) | _(9) | _(10) | _(11) | _(12) | _(13) | _(14) | _(15));
117 uword n_search_keys,
u32 * result_indices)
120 uword *k, *hash_keys;
121 uword n_left, bucket_mask;
126 memset (result_indices, ~0,
sizeof (result_indices[0]) * n_search_keys);
133 n_left = n_search_keys;
139 u32 a0, b0, c0, bi0, valid0, match0;
140 u32 a1, b1, c1, bi1, valid1, match1;
141 uword k0, k1, *h0, *h1;
165 bi0 = c0 & bucket_mask;
166 bi1 = c1 & bucket_mask;
168 h0 = hash_keys + bi0;
169 h1 = hash_keys + bi1;
181 r[0] = match0 ? bi0 : ~0;
182 r[1] = match1 ? bi1 : ~0;
189 r[-2] = p ? p[0] : ~0;
196 r[-1] = p ? p[0] : ~0;
202 u32 a0, b0, c0, bi0, valid0, match0;
219 bi0 = c0 & bucket_mask;
221 h0 = hash_keys + bi0;
229 r[0] = match0 ? bi0 : ~0;
236 r[-1] = p ? p[0] : ~0;
249 uword *k, *hash_keys;
250 uword n_left, match_mask, bucket_mask;
259 n_left = n_search_keys;
263 u32 a0, b0, c0, bi0, valid0;
264 u32 a1, b1, c1, bi1, valid1;
265 uword k0, k1, *h0, *h1;
289 bi0 = c0 & bucket_mask;
290 bi1 = c1 & bucket_mask;
292 h0 = hash_keys + bi0;
293 h1 = hash_keys + bi1;
308 bi += ((is_match1 ? bi1 : bi0)
310 *matching_key = (k - 2 - search_keys) + is_match1;
319 uword ki = k - 2 - search_keys;
340 u32 a0, b0, c0, bi0, valid0;
357 bi0 = c0 & bucket_mask;
359 h0 = hash_keys + bi0;
368 *matching_key = (k - 1 - search_keys);
378 *matching_key = (k - 1 - search_keys);
418 v = _vec_resize (v, dl, (l + dl) * elt_bytes,
sizeof (h[0]),
420 memset (v + l * elt_bytes, ~0, dl * elt_bytes);
462 _qhash_set_multiple (
void *
v,
465 uword n_search_keys,
u32 * result_indices)
468 uword *k, *hash_keys;
469 uword n_left, n_elts, bucket_mask;
473 v = _qhash_resize (
v, n_search_keys, elt_bytes);
488 n_left = n_search_keys;
493 u32 a0, b0, c0, bi0, match0, valid0, free0;
494 u32 a1, b1, c1, bi1, match1, valid1, free1;
524 bi0 = c0 & bucket_mask;
525 bi1 = c1 & bucket_mask;
527 h0 = hash_keys + bi0;
528 h1 = hash_keys + bi1;
540 valid1 = valid1 | (bi0 == bi1 ? free0 : 0);
543 n_elts += (match0 == 0) + (match1 == 0);
545 match0 = match0 ? match0 : free0;
546 match1 = match1 ? match1 : free1;
559 r[0] = h0 - hash_keys;
560 r[1] = h1 - hash_keys;
575 r[0] = h0 - hash_keys;
586 r[1] = h1 - hash_keys;
594 u32 a0, b0, c0, bi0, match0, valid0, free0;
611 bi0 = c0 & bucket_mask;
613 h0 = hash_keys + bi0;
622 n_elts += (match0 == 0);
624 match0 = match0 ? match0 : free0;
634 r[0] = h0 - hash_keys;
657 uword i, j = 0, k, l, t = ~0;
676 j = qhash_hash_mix (h, p->key) / QHASH_KEYS_PER_BUCKET;
696 clib_memswap (v + t * elt_bytes, v + l * elt_bytes, elt_bytes);
706 _qhash_unset_multiple (
void *
v,
709 uword n_search_keys,
u32 * result_indices)
712 uword *k, *hash_keys;
713 uword n_left, n_elts, bucket_mask;
719 for (i = 0; i < n_search_keys; i++)
720 result_indices[i] = ~0;
728 n_left = n_search_keys;
733 u32 a0, b0, c0, bi0, match0, valid0;
734 u32 a1, b1, c1, bi1, match1, valid1;
764 bi0 = c0 & bucket_mask;
765 bi1 = c1 & bucket_mask;
767 h0 = hash_keys + bi0;
768 h1 = hash_keys + bi1;
777 n_elts -= (match0 != 0) + (match1 != 0);
786 valid1 = bi0 == bi1 ? valid0 : valid1;
805 n_elts -= (match1 != 0);
814 u32 a0, b0, c0, bi0, match0, valid0;
831 bi0 = c0 & bucket_mask;
833 h0 = hash_keys + bi0;
838 n_elts -= (match0 != 0);
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
void clib_memswap(void *_a, void *_b, uword bytes)
#define hash_set(h, key, value)
sll srl srl sll sra u16x4 i
#define hash_unset(h, key)
static void qhash_min_log2_init()
static qhash_t * qhash_header(void *v)
static uword qhash_search_bucket(uword *hash_keys, uword search_key, uword m)
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
#define QHASH_KEYS_PER_BUCKET
static uword qhash_find_free(uword i, uword valid_mask)
static uword min_log2(uword x)
static uword qhash_unset_overflow(void *v, uword key, uword bi, uword *n_elts)
static uword pow2_mask(uword x)
#define vec_resize(V, N)
Resize a vector (no header, unspecified alignment) Add N elements to end of given vector V...
static uword unset_slow_path(void *v, uword elt_bytes, uword k0, uword bi0, uword valid0, uword match0, uword *n_elts)
static void * qhash_set_overflow(void *v, uword elt_bytes, uword key, uword bi, uword *n_elts, u32 *result)
#define hash_mix32(a0, b0, c0)
static uword round_pow2(uword x, uword pow2)
static uword first_set(uword x)
static uword hash_elts(void *v)
static uword qhash_min_log2(uword x)
#define QHASH_LOG2_KEYS_PER_BUCKET
static uword is_pow2(uword x)
void qhash_get_multiple(void *v, uword *search_keys, uword n_search_keys, u32 *result_indices)
#define clib_mem_alloc_aligned_no_fail(size, align)
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static u8 min_log2_table[256]
#define hash_foreach_pair(p, v, body)
Iterate over hash pairs.
static uword max_log2(uword x)
static void qhash_set_valid_elt_mask(qhash_t *h, uword i, uword mask)
#define hash_mix32_step_1(a, b, c)
u32 qhash_get_first_match(void *v, uword *search_keys, uword n_search_keys, uword *matching_key)
#define hash_mix32_step_2(a, b, c)
#define hash_mix32_step_3(a, b, c)
#define CLIB_CACHE_LINE_BYTES
u32 * overflow_free_indices
static uword qhash_get_valid_elt_mask(qhash_t *h, uword i)
#define hash_unset3(h, key, old_value)
u8 * hash_key_valid_bitmap