97 int n_keys_left, b_mask, a_shift;
102 b_mask = (1 << pm->
b_bits) - 1;
108 while (n_keys_left >= 2)
115 x0 += (
u32) k[0].key;
116 x1 += (
u32) k[1].key;
121 k[0].
b = z0 & b_mask;
122 k[1].
b = z1 & b_mask;
123 k[0].
a = z0 >> a_shift;
124 k[1].
a = z1 >> a_shift;
132 if (n_keys_left >= 1)
141 k[0].
b = z0 & b_mask;
142 k[0].
a = z0 >> a_shift;
154 int n_keys_left, b_mask, a_shift;
159 b_mask = (1 << pm->
b_bits) - 1;
165 while (n_keys_left >= 2)
172 x0 += (
u64) k[0].key;
173 x1 += (
u64) k[1].key;
178 k[0].
b = z0 & b_mask;
179 k[1].
b = z1 & b_mask;
180 k[0].
a = z0 >> a_shift;
181 k[1].
a = z1 >> a_shift;
189 if (n_keys_left >= 1)
198 k[0].
b = z0 & b_mask;
199 k[0].
a = z0 >> a_shift;
211 int n_keys_left, b_mask, a_shift;
216 b_mask = (1 << pm->
b_bits) - 1;
222 while (n_keys_left >= 2)
242 k[0].
b = z0 & b_mask;
243 k[1].
b = z1 & b_mask;
244 k[0].
a = z0 >> a_shift;
245 k[1].
a = z1 >> a_shift;
253 if (n_keys_left >= 1)
267 k[0].
b = z0 & b_mask;
268 k[0].
a = z0 >> a_shift;
280 int n_keys_left, b_mask, a_shift;
285 b_mask = (1 << pm->
b_bits) - 1;
291 while (n_keys_left >= 2)
311 k[0].
b = z0 & b_mask;
312 k[1].
b = z1 & b_mask;
313 k[0].
a = z0 >> a_shift;
314 k[1].
a = z1 >> a_shift;
322 if (n_keys_left >= 1)
336 k[0].
b = z0 & b_mask;
337 k[0].
a = z0 >> a_shift;
383 tb = pm->
tabb + k->
b;
385 for (i = 0; i <
vec_len (ki); i++)
387 l = pm->
keys + ki[
i];
403 return no_collisions;
413 u32 ki,
i, hash, child, parent;
420 for (child = tail - 1; child; child = parent)
422 q_child = &pm->
tabq[child];
424 q_parent = &pm->
tabq[parent];
439 if (ki == pm->
tabh[hash])
459 else if (pm->
tabh[hash] != ~0)
514 for (q = 0; q < tail; q++)
522 for (v = 0; v < v_limit; v++)
528 ki = tb_parent->
keys[
i];
529 k_parent = pm->
keys + ki;
539 k_child = pm->
keys + ki;
540 tb_hit = pm->
tabb + k_child->
b;
545 if (tb_child == tb_hit)
552 if (tb_hit->
water_b == high_water)
561 tb_child->
water_b = high_water;
562 pm->
tabq[tail].
b_q = tb_child ? tb_child - pm->
tabb : ~0;
572 if (
apply (pm, tail, 0))
594 tb1 = sort_tabb + b1[0];
595 tb2 = sort_tabb + b2[0];
614 sort_tabb = pm->
tabb;
667 u32 s_bits, s_max, a_max, b_max, n_keys;
668 int is_minimal, is_fast_mode;
669 const u32 b_max_use_scramble_threshold = 4096;
716 else if (s_max / 4 < b_max_use_scramble_threshold)
718 if (n_keys <= s_max * 0.52)
719 a_max = b_max = s_max / 8;
721 a_max = b_max = s_max / 4;
725 a_max = ((n_keys <= s_max * (5.0 / 8.0)) ? s_max / 8 :
727 s_max * (3.0 / 4.0)) ? s_max / 4 : s_max / 2);
733 a_max = b_max = s_max / 2;
737 b_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 4 : s_max / 2;
742 a_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 8 : s_max / 2;
743 b_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 4 : s_max / 2;
748 a_max = b_max = s_max / 2;
755 if (is_fast_mode && n_keys > s_max * 0.8)
761 if (s_max / 4 <= (1 << 14))
762 b_max = ((n_keys <= s_max * 0.56) ? s_max / 32 :
763 (n_keys <= s_max * 0.74) ? s_max / 16 : s_max / 8);
765 b_max = ((n_keys <= s_max * 0.6) ? s_max / 16 :
766 (n_keys <= s_max * 0.8) ? s_max / 8 : s_max / 4);
768 if (is_fast_mode && b_max < s_max / 8)
777 ASSERT (s_max == (1 << s_bits));
783 if (b_max >= b_max_use_scramble_threshold)
793 int mask = (1 << nbits) - 1;
794 int const2 = 1 + nbits / 2;
795 int const3 = 1 + nbits / 3;
796 int const4 = 1 + nbits / 4;
797 int const5 = 1 + nbits / 5;
798 for (i = 0; i < 20; i++)
800 x = (x + (x << const2)) & mask;
801 x = (x ^ (x >> const3));
802 x = (x + (x << const4)) & mask;
803 x = (x ^ (x >> const5));
825 u32 max_a_bits, n_tries_this_a_b, want_minimal;
836 max_a_bits = pm->
s_bits - want_minimal;
851 n_tries_this_a_b = 0;
874 if (n_tries_this_a_b < 2048)
878 if (pm->
a_bits < max_a_bits)
984 uword *unique_bitmap = 0;
1003 unique_bitmap = clib_bitmap_ori (unique_bitmap, h);
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
static void init_keys_indirect_u32(phash_main_t *pm)
clib_error_t * phash_validate(phash_main_t *pm)
sll srl srl sll sra u16x4 i
#define clib_error(format, args...)
#define PHASH_FLAG_FAST_MODE
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
static void phash_main_free_working_memory(phash_main_t *pm)
static void guess_initial_parameters(phash_main_t *pm)
static u64 random_u64(u64 *seed)
64-bit random number generator Again, constants courtesy of Donald Knuth.
#define vec_bytes(v)
Number of data bytes in vector.
static int phash_tabb_compare(void *a1, void *a2)
static uword min_log2(uword x)
static void init_keys_direct_u32(phash_main_t *pm)
#define PHASH_FLAG_MINIMAL
clib_error_t * phash_find_perfect_hash(phash_main_t *pm)
#define clib_error_return(e, args...)
static int augment(phash_main_t *pm, u32 b_root, u32 high_water)
#define vec_resize(V, N)
Resize a vector (no header, unspecified alignment) Add N elements to end of given vector V...
static u32 scramble_permute(u32 x, u32 nbits)
static int init_tabb(phash_main_t *pm)
void(* key_seed2)(void *private, uword key1, uword key2, void *seed)
static int perfect(phash_main_t *pm)
#define hash_mix64(a0, b0, c0)
#define vec_free(V)
Free vector's memory (no header).
#define hash_mix32(a0, b0, c0)
void(* key_seed1)(void *private, uword key, void *seed)
static uword clib_bitmap_get(uword *ai, uword i)
Gets the ith bit value from a bitmap.
static int apply(phash_main_t *pm, u32 tail, u32 rollback)
Bitmaps built as vectors of machine words.
#define clib_bitmap_free(v)
Free a bitmap.
static uword is_pow2(uword x)
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static uword max_log2(uword x)
#define vec_sort_with_function(vec, f)
Sort a vector using the supplied element comparison function.
static phash_tabb_t * sort_tabb
uword phash_hash_slow(phash_main_t *pm, uword key)
Linear Congruential Random Number Generator.
int(* key_is_equal)(void *private, uword key1, uword key2)
#define vec_foreach(var, vec)
Vector iterator.
static void init_keys_indirect_u64(phash_main_t *pm)
static void init_keys_direct_u64(phash_main_t *pm)
#define vec_validate_init_empty(V, I, INIT)
Make sure vector is long enough for given index and initialize empty space (no header, unspecified alignment)
static void scramble_init(phash_main_t *pm)
#define PHASH_FLAG_USE_SCRAMBLE
static void phash_tabb_free(phash_tabb_t *b)