diff options
Diffstat (limited to 'vppinfra/vppinfra/qhash.c')
| -rw-r--r-- | vppinfra/vppinfra/qhash.c | 858 |
1 files changed, 0 insertions, 858 deletions
diff --git a/vppinfra/vppinfra/qhash.c b/vppinfra/vppinfra/qhash.c deleted file mode 100644 index f4e38c4a1d7..00000000000 --- a/vppinfra/vppinfra/qhash.c +++ /dev/null @@ -1,858 +0,0 @@ -/* - * Copyright (c) 2015 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -/* - Copyright (c) 2006 Eliot Dresselhaus - - Permission is hereby granted, free of charge, to any person obtaining - a copy of this software and associated documentation files (the - "Software"), to deal in the Software without restriction, including - without limitation the rights to use, copy, modify, merge, publish, - distribute, sublicense, and/or sell copies of the Software, and to - permit persons to whom the Software is furnished to do so, subject to - the following conditions: - - The above copyright notice and this permission notice shall be - included in all copies or substantial portions of the Software. - - THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND - NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE - LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION - OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION - WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -*/ - -#include <vppinfra/qhash.h> - -#define QHASH_ALL_VALID ((1 << QHASH_KEYS_PER_BUCKET) - 1) - -void * -_qhash_resize (void *v, uword length, uword elt_bytes) -{ - qhash_t *h; - uword l; - - l = clib_max (max_log2 (length), 2 + QHASH_LOG2_KEYS_PER_BUCKET); - - /* Round up if less than 1/2 full. */ - l += ((f64) length / (f64) (1 << l)) < .5; - - v = _vec_resize (0, 1 << l, elt_bytes << l, sizeof (h[0]), - /* align */ sizeof (uword)); - - h = qhash_header (v); - h->n_elts = 0; - h->log2_hash_size = l; - h->hash_keys = - clib_mem_alloc_aligned_no_fail (sizeof (h->hash_keys[0]) << l, - CLIB_CACHE_LINE_BYTES); - vec_resize (h->hash_key_valid_bitmap, - 1 << (l - QHASH_LOG2_KEYS_PER_BUCKET)); - memset (v, ~0, elt_bytes << l); - - return v; -} - -static u8 min_log2_table[256]; - -static inline uword -qhash_min_log2 (uword x) -{ - ASSERT (is_pow2 (x)); - ASSERT (x < 256); - return min_log2_table[x]; -} - -static void -qhash_min_log2_init () -{ - int i; - for (i = 0; i < 256; i++) - min_log2_table[i] = min_log2 (i); -} - -always_inline uword -qhash_get_valid_elt_mask (qhash_t * h, uword i) -{ - return h->hash_key_valid_bitmap[i / QHASH_KEYS_PER_BUCKET]; -} - -always_inline void -qhash_set_valid_elt_mask (qhash_t * h, uword i, uword mask) -{ - h->hash_key_valid_bitmap[i / QHASH_KEYS_PER_BUCKET] = mask; -} - -always_inline uword -qhash_search_bucket (uword * hash_keys, uword search_key, uword m) -{ - uword t; -#define _(i) ((hash_keys[i] == search_key) << i) - t = (_(0) | _(1) | _(2) | _(3)); - if (QHASH_KEYS_PER_BUCKET > 4) - t |= (_(4) | _(5) | _(6) | _(7)); - if (QHASH_KEYS_PER_BUCKET > 8) - t |= (_(8) | _(9) | _(10) | _(11) | _(12) | _(13) | _(14) | _(15)); -#undef _ - return m & t; -} - -/* Lookup multiple keys in the same hash table. */ -void -qhash_get_multiple (void *v, - uword * search_keys, - uword n_search_keys, u32 * result_indices) -{ - qhash_t *h = qhash_header (v); - uword *k, *hash_keys; - uword n_left, bucket_mask; - u32 *r; - - if (!v) - { - memset (result_indices, ~0, sizeof (result_indices[0]) * n_search_keys); - return; - } - - bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1); - - k = search_keys; - n_left = n_search_keys; - hash_keys = h->hash_keys; - r = result_indices; - - while (n_left >= 2) - { - u32 a0, b0, c0, bi0, valid0, match0; - u32 a1, b1, c1, bi1, valid1, match1; - uword k0, k1, *h0, *h1; - - k0 = k[0]; - k1 = k[1]; - n_left -= 2; - k += 2; - - a0 = a1 = h->hash_seeds[0]; - b0 = b1 = h->hash_seeds[1]; - c0 = c1 = h->hash_seeds[2]; - a0 ^= k0; - a1 ^= k1; -#if uword_bits == 64 - b0 ^= k0 >> 32; - b1 ^= k1 >> 32; -#endif - - hash_mix32_step_1 (a0, b0, c0); - hash_mix32_step_1 (a1, b1, c1); - hash_mix32_step_2 (a0, b0, c0); - hash_mix32_step_2 (a1, b1, c1); - hash_mix32_step_3 (a0, b0, c0); - hash_mix32_step_3 (a1, b1, c1); - - bi0 = c0 & bucket_mask; - bi1 = c1 & bucket_mask; - - h0 = hash_keys + bi0; - h1 = hash_keys + bi1; - - /* Search two buckets. */ - valid0 = qhash_get_valid_elt_mask (h, bi0); - valid1 = qhash_get_valid_elt_mask (h, bi1); - - match0 = qhash_search_bucket (h0, k0, valid0); - match1 = qhash_search_bucket (h1, k1, valid1); - - bi0 += qhash_min_log2 (match0); - bi1 += qhash_min_log2 (match1); - - r[0] = match0 ? bi0 : ~0; - r[1] = match1 ? bi1 : ~0; - r += 2; - - /* Full buckets trigger search of overflow hash. */ - if (PREDICT_FALSE (!match0 && valid0 == QHASH_ALL_VALID)) - { - uword *p = hash_get (h->overflow_hash, k0); - r[-2] = p ? p[0] : ~0; - } - - /* Full buckets trigger search of overflow hash. */ - if (PREDICT_FALSE (!match1 && valid1 == QHASH_ALL_VALID)) - { - uword *p = hash_get (h->overflow_hash, k1); - r[-1] = p ? p[0] : ~0; - } - } - - while (n_left >= 1) - { - u32 a0, b0, c0, bi0, valid0, match0; - uword k0, *h0; - - k0 = k[0]; - n_left -= 1; - k += 1; - - a0 = h->hash_seeds[0]; - b0 = h->hash_seeds[1]; - c0 = h->hash_seeds[2]; - a0 ^= k0; -#if uword_bits == 64 - b0 ^= k0 >> 32; -#endif - - hash_mix32 (a0, b0, c0); - - bi0 = c0 & bucket_mask; - - h0 = hash_keys + bi0; - - /* Search one bucket. */ - valid0 = qhash_get_valid_elt_mask (h, bi0); - match0 = qhash_search_bucket (h0, k0, valid0); - - bi0 += qhash_min_log2 (match0); - - r[0] = match0 ? bi0 : ~0; - r += 1; - - /* Full buckets trigger search of overflow hash. */ - if (PREDICT_FALSE (!match0 && valid0 == QHASH_ALL_VALID)) - { - uword *p = hash_get (h->overflow_hash, k0); - r[-1] = p ? p[0] : ~0; - } - } -} - -/* Lookup multiple keys in the same hash table. - Returns index of first matching key. */ -u32 -qhash_get_first_match (void *v, - uword * search_keys, - uword n_search_keys, uword * matching_key) -{ - qhash_t *h = qhash_header (v); - uword *k, *hash_keys; - uword n_left, match_mask, bucket_mask; - - if (!v) - return ~0; - - match_mask = 0; - bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1); - - k = search_keys; - n_left = n_search_keys; - hash_keys = h->hash_keys; - while (n_left >= 2) - { - u32 a0, b0, c0, bi0, valid0; - u32 a1, b1, c1, bi1, valid1; - uword k0, k1, *h0, *h1; - - k0 = k[0]; - k1 = k[1]; - n_left -= 2; - k += 2; - - a0 = a1 = h->hash_seeds[0]; - b0 = b1 = h->hash_seeds[1]; - c0 = c1 = h->hash_seeds[2]; - a0 ^= k0; - a1 ^= k1; -#if uword_bits == 64 - b0 ^= k0 >> 32; - b1 ^= k1 >> 32; -#endif - - hash_mix32_step_1 (a0, b0, c0); - hash_mix32_step_1 (a1, b1, c1); - hash_mix32_step_2 (a0, b0, c0); - hash_mix32_step_2 (a1, b1, c1); - hash_mix32_step_3 (a0, b0, c0); - hash_mix32_step_3 (a1, b1, c1); - - bi0 = c0 & bucket_mask; - bi1 = c1 & bucket_mask; - - h0 = hash_keys + bi0; - h1 = hash_keys + bi1; - - /* Search two buckets. */ - valid0 = qhash_get_valid_elt_mask (h, bi0); - valid1 = qhash_get_valid_elt_mask (h, bi1); - match_mask = qhash_search_bucket (h0, k0, valid0); - match_mask |= (qhash_search_bucket (h1, k1, valid1) - << QHASH_KEYS_PER_BUCKET); - if (match_mask) - { - uword bi, is_match1; - - bi = qhash_min_log2 (match_mask); - is_match1 = bi >= QHASH_KEYS_PER_BUCKET; - - bi += ((is_match1 ? bi1 : bi0) - - (is_match1 << QHASH_LOG2_KEYS_PER_BUCKET)); - *matching_key = (k - 2 - search_keys) + is_match1; - return bi; - } - - /* Full buckets trigger search of overflow hash. */ - if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID - || valid1 == QHASH_ALL_VALID)) - { - uword *p = 0; - uword ki = k - 2 - search_keys; - - if (valid0 == QHASH_ALL_VALID) - p = hash_get (h->overflow_hash, k0); - - if (!p && valid1 == QHASH_ALL_VALID) - { - p = hash_get (h->overflow_hash, k1); - ki++; - } - - if (p) - { - *matching_key = ki; - return p[0]; - } - } - } - - while (n_left >= 1) - { - u32 a0, b0, c0, bi0, valid0; - uword k0, *h0; - - k0 = k[0]; - n_left -= 1; - k += 1; - - a0 = h->hash_seeds[0]; - b0 = h->hash_seeds[1]; - c0 = h->hash_seeds[2]; - a0 ^= k0; -#if uword_bits == 64 - b0 ^= k0 >> 32; -#endif - - hash_mix32 (a0, b0, c0); - - bi0 = c0 & bucket_mask; - - h0 = hash_keys + bi0; - - /* Search one bucket. */ - valid0 = qhash_get_valid_elt_mask (h, bi0); - match_mask = qhash_search_bucket (h0, k0, valid0); - if (match_mask) - { - uword bi; - bi = bi0 + qhash_min_log2 (match_mask); - *matching_key = (k - 1 - search_keys); - return bi; - } - - /* Full buckets trigger search of overflow hash. */ - if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID)) - { - uword *p = hash_get (h->overflow_hash, k0); - if (p) - { - *matching_key = (k - 1 - search_keys); - return p[0]; - } - } - } - - return ~0; -} - -static void * -qhash_set_overflow (void *v, uword elt_bytes, - uword key, uword bi, uword * n_elts, u32 * result) -{ - qhash_t *h = qhash_header (v); - uword *p = hash_get (h->overflow_hash, key); - uword i; - - bi /= QHASH_KEYS_PER_BUCKET; - - if (p) - i = p[0]; - else - { - uword l = vec_len (h->overflow_free_indices); - if (l > 0) - { - i = h->overflow_free_indices[l - 1]; - _vec_len (h->overflow_free_indices) = l - 1; - } - else - i = (1 << h->log2_hash_size) + hash_elts (h->overflow_hash); - hash_set (h->overflow_hash, key, i); - vec_validate (h->overflow_counts, bi); - h->overflow_counts[bi] += 1; - *n_elts += 1; - - l = vec_len (v); - if (i >= l) - { - uword dl = round_pow2 (1 + i - l, 8); - v = _vec_resize (v, dl, (l + dl) * elt_bytes, sizeof (h[0]), - /* align */ sizeof (uword)); - memset (v + l * elt_bytes, ~0, dl * elt_bytes); - } - } - - *result = i; - - return v; -} - -static uword -qhash_unset_overflow (void *v, uword key, uword bi, uword * n_elts) -{ - qhash_t *h = qhash_header (v); - uword *p = hash_get (h->overflow_hash, key); - uword result; - - bi /= QHASH_KEYS_PER_BUCKET; - - if (p) - { - result = p[0]; - hash_unset (h->overflow_hash, key); - ASSERT (bi < vec_len (h->overflow_counts)); - ASSERT (h->overflow_counts[bi] > 0); - ASSERT (*n_elts > 0); - vec_add1 (h->overflow_free_indices, result); - h->overflow_counts[bi] -= 1; - *n_elts -= 1; - } - else - result = ~0; - - return result; -} - -always_inline uword -qhash_find_free (uword i, uword valid_mask) -{ - return first_set (~valid_mask & pow2_mask (QHASH_KEYS_PER_BUCKET)); -} - -void * -_qhash_set_multiple (void *v, - uword elt_bytes, - uword * search_keys, - uword n_search_keys, u32 * result_indices) -{ - qhash_t *h = qhash_header (v); - uword *k, *hash_keys; - uword n_left, n_elts, bucket_mask; - u32 *r; - - if (vec_len (v) < n_search_keys) - v = _qhash_resize (v, n_search_keys, elt_bytes); - - if (qhash_min_log2 (2) != 1) - { - qhash_min_log2_init (); - ASSERT (qhash_min_log2 (2) == 1); - } - - ASSERT (v != 0); - - bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1); - - hash_keys = h->hash_keys; - k = search_keys; - r = result_indices; - n_left = n_search_keys; - n_elts = h->n_elts; - - while (n_left >= 2) - { - u32 a0, b0, c0, bi0, match0, valid0, free0; - u32 a1, b1, c1, bi1, match1, valid1, free1; - uword k0, *h0; - uword k1, *h1; - - k0 = k[0]; - k1 = k[1]; - - /* Keys must be unique. */ - ASSERT (k0 != k1); - - n_left -= 2; - k += 2; - - a0 = a1 = h->hash_seeds[0]; - b0 = b1 = h->hash_seeds[1]; - c0 = c1 = h->hash_seeds[2]; - a0 ^= k0; - a1 ^= k1; -#if uword_bits == 64 - b0 ^= k0 >> 32; - b1 ^= k1 >> 32; -#endif - - hash_mix32_step_1 (a0, b0, c0); - hash_mix32_step_1 (a1, b1, c1); - hash_mix32_step_2 (a0, b0, c0); - hash_mix32_step_2 (a1, b1, c1); - hash_mix32_step_3 (a0, b0, c0); - hash_mix32_step_3 (a1, b1, c1); - - bi0 = c0 & bucket_mask; - bi1 = c1 & bucket_mask; - - h0 = hash_keys + bi0; - h1 = hash_keys + bi1; - - /* Search two buckets. */ - valid0 = qhash_get_valid_elt_mask (h, bi0); - valid1 = qhash_get_valid_elt_mask (h, bi1); - - match0 = qhash_search_bucket (h0, k0, valid0); - match1 = qhash_search_bucket (h1, k1, valid1); - - /* Find first free element starting at hash offset into bucket. */ - free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0); - - valid1 = valid1 | (bi0 == bi1 ? free0 : 0); - free1 = qhash_find_free (c1 & (QHASH_KEYS_PER_BUCKET - 1), valid1); - - n_elts += (match0 == 0) + (match1 == 0); - - match0 = match0 ? match0 : free0; - match1 = match1 ? match1 : free1; - - valid0 |= match0; - valid1 |= match1; - - h0 += qhash_min_log2 (match0); - h1 += qhash_min_log2 (match1); - - if (PREDICT_FALSE (!match0 || !match1)) - goto slow_path2; - - h0[0] = k0; - h1[0] = k1; - r[0] = h0 - hash_keys; - r[1] = h1 - hash_keys; - r += 2; - qhash_set_valid_elt_mask (h, bi0, valid0); - qhash_set_valid_elt_mask (h, bi1, valid1); - continue; - - slow_path2: - if (!match0) - { - n_elts -= 1; - v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]); - } - else - { - h0[0] = k0; - r[0] = h0 - hash_keys; - qhash_set_valid_elt_mask (h, bi0, valid0); - } - if (!match1) - { - n_elts -= 1; - v = qhash_set_overflow (v, elt_bytes, k1, bi1, &n_elts, &r[1]); - } - else - { - h1[0] = k1; - r[1] = h1 - hash_keys; - qhash_set_valid_elt_mask (h, bi1, valid1); - } - r += 2; - } - - while (n_left >= 1) - { - u32 a0, b0, c0, bi0, match0, valid0, free0; - uword k0, *h0; - - k0 = k[0]; - n_left -= 1; - k += 1; - - a0 = h->hash_seeds[0]; - b0 = h->hash_seeds[1]; - c0 = h->hash_seeds[2]; - a0 ^= k0; -#if uword_bits == 64 - b0 ^= k0 >> 32; -#endif - - hash_mix32 (a0, b0, c0); - - bi0 = c0 & bucket_mask; - - h0 = hash_keys + bi0; - - valid0 = qhash_get_valid_elt_mask (h, bi0); - - /* Find first free element starting at hash offset into bucket. */ - free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0); - - match0 = qhash_search_bucket (h0, k0, valid0); - - n_elts += (match0 == 0); - - match0 = match0 ? match0 : free0; - - valid0 |= match0; - - h0 += qhash_min_log2 (match0); - - if (PREDICT_FALSE (!match0)) - goto slow_path1; - - h0[0] = k0; - r[0] = h0 - hash_keys; - r += 1; - qhash_set_valid_elt_mask (h, bi0, valid0); - continue; - - slow_path1: - n_elts -= 1; - v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]); - r += 1; - } - - h = qhash_header (v); - h->n_elts = n_elts; - - return v; -} - -static uword -unset_slow_path (void *v, uword elt_bytes, - uword k0, uword bi0, uword valid0, uword match0, - uword * n_elts) -{ - qhash_t *h = qhash_header (v); - uword i, j = 0, k, l, t = ~0; - hash_pair_t *p, *found; - - if (!match0) - { - if (valid0 == QHASH_ALL_VALID) - t = qhash_unset_overflow (v, k0, bi0, n_elts); - return t; - } - - i = bi0 / QHASH_KEYS_PER_BUCKET; - t = bi0 + qhash_min_log2 (match0); - - if (valid0 == QHASH_ALL_VALID - && i < vec_len (h->overflow_counts) && h->overflow_counts[i] > 0) - { - found = 0; - /* *INDENT-OFF* */ - hash_foreach_pair (p, h->overflow_hash, ({ - j = qhash_hash_mix (h, p->key) / QHASH_KEYS_PER_BUCKET; - if (j == i) - { - found = p; - break; - } - })); - /* *INDENT-ON* */ - ASSERT (found != 0); - ASSERT (j == i); - - l = found->value[0]; - k = found->key; - hash_unset3 (h->overflow_hash, k, &j); - vec_add1 (h->overflow_free_indices, j); - h->overflow_counts[i] -= 1; - - qhash_set_valid_elt_mask (h, bi0, valid0); - - h->hash_keys[t] = k; - clib_memswap (v + t * elt_bytes, v + l * elt_bytes, elt_bytes); - t = l; - } - else - qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0); - - return t; -} - -void -_qhash_unset_multiple (void *v, - uword elt_bytes, - uword * search_keys, - uword n_search_keys, u32 * result_indices) -{ - qhash_t *h = qhash_header (v); - uword *k, *hash_keys; - uword n_left, n_elts, bucket_mask; - u32 *r; - - if (!v) - { - uword i; - for (i = 0; i < n_search_keys; i++) - result_indices[i] = ~0; - } - - bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1); - - hash_keys = h->hash_keys; - k = search_keys; - r = result_indices; - n_left = n_search_keys; - n_elts = h->n_elts; - - while (n_left >= 2) - { - u32 a0, b0, c0, bi0, match0, valid0; - u32 a1, b1, c1, bi1, match1, valid1; - uword k0, *h0; - uword k1, *h1; - - k0 = k[0]; - k1 = k[1]; - - /* Keys must be unique. */ - ASSERT (k0 != k1); - - n_left -= 2; - k += 2; - - a0 = a1 = h->hash_seeds[0]; - b0 = b1 = h->hash_seeds[1]; - c0 = c1 = h->hash_seeds[2]; - a0 ^= k0; - a1 ^= k1; -#if uword_bits == 64 - b0 ^= k0 >> 32; - b1 ^= k1 >> 32; -#endif - - hash_mix32_step_1 (a0, b0, c0); - hash_mix32_step_1 (a1, b1, c1); - hash_mix32_step_2 (a0, b0, c0); - hash_mix32_step_2 (a1, b1, c1); - hash_mix32_step_3 (a0, b0, c0); - hash_mix32_step_3 (a1, b1, c1); - - bi0 = c0 & bucket_mask; - bi1 = c1 & bucket_mask; - - h0 = hash_keys + bi0; - h1 = hash_keys + bi1; - - /* Search two buckets. */ - valid0 = qhash_get_valid_elt_mask (h, bi0); - valid1 = qhash_get_valid_elt_mask (h, bi1); - - match0 = qhash_search_bucket (h0, k0, valid0); - match1 = qhash_search_bucket (h1, k1, valid1); - - n_elts -= (match0 != 0) + (match1 != 0); - - if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID - || valid1 == QHASH_ALL_VALID)) - goto slow_path2; - - valid0 ^= match0; - qhash_set_valid_elt_mask (h, bi0, valid0); - - valid1 = bi0 == bi1 ? valid0 : valid1; - valid1 ^= match1; - - qhash_set_valid_elt_mask (h, bi1, valid1); - - r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0; - r[1] = match1 ? bi1 + qhash_min_log2 (match1) : ~0; - r += 2; - continue; - - slow_path2: - r[0] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0, &n_elts); - if (bi0 == bi1) - { - /* Search again in same bucket to test new overflow element. */ - valid1 = qhash_get_valid_elt_mask (h, bi0); - if (!match1) - { - match1 = qhash_search_bucket (h1, k1, valid1); - n_elts -= (match1 != 0); - } - } - r[1] = unset_slow_path (v, elt_bytes, k1, bi1, valid1, match1, &n_elts); - r += 2; - } - - while (n_left >= 1) - { - u32 a0, b0, c0, bi0, match0, valid0; - uword k0, *h0; - - k0 = k[0]; - n_left -= 1; - k += 1; - - a0 = h->hash_seeds[0]; - b0 = h->hash_seeds[1]; - c0 = h->hash_seeds[2]; - a0 ^= k0; -#if uword_bits == 64 - b0 ^= k0 >> 32; -#endif - - hash_mix32 (a0, b0, c0); - - bi0 = c0 & bucket_mask; - - h0 = hash_keys + bi0; - - valid0 = qhash_get_valid_elt_mask (h, bi0); - - match0 = qhash_search_bucket (h0, k0, valid0); - n_elts -= (match0 != 0); - qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0); - - r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0; - r += 1; - - if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID)) - r[-1] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0, - &n_elts); - } - - h->n_elts = n_elts; -} - -/* - * fd.io coding-style-patch-verification: ON - * - * Local Variables: - * eval: (c-set-style "gnu") - * End: - */ |