diff options
Diffstat (limited to 'extras/deprecated/vppinfra/vhash.h')
| -rw-r--r-- | extras/deprecated/vppinfra/vhash.h | 850 |
1 files changed, 850 insertions, 0 deletions
diff --git a/extras/deprecated/vppinfra/vhash.h b/extras/deprecated/vppinfra/vhash.h new file mode 100644 index 00000000000..85dfb788308 --- /dev/null +++ b/extras/deprecated/vppinfra/vhash.h @@ -0,0 +1,850 @@ +/* + * 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 (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: + */ |