2 * Copyright (c) 2015 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
16 Copyright (c) 2006 Eliot Dresselhaus
18 Permission is hereby granted, free of charge, to any person obtaining
19 a copy of this software and associated documentation files (the
20 "Software"), to deal in the Software without restriction, including
21 without limitation the rights to use, copy, modify, merge, publish,
22 distribute, sublicense, and/or sell copies of the Software, and to
23 permit persons to whom the Software is furnished to do so, subject to
24 the following conditions:
26 The above copyright notice and this permission notice shall be
27 included in all copies or substantial portions of the Software.
29 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33 LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34 OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38 #include <vppinfra/qhash.h>
40 #define QHASH_ALL_VALID ((1 << QHASH_KEYS_PER_BUCKET) - 1)
43 _qhash_resize (void *v, uword length, uword elt_bytes)
48 l = clib_max (max_log2 (length), 2 + QHASH_LOG2_KEYS_PER_BUCKET);
50 /* Round up if less than 1/2 full. */
51 l += ((f64) length / (f64) (1 << l)) < .5;
53 v = _vec_resize (0, 1 << l, elt_bytes << l, sizeof (h[0]),
54 /* align */ sizeof (uword));
58 h->log2_hash_size = l;
60 clib_mem_alloc_aligned_no_fail (sizeof (h->hash_keys[0]) << l,
61 CLIB_CACHE_LINE_BYTES);
62 vec_resize (h->hash_key_valid_bitmap,
63 1 << (l - QHASH_LOG2_KEYS_PER_BUCKET));
64 memset (v, ~0, elt_bytes << l);
69 static u8 min_log2_table[256];
72 qhash_min_log2 (uword x)
76 return min_log2_table[x];
80 qhash_min_log2_init ()
83 for (i = 0; i < 256; i++)
84 min_log2_table[i] = min_log2 (i);
88 qhash_get_valid_elt_mask (qhash_t * h, uword i)
90 return h->hash_key_valid_bitmap[i / QHASH_KEYS_PER_BUCKET];
94 qhash_set_valid_elt_mask (qhash_t * h, uword i, uword mask)
96 h->hash_key_valid_bitmap[i / QHASH_KEYS_PER_BUCKET] = mask;
100 qhash_search_bucket (uword * hash_keys, uword search_key, uword m)
103 #define _(i) ((hash_keys[i] == search_key) << i)
104 t = (_(0) | _(1) | _(2) | _(3));
105 if (QHASH_KEYS_PER_BUCKET > 4)
106 t |= (_(4) | _(5) | _(6) | _(7));
107 if (QHASH_KEYS_PER_BUCKET > 8)
108 t |= (_(8) | _(9) | _(10) | _(11) | _(12) | _(13) | _(14) | _(15));
113 /* Lookup multiple keys in the same hash table. */
115 qhash_get_multiple (void *v,
117 uword n_search_keys, u32 * result_indices)
119 qhash_t *h = qhash_header (v);
120 uword *k, *hash_keys;
121 uword n_left, bucket_mask;
126 memset (result_indices, ~0, sizeof (result_indices[0]) * n_search_keys);
130 bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
133 n_left = n_search_keys;
134 hash_keys = h->hash_keys;
139 u32 a0, b0, c0, bi0, valid0, match0;
140 u32 a1, b1, c1, bi1, valid1, match1;
141 uword k0, k1, *h0, *h1;
148 a0 = a1 = h->hash_seeds[0];
149 b0 = b1 = h->hash_seeds[1];
150 c0 = c1 = h->hash_seeds[2];
158 hash_mix32_step_1 (a0, b0, c0);
159 hash_mix32_step_1 (a1, b1, c1);
160 hash_mix32_step_2 (a0, b0, c0);
161 hash_mix32_step_2 (a1, b1, c1);
162 hash_mix32_step_3 (a0, b0, c0);
163 hash_mix32_step_3 (a1, b1, c1);
165 bi0 = c0 & bucket_mask;
166 bi1 = c1 & bucket_mask;
168 h0 = hash_keys + bi0;
169 h1 = hash_keys + bi1;
171 /* Search two buckets. */
172 valid0 = qhash_get_valid_elt_mask (h, bi0);
173 valid1 = qhash_get_valid_elt_mask (h, bi1);
175 match0 = qhash_search_bucket (h0, k0, valid0);
176 match1 = qhash_search_bucket (h1, k1, valid1);
178 bi0 += qhash_min_log2 (match0);
179 bi1 += qhash_min_log2 (match1);
181 r[0] = match0 ? bi0 : ~0;
182 r[1] = match1 ? bi1 : ~0;
185 /* Full buckets trigger search of overflow hash. */
186 if (PREDICT_FALSE (!match0 && valid0 == QHASH_ALL_VALID))
188 uword *p = hash_get (h->overflow_hash, k0);
189 r[-2] = p ? p[0] : ~0;
192 /* Full buckets trigger search of overflow hash. */
193 if (PREDICT_FALSE (!match1 && valid1 == QHASH_ALL_VALID))
195 uword *p = hash_get (h->overflow_hash, k1);
196 r[-1] = p ? p[0] : ~0;
202 u32 a0, b0, c0, bi0, valid0, match0;
209 a0 = h->hash_seeds[0];
210 b0 = h->hash_seeds[1];
211 c0 = h->hash_seeds[2];
217 hash_mix32 (a0, b0, c0);
219 bi0 = c0 & bucket_mask;
221 h0 = hash_keys + bi0;
223 /* Search one bucket. */
224 valid0 = qhash_get_valid_elt_mask (h, bi0);
225 match0 = qhash_search_bucket (h0, k0, valid0);
227 bi0 += qhash_min_log2 (match0);
229 r[0] = match0 ? bi0 : ~0;
232 /* Full buckets trigger search of overflow hash. */
233 if (PREDICT_FALSE (!match0 && valid0 == QHASH_ALL_VALID))
235 uword *p = hash_get (h->overflow_hash, k0);
236 r[-1] = p ? p[0] : ~0;
241 /* Lookup multiple keys in the same hash table.
242 Returns index of first matching key. */
244 qhash_get_first_match (void *v,
246 uword n_search_keys, uword * matching_key)
248 qhash_t *h = qhash_header (v);
249 uword *k, *hash_keys;
250 uword n_left, match_mask, bucket_mask;
256 bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
259 n_left = n_search_keys;
260 hash_keys = h->hash_keys;
263 u32 a0, b0, c0, bi0, valid0;
264 u32 a1, b1, c1, bi1, valid1;
265 uword k0, k1, *h0, *h1;
272 a0 = a1 = h->hash_seeds[0];
273 b0 = b1 = h->hash_seeds[1];
274 c0 = c1 = h->hash_seeds[2];
282 hash_mix32_step_1 (a0, b0, c0);
283 hash_mix32_step_1 (a1, b1, c1);
284 hash_mix32_step_2 (a0, b0, c0);
285 hash_mix32_step_2 (a1, b1, c1);
286 hash_mix32_step_3 (a0, b0, c0);
287 hash_mix32_step_3 (a1, b1, c1);
289 bi0 = c0 & bucket_mask;
290 bi1 = c1 & bucket_mask;
292 h0 = hash_keys + bi0;
293 h1 = hash_keys + bi1;
295 /* Search two buckets. */
296 valid0 = qhash_get_valid_elt_mask (h, bi0);
297 valid1 = qhash_get_valid_elt_mask (h, bi1);
298 match_mask = qhash_search_bucket (h0, k0, valid0);
299 match_mask |= (qhash_search_bucket (h1, k1, valid1)
300 << QHASH_KEYS_PER_BUCKET);
305 bi = qhash_min_log2 (match_mask);
306 is_match1 = bi >= QHASH_KEYS_PER_BUCKET;
308 bi += ((is_match1 ? bi1 : bi0)
309 - (is_match1 << QHASH_LOG2_KEYS_PER_BUCKET));
310 *matching_key = (k - 2 - search_keys) + is_match1;
314 /* Full buckets trigger search of overflow hash. */
315 if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID
316 || valid1 == QHASH_ALL_VALID))
319 uword ki = k - 2 - search_keys;
321 if (valid0 == QHASH_ALL_VALID)
322 p = hash_get (h->overflow_hash, k0);
324 if (!p && valid1 == QHASH_ALL_VALID)
326 p = hash_get (h->overflow_hash, k1);
340 u32 a0, b0, c0, bi0, valid0;
347 a0 = h->hash_seeds[0];
348 b0 = h->hash_seeds[1];
349 c0 = h->hash_seeds[2];
355 hash_mix32 (a0, b0, c0);
357 bi0 = c0 & bucket_mask;
359 h0 = hash_keys + bi0;
361 /* Search one bucket. */
362 valid0 = qhash_get_valid_elt_mask (h, bi0);
363 match_mask = qhash_search_bucket (h0, k0, valid0);
367 bi = bi0 + qhash_min_log2 (match_mask);
368 *matching_key = (k - 1 - search_keys);
372 /* Full buckets trigger search of overflow hash. */
373 if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID))
375 uword *p = hash_get (h->overflow_hash, k0);
378 *matching_key = (k - 1 - search_keys);
388 qhash_set_overflow (void *v, uword elt_bytes,
389 uword key, uword bi, uword * n_elts, u32 * result)
391 qhash_t *h = qhash_header (v);
392 uword *p = hash_get (h->overflow_hash, key);
395 bi /= QHASH_KEYS_PER_BUCKET;
401 uword l = vec_len (h->overflow_free_indices);
404 i = h->overflow_free_indices[l - 1];
405 _vec_len (h->overflow_free_indices) = l - 1;
408 i = (1 << h->log2_hash_size) + hash_elts (h->overflow_hash);
409 hash_set (h->overflow_hash, key, i);
410 vec_validate (h->overflow_counts, bi);
411 h->overflow_counts[bi] += 1;
417 uword dl = round_pow2 (1 + i - l, 8);
418 v = _vec_resize (v, dl, (l + dl) * elt_bytes, sizeof (h[0]),
419 /* align */ sizeof (uword));
420 memset (v + l * elt_bytes, ~0, dl * elt_bytes);
430 qhash_unset_overflow (void *v, uword key, uword bi, uword * n_elts)
432 qhash_t *h = qhash_header (v);
433 uword *p = hash_get (h->overflow_hash, key);
436 bi /= QHASH_KEYS_PER_BUCKET;
441 hash_unset (h->overflow_hash, key);
442 ASSERT (bi < vec_len (h->overflow_counts));
443 ASSERT (h->overflow_counts[bi] > 0);
444 ASSERT (*n_elts > 0);
445 vec_add1 (h->overflow_free_indices, result);
446 h->overflow_counts[bi] -= 1;
456 qhash_find_free (uword i, uword valid_mask)
458 return first_set (~valid_mask & pow2_mask (QHASH_KEYS_PER_BUCKET));
462 _qhash_set_multiple (void *v,
465 uword n_search_keys, u32 * result_indices)
467 qhash_t *h = qhash_header (v);
468 uword *k, *hash_keys;
469 uword n_left, n_elts, bucket_mask;
472 if (vec_len (v) < n_search_keys)
473 v = _qhash_resize (v, n_search_keys, elt_bytes);
475 if (qhash_min_log2 (2) != 1)
477 qhash_min_log2_init ();
478 ASSERT (qhash_min_log2 (2) == 1);
483 bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
485 hash_keys = h->hash_keys;
488 n_left = n_search_keys;
493 u32 a0, b0, c0, bi0, match0, valid0, free0;
494 u32 a1, b1, c1, bi1, match1, valid1, free1;
501 /* Keys must be unique. */
507 a0 = a1 = h->hash_seeds[0];
508 b0 = b1 = h->hash_seeds[1];
509 c0 = c1 = h->hash_seeds[2];
517 hash_mix32_step_1 (a0, b0, c0);
518 hash_mix32_step_1 (a1, b1, c1);
519 hash_mix32_step_2 (a0, b0, c0);
520 hash_mix32_step_2 (a1, b1, c1);
521 hash_mix32_step_3 (a0, b0, c0);
522 hash_mix32_step_3 (a1, b1, c1);
524 bi0 = c0 & bucket_mask;
525 bi1 = c1 & bucket_mask;
527 h0 = hash_keys + bi0;
528 h1 = hash_keys + bi1;
530 /* Search two buckets. */
531 valid0 = qhash_get_valid_elt_mask (h, bi0);
532 valid1 = qhash_get_valid_elt_mask (h, bi1);
534 match0 = qhash_search_bucket (h0, k0, valid0);
535 match1 = qhash_search_bucket (h1, k1, valid1);
537 /* Find first free element starting at hash offset into bucket. */
538 free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
540 valid1 = valid1 | (bi0 == bi1 ? free0 : 0);
541 free1 = qhash_find_free (c1 & (QHASH_KEYS_PER_BUCKET - 1), valid1);
543 n_elts += (match0 == 0) + (match1 == 0);
545 match0 = match0 ? match0 : free0;
546 match1 = match1 ? match1 : free1;
551 h0 += qhash_min_log2 (match0);
552 h1 += qhash_min_log2 (match1);
554 if (PREDICT_FALSE (!match0 || !match1))
559 r[0] = h0 - hash_keys;
560 r[1] = h1 - hash_keys;
562 qhash_set_valid_elt_mask (h, bi0, valid0);
563 qhash_set_valid_elt_mask (h, bi1, valid1);
570 v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
575 r[0] = h0 - hash_keys;
576 qhash_set_valid_elt_mask (h, bi0, valid0);
581 v = qhash_set_overflow (v, elt_bytes, k1, bi1, &n_elts, &r[1]);
586 r[1] = h1 - hash_keys;
587 qhash_set_valid_elt_mask (h, bi1, valid1);
594 u32 a0, b0, c0, bi0, match0, valid0, free0;
601 a0 = h->hash_seeds[0];
602 b0 = h->hash_seeds[1];
603 c0 = h->hash_seeds[2];
609 hash_mix32 (a0, b0, c0);
611 bi0 = c0 & bucket_mask;
613 h0 = hash_keys + bi0;
615 valid0 = qhash_get_valid_elt_mask (h, bi0);
617 /* Find first free element starting at hash offset into bucket. */
618 free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
620 match0 = qhash_search_bucket (h0, k0, valid0);
622 n_elts += (match0 == 0);
624 match0 = match0 ? match0 : free0;
628 h0 += qhash_min_log2 (match0);
630 if (PREDICT_FALSE (!match0))
634 r[0] = h0 - hash_keys;
636 qhash_set_valid_elt_mask (h, bi0, valid0);
641 v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
645 h = qhash_header (v);
652 unset_slow_path (void *v, uword elt_bytes,
653 uword k0, uword bi0, uword valid0, uword match0,
656 qhash_t *h = qhash_header (v);
657 uword i, j = 0, k, l, t = ~0;
658 hash_pair_t *p, *found;
662 if (valid0 == QHASH_ALL_VALID)
663 t = qhash_unset_overflow (v, k0, bi0, n_elts);
667 i = bi0 / QHASH_KEYS_PER_BUCKET;
668 t = bi0 + qhash_min_log2 (match0);
670 if (valid0 == QHASH_ALL_VALID
671 && i < vec_len (h->overflow_counts) && h->overflow_counts[i] > 0)
675 hash_foreach_pair (p, h->overflow_hash, ({
676 j = qhash_hash_mix (h, p->key) / QHASH_KEYS_PER_BUCKET;
689 hash_unset3 (h->overflow_hash, k, &j);
690 vec_add1 (h->overflow_free_indices, j);
691 h->overflow_counts[i] -= 1;
693 qhash_set_valid_elt_mask (h, bi0, valid0);
696 clib_memswap (v + t * elt_bytes, v + l * elt_bytes, elt_bytes);
700 qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
706 _qhash_unset_multiple (void *v,
709 uword n_search_keys, u32 * result_indices)
711 qhash_t *h = qhash_header (v);
712 uword *k, *hash_keys;
713 uword n_left, n_elts, bucket_mask;
719 for (i = 0; i < n_search_keys; i++)
720 result_indices[i] = ~0;
723 bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
725 hash_keys = h->hash_keys;
728 n_left = n_search_keys;
733 u32 a0, b0, c0, bi0, match0, valid0;
734 u32 a1, b1, c1, bi1, match1, valid1;
741 /* Keys must be unique. */
747 a0 = a1 = h->hash_seeds[0];
748 b0 = b1 = h->hash_seeds[1];
749 c0 = c1 = h->hash_seeds[2];
757 hash_mix32_step_1 (a0, b0, c0);
758 hash_mix32_step_1 (a1, b1, c1);
759 hash_mix32_step_2 (a0, b0, c0);
760 hash_mix32_step_2 (a1, b1, c1);
761 hash_mix32_step_3 (a0, b0, c0);
762 hash_mix32_step_3 (a1, b1, c1);
764 bi0 = c0 & bucket_mask;
765 bi1 = c1 & bucket_mask;
767 h0 = hash_keys + bi0;
768 h1 = hash_keys + bi1;
770 /* Search two buckets. */
771 valid0 = qhash_get_valid_elt_mask (h, bi0);
772 valid1 = qhash_get_valid_elt_mask (h, bi1);
774 match0 = qhash_search_bucket (h0, k0, valid0);
775 match1 = qhash_search_bucket (h1, k1, valid1);
777 n_elts -= (match0 != 0) + (match1 != 0);
779 if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID
780 || valid1 == QHASH_ALL_VALID))
784 qhash_set_valid_elt_mask (h, bi0, valid0);
786 valid1 = bi0 == bi1 ? valid0 : valid1;
789 qhash_set_valid_elt_mask (h, bi1, valid1);
791 r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
792 r[1] = match1 ? bi1 + qhash_min_log2 (match1) : ~0;
797 r[0] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0, &n_elts);
800 /* Search again in same bucket to test new overflow element. */
801 valid1 = qhash_get_valid_elt_mask (h, bi0);
804 match1 = qhash_search_bucket (h1, k1, valid1);
805 n_elts -= (match1 != 0);
808 r[1] = unset_slow_path (v, elt_bytes, k1, bi1, valid1, match1, &n_elts);
814 u32 a0, b0, c0, bi0, match0, valid0;
821 a0 = h->hash_seeds[0];
822 b0 = h->hash_seeds[1];
823 c0 = h->hash_seeds[2];
829 hash_mix32 (a0, b0, c0);
831 bi0 = c0 & bucket_mask;
833 h0 = hash_keys + bi0;
835 valid0 = qhash_get_valid_elt_mask (h, bi0);
837 match0 = qhash_search_bucket (h0, k0, valid0);
838 n_elts -= (match0 != 0);
839 qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
841 r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
844 if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID))
845 r[-1] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0,
853 * fd.io coding-style-patch-verification: ON
856 * eval: (c-set-style "gnu")