40 #define QHASH_ALL_VALID ((1 << QHASH_KEYS_PER_BUCKET) - 1) 51 l += ((
f64) length / (
f64) (1 << l)) < .5;
53 v = _vec_resize (0, 1 << l, elt_bytes << l,
sizeof (h[0]),
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;
127 sizeof (result_indices[0]) * n_search_keys);
134 n_left = n_search_keys;
140 u32 a0, b0, c0, bi0, valid0, match0;
141 u32 a1, b1, c1, bi1, valid1, match1;
142 uword k0, k1, *h0, *h1;
166 bi0 = c0 & bucket_mask;
167 bi1 = c1 & bucket_mask;
169 h0 = hash_keys + bi0;
170 h1 = hash_keys + bi1;
182 r[0] = match0 ? bi0 : ~0;
183 r[1] = match1 ? bi1 : ~0;
190 r[-2] = p ? p[0] : ~0;
197 r[-1] = p ? p[0] : ~0;
203 u32 a0, b0, c0, bi0, valid0, match0;
220 bi0 = c0 & bucket_mask;
222 h0 = hash_keys + bi0;
230 r[0] = match0 ? bi0 : ~0;
237 r[-1] = p ? p[0] : ~0;
250 uword *k, *hash_keys;
251 uword n_left, match_mask, bucket_mask;
260 n_left = n_search_keys;
264 u32 a0, b0, c0, bi0, valid0;
265 u32 a1, b1, c1, bi1, valid1;
266 uword k0, k1, *h0, *h1;
290 bi0 = c0 & bucket_mask;
291 bi1 = c1 & bucket_mask;
293 h0 = hash_keys + bi0;
294 h1 = hash_keys + bi1;
309 bi += ((is_match1 ? bi1 : bi0)
311 *matching_key = (k - 2 - search_keys) + is_match1;
320 uword ki = k - 2 - search_keys;
341 u32 a0, b0, c0, bi0, valid0;
358 bi0 = c0 & bucket_mask;
360 h0 = hash_keys + bi0;
369 *matching_key = (k - 1 - search_keys);
379 *matching_key = (k - 1 - search_keys);
419 v = _vec_resize (v, dl, (l + dl) * elt_bytes,
sizeof (h[0]),
421 clib_memset (v + l * elt_bytes, ~0, dl * elt_bytes);
463 _qhash_set_multiple (
void *v,
466 uword n_search_keys,
u32 * result_indices)
469 uword *k, *hash_keys;
470 uword n_left, n_elts, bucket_mask;
473 if (
vec_len (v) < n_search_keys)
474 v = _qhash_resize (v, n_search_keys, elt_bytes);
489 n_left = n_search_keys;
494 u32 a0, b0, c0, bi0, match0, valid0, free0;
495 u32 a1, b1, c1, bi1, match1, valid1, free1;
525 bi0 = c0 & bucket_mask;
526 bi1 = c1 & bucket_mask;
528 h0 = hash_keys + bi0;
529 h1 = hash_keys + bi1;
541 valid1 = valid1 | (bi0 == bi1 ? free0 : 0);
544 n_elts += (match0 == 0) + (match1 == 0);
546 match0 = match0 ? match0 : free0;
547 match1 = match1 ? match1 : free1;
560 r[0] = h0 - hash_keys;
561 r[1] = h1 - hash_keys;
576 r[0] = h0 - hash_keys;
587 r[1] = h1 - hash_keys;
595 u32 a0, b0, c0, bi0, match0, valid0, free0;
612 bi0 = c0 & bucket_mask;
614 h0 = hash_keys + bi0;
623 n_elts += (match0 == 0);
625 match0 = match0 ? match0 : free0;
635 r[0] = h0 - hash_keys;
658 uword i, j = 0, k, l, t = ~0;
677 j = qhash_hash_mix (h, p->key) / QHASH_KEYS_PER_BUCKET;
697 clib_memswap (v + t * elt_bytes, v + l * elt_bytes, elt_bytes);
707 _qhash_unset_multiple (
void *v,
710 uword n_search_keys,
u32 * result_indices)
713 uword *k, *hash_keys;
714 uword n_left, n_elts, bucket_mask;
720 for (i = 0; i < n_search_keys; i++)
721 result_indices[i] = ~0;
729 n_left = n_search_keys;
734 u32 a0, b0, c0, bi0, match0, valid0;
735 u32 a1, b1, c1, bi1, match1, valid1;
765 bi0 = c0 & bucket_mask;
766 bi1 = c1 & bucket_mask;
768 h0 = hash_keys + bi0;
769 h1 = hash_keys + bi1;
778 n_elts -= (match0 != 0) + (match1 != 0);
787 valid1 = bi0 == bi1 ? valid0 : valid1;
798 r[0] =
unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0, &n_elts);
806 n_elts -= (match1 != 0);
809 r[1] =
unset_slow_path (v, elt_bytes, k1, bi1, valid1, match1, &n_elts);
815 u32 a0, b0, c0, bi0, match0, valid0;
832 bi0 = c0 & bucket_mask;
834 h0 = hash_keys + bi0;
839 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)
#define hash_unset(h, key)
static void qhash_min_log2_init()
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
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)
sll srl srl sll sra u16x4 i
#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