FD.io VPP  v16.06
Vector Packet Processing
qhash.c
Go to the documentation of this file.
1 /*
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:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
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.
14  */
15 /*
16  Copyright (c) 2006 Eliot Dresselhaus
17 
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:
25 
26  The above copyright notice and this permission notice shall be
27  included in all copies or substantial portions of the Software.
28 
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.
36 */
37 
38 #include <vppinfra/qhash.h>
39 
40 #define QHASH_ALL_VALID ((1 << QHASH_KEYS_PER_BUCKET) - 1)
41 
42 void *
43 _qhash_resize (void * v, uword length, uword elt_bytes)
44 {
45  qhash_t * h;
46  uword l;
47 
48  l = clib_max (max_log2 (length), 2 + QHASH_LOG2_KEYS_PER_BUCKET);
49 
50  /* Round up if less than 1/2 full. */
51  l += ((f64) length / (f64) (1 << l)) < .5;
52 
53  v = _vec_resize (0, 1 << l,
54  elt_bytes << l,
55  sizeof (h[0]),
56  /* align */ sizeof (uword));
57 
58  h = qhash_header (v);
59  h->n_elts = 0;
60  h->log2_hash_size = l;
61  h->hash_keys = clib_mem_alloc_aligned_no_fail (sizeof (h->hash_keys[0]) << l,
64  1 << (l - QHASH_LOG2_KEYS_PER_BUCKET));
65  memset (v, ~0, elt_bytes << l);
66 
67  return v;
68 }
69 
70 static u8 min_log2_table[256];
71 
72 static inline uword
74 {
75  ASSERT (is_pow2 (x));
76  ASSERT (x < 256);
77  return min_log2_table[x];
78 }
79 
80 static void qhash_min_log2_init ()
81 {
82  int i;
83  for (i = 0; i < 256; i++)
84  min_log2_table[i] = min_log2 (i);
85 }
86 
90 
91 always_inline void
94 
96 qhash_search_bucket (uword * hash_keys, uword search_key,
97  uword m)
98 {
99  uword t;
100 #define _(i) ((hash_keys[i] == search_key) << i)
101  t = (_ (0) | _ (1) | _ (2) | _ (3));
102  if (QHASH_KEYS_PER_BUCKET > 4)
103  t |= (_ (4) | _ (5) | _ (6) | _ (7));
104  if (QHASH_KEYS_PER_BUCKET > 8)
105  t |= (_ (8) | _ (9) | _ (10) | _ (11)
106  | _ (12) | _ (13) | _ (14) | _ (15));
107 #undef _
108  return m & t;
109 }
110 
111 /* Lookup multiple keys in the same hash table. */
112 void
114  uword * search_keys,
115  uword n_search_keys,
116  u32 * result_indices)
117 {
118  qhash_t * h = qhash_header (v);
119  uword * k, * hash_keys;
120  uword n_left, bucket_mask;
121  u32 * r;
122 
123  if (! v)
124  {
125  memset (result_indices, ~0, sizeof (result_indices[0]) * n_search_keys);
126  return;
127  }
128 
129  bucket_mask = pow2_mask (h->log2_hash_size) &~ (QHASH_KEYS_PER_BUCKET - 1);
130 
131  k = search_keys;
132  n_left = n_search_keys;
133  hash_keys = h->hash_keys;
134  r = result_indices;
135 
136  while (n_left >= 2)
137  {
138  u32 a0, b0, c0, bi0, valid0, match0;
139  u32 a1, b1, c1, bi1, valid1, match1;
140  uword k0, k1, * h0, * h1;
141 
142  k0 = k[0];
143  k1 = k[1];
144  n_left -= 2;
145  k += 2;
146 
147  a0 = a1 = h->hash_seeds[0];
148  b0 = b1 = h->hash_seeds[1];
149  c0 = c1 = h->hash_seeds[2];
150  a0 ^= k0;
151  a1 ^= k1;
152 #if uword_bits == 64
153  b0 ^= k0 >> 32;
154  b1 ^= k1 >> 32;
155 #endif
156 
157  hash_mix32_step_1 (a0, b0, c0);
158  hash_mix32_step_1 (a1, b1, c1);
159  hash_mix32_step_2 (a0, b0, c0);
160  hash_mix32_step_2 (a1, b1, c1);
161  hash_mix32_step_3 (a0, b0, c0);
162  hash_mix32_step_3 (a1, b1, c1);
163 
164  bi0 = c0 & bucket_mask;
165  bi1 = c1 & bucket_mask;
166 
167  h0 = hash_keys + bi0;
168  h1 = hash_keys + bi1;
169 
170  /* Search two buckets. */
171  valid0 = qhash_get_valid_elt_mask (h, bi0);
172  valid1 = qhash_get_valid_elt_mask (h, bi1);
173 
174  match0 = qhash_search_bucket (h0, k0, valid0);
175  match1 = qhash_search_bucket (h1, k1, valid1);
176 
177  bi0 += qhash_min_log2 (match0);
178  bi1 += qhash_min_log2 (match1);
179 
180  r[0] = match0 ? bi0 : ~0;
181  r[1] = match1 ? bi1 : ~0;
182  r += 2;
183 
184  /* Full buckets trigger search of overflow hash. */
185  if (PREDICT_FALSE (! match0 && valid0 == QHASH_ALL_VALID))
186  {
187  uword * p = hash_get (h->overflow_hash, k0);
188  r[-2] = p ? p[0] : ~0;
189  }
190 
191  /* Full buckets trigger search of overflow hash. */
192  if (PREDICT_FALSE (! match1 && valid1 == QHASH_ALL_VALID))
193  {
194  uword * p = hash_get (h->overflow_hash, k1);
195  r[-1] = p ? p[0] : ~0;
196  }
197  }
198 
199  while (n_left >= 1)
200  {
201  u32 a0, b0, c0, bi0, valid0, match0;
202  uword k0, * h0;
203 
204  k0 = k[0];
205  n_left -= 1;
206  k += 1;
207 
208  a0 = h->hash_seeds[0];
209  b0 = h->hash_seeds[1];
210  c0 = h->hash_seeds[2];
211  a0 ^= k0;
212 #if uword_bits == 64
213  b0 ^= k0 >> 32;
214 #endif
215 
216  hash_mix32 (a0, b0, c0);
217 
218  bi0 = c0 & bucket_mask;
219 
220  h0 = hash_keys + bi0;
221 
222  /* Search one bucket. */
223  valid0 = qhash_get_valid_elt_mask (h, bi0);
224  match0 = qhash_search_bucket (h0, k0, valid0);
225 
226  bi0 += qhash_min_log2 (match0);
227 
228  r[0] = match0 ? bi0 : ~0;
229  r += 1;
230 
231  /* Full buckets trigger search of overflow hash. */
232  if (PREDICT_FALSE (! match0 && valid0 == QHASH_ALL_VALID))
233  {
234  uword * p = hash_get (h->overflow_hash, k0);
235  r[-1] = p ? p[0] : ~0;
236  }
237  }
238 }
239 
240 /* Lookup multiple keys in the same hash table.
241  Returns index of first matching key. */
242 u32
244  uword * search_keys,
245  uword n_search_keys,
246  uword * matching_key)
247 {
248  qhash_t * h = qhash_header (v);
249  uword * k, * hash_keys;
250  uword n_left, match_mask, bucket_mask;
251 
252  if (! v)
253  return ~0;
254 
255  match_mask = 0;
256  bucket_mask = pow2_mask (h->log2_hash_size) &~ (QHASH_KEYS_PER_BUCKET - 1);
257 
258  k = search_keys;
259  n_left = n_search_keys;
260  hash_keys = h->hash_keys;
261  while (n_left >= 2)
262  {
263  u32 a0, b0, c0, bi0, valid0;
264  u32 a1, b1, c1, bi1, valid1;
265  uword k0, k1, * h0, * h1;
266 
267  k0 = k[0];
268  k1 = k[1];
269  n_left -= 2;
270  k += 2;
271 
272  a0 = a1 = h->hash_seeds[0];
273  b0 = b1 = h->hash_seeds[1];
274  c0 = c1 = h->hash_seeds[2];
275  a0 ^= k0;
276  a1 ^= k1;
277 #if uword_bits == 64
278  b0 ^= k0 >> 32;
279  b1 ^= k1 >> 32;
280 #endif
281 
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);
288 
289  bi0 = c0 & bucket_mask;
290  bi1 = c1 & bucket_mask;
291 
292  h0 = hash_keys + bi0;
293  h1 = hash_keys + bi1;
294 
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)
301  if (match_mask)
302  {
303  uword bi, is_match1;
304 
305  bi = qhash_min_log2 (match_mask);
306  is_match1 = bi >= QHASH_KEYS_PER_BUCKET;
307 
308  bi += ((is_match1 ? bi1 : bi0)
309  - (is_match1 << QHASH_LOG2_KEYS_PER_BUCKET));
310  *matching_key = (k - 2 - search_keys) + is_match1;
311  return bi;
312  }
313 
314  /* Full buckets trigger search of overflow hash. */
315  if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID
316  || valid1 == QHASH_ALL_VALID))
317  {
318  uword * p = 0;
319  uword ki = k - 2 - search_keys;
320 
321  if (valid0 == QHASH_ALL_VALID)
322  p = hash_get (h->overflow_hash, k0);
323 
324  if (! p && valid1 == QHASH_ALL_VALID)
325  {
326  p = hash_get (h->overflow_hash, k1);
327  ki++;
328  }
329 
330  if (p)
331  {
332  *matching_key = ki;
333  return p[0];
334  }
335  }
336  }
337 
338  while (n_left >= 1)
339  {
340  u32 a0, b0, c0, bi0, valid0;
341  uword k0, * h0;
342 
343  k0 = k[0];
344  n_left -= 1;
345  k += 1;
346 
347  a0 = h->hash_seeds[0];
348  b0 = h->hash_seeds[1];
349  c0 = h->hash_seeds[2];
350  a0 ^= k0;
351 #if uword_bits == 64
352  b0 ^= k0 >> 32;
353 #endif
354 
355  hash_mix32 (a0, b0, c0);
356 
357  bi0 = c0 & bucket_mask;
358 
359  h0 = hash_keys + bi0;
360 
361  /* Search one bucket. */
362  valid0 = qhash_get_valid_elt_mask (h, bi0);
363  match_mask = qhash_search_bucket (h0, k0, valid0);
364  if (match_mask)
365  {
366  uword bi;
367  bi = bi0 + qhash_min_log2 (match_mask);
368  *matching_key = (k - 1 - search_keys);
369  return bi;
370  }
371 
372  /* Full buckets trigger search of overflow hash. */
373  if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID))
374  {
375  uword * p = hash_get (h->overflow_hash, k0);
376  if (p)
377  {
378  *matching_key = (k - 1 - search_keys);
379  return p[0];
380  }
381  }
382  }
383 
384  return ~0;
385 }
386 
387 static void *
388 qhash_set_overflow (void * v, uword elt_bytes,
389  uword key, uword bi,
390  uword * n_elts,
391  u32 * result)
392 {
393  qhash_t * h = qhash_header (v);
394  uword * p = hash_get (h->overflow_hash, key);
395  uword i;
396 
397  bi /= QHASH_KEYS_PER_BUCKET;
398 
399  if (p)
400  i = p[0];
401  else
402  {
404  if (l > 0)
405  {
406  i = h->overflow_free_indices[l - 1];
407  _vec_len (h->overflow_free_indices) = l - 1;
408  }
409  else
410  i = (1 << h->log2_hash_size) + hash_elts (h->overflow_hash);
411  hash_set (h->overflow_hash, key, i);
412  vec_validate (h->overflow_counts, bi);
413  h->overflow_counts[bi] += 1;
414  *n_elts += 1;
415 
416  l = vec_len (v);
417  if (i >= l)
418  {
419  uword dl = round_pow2 (1 + i - l, 8);
420  v = _vec_resize (v, dl,
421  (l + dl) * elt_bytes,
422  sizeof (h[0]),
423  /* align */ sizeof (uword));
424  memset (v + l*elt_bytes, ~0, dl * elt_bytes);
425  }
426  }
427 
428  *result = i;
429 
430  return v;
431 }
432 
433 static uword
434 qhash_unset_overflow (void * v, uword key, uword bi, uword * n_elts)
435 {
436  qhash_t * h = qhash_header (v);
437  uword * p = hash_get (h->overflow_hash, key);
438  uword result;
439 
440  bi /= QHASH_KEYS_PER_BUCKET;
441 
442  if (p)
443  {
444  result = p[0];
445  hash_unset (h->overflow_hash, key);
446  ASSERT (bi < vec_len (h->overflow_counts));
447  ASSERT (h->overflow_counts[bi] > 0);
448  ASSERT (*n_elts > 0);
449  vec_add1 (h->overflow_free_indices, result);
450  h->overflow_counts[bi] -= 1;
451  *n_elts -= 1;
452  }
453  else
454  result = ~0;
455 
456  return result;
457 }
458 
461 { return first_set (~valid_mask & pow2_mask (QHASH_KEYS_PER_BUCKET)); }
462 
463 void *
464 _qhash_set_multiple (void * v,
465  uword elt_bytes,
466  uword * search_keys,
467  uword n_search_keys,
468  u32 * result_indices)
469 {
470  qhash_t * h = qhash_header (v);
471  uword * k, * hash_keys;
472  uword n_left, n_elts, bucket_mask;
473  u32 * r;
474 
475  if (vec_len (v) < n_search_keys)
476  v = _qhash_resize (v, n_search_keys, elt_bytes);
477 
478  if (qhash_min_log2 (2) != 1)
479  {
481  ASSERT (qhash_min_log2 (2) == 1);
482  }
483 
484  ASSERT (v != 0);
485 
486  bucket_mask = pow2_mask (h->log2_hash_size) &~ (QHASH_KEYS_PER_BUCKET - 1);
487 
488  hash_keys = h->hash_keys;
489  k = search_keys;
490  r = result_indices;
491  n_left = n_search_keys;
492  n_elts = h->n_elts;
493 
494  while (n_left >= 2)
495  {
496  u32 a0, b0, c0, bi0, match0, valid0, free0;
497  u32 a1, b1, c1, bi1, match1, valid1, free1;
498  uword k0, * h0;
499  uword k1, * h1;
500 
501  k0 = k[0];
502  k1 = k[1];
503 
504  /* Keys must be unique. */
505  ASSERT (k0 != k1);
506 
507  n_left -= 2;
508  k += 2;
509 
510  a0 = a1 = h->hash_seeds[0];
511  b0 = b1 = h->hash_seeds[1];
512  c0 = c1 = h->hash_seeds[2];
513  a0 ^= k0;
514  a1 ^= k1;
515 #if uword_bits == 64
516  b0 ^= k0 >> 32;
517  b1 ^= k1 >> 32;
518 #endif
519 
520  hash_mix32_step_1 (a0, b0, c0);
521  hash_mix32_step_1 (a1, b1, c1);
522  hash_mix32_step_2 (a0, b0, c0);
523  hash_mix32_step_2 (a1, b1, c1);
524  hash_mix32_step_3 (a0, b0, c0);
525  hash_mix32_step_3 (a1, b1, c1);
526 
527  bi0 = c0 & bucket_mask;
528  bi1 = c1 & bucket_mask;
529 
530  h0 = hash_keys + bi0;
531  h1 = hash_keys + bi1;
532 
533  /* Search two buckets. */
534  valid0 = qhash_get_valid_elt_mask (h, bi0);
535  valid1 = qhash_get_valid_elt_mask (h, bi1);
536 
537  match0 = qhash_search_bucket (h0, k0, valid0);
538  match1 = qhash_search_bucket (h1, k1, valid1);
539 
540  /* Find first free element starting at hash offset into bucket. */
541  free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
542 
543  valid1 = valid1 | (bi0 == bi1 ? free0 : 0);
544  free1 = qhash_find_free (c1 & (QHASH_KEYS_PER_BUCKET - 1), valid1);
545 
546  n_elts += (match0 == 0) + (match1 == 0);
547 
548  match0 = match0 ? match0 : free0;
549  match1 = match1 ? match1 : free1;
550 
551  valid0 |= match0;
552  valid1 |= match1;
553 
554  h0 += qhash_min_log2 (match0);
555  h1 += qhash_min_log2 (match1);
556 
557  if (PREDICT_FALSE (! match0 || ! match1))
558  goto slow_path2;
559 
560  h0[0] = k0;
561  h1[0] = k1;
562  r[0] = h0 - hash_keys;
563  r[1] = h1 - hash_keys;
564  r += 2;
565  qhash_set_valid_elt_mask (h, bi0, valid0);
566  qhash_set_valid_elt_mask (h, bi1, valid1);
567  continue;
568 
569  slow_path2:
570  if (! match0)
571  {
572  n_elts -= 1;
573  v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
574  }
575  else
576  {
577  h0[0] = k0;
578  r[0] = h0 - hash_keys;
579  qhash_set_valid_elt_mask (h, bi0, valid0);
580  }
581  if (! match1)
582  {
583  n_elts -= 1;
584  v = qhash_set_overflow (v, elt_bytes, k1, bi1, &n_elts, &r[1]);
585  }
586  else
587  {
588  h1[0] = k1;
589  r[1] = h1 - hash_keys;
590  qhash_set_valid_elt_mask (h, bi1, valid1);
591  }
592  r += 2;
593  }
594 
595  while (n_left >= 1)
596  {
597  u32 a0, b0, c0, bi0, match0, valid0, free0;
598  uword k0, * h0;
599 
600  k0 = k[0];
601  n_left -= 1;
602  k += 1;
603 
604  a0 = h->hash_seeds[0];
605  b0 = h->hash_seeds[1];
606  c0 = h->hash_seeds[2];
607  a0 ^= k0;
608 #if uword_bits == 64
609  b0 ^= k0 >> 32;
610 #endif
611 
612  hash_mix32 (a0, b0, c0);
613 
614  bi0 = c0 & bucket_mask;
615 
616  h0 = hash_keys + bi0;
617 
618  valid0 = qhash_get_valid_elt_mask (h, bi0);
619 
620  /* Find first free element starting at hash offset into bucket. */
621  free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
622 
623  match0 = qhash_search_bucket (h0, k0, valid0);
624 
625  n_elts += (match0 == 0);
626 
627  match0 = match0 ? match0 : free0;
628 
629  valid0 |= match0;
630 
631  h0 += qhash_min_log2 (match0);
632 
633  if (PREDICT_FALSE (! match0))
634  goto slow_path1;
635 
636  h0[0] = k0;
637  r[0] = h0 - hash_keys;
638  r += 1;
639  qhash_set_valid_elt_mask (h, bi0, valid0);
640  continue;
641 
642  slow_path1:
643  n_elts -= 1;
644  v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
645  r += 1;
646  }
647 
648  h = qhash_header (v);
649  h->n_elts = n_elts;
650 
651  return v;
652 }
653 
654 static uword
655 unset_slow_path (void * v, uword elt_bytes,
656  uword k0, uword bi0, uword valid0, uword match0,
657  uword * n_elts)
658 {
659  qhash_t * h = qhash_header (v);
660  uword i, j = 0, k, l, t = ~0;
661  hash_pair_t * p, * found;
662 
663  if (! match0)
664  {
665  if (valid0 == QHASH_ALL_VALID)
666  t = qhash_unset_overflow (v, k0, bi0, n_elts);
667  return t;
668  }
669 
670  i = bi0 / QHASH_KEYS_PER_BUCKET;
671  t = bi0 + qhash_min_log2 (match0);
672 
673  if (valid0 == QHASH_ALL_VALID
674  && i < vec_len (h->overflow_counts)
675  && h->overflow_counts[i] > 0)
676  {
677  found = 0;
679  j = qhash_hash_mix (h, p->key) / QHASH_KEYS_PER_BUCKET;
680  if (j == i)
681  {
682  found = p;
683  break;
684  }
685  }));
686  ASSERT (found != 0);
687  ASSERT (j == i);
688 
689  l = found->value[0];
690  k = found->key;
691  hash_unset3 (h->overflow_hash, k, &j);
693  h->overflow_counts[i] -= 1;
694 
695  qhash_set_valid_elt_mask (h, bi0, valid0);
696 
697  h->hash_keys[t] = k;
698  clib_memswap (v + t*elt_bytes,
699  v + l*elt_bytes,
700  elt_bytes);
701  t = l;
702  }
703  else
704  qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
705 
706  return t;
707 }
708 
709 void
710 _qhash_unset_multiple (void * v,
711  uword elt_bytes,
712  uword * search_keys,
713  uword n_search_keys,
714  u32 * result_indices)
715 {
716  qhash_t * h = qhash_header (v);
717  uword * k, * hash_keys;
718  uword n_left, n_elts, bucket_mask;
719  u32 * r;
720 
721  if (! v)
722  {
723  uword i;
724  for (i = 0; i < n_search_keys; i++)
725  result_indices[i] = ~0;
726  }
727 
728  bucket_mask = pow2_mask (h->log2_hash_size) &~ (QHASH_KEYS_PER_BUCKET - 1);
729 
730  hash_keys = h->hash_keys;
731  k = search_keys;
732  r = result_indices;
733  n_left = n_search_keys;
734  n_elts = h->n_elts;
735 
736  while (n_left >= 2)
737  {
738  u32 a0, b0, c0, bi0, match0, valid0;
739  u32 a1, b1, c1, bi1, match1, valid1;
740  uword k0, * h0;
741  uword k1, * h1;
742 
743  k0 = k[0];
744  k1 = k[1];
745 
746  /* Keys must be unique. */
747  ASSERT (k0 != k1);
748 
749  n_left -= 2;
750  k += 2;
751 
752  a0 = a1 = h->hash_seeds[0];
753  b0 = b1 = h->hash_seeds[1];
754  c0 = c1 = h->hash_seeds[2];
755  a0 ^= k0;
756  a1 ^= k1;
757 #if uword_bits == 64
758  b0 ^= k0 >> 32;
759  b1 ^= k1 >> 32;
760 #endif
761 
762  hash_mix32_step_1 (a0, b0, c0);
763  hash_mix32_step_1 (a1, b1, c1);
764  hash_mix32_step_2 (a0, b0, c0);
765  hash_mix32_step_2 (a1, b1, c1);
766  hash_mix32_step_3 (a0, b0, c0);
767  hash_mix32_step_3 (a1, b1, c1);
768 
769  bi0 = c0 & bucket_mask;
770  bi1 = c1 & bucket_mask;
771 
772  h0 = hash_keys + bi0;
773  h1 = hash_keys + bi1;
774 
775  /* Search two buckets. */
776  valid0 = qhash_get_valid_elt_mask (h, bi0);
777  valid1 = qhash_get_valid_elt_mask (h, bi1);
778 
779  match0 = qhash_search_bucket (h0, k0, valid0);
780  match1 = qhash_search_bucket (h1, k1, valid1);
781 
782  n_elts -= (match0 != 0) + (match1 != 0);
783 
784  if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID
785  || valid1 == QHASH_ALL_VALID))
786  goto slow_path2;
787 
788  valid0 ^= match0;
789  qhash_set_valid_elt_mask (h, bi0, valid0);
790 
791  valid1 = bi0 == bi1 ? valid0 : valid1;
792  valid1 ^= match1;
793 
794  qhash_set_valid_elt_mask (h, bi1, valid1);
795 
796  r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
797  r[1] = match1 ? bi1 + qhash_min_log2 (match1) : ~0;
798  r += 2;
799  continue;
800 
801  slow_path2:
802  r[0] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0,
803  &n_elts);
804  if (bi0 == bi1)
805  {
806  /* Search again in same bucket to test new overflow element. */
807  valid1 = qhash_get_valid_elt_mask (h, bi0);
808  if (! match1)
809  {
810  match1 = qhash_search_bucket (h1, k1, valid1);
811  n_elts -= (match1 != 0);
812  }
813  }
814  r[1] = unset_slow_path (v, elt_bytes, k1, bi1, valid1, match1,
815  &n_elts);
816  r += 2;
817  }
818 
819  while (n_left >= 1)
820  {
821  u32 a0, b0, c0, bi0, match0, valid0;
822  uword k0, * h0;
823 
824  k0 = k[0];
825  n_left -= 1;
826  k += 1;
827 
828  a0 = h->hash_seeds[0];
829  b0 = h->hash_seeds[1];
830  c0 = h->hash_seeds[2];
831  a0 ^= k0;
832 #if uword_bits == 64
833  b0 ^= k0 >> 32;
834 #endif
835 
836  hash_mix32 (a0, b0, c0);
837 
838  bi0 = c0 & bucket_mask;
839 
840  h0 = hash_keys + bi0;
841 
842  valid0 = qhash_get_valid_elt_mask (h, bi0);
843 
844  match0 = qhash_search_bucket (h0, k0, valid0);
845  n_elts -= (match0 != 0);
846  qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
847 
848  r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
849  r += 1;
850 
851  if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID))
852  r[-1] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0,
853  &n_elts);
854  }
855 
856  h->n_elts = n_elts;
857 }
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:394
void clib_memswap(void *_a, void *_b, uword bytes)
Definition: string.c:42
always_inline uword round_pow2(uword x, uword pow2)
Definition: clib.h:255
#define hash_set(h, key, value)
Definition: hash.h:237
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:267
#define hash_unset(h, key)
Definition: hash.h:243
static void qhash_min_log2_init()
Definition: qhash.c:80
u32 n_elts
Definition: qhash.h:47
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:480
#define QHASH_KEYS_PER_BUCKET
Definition: qhash.h:77
always_inline uword max_log2(uword x)
Definition: clib.h:216
u32 * overflow_counts
Definition: qhash.h:57
uword value[0]
Definition: hash.h:151
always_inline uword qhash_get_valid_elt_mask(qhash_t *h, uword i)
Definition: qhash.c:88
always_inline qhash_t * qhash_header(void *v)
Definition: qhash.h:65
static uword qhash_unset_overflow(void *v, uword key, uword bi, uword *n_elts)
Definition: qhash.c:434
always_inline uword first_set(uword x)
Definition: clib.h:265
#define always_inline
Definition: clib.h:84
#define vec_resize(V, N)
Resize a vector (no header, unspecified alignment) Add N elements to end of given vector V...
Definition: vec.h:199
u32 log2_hash_size
Definition: qhash.h:49
static uword unset_slow_path(void *v, uword elt_bytes, uword k0, uword bi0, uword valid0, uword match0, uword *n_elts)
Definition: qhash.c:655
static void * qhash_set_overflow(void *v, uword elt_bytes, uword key, uword bi, uword *n_elts, u32 *result)
Definition: qhash.c:388
#define hash_get(h, key)
Definition: hash.h:231
always_inline uword qhash_search_bucket(uword *hash_keys, uword search_key, uword m)
Definition: qhash.c:96
uword * overflow_hash
Definition: qhash.h:55
#define PREDICT_FALSE(x)
Definition: clib.h:97
#define QHASH_ALL_VALID
Definition: qhash.c:40
always_inline void qhash_set_valid_elt_mask(qhash_t *h, uword i, uword mask)
Definition: qhash.c:92
#define hash_mix32(a0, b0, c0)
Definition: hash.h:474
always_inline uword hash_elts(void *v)
Definition: hash.h:111
always_inline uword is_pow2(uword x)
Definition: clib.h:252
always_inline uword qhash_find_free(uword i, uword valid_mask)
Definition: qhash.c:460
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
static uword qhash_min_log2(uword x)
Definition: qhash.c:73
u32 hash_seeds[3]
Definition: qhash.h:52
#define QHASH_LOG2_KEYS_PER_BUCKET
Definition: qhash.h:76
#define clib_max(x, y)
Definition: clib.h:288
void qhash_get_multiple(void *v, uword *search_keys, uword n_search_keys, u32 *result_indices)
Definition: qhash.c:113
u64 uword
Definition: types.h:112
#define clib_mem_alloc_aligned_no_fail(size, align)
Definition: mem.h:118
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
double f64
Definition: types.h:140
static u8 min_log2_table[256]
Definition: qhash.c:70
unsigned char u8
Definition: types.h:56
#define hash_foreach_pair(p, v, body)
Definition: hash.h:311
Definition: qhash.h:45
uword * hash_keys
Definition: qhash.h:61
#define hash_mix32_step_1(a, b, c)
Definition: hash.h:455
u32 qhash_get_first_match(void *v, uword *search_keys, uword n_search_keys, uword *matching_key)
Definition: qhash.c:243
always_inline uword min_log2(uword x)
Definition: clib.h:181
#define hash_mix32_step_2(a, b, c)
Definition: hash.h:456
always_inline uword pow2_mask(uword x)
Definition: clib.h:242
#define hash_mix32_step_3(a, b, c)
Definition: hash.h:457
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:67
u32 * overflow_free_indices
Definition: qhash.h:57
uword key
Definition: hash.h:148
#define hash_unset3(h, key, old_value)
Definition: hash.h:246
u8 * hash_key_valid_bitmap
Definition: qhash.h:59