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 clib_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 clib_memset (result_indices, ~0,
127 sizeof (result_indices[0]) * n_search_keys);
131 bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
134 n_left = n_search_keys;
135 hash_keys = h->hash_keys;
140 u32 a0, b0, c0, bi0, valid0, match0;
141 u32 a1, b1, c1, bi1, valid1, match1;
142 uword k0, k1, *h0, *h1;
149 a0 = a1 = h->hash_seeds[0];
150 b0 = b1 = h->hash_seeds[1];
151 c0 = c1 = h->hash_seeds[2];
159 hash_mix32_step_1 (a0, b0, c0);
160 hash_mix32_step_1 (a1, b1, c1);
161 hash_mix32_step_2 (a0, b0, c0);
162 hash_mix32_step_2 (a1, b1, c1);
163 hash_mix32_step_3 (a0, b0, c0);
164 hash_mix32_step_3 (a1, b1, c1);
166 bi0 = c0 & bucket_mask;
167 bi1 = c1 & bucket_mask;
169 h0 = hash_keys + bi0;
170 h1 = hash_keys + bi1;
172 /* Search two buckets. */
173 valid0 = qhash_get_valid_elt_mask (h, bi0);
174 valid1 = qhash_get_valid_elt_mask (h, bi1);
176 match0 = qhash_search_bucket (h0, k0, valid0);
177 match1 = qhash_search_bucket (h1, k1, valid1);
179 bi0 += qhash_min_log2 (match0);
180 bi1 += qhash_min_log2 (match1);
182 r[0] = match0 ? bi0 : ~0;
183 r[1] = match1 ? bi1 : ~0;
186 /* Full buckets trigger search of overflow hash. */
187 if (PREDICT_FALSE (!match0 && valid0 == QHASH_ALL_VALID))
189 uword *p = hash_get (h->overflow_hash, k0);
190 r[-2] = p ? p[0] : ~0;
193 /* Full buckets trigger search of overflow hash. */
194 if (PREDICT_FALSE (!match1 && valid1 == QHASH_ALL_VALID))
196 uword *p = hash_get (h->overflow_hash, k1);
197 r[-1] = p ? p[0] : ~0;
203 u32 a0, b0, c0, bi0, valid0, match0;
210 a0 = h->hash_seeds[0];
211 b0 = h->hash_seeds[1];
212 c0 = h->hash_seeds[2];
218 hash_mix32 (a0, b0, c0);
220 bi0 = c0 & bucket_mask;
222 h0 = hash_keys + bi0;
224 /* Search one bucket. */
225 valid0 = qhash_get_valid_elt_mask (h, bi0);
226 match0 = qhash_search_bucket (h0, k0, valid0);
228 bi0 += qhash_min_log2 (match0);
230 r[0] = match0 ? bi0 : ~0;
233 /* Full buckets trigger search of overflow hash. */
234 if (PREDICT_FALSE (!match0 && valid0 == QHASH_ALL_VALID))
236 uword *p = hash_get (h->overflow_hash, k0);
237 r[-1] = p ? p[0] : ~0;
242 /* Lookup multiple keys in the same hash table.
243 Returns index of first matching key. */
245 qhash_get_first_match (void *v,
247 uword n_search_keys, uword * matching_key)
249 qhash_t *h = qhash_header (v);
250 uword *k, *hash_keys;
251 uword n_left, match_mask, bucket_mask;
257 bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
260 n_left = n_search_keys;
261 hash_keys = h->hash_keys;
264 u32 a0, b0, c0, bi0, valid0;
265 u32 a1, b1, c1, bi1, valid1;
266 uword k0, k1, *h0, *h1;
273 a0 = a1 = h->hash_seeds[0];
274 b0 = b1 = h->hash_seeds[1];
275 c0 = c1 = h->hash_seeds[2];
283 hash_mix32_step_1 (a0, b0, c0);
284 hash_mix32_step_1 (a1, b1, c1);
285 hash_mix32_step_2 (a0, b0, c0);
286 hash_mix32_step_2 (a1, b1, c1);
287 hash_mix32_step_3 (a0, b0, c0);
288 hash_mix32_step_3 (a1, b1, c1);
290 bi0 = c0 & bucket_mask;
291 bi1 = c1 & bucket_mask;
293 h0 = hash_keys + bi0;
294 h1 = hash_keys + bi1;
296 /* Search two buckets. */
297 valid0 = qhash_get_valid_elt_mask (h, bi0);
298 valid1 = qhash_get_valid_elt_mask (h, bi1);
299 match_mask = qhash_search_bucket (h0, k0, valid0);
300 match_mask |= (qhash_search_bucket (h1, k1, valid1)
301 << QHASH_KEYS_PER_BUCKET);
306 bi = qhash_min_log2 (match_mask);
307 is_match1 = bi >= QHASH_KEYS_PER_BUCKET;
309 bi += ((is_match1 ? bi1 : bi0)
310 - (is_match1 << QHASH_LOG2_KEYS_PER_BUCKET));
311 *matching_key = (k - 2 - search_keys) + is_match1;
315 /* Full buckets trigger search of overflow hash. */
316 if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID
317 || valid1 == QHASH_ALL_VALID))
320 uword ki = k - 2 - search_keys;
322 if (valid0 == QHASH_ALL_VALID)
323 p = hash_get (h->overflow_hash, k0);
325 if (!p && valid1 == QHASH_ALL_VALID)
327 p = hash_get (h->overflow_hash, k1);
341 u32 a0, b0, c0, bi0, valid0;
348 a0 = h->hash_seeds[0];
349 b0 = h->hash_seeds[1];
350 c0 = h->hash_seeds[2];
356 hash_mix32 (a0, b0, c0);
358 bi0 = c0 & bucket_mask;
360 h0 = hash_keys + bi0;
362 /* Search one bucket. */
363 valid0 = qhash_get_valid_elt_mask (h, bi0);
364 match_mask = qhash_search_bucket (h0, k0, valid0);
368 bi = bi0 + qhash_min_log2 (match_mask);
369 *matching_key = (k - 1 - search_keys);
373 /* Full buckets trigger search of overflow hash. */
374 if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID))
376 uword *p = hash_get (h->overflow_hash, k0);
379 *matching_key = (k - 1 - search_keys);
389 qhash_set_overflow (void *v, uword elt_bytes,
390 uword key, uword bi, uword * n_elts, u32 * result)
392 qhash_t *h = qhash_header (v);
393 uword *p = hash_get (h->overflow_hash, key);
396 bi /= QHASH_KEYS_PER_BUCKET;
402 uword l = vec_len (h->overflow_free_indices);
405 i = h->overflow_free_indices[l - 1];
406 _vec_len (h->overflow_free_indices) = l - 1;
409 i = (1 << h->log2_hash_size) + hash_elts (h->overflow_hash);
410 hash_set (h->overflow_hash, key, i);
411 vec_validate (h->overflow_counts, bi);
412 h->overflow_counts[bi] += 1;
418 uword dl = round_pow2 (1 + i - l, 8);
419 v = _vec_resize (v, dl, (l + dl) * elt_bytes, sizeof (h[0]),
420 /* align */ sizeof (uword));
421 clib_memset (v + l * elt_bytes, ~0, dl * elt_bytes);
431 qhash_unset_overflow (void *v, uword key, uword bi, uword * n_elts)
433 qhash_t *h = qhash_header (v);
434 uword *p = hash_get (h->overflow_hash, key);
437 bi /= QHASH_KEYS_PER_BUCKET;
442 hash_unset (h->overflow_hash, key);
443 ASSERT (bi < vec_len (h->overflow_counts));
444 ASSERT (h->overflow_counts[bi] > 0);
445 ASSERT (*n_elts > 0);
446 vec_add1 (h->overflow_free_indices, result);
447 h->overflow_counts[bi] -= 1;
457 qhash_find_free (uword i, uword valid_mask)
459 return first_set (~valid_mask & pow2_mask (QHASH_KEYS_PER_BUCKET));
463 _qhash_set_multiple (void *v,
466 uword n_search_keys, u32 * result_indices)
468 qhash_t *h = qhash_header (v);
469 uword *k, *hash_keys;
470 uword n_left, n_elts, bucket_mask;
473 if (vec_len (v) < n_search_keys)
474 v = _qhash_resize (v, n_search_keys, elt_bytes);
476 if (qhash_min_log2 (2) != 1)
478 qhash_min_log2_init ();
479 ASSERT (qhash_min_log2 (2) == 1);
484 bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
486 hash_keys = h->hash_keys;
489 n_left = n_search_keys;
494 u32 a0, b0, c0, bi0, match0, valid0, free0;
495 u32 a1, b1, c1, bi1, match1, valid1, free1;
502 /* Keys must be unique. */
508 a0 = a1 = h->hash_seeds[0];
509 b0 = b1 = h->hash_seeds[1];
510 c0 = c1 = h->hash_seeds[2];
518 hash_mix32_step_1 (a0, b0, c0);
519 hash_mix32_step_1 (a1, b1, c1);
520 hash_mix32_step_2 (a0, b0, c0);
521 hash_mix32_step_2 (a1, b1, c1);
522 hash_mix32_step_3 (a0, b0, c0);
523 hash_mix32_step_3 (a1, b1, c1);
525 bi0 = c0 & bucket_mask;
526 bi1 = c1 & bucket_mask;
528 h0 = hash_keys + bi0;
529 h1 = hash_keys + bi1;
531 /* Search two buckets. */
532 valid0 = qhash_get_valid_elt_mask (h, bi0);
533 valid1 = qhash_get_valid_elt_mask (h, bi1);
535 match0 = qhash_search_bucket (h0, k0, valid0);
536 match1 = qhash_search_bucket (h1, k1, valid1);
538 /* Find first free element starting at hash offset into bucket. */
539 free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
541 valid1 = valid1 | (bi0 == bi1 ? free0 : 0);
542 free1 = qhash_find_free (c1 & (QHASH_KEYS_PER_BUCKET - 1), valid1);
544 n_elts += (match0 == 0) + (match1 == 0);
546 match0 = match0 ? match0 : free0;
547 match1 = match1 ? match1 : free1;
552 h0 += qhash_min_log2 (match0);
553 h1 += qhash_min_log2 (match1);
555 if (PREDICT_FALSE (!match0 || !match1))
560 r[0] = h0 - hash_keys;
561 r[1] = h1 - hash_keys;
563 qhash_set_valid_elt_mask (h, bi0, valid0);
564 qhash_set_valid_elt_mask (h, bi1, valid1);
571 v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
576 r[0] = h0 - hash_keys;
577 qhash_set_valid_elt_mask (h, bi0, valid0);
582 v = qhash_set_overflow (v, elt_bytes, k1, bi1, &n_elts, &r[1]);
587 r[1] = h1 - hash_keys;
588 qhash_set_valid_elt_mask (h, bi1, valid1);
595 u32 a0, b0, c0, bi0, match0, valid0, free0;
602 a0 = h->hash_seeds[0];
603 b0 = h->hash_seeds[1];
604 c0 = h->hash_seeds[2];
610 hash_mix32 (a0, b0, c0);
612 bi0 = c0 & bucket_mask;
614 h0 = hash_keys + bi0;
616 valid0 = qhash_get_valid_elt_mask (h, bi0);
618 /* Find first free element starting at hash offset into bucket. */
619 free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
621 match0 = qhash_search_bucket (h0, k0, valid0);
623 n_elts += (match0 == 0);
625 match0 = match0 ? match0 : free0;
629 h0 += qhash_min_log2 (match0);
631 if (PREDICT_FALSE (!match0))
635 r[0] = h0 - hash_keys;
637 qhash_set_valid_elt_mask (h, bi0, valid0);
642 v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
646 h = qhash_header (v);
653 unset_slow_path (void *v, uword elt_bytes,
654 uword k0, uword bi0, uword valid0, uword match0,
657 qhash_t *h = qhash_header (v);
658 uword i, j = 0, k, l, t = ~0;
659 hash_pair_t *p, *found;
663 if (valid0 == QHASH_ALL_VALID)
664 t = qhash_unset_overflow (v, k0, bi0, n_elts);
668 i = bi0 / QHASH_KEYS_PER_BUCKET;
669 t = bi0 + qhash_min_log2 (match0);
671 if (valid0 == QHASH_ALL_VALID
672 && i < vec_len (h->overflow_counts) && h->overflow_counts[i] > 0)
676 hash_foreach_pair (p, h->overflow_hash, ({
677 j = qhash_hash_mix (h, p->key) / QHASH_KEYS_PER_BUCKET;
690 hash_unset3 (h->overflow_hash, k, &j);
691 vec_add1 (h->overflow_free_indices, j);
692 h->overflow_counts[i] -= 1;
694 qhash_set_valid_elt_mask (h, bi0, valid0);
697 clib_memswap (v + t * elt_bytes, v + l * elt_bytes, elt_bytes);
701 qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
707 _qhash_unset_multiple (void *v,
710 uword n_search_keys, u32 * result_indices)
712 qhash_t *h = qhash_header (v);
713 uword *k, *hash_keys;
714 uword n_left, n_elts, bucket_mask;
720 for (i = 0; i < n_search_keys; i++)
721 result_indices[i] = ~0;
724 bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
726 hash_keys = h->hash_keys;
729 n_left = n_search_keys;
734 u32 a0, b0, c0, bi0, match0, valid0;
735 u32 a1, b1, c1, bi1, match1, valid1;
742 /* Keys must be unique. */
748 a0 = a1 = h->hash_seeds[0];
749 b0 = b1 = h->hash_seeds[1];
750 c0 = c1 = h->hash_seeds[2];
758 hash_mix32_step_1 (a0, b0, c0);
759 hash_mix32_step_1 (a1, b1, c1);
760 hash_mix32_step_2 (a0, b0, c0);
761 hash_mix32_step_2 (a1, b1, c1);
762 hash_mix32_step_3 (a0, b0, c0);
763 hash_mix32_step_3 (a1, b1, c1);
765 bi0 = c0 & bucket_mask;
766 bi1 = c1 & bucket_mask;
768 h0 = hash_keys + bi0;
769 h1 = hash_keys + bi1;
771 /* Search two buckets. */
772 valid0 = qhash_get_valid_elt_mask (h, bi0);
773 valid1 = qhash_get_valid_elt_mask (h, bi1);
775 match0 = qhash_search_bucket (h0, k0, valid0);
776 match1 = qhash_search_bucket (h1, k1, valid1);
778 n_elts -= (match0 != 0) + (match1 != 0);
780 if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID
781 || valid1 == QHASH_ALL_VALID))
785 qhash_set_valid_elt_mask (h, bi0, valid0);
787 valid1 = bi0 == bi1 ? valid0 : valid1;
790 qhash_set_valid_elt_mask (h, bi1, valid1);
792 r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
793 r[1] = match1 ? bi1 + qhash_min_log2 (match1) : ~0;
798 r[0] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0, &n_elts);
801 /* Search again in same bucket to test new overflow element. */
802 valid1 = qhash_get_valid_elt_mask (h, bi0);
805 match1 = qhash_search_bucket (h1, k1, valid1);
806 n_elts -= (match1 != 0);
809 r[1] = unset_slow_path (v, elt_bytes, k1, bi1, valid1, match1, &n_elts);
815 u32 a0, b0, c0, bi0, match0, valid0;
822 a0 = h->hash_seeds[0];
823 b0 = h->hash_seeds[1];
824 c0 = h->hash_seeds[2];
830 hash_mix32 (a0, b0, c0);
832 bi0 = c0 & bucket_mask;
834 h0 = hash_keys + bi0;
836 valid0 = qhash_get_valid_elt_mask (h, bi0);
838 match0 = qhash_search_bucket (h0, k0, valid0);
839 n_elts -= (match0 != 0);
840 qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
842 r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
845 if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID))
846 r[-1] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0,
854 * fd.io coding-style-patch-verification: ON
857 * eval: (c-set-style "gnu")