From 053d0935244843199c433e92df666b4f79007727 Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Wed, 22 Apr 2020 10:02:31 -0400 Subject: vppinfra: move unused code to extras/deprecated/vppinfra Type: improvement Signed-off-by: Dave Barach Change-Id: Id28299a188feefa1899d835fd499f018af95d81b --- src/vppinfra/vhash.h | 850 --------------------------------------------------- 1 file changed, 850 deletions(-) delete mode 100644 src/vppinfra/vhash.h (limited to 'src/vppinfra/vhash.h') diff --git a/src/vppinfra/vhash.h b/src/vppinfra/vhash.h deleted file mode 100644 index 85dfb788308..00000000000 --- a/src/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 - -#ifdef CLIB_HAVE_VEC128 - -#include -#include -#include - -/* 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 (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 = (b0->key[wi].as_u32x4 == _k0); \ - cmp1 = (b1->key[wi].as_u32x4 == _k1); \ - cmp2 = (b2->key[wi].as_u32x4 == _k2); \ - cmp3 = (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: - */ -- cgit 1.2.3-korg