aboutsummaryrefslogtreecommitdiffstats
path: root/vppinfra/vppinfra/vhash.h
diff options
context:
space:
mode:
Diffstat (limited to 'vppinfra/vppinfra/vhash.h')
-rw-r--r--vppinfra/vppinfra/vhash.h850
1 files changed, 0 insertions, 850 deletions
diff --git a/vppinfra/vppinfra/vhash.h b/vppinfra/vppinfra/vhash.h
deleted file mode 100644
index 5ab42292001..00000000000
--- a/vppinfra/vppinfra/vhash.h
+++ /dev/null
@@ -1,850 +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) 2010 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.
-*/
-
-#ifndef included_clib_vhash_h
-#define included_clib_vhash_h
-
-#include <vppinfra/vector.h>
-
-#ifdef CLIB_HAVE_VEC128
-
-#include <vppinfra/cache.h>
-#include <vppinfra/hash.h>
-#include <vppinfra/pipeline.h>
-
-/* Gathers 32 bits worth of key with given index. */
-typedef u32 (vhash_key_function_t) (void *state, u32 vector_index,
- u32 key_word_index);
-typedef u32x4 (vhash_4key_function_t) (void *state, u32 vector_index,
- u32 key_word_index);
-/* Sets/gets result of hash lookup. */
-typedef u32 (vhash_result_function_t) (void *state, u32 vector_index,
- u32 result, u32 n_key_u32);
-typedef u32x4 (vhash_4result_function_t) (void *state, u32 vector_index,
- u32x4 results, u32 n_key_u32);
-
-typedef struct
-{
- u32x4_union_t hashed_key[3];
-} vhash_hashed_key_t;
-
-/* Search buckets are really this structure. */
-typedef struct
-{
- /* 4 results for this bucket.
- Zero is used to mark empty results. This means user can't use the result ~0
- since user results differ from internal results stored in buckets by 1.
- e.g. internal result = user result + 1. */
- u32x4_union_t result;
-
- /* n_key_u32s u32x4s of key data follow. */
- u32x4_union_t key[0];
-} vhash_search_bucket_t;
-
-typedef struct
-{
- u32x4_union_t *search_buckets;
-
- /* Vector of bucket free indices. */
- u32 *free_indices;
-
- /* Number of entries in this overflow bucket. */
- u32 n_overflow;
-} vhash_overflow_buckets_t;
-
-typedef struct
-{
- /* 2^log2_n_keys keys grouped in groups of 4.
- Each bucket contains 4 results plus 4 keys for a
- total of (1 + n_key_u32) u32x4s. */
- u32x4_union_t *search_buckets;
-
- /* When a bucket of 4 results/keys are full we search
- the overflow. hash_key is used to select which overflow
- bucket. */
- vhash_overflow_buckets_t overflow_buckets[16];
-
- /* Total count of occupied elements in hash table. */
- u32 n_elts;
-
- u32 log2_n_keys;
-
- /* Number of 32 bit words in a hash key. */
- u32 n_key_u32;
-
- u32x4_union_t bucket_mask;
-
- /* table[i] = min_log2 (first_set (~i)). */
- u8 find_first_zero_table[16];
-
- /* Hash seeds for Jenkins hash. */
- u32x4_union_t hash_seeds[3];
-
- /* Key work space is a vector of length
- n_key_u32s << log2_n_key_word_len_u32x. */
- u32 log2_n_key_word_len_u32x;
-
- /* Work space to store keys between pipeline stages. */
- u32x4_union_t *key_work_space;
-
- /* Hash work space to store Jenkins hash values between
- pipeline stages. */
- vhash_hashed_key_t *hash_work_space;
-} vhash_t;
-
-always_inline vhash_overflow_buckets_t *
-vhash_get_overflow_buckets (vhash_t * h, u32 key)
-{
- u32 i = (((key & h->bucket_mask.as_u32[0]) >> 2) & 0xf);
- ASSERT (i < ARRAY_LEN (h->overflow_buckets));
- return h->overflow_buckets + i;
-}
-
-always_inline uword
-vhash_is_non_empty_overflow_bucket (vhash_t * h, u32 key)
-{
- u32 i = (((key & h->bucket_mask.as_u32[0]) >> 2) & 0xf);
- ASSERT (i < ARRAY_LEN (h->overflow_buckets));
- return h->overflow_buckets[i].n_overflow > 0;
-}
-
-always_inline void
-vhash_free_overflow_buckets (vhash_overflow_buckets_t * obs)
-{
- vec_free (obs->search_buckets);
- vec_free (obs->free_indices);
-}
-
-always_inline void
-vhash_free (vhash_t * h)
-{
- uword i;
- for (i = 0; i < ARRAY_LEN (h->overflow_buckets); i++)
- vhash_free_overflow_buckets (&h->overflow_buckets[i]);
- vec_free (h->search_buckets);
- vec_free (h->key_work_space);
- vec_free (h->hash_work_space);
-}
-
-always_inline void
-vhash_set_key_word (vhash_t * h, u32 wi, u32 vi, u32 value)
-{
- u32 i0 = (wi << h->log2_n_key_word_len_u32x) + (vi / 4);
- u32 i1 = vi % 4;
- vec_elt (h->key_work_space, i0).as_u32[i1] = value;
-}
-
-always_inline void
-vhash_set_key_word_u32x (vhash_t * h, u32 wi, u32 vi, u32x value)
-{
- u32 i0 = (wi << h->log2_n_key_word_len_u32x) + (vi / 4);
- vec_elt (h->key_work_space, i0).as_u32x4 = value;
-}
-
-always_inline u32
-vhash_get_key_word (vhash_t * h, u32 wi, u32 vi)
-{
- u32 i0 = (wi << h->log2_n_key_word_len_u32x) + (vi / 4);
- u32 i1 = vi % 4;
- return vec_elt (h->key_work_space, i0).as_u32[i1];
-}
-
-always_inline u32x
-vhash_get_key_word_u32x (vhash_t * h, u32 wi, u32 vi)
-{
- u32 i0 = (wi << h->log2_n_key_word_len_u32x) + vi;
- return vec_elt (h->key_work_space, i0).as_u32x4;
-}
-
-always_inline void
-vhash_validate_sizes (vhash_t * h, u32 n_key_u32, u32 n_vectors)
-{
- u32 n, l;
-
- n = max_pow2 (n_vectors) / 4;
- n = clib_max (n, 8);
-
- h->log2_n_key_word_len_u32x = l = min_log2 (n);
- vec_validate_aligned (h->key_work_space, (n_key_u32 << l) - 1,
- CLIB_CACHE_LINE_BYTES);
- vec_validate_aligned (h->hash_work_space, n - 1, CLIB_CACHE_LINE_BYTES);
-}
-
-always_inline void
-vhash_gather_key_stage (vhash_t * h,
- u32 vector_index,
- u32 n_vectors,
- vhash_key_function_t key_function,
- void *state, u32 n_key_u32s)
-{
- u32 i, j, vi;
-
- /* Gather keys for 4 packets (for 128 bit vector length e.g. u32x4). */
- for (i = 0; i < n_vectors; i++)
- {
- vi = vector_index * 4 + i;
- for (j = 0; j < n_key_u32s; j++)
- vhash_set_key_word (h, j, vi, key_function (state, vi, j));
- }
-}
-
-always_inline void
-vhash_gather_4key_stage (vhash_t * h,
- u32 vector_index,
- vhash_4key_function_t key_function,
- void *state, u32 n_key_u32s)
-{
- u32 j, vi;
- vi = vector_index * 4;
- for (j = 0; j < n_key_u32s; j++)
- vhash_set_key_word_u32x (h, j, vi, key_function (state, vi, j));
-}
-
-always_inline void
-vhash_mix_stage (vhash_t * h, u32 vector_index, u32 n_key_u32s)
-{
- i32 i, n_left;
- u32x a, b, c;
-
- /* Only need to do this for keys longer than 12 bytes. */
- ASSERT (n_key_u32s > 3);
-
- a = h->hash_seeds[0].as_u32x4;
- b = h->hash_seeds[1].as_u32x4;
- c = h->hash_seeds[2].as_u32x4;
- for (i = 0, n_left = n_key_u32s - 3; n_left > 0; n_left -= 3, i += 3)
- {
- a +=
- vhash_get_key_word_u32x (h, n_key_u32s - 1 - (i + 0), vector_index);
- if (n_left > 1)
- b +=
- vhash_get_key_word_u32x (h, n_key_u32s - 1 - (i + 1), vector_index);
- if (n_left > 2)
- c +=
- vhash_get_key_word_u32x (h, n_key_u32s - 1 - (i + 2), vector_index);
-
- hash_v3_mix_u32x (a, b, c);
- }
-
- /* Save away a, b, c for later finalize. */
- {
- vhash_hashed_key_t *hk =
- vec_elt_at_index (h->hash_work_space, vector_index);
- hk->hashed_key[0].as_u32x4 = a;
- hk->hashed_key[1].as_u32x4 = b;
- hk->hashed_key[2].as_u32x4 = c;
- }
-}
-
-always_inline vhash_search_bucket_t *
-vhash_get_search_bucket_with_index (vhash_t * h, u32 i, u32 n_key_u32s)
-{
- return ((vhash_search_bucket_t *)
- vec_elt_at_index (h->search_buckets,
- (i / 4) *
- ((sizeof (vhash_search_bucket_t) /
- sizeof (u32x4)) + n_key_u32s)));
-}
-
-always_inline vhash_search_bucket_t *
-vhash_get_search_bucket (vhash_t * h, u32 key_hash, u32 n_key_u32s)
-{
- u32 i = key_hash & h->bucket_mask.as_u32[0];
- return vhash_get_search_bucket_with_index (h, i, n_key_u32s);
-}
-
-always_inline u32x4
-vhash_get_4_search_bucket_byte_offsets (vhash_t * h, u32x4 key_hash,
- u32 n_key_u32s)
-{
- vhash_search_bucket_t *b;
- u32 n_bytes_per_bucket = sizeof (b[0]) + n_key_u32s * sizeof (b->key[0]);
- u32x4 r = key_hash & h->bucket_mask.as_u32x4;
-
- /* Multiply with shifts and adds to get bucket byte offset. */
-#define _(x) u32x4_ishift_left (r, (x) - 2)
- if (n_bytes_per_bucket == (1 << 5))
- r = _(5);
- else if (n_bytes_per_bucket == ((1 << 5) + (1 << 4)))
- r = _(5) + _(4);
- else if (n_bytes_per_bucket == (1 << 6))
- r = _(6);
- else if (n_bytes_per_bucket == ((1 << 6) + (1 << 4)))
- r = _(6) + _(4);
- else if (n_bytes_per_bucket == ((1 << 6) + (1 << 5)))
- r = _(6) + _(5);
- else if (n_bytes_per_bucket == ((1 << 6) + (1 << 5) + (1 << 4)))
- r = _(6) + _(5) + _(4);
- else
- ASSERT (0);
-#undef _
- return r;
-}
-
-always_inline void
-vhash_finalize_stage (vhash_t * h, u32 vector_index, u32 n_key_u32s)
-{
- i32 n_left;
- u32x a, b, c;
- vhash_hashed_key_t *hk =
- vec_elt_at_index (h->hash_work_space, vector_index);
-
- if (n_key_u32s <= 3)
- {
- a = h->hash_seeds[0].as_u32x4;
- b = h->hash_seeds[1].as_u32x4;
- c = h->hash_seeds[2].as_u32x4;
- n_left = n_key_u32s;
- }
- else
- {
- a = hk->hashed_key[0].as_u32x4;
- b = hk->hashed_key[1].as_u32x4;
- c = hk->hashed_key[2].as_u32x4;
- n_left = 3;
- }
-
- if (n_left > 0)
- a += vhash_get_key_word_u32x (h, 0, vector_index);
- if (n_left > 1)
- b += vhash_get_key_word_u32x (h, 1, vector_index);
- if (n_left > 2)
- c += vhash_get_key_word_u32x (h, 2, vector_index);
-
- hash_v3_finalize_u32x (a, b, c);
-
- /* Only save away last 32 bits of hash code. */
- hk->hashed_key[2].as_u32x4 = c;
-
- /* Prefetch buckets. This costs a bit for small tables but saves
- big for large ones. */
- {
- vhash_search_bucket_t *b0, *b1, *b2, *b3;
- u32x4_union_t kh;
-
- kh.as_u32x4 = vhash_get_4_search_bucket_byte_offsets (h, c, n_key_u32s);
- hk->hashed_key[1].as_u32x4 = kh.as_u32x4;
-
- b0 = (void *) h->search_buckets + kh.as_u32[0];
- b1 = (void *) h->search_buckets + kh.as_u32[1];
- b2 = (void *) h->search_buckets + kh.as_u32[2];
- b3 = (void *) h->search_buckets + kh.as_u32[3];
-
- CLIB_PREFETCH (b0, sizeof (b0[0]) + n_key_u32s * sizeof (b0->key[0]),
- READ);
- CLIB_PREFETCH (b1, sizeof (b1[0]) + n_key_u32s * sizeof (b1->key[0]),
- READ);
- CLIB_PREFETCH (b2, sizeof (b2[0]) + n_key_u32s * sizeof (b2->key[0]),
- READ);
- CLIB_PREFETCH (b3, sizeof (b3[0]) + n_key_u32s * sizeof (b3->key[0]),
- READ);
- }
-}
-
-always_inline u32
-vhash_merge_results (u32x4 r)
-{
- r = r | u32x4_word_shift_right (r, 2);
- r = r | u32x4_word_shift_right (r, 1);
- return u32x4_get0 (r);
-}
-
-/* Bucket is full if none of its 4 results are 0. */
-always_inline u32
-vhash_search_bucket_is_full (u32x4 r)
-{
- return u32x4_zero_byte_mask (r) == 0;
-}
-
-always_inline u32
-vhash_non_empty_result_index (u32x4 x)
-{
- u32 empty_mask = u32x4_zero_byte_mask (x);
- ASSERT (empty_mask != 0xffff);
- return min_log2 (0xffff & ~empty_mask) / 4;
-}
-
-always_inline u32
-vhash_empty_result_index (u32x4 x)
-{
- u32 empty_mask = u32x4_zero_byte_mask (x);
- ASSERT (empty_mask != 0);
- return min_log2 (0xffff & empty_mask) / 4;
-}
-
-always_inline u32x4
-vhash_bucket_compare (vhash_t * h,
- u32x4_union_t * bucket, u32 key_word_index, u32 vi)
-{
- u32 k = vhash_get_key_word (h, key_word_index, vi);
- u32x4 x = { k, k, k, k };
- return u32x4_is_equal (bucket[key_word_index].as_u32x4, x);
-}
-
-#define vhash_bucket_compare_4(h,wi,vi,b0,b1,b2,b3,cmp0,cmp1,cmp2,cmp3) \
-do { \
- u32x4 _k4 = vhash_get_key_word_u32x ((h), (wi), (vi)); \
- u32x4 _k0 = u32x4_splat_word (_k4, 0); \
- u32x4 _k1 = u32x4_splat_word (_k4, 1); \
- u32x4 _k2 = u32x4_splat_word (_k4, 2); \
- u32x4 _k3 = u32x4_splat_word (_k4, 3); \
- \
- cmp0 = u32x4_is_equal (b0->key[wi].as_u32x4, _k0); \
- cmp1 = u32x4_is_equal (b1->key[wi].as_u32x4, _k1); \
- cmp2 = u32x4_is_equal (b2->key[wi].as_u32x4, _k2); \
- cmp3 = u32x4_is_equal (b3->key[wi].as_u32x4, _k3); \
-} while (0)
-
-u32 vhash_get_overflow (vhash_t * h, u32 key_hash, u32 vi, u32 n_key_u32s);
-
-always_inline void
-vhash_get_stage (vhash_t * h,
- u32 vector_index,
- u32 n_vectors,
- vhash_result_function_t result_function,
- void *state, u32 n_key_u32s)
-{
- u32 i, j;
- vhash_hashed_key_t *hk =
- vec_elt_at_index (h->hash_work_space, vector_index);
- vhash_search_bucket_t *b;
-
- for (i = 0; i < n_vectors; i++)
- {
- u32 vi = vector_index * 4 + i;
- u32 key_hash = hk->hashed_key[2].as_u32[i];
- u32 result;
- u32x4 r, r0;
-
- b = vhash_get_search_bucket (h, key_hash, n_key_u32s);
-
- r = r0 = b->result.as_u32x4;
- for (j = 0; j < n_key_u32s; j++)
- r &= vhash_bucket_compare (h, &b->key[0], j, vi);
-
- /* At this point only one of 4 results should be non-zero.
- So we can or all 4 together and get the valid result (if there is one). */
- result = vhash_merge_results (r);
-
- if (!result && vhash_search_bucket_is_full (r0))
- result = vhash_get_overflow (h, key_hash, vi, n_key_u32s);
-
- result_function (state, vi, result - 1, n_key_u32s);
- }
-}
-
-always_inline void
-vhash_get_4_stage (vhash_t * h,
- u32 vector_index,
- vhash_4result_function_t result_function,
- void *state, u32 n_key_u32s)
-{
- u32 i, vi;
- vhash_hashed_key_t *hk =
- vec_elt_at_index (h->hash_work_space, vector_index);
- vhash_search_bucket_t *b0, *b1, *b2, *b3;
- u32x4 r0, r1, r2, r3, r0_before, r1_before, r2_before, r3_before;
- u32x4_union_t kh;
-
- kh.as_u32x4 = hk->hashed_key[1].as_u32x4;
-
- b0 = (void *) h->search_buckets + kh.as_u32[0];
- b1 = (void *) h->search_buckets + kh.as_u32[1];
- b2 = (void *) h->search_buckets + kh.as_u32[2];
- b3 = (void *) h->search_buckets + kh.as_u32[3];
-
- r0 = r0_before = b0->result.as_u32x4;
- r1 = r1_before = b1->result.as_u32x4;
- r2 = r2_before = b2->result.as_u32x4;
- r3 = r3_before = b3->result.as_u32x4;
-
- vi = vector_index * 4;
-
- for (i = 0; i < n_key_u32s; i++)
- {
- u32x4 c0, c1, c2, c3;
- vhash_bucket_compare_4 (h, i, vector_index,
- b0, b1, b2, b3, c0, c1, c2, c3);
- r0 &= c0;
- r1 &= c1;
- r2 &= c2;
- r3 &= c3;
- }
-
- u32x4_transpose (r0, r1, r2, r3);
-
- /* Gather together 4 results. */
- {
- u32x4_union_t r;
- u32x4 ones = { 1, 1, 1, 1 };
- u32 not_found_mask;
-
- r.as_u32x4 = r0 | r1 | r2 | r3;
- not_found_mask = u32x4_zero_byte_mask (r.as_u32x4);
- not_found_mask &= ((vhash_search_bucket_is_full (r0_before) << (4 * 0))
- | (vhash_search_bucket_is_full (r1_before) << (4 * 1))
- | (vhash_search_bucket_is_full (r2_before) << (4 * 2))
- | (vhash_search_bucket_is_full (r3_before) <<
- (4 * 3)));
- if (not_found_mask)
- {
- u32x4_union_t key_hash;
-
- key_hash.as_u32x4 =
- hk->hashed_key[2].as_u32x4 & h->bucket_mask.as_u32x4;
-
- /* Slow path: one of the buckets may have been full and we need to search overflow. */
- if (not_found_mask & (1 << (4 * 0)))
- r.as_u32[0] = vhash_get_overflow (h, key_hash.as_u32[0],
- vi + 0, n_key_u32s);
- if (not_found_mask & (1 << (4 * 1)))
- r.as_u32[1] = vhash_get_overflow (h, key_hash.as_u32[1],
- vi + 1, n_key_u32s);
- if (not_found_mask & (1 << (4 * 2)))
- r.as_u32[2] = vhash_get_overflow (h, key_hash.as_u32[2],
- vi + 2, n_key_u32s);
- if (not_found_mask & (1 << (4 * 3)))
- r.as_u32[3] = vhash_get_overflow (h, key_hash.as_u32[3],
- vi + 3, n_key_u32s);
- }
-
- result_function (state, vi, r.as_u32x4 - ones, n_key_u32s);
- }
-}
-
-u32
-vhash_set_overflow (vhash_t * h,
- u32 key_hash, u32 vi, u32 new_result, u32 n_key_u32s);
-
-always_inline void
-vhash_set_stage (vhash_t * h,
- u32 vector_index,
- u32 n_vectors,
- vhash_result_function_t result_function,
- void *state, u32 n_key_u32s)
-{
- u32 i, j, n_new_elts = 0;
- vhash_hashed_key_t *hk =
- vec_elt_at_index (h->hash_work_space, vector_index);
- vhash_search_bucket_t *b;
-
- for (i = 0; i < n_vectors; i++)
- {
- u32 vi = vector_index * 4 + i;
- u32 key_hash = hk->hashed_key[2].as_u32[i];
- u32 old_result, new_result;
- u32 i_set;
- u32x4 r, r0, cmp;
-
- b = vhash_get_search_bucket (h, key_hash, n_key_u32s);
-
- cmp = vhash_bucket_compare (h, &b->key[0], 0, vi);
- for (j = 1; j < n_key_u32s; j++)
- cmp &= vhash_bucket_compare (h, &b->key[0], j, vi);
-
- r0 = b->result.as_u32x4;
- r = r0 & cmp;
-
- /* At this point only one of 4 results should be non-zero.
- So we can or all 4 together and get the valid result (if there is one). */
- old_result = vhash_merge_results (r);
-
- if (!old_result && vhash_search_bucket_is_full (r0))
- old_result = vhash_get_overflow (h, key_hash, vi, n_key_u32s);
-
- /* Get new result; possibly do something with old result. */
- new_result = result_function (state, vi, old_result - 1, n_key_u32s);
-
- /* User cannot use ~0 as a hash result since a result of 0 is
- used to mark unused bucket entries. */
- ASSERT (new_result + 1 != 0);
- new_result += 1;
-
- /* Set over-writes existing result. */
- if (old_result)
- {
- i_set = vhash_non_empty_result_index (r);
- b->result.as_u32[i_set] = new_result;
- }
- else
- {
- /* Set allocates new result. */
- u32 valid_mask;
-
- valid_mask = (((b->result.as_u32[0] != 0) << 0)
- | ((b->result.as_u32[1] != 0) << 1)
- | ((b->result.as_u32[2] != 0) << 2)
- | ((b->result.as_u32[3] != 0) << 3));
-
- /* Rotate 4 bit valid mask so that key_hash corresponds to bit 0. */
- i_set = key_hash & 3;
- valid_mask =
- ((valid_mask >> i_set) | (valid_mask << (4 - i_set))) & 0xf;
-
- /* Insert into first empty position in bucket after key_hash. */
- i_set = (i_set + h->find_first_zero_table[valid_mask]) & 3;
-
- if (valid_mask != 0xf)
- {
- n_new_elts += 1;
-
- b->result.as_u32[i_set] = new_result;
-
- /* Insert new key into search bucket. */
- for (j = 0; j < n_key_u32s; j++)
- b->key[j].as_u32[i_set] = vhash_get_key_word (h, j, vi);
- }
- else
- vhash_set_overflow (h, key_hash, vi, new_result, n_key_u32s);
- }
- }
-
- h->n_elts += n_new_elts;
-}
-
-u32 vhash_unset_overflow (vhash_t * h, u32 key_hash, u32 vi, u32 n_key_u32s);
-
-void
-vhash_unset_refill_from_overflow (vhash_t * h,
- vhash_search_bucket_t * b,
- u32 key_hash, u32 n_key_u32s);
-
-/* Note: Eliot tried doing 4 unsets at once and could not get a speed up
- and abandoned vhash_unset_4_stage. */
-always_inline void
-vhash_unset_stage (vhash_t * h,
- u32 vector_index,
- u32 n_vectors,
- vhash_result_function_t result_function,
- void *state, u32 n_key_u32s)
-{
- u32 i, j, n_elts_unset = 0;
- vhash_hashed_key_t *hk =
- vec_elt_at_index (h->hash_work_space, vector_index);
- vhash_search_bucket_t *b;
-
- for (i = 0; i < n_vectors; i++)
- {
- u32 vi = vector_index * 4 + i;
- u32 key_hash = hk->hashed_key[2].as_u32[i];
- u32 old_result;
- u32x4 cmp, r0;
-
- b = vhash_get_search_bucket (h, key_hash, n_key_u32s);
-
- cmp = vhash_bucket_compare (h, &b->key[0], 0, vi);
- for (j = 1; j < n_key_u32s; j++)
- cmp &= vhash_bucket_compare (h, &b->key[0], j, vi);
-
- r0 = b->result.as_u32x4;
-
- /* At this point cmp is all ones where key matches and zero otherwise.
- So, this will invalidate results for matching key and do nothing otherwise. */
- b->result.as_u32x4 = r0 & ~cmp;
-
- old_result = vhash_merge_results (r0 & cmp);
-
- n_elts_unset += old_result != 0;
-
- if (vhash_search_bucket_is_full (r0))
- {
- if (old_result)
- vhash_unset_refill_from_overflow (h, b, key_hash, n_key_u32s);
- else
- old_result = vhash_unset_overflow (h, key_hash, vi, n_key_u32s);
- }
-
- result_function (state, vi, old_result - 1, n_key_u32s);
- }
- ASSERT (h->n_elts >= n_elts_unset);
- h->n_elts -= n_elts_unset;
-}
-
-void vhash_init (vhash_t * h, u32 log2_n_keys, u32 n_key_u32,
- u32 * hash_seeds);
-
-void vhash_resize (vhash_t * old, u32 log2_n_keys);
-
-typedef struct
-{
- vhash_t *vhash;
-
- union
- {
- struct
- {
- u32 *keys;
- u32 *results;
- };
-
- /* Vector layout for get keys. */
- struct
- {
- u32x4_union_t *get_keys;
- u32x4_union_t *get_results;
- };
- };
-
- u32 n_vectors_div_4;
- u32 n_vectors_mod_4;
-
- u32 n_key_u32;
-
- u32 n_keys;
-} vhash_main_t;
-
-always_inline u32
-vhash_get_alloc_keys (vhash_main_t * vm, u32 n_keys, u32 n_key_u32)
-{
- u32 i, n;
-
- i = vm->n_keys;
- vm->n_keys = i + n_keys;
-
- n = (round_pow2 (vm->n_keys, 4) / 4) * n_key_u32;
-
- vec_validate_aligned (vm->get_keys, n - 1, sizeof (vm->get_keys[0]));
- vec_validate_aligned (vm->get_results, n - 1, sizeof (vm->get_results[0]));
-
- return i;
-}
-
-always_inline void
-vhash_get_set_key_word (vhash_main_t * vm, u32 vi, u32 wi, u32 n_key_u32,
- u32 value)
-{
- u32x4_union_t *k = vec_elt_at_index (vm->get_keys, (vi / 4) * n_key_u32);
- ASSERT (wi < n_key_u32);
- k[wi].as_u32[vi % 4] = value;
-}
-
-always_inline u32
-vhash_get_fetch_result (vhash_main_t * vm, u32 vi)
-{
- u32x4_union_t *r = vec_elt_at_index (vm->get_results, vi / 4);
- return r->as_u32[vi % 4];
-}
-
-void vhash_main_get (vhash_main_t * vm);
-
-always_inline u32
-vhash_set_alloc_keys (vhash_main_t * vm, u32 n_keys, u32 n_key_u32)
-{
- u32 i;
-
- i = vm->n_keys;
- vm->n_keys = i + n_keys;
-
- vec_resize (vm->keys, n_keys * n_key_u32);
- vec_resize (vm->results, n_keys);
-
- return i;
-}
-
-always_inline void
-vhash_set_set_key_word (vhash_main_t * vm, u32 vi, u32 wi, u32 n_key_u32,
- u32 value)
-{
- u32 *k = vec_elt_at_index (vm->keys, vi * n_key_u32);
- ASSERT (wi < n_key_u32);
- k[wi] = value;
-}
-
-always_inline void
-vhash_set_set_result (vhash_main_t * vm, u32 vi, u32 result)
-{
- u32 *r = vec_elt_at_index (vm->results, vi);
- r[0] = result;
-}
-
-always_inline u32
-vhash_set_fetch_old_result (vhash_main_t * vm, u32 vi)
-{
- u32 *r = vec_elt_at_index (vm->results, vi);
- return r[0];
-}
-
-void vhash_main_set (vhash_main_t * vm);
-
-always_inline u32
-vhash_unset_alloc_keys (vhash_main_t * vm, u32 n_keys, u32 n_key_u32)
-{
- return vhash_set_alloc_keys (vm, n_keys, n_key_u32);
-}
-
-always_inline void
-vhash_unset_set_key_word (vhash_main_t * vm, u32 vi, u32 wi, u32 n_key_u32,
- u32 value)
-{
- vhash_set_set_key_word (vm, vi, wi, n_key_u32, value);
-}
-
-always_inline void
-vhash_unset_set_result (vhash_main_t * vm, u32 vi, u32 result)
-{
- vhash_set_set_result (vm, vi, result);
-}
-
-always_inline u32
-vhash_unset_fetch_old_result (vhash_main_t * vm, u32 vi)
-{
- return vhash_set_fetch_old_result (vm, vi);
-}
-
-void vhash_main_unset (vhash_main_t * vm);
-
-typedef struct
-{
- vhash_main_t new;
-
- vhash_t *old;
-} vhash_resize_t;
-
-u32 vhash_resize_incremental (vhash_resize_t * vr, u32 vector_index,
- u32 n_vectors);
-
-#endif /* CLIB_HAVE_VEC128 */
-
-#endif /* included_clib_vhash_h */
-
-/*
- * fd.io coding-style-patch-verification: ON
- *
- * Local Variables:
- * eval: (c-set-style "gnu")
- * End:
- */