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,
65 memset (v, ~0, elt_bytes << l);
83 for (i = 0; i < 256; i++)
100 #define _(i) ((hash_keys[i] == search_key) << i) 101 t = (_ (0) | _ (1) | _ (2) | _ (3));
103 t |= (_ (4) | _ (5) | _ (6) | _ (7));
105 t |= (_ (8) | _ (9) | _ (10) | _ (11)
106 | _ (12) | _ (13) | _ (14) | _ (15));
116 u32 * result_indices)
119 uword * k, * hash_keys;
120 uword n_left, bucket_mask;
125 memset (result_indices, ~0,
sizeof (result_indices[0]) * n_search_keys);
132 n_left = n_search_keys;
138 u32 a0, b0, c0, bi0, valid0, match0;
139 u32 a1, b1, c1, bi1, valid1, match1;
140 uword k0, k1, * h0, * h1;
164 bi0 = c0 & bucket_mask;
165 bi1 = c1 & bucket_mask;
167 h0 = hash_keys + bi0;
168 h1 = hash_keys + bi1;
180 r[0] = match0 ? bi0 : ~0;
181 r[1] = match1 ? bi1 : ~0;
188 r[-2] = p ? p[0] : ~0;
195 r[-1] = p ? p[0] : ~0;
201 u32 a0, b0, c0, bi0, valid0, match0;
218 bi0 = c0 & bucket_mask;
220 h0 = hash_keys + bi0;
228 r[0] = match0 ? bi0 : ~0;
235 r[-1] = p ? p[0] : ~0;
246 uword * matching_key)
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);
420 v = _vec_resize (v, dl,
421 (l + dl) * elt_bytes,
424 memset (v + l*elt_bytes, ~0, dl * elt_bytes);
464 _qhash_set_multiple (
void * v,
468 u32 * result_indices)
471 uword * k, * hash_keys;
472 uword n_left, n_elts, bucket_mask;
475 if (
vec_len (v) < n_search_keys)
476 v = _qhash_resize (v, n_search_keys, elt_bytes);
491 n_left = n_search_keys;
496 u32 a0, b0, c0, bi0, match0, valid0, free0;
497 u32 a1, b1, c1, bi1, match1, valid1, free1;
527 bi0 = c0 & bucket_mask;
528 bi1 = c1 & bucket_mask;
530 h0 = hash_keys + bi0;
531 h1 = hash_keys + bi1;
543 valid1 = valid1 | (bi0 == bi1 ? free0 : 0);
546 n_elts += (match0 == 0) + (match1 == 0);
548 match0 = match0 ? match0 : free0;
549 match1 = match1 ? match1 : free1;
562 r[0] = h0 - hash_keys;
563 r[1] = h1 - hash_keys;
578 r[0] = h0 - hash_keys;
589 r[1] = h1 - hash_keys;
597 u32 a0, b0, c0, bi0, match0, valid0, free0;
614 bi0 = c0 & bucket_mask;
616 h0 = hash_keys + bi0;
625 n_elts += (match0 == 0);
627 match0 = match0 ? match0 : free0;
637 r[0] = h0 - hash_keys;
660 uword i, j = 0, k, l, t = ~0;
679 j = qhash_hash_mix (h, p->key) / QHASH_KEYS_PER_BUCKET;
710 _qhash_unset_multiple (
void * v,
714 u32 * result_indices)
717 uword * k, * hash_keys;
718 uword n_left, n_elts, bucket_mask;
724 for (i = 0; i < n_search_keys; i++)
725 result_indices[i] = ~0;
733 n_left = n_search_keys;
738 u32 a0, b0, c0, bi0, match0, valid0;
739 u32 a1, b1, c1, bi1, match1, valid1;
769 bi0 = c0 & bucket_mask;
770 bi1 = c1 & bucket_mask;
772 h0 = hash_keys + bi0;
773 h1 = hash_keys + bi1;
782 n_elts -= (match0 != 0) + (match1 != 0);
791 valid1 = bi0 == bi1 ? valid0 : valid1;
811 n_elts -= (match1 != 0);
821 u32 a0, b0, c0, bi0, match0, valid0;
838 bi0 = c0 & bucket_mask;
840 h0 = hash_keys + bi0;
845 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)
always_inline uword round_pow2(uword x, uword pow2)
#define hash_set(h, key, value)
sll srl srl sll sra u16x4 i
#define hash_unset(h, key)
static void qhash_min_log2_init()
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
#define QHASH_KEYS_PER_BUCKET
always_inline uword max_log2(uword x)
always_inline uword qhash_get_valid_elt_mask(qhash_t *h, uword i)
always_inline qhash_t * qhash_header(void *v)
static uword qhash_unset_overflow(void *v, uword key, uword bi, uword *n_elts)
always_inline uword first_set(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)
always_inline uword qhash_search_bucket(uword *hash_keys, uword search_key, uword m)
always_inline void qhash_set_valid_elt_mask(qhash_t *h, uword i, uword mask)
#define hash_mix32(a0, b0, c0)
always_inline uword hash_elts(void *v)
always_inline uword is_pow2(uword x)
always_inline uword qhash_find_free(uword i, uword valid_mask)
static uword qhash_min_log2(uword x)
#define QHASH_LOG2_KEYS_PER_BUCKET
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)
#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)
always_inline uword min_log2(uword x)
#define hash_mix32_step_2(a, b, c)
always_inline uword pow2_mask(uword x)
#define hash_mix32_step_3(a, b, c)
#define CLIB_CACHE_LINE_BYTES
u32 * overflow_free_indices
#define hash_unset3(h, key, old_value)
u8 * hash_key_valid_bitmap