vppinfra/vppinfra/qhash.c

   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, elt_bytes << l, sizeof (h[0]),
  54                    /* align */ sizeof (uword));
  55
  56   h = qhash_header (v);
  57   h->n_elts = 0;
  58   h->log2_hash_size = l;
  59   h->hash_keys =
  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);
  65
  66   return v;
  67 }
  68
  69 static u8 min_log2_table[256];
  70
  71 static inline uword
  72 qhash_min_log2 (uword x)
  73 {
  74   ASSERT (is_pow2 (x));
  75   ASSERT (x < 256);
  76   return min_log2_table[x];
  77 }
  78
  79 static void
  80 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
  87 always_inline uword
  88 qhash_get_valid_elt_mask (qhash_t * h, uword i)
  89 {
  90   return h->hash_key_valid_bitmap[i / QHASH_KEYS_PER_BUCKET];
  91 }
  92
  93 always_inline void
  94 qhash_set_valid_elt_mask (qhash_t * h, uword i, uword mask)
  95 {
  96   h->hash_key_valid_bitmap[i / QHASH_KEYS_PER_BUCKET] = mask;
  97 }
  98
  99 always_inline uword
 100 qhash_search_bucket (uword * hash_keys, uword search_key, uword m)
 101 {
 102   uword t;
 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));
 109 #undef _
 110   return m & t;
 111 }
 112
 113 /* Lookup multiple keys in the same hash table. */
 114 void
 115 qhash_get_multiple (void *v,
 116                     uword * search_keys,
 117                     uword n_search_keys, u32 * result_indices)
 118 {
 119   qhash_t *h = qhash_header (v);
 120   uword *k, *hash_keys;
 121   uword n_left, bucket_mask;
 122   u32 *r;
 123
 124   if (!v)
 125     {
 126       memset (result_indices, ~0, sizeof (result_indices[0]) * n_search_keys);
 127       return;
 128     }
 129
 130   bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
 131
 132   k = search_keys;
 133   n_left = n_search_keys;
 134   hash_keys = h->hash_keys;
 135   r = result_indices;
 136
 137   while (n_left >= 2)
 138     {
 139       u32 a0, b0, c0, bi0, valid0, match0;
 140       u32 a1, b1, c1, bi1, valid1, match1;
 141       uword k0, k1, *h0, *h1;
 142
 143       k0 = k[0];
 144       k1 = k[1];
 145       n_left -= 2;
 146       k += 2;
 147
 148       a0 = a1 = h->hash_seeds[0];
 149       b0 = b1 = h->hash_seeds[1];
 150       c0 = c1 = h->hash_seeds[2];
 151       a0 ^= k0;
 152       a1 ^= k1;
 153 #if uword_bits == 64
 154       b0 ^= k0 >> 32;
 155       b1 ^= k1 >> 32;
 156 #endif
 157
 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);
 164
 165       bi0 = c0 & bucket_mask;
 166       bi1 = c1 & bucket_mask;
 167
 168       h0 = hash_keys + bi0;
 169       h1 = hash_keys + bi1;
 170
 171       /* Search two buckets. */
 172       valid0 = qhash_get_valid_elt_mask (h, bi0);
 173       valid1 = qhash_get_valid_elt_mask (h, bi1);
 174
 175       match0 = qhash_search_bucket (h0, k0, valid0);
 176       match1 = qhash_search_bucket (h1, k1, valid1);
 177
 178       bi0 += qhash_min_log2 (match0);
 179       bi1 += qhash_min_log2 (match1);
 180
 181       r[0] = match0 ? bi0 : ~0;
 182       r[1] = match1 ? bi1 : ~0;
 183       r += 2;
 184
 185       /* Full buckets trigger search of overflow hash. */
 186       if (PREDICT_FALSE (!match0 && valid0 == QHASH_ALL_VALID))
 187         {
 188           uword *p = hash_get (h->overflow_hash, k0);
 189           r[-2] = p ? p[0] : ~0;
 190         }
 191
 192       /* Full buckets trigger search of overflow hash. */
 193       if (PREDICT_FALSE (!match1 && valid1 == QHASH_ALL_VALID))
 194         {
 195           uword *p = hash_get (h->overflow_hash, k1);
 196           r[-1] = p ? p[0] : ~0;
 197         }
 198     }
 199
 200   while (n_left >= 1)
 201     {
 202       u32 a0, b0, c0, bi0, valid0, match0;
 203       uword k0, *h0;
 204
 205       k0 = k[0];
 206       n_left -= 1;
 207       k += 1;
 208
 209       a0 = h->hash_seeds[0];
 210       b0 = h->hash_seeds[1];
 211       c0 = h->hash_seeds[2];
 212       a0 ^= k0;
 213 #if uword_bits == 64
 214       b0 ^= k0 >> 32;
 215 #endif
 216
 217       hash_mix32 (a0, b0, c0);
 218
 219       bi0 = c0 & bucket_mask;
 220
 221       h0 = hash_keys + bi0;
 222
 223       /* Search one bucket. */
 224       valid0 = qhash_get_valid_elt_mask (h, bi0);
 225       match0 = qhash_search_bucket (h0, k0, valid0);
 226
 227       bi0 += qhash_min_log2 (match0);
 228
 229       r[0] = match0 ? bi0 : ~0;
 230       r += 1;
 231
 232       /* Full buckets trigger search of overflow hash. */
 233       if (PREDICT_FALSE (!match0 && valid0 == QHASH_ALL_VALID))
 234         {
 235           uword *p = hash_get (h->overflow_hash, k0);
 236           r[-1] = p ? p[0] : ~0;
 237         }
 238     }
 239 }
 240
 241 /* Lookup multiple keys in the same hash table.
 242    Returns index of first matching key. */
 243 u32
 244 qhash_get_first_match (void *v,
 245                        uword * search_keys,
 246                        uword n_search_keys, 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)
 300                      << QHASH_KEYS_PER_BUCKET);
 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, uword * n_elts, u32 * result)
 390 {
 391   qhash_t *h = qhash_header (v);
 392   uword *p = hash_get (h->overflow_hash, key);
 393   uword i;
 394
 395   bi /= QHASH_KEYS_PER_BUCKET;
 396
 397   if (p)
 398     i = p[0];
 399   else
 400     {
 401       uword l = vec_len (h->overflow_free_indices);
 402       if (l > 0)
 403         {
 404           i = h->overflow_free_indices[l - 1];
 405           _vec_len (h->overflow_free_indices) = l - 1;
 406         }
 407       else
 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;
 412       *n_elts += 1;
 413
 414       l = vec_len (v);
 415       if (i >= l)
 416         {
 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);
 421         }
 422     }
 423
 424   *result = i;
 425
 426   return v;
 427 }
 428
 429 static uword
 430 qhash_unset_overflow (void *v, uword key, uword bi, uword * n_elts)
 431 {
 432   qhash_t *h = qhash_header (v);
 433   uword *p = hash_get (h->overflow_hash, key);
 434   uword result;
 435
 436   bi /= QHASH_KEYS_PER_BUCKET;
 437
 438   if (p)
 439     {
 440       result = p[0];
 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;
 447       *n_elts -= 1;
 448     }
 449   else
 450     result = ~0;
 451
 452   return result;
 453 }
 454
 455 always_inline uword
 456 qhash_find_free (uword i, uword valid_mask)
 457 {
 458   return first_set (~valid_mask & pow2_mask (QHASH_KEYS_PER_BUCKET));
 459 }
 460
 461 void *
 462 _qhash_set_multiple (void *v,
 463                      uword elt_bytes,
 464                      uword * search_keys,
 465                      uword n_search_keys, u32 * result_indices)
 466 {
 467   qhash_t *h = qhash_header (v);
 468   uword *k, *hash_keys;
 469   uword n_left, n_elts, bucket_mask;
 470   u32 *r;
 471
 472   if (vec_len (v) < n_search_keys)
 473     v = _qhash_resize (v, n_search_keys, elt_bytes);
 474
 475   if (qhash_min_log2 (2) != 1)
 476     {
 477       qhash_min_log2_init ();
 478       ASSERT (qhash_min_log2 (2) == 1);
 479     }
 480
 481   ASSERT (v != 0);
 482
 483   bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
 484
 485   hash_keys = h->hash_keys;
 486   k = search_keys;
 487   r = result_indices;
 488   n_left = n_search_keys;
 489   n_elts = h->n_elts;
 490
 491   while (n_left >= 2)
 492     {
 493       u32 a0, b0, c0, bi0, match0, valid0, free0;
 494       u32 a1, b1, c1, bi1, match1, valid1, free1;
 495       uword k0, *h0;
 496       uword k1, *h1;
 497
 498       k0 = k[0];
 499       k1 = k[1];
 500
 501       /* Keys must be unique. */
 502       ASSERT (k0 != k1);
 503
 504       n_left -= 2;
 505       k += 2;
 506
 507       a0 = a1 = h->hash_seeds[0];
 508       b0 = b1 = h->hash_seeds[1];
 509       c0 = c1 = h->hash_seeds[2];
 510       a0 ^= k0;
 511       a1 ^= k1;
 512 #if uword_bits == 64
 513       b0 ^= k0 >> 32;
 514       b1 ^= k1 >> 32;
 515 #endif
 516
 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);
 523
 524       bi0 = c0 & bucket_mask;
 525       bi1 = c1 & bucket_mask;
 526
 527       h0 = hash_keys + bi0;
 528       h1 = hash_keys + bi1;
 529
 530       /* Search two buckets. */
 531       valid0 = qhash_get_valid_elt_mask (h, bi0);
 532       valid1 = qhash_get_valid_elt_mask (h, bi1);
 533
 534       match0 = qhash_search_bucket (h0, k0, valid0);
 535       match1 = qhash_search_bucket (h1, k1, valid1);
 536
 537       /* Find first free element starting at hash offset into bucket. */
 538       free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
 539
 540       valid1 = valid1 | (bi0 == bi1 ? free0 : 0);
 541       free1 = qhash_find_free (c1 & (QHASH_KEYS_PER_BUCKET - 1), valid1);
 542
 543       n_elts += (match0 == 0) + (match1 == 0);
 544
 545       match0 = match0 ? match0 : free0;
 546       match1 = match1 ? match1 : free1;
 547
 548       valid0 |= match0;
 549       valid1 |= match1;
 550
 551       h0 += qhash_min_log2 (match0);
 552       h1 += qhash_min_log2 (match1);
 553
 554       if (PREDICT_FALSE (!match0 || !match1))
 555         goto slow_path2;
 556
 557       h0[0] = k0;
 558       h1[0] = k1;
 559       r[0] = h0 - hash_keys;
 560       r[1] = h1 - hash_keys;
 561       r += 2;
 562       qhash_set_valid_elt_mask (h, bi0, valid0);
 563       qhash_set_valid_elt_mask (h, bi1, valid1);
 564       continue;
 565
 566     slow_path2:
 567       if (!match0)
 568         {
 569           n_elts -= 1;
 570           v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
 571         }
 572       else
 573         {
 574           h0[0] = k0;
 575           r[0] = h0 - hash_keys;
 576           qhash_set_valid_elt_mask (h, bi0, valid0);
 577         }
 578       if (!match1)
 579         {
 580           n_elts -= 1;
 581           v = qhash_set_overflow (v, elt_bytes, k1, bi1, &n_elts, &r[1]);
 582         }
 583       else
 584         {
 585           h1[0] = k1;
 586           r[1] = h1 - hash_keys;
 587           qhash_set_valid_elt_mask (h, bi1, valid1);
 588         }
 589       r += 2;
 590     }
 591
 592   while (n_left >= 1)
 593     {
 594       u32 a0, b0, c0, bi0, match0, valid0, free0;
 595       uword k0, *h0;
 596
 597       k0 = k[0];
 598       n_left -= 1;
 599       k += 1;
 600
 601       a0 = h->hash_seeds[0];
 602       b0 = h->hash_seeds[1];
 603       c0 = h->hash_seeds[2];
 604       a0 ^= k0;
 605 #if uword_bits == 64
 606       b0 ^= k0 >> 32;
 607 #endif
 608
 609       hash_mix32 (a0, b0, c0);
 610
 611       bi0 = c0 & bucket_mask;
 612
 613       h0 = hash_keys + bi0;
 614
 615       valid0 = qhash_get_valid_elt_mask (h, bi0);
 616
 617       /* Find first free element starting at hash offset into bucket. */
 618       free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
 619
 620       match0 = qhash_search_bucket (h0, k0, valid0);
 621
 622       n_elts += (match0 == 0);
 623
 624       match0 = match0 ? match0 : free0;
 625
 626       valid0 |= match0;
 627
 628       h0 += qhash_min_log2 (match0);
 629
 630       if (PREDICT_FALSE (!match0))
 631         goto slow_path1;
 632
 633       h0[0] = k0;
 634       r[0] = h0 - hash_keys;
 635       r += 1;
 636       qhash_set_valid_elt_mask (h, bi0, valid0);
 637       continue;
 638
 639     slow_path1:
 640       n_elts -= 1;
 641       v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
 642       r += 1;
 643     }
 644
 645   h = qhash_header (v);
 646   h->n_elts = n_elts;
 647
 648   return v;
 649 }
 650
 651 static uword
 652 unset_slow_path (void *v, uword elt_bytes,
 653                  uword k0, uword bi0, uword valid0, uword match0,
 654                  uword * n_elts)
 655 {
 656   qhash_t *h = qhash_header (v);
 657   uword i, j = 0, k, l, t = ~0;
 658   hash_pair_t *p, *found;
 659
 660   if (!match0)
 661     {
 662       if (valid0 == QHASH_ALL_VALID)
 663         t = qhash_unset_overflow (v, k0, bi0, n_elts);
 664       return t;
 665     }
 666
 667   i = bi0 / QHASH_KEYS_PER_BUCKET;
 668   t = bi0 + qhash_min_log2 (match0);
 669
 670   if (valid0 == QHASH_ALL_VALID
 671       && i < vec_len (h->overflow_counts) && h->overflow_counts[i] > 0)
 672     {
 673       found = 0;
 674       /* *INDENT-OFF* */
 675       hash_foreach_pair (p, h->overflow_hash, ({
 676         j = qhash_hash_mix (h, p->key) / QHASH_KEYS_PER_BUCKET;
 677         if (j == i)
 678           {
 679             found = p;
 680             break;
 681           }
 682       }));
 683       /* *INDENT-ON* */
 684       ASSERT (found != 0);
 685       ASSERT (j == i);
 686
 687       l = found->value[0];
 688       k = found->key;
 689       hash_unset3 (h->overflow_hash, k, &j);
 690       vec_add1 (h->overflow_free_indices, j);
 691       h->overflow_counts[i] -= 1;
 692
 693       qhash_set_valid_elt_mask (h, bi0, valid0);
 694
 695       h->hash_keys[t] = k;
 696       clib_memswap (v + t * elt_bytes, v + l * elt_bytes, elt_bytes);
 697       t = l;
 698     }
 699   else
 700     qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
 701
 702   return t;
 703 }
 704
 705 void
 706 _qhash_unset_multiple (void *v,
 707                        uword elt_bytes,
 708                        uword * search_keys,
 709                        uword n_search_keys, u32 * result_indices)
 710 {
 711   qhash_t *h = qhash_header (v);
 712   uword *k, *hash_keys;
 713   uword n_left, n_elts, bucket_mask;
 714   u32 *r;
 715
 716   if (!v)
 717     {
 718       uword i;
 719       for (i = 0; i < n_search_keys; i++)
 720         result_indices[i] = ~0;
 721     }
 722
 723   bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
 724
 725   hash_keys = h->hash_keys;
 726   k = search_keys;
 727   r = result_indices;
 728   n_left = n_search_keys;
 729   n_elts = h->n_elts;
 730
 731   while (n_left >= 2)
 732     {
 733       u32 a0, b0, c0, bi0, match0, valid0;
 734       u32 a1, b1, c1, bi1, match1, valid1;
 735       uword k0, *h0;
 736       uword k1, *h1;
 737
 738       k0 = k[0];
 739       k1 = k[1];
 740
 741       /* Keys must be unique. */
 742       ASSERT (k0 != k1);
 743
 744       n_left -= 2;
 745       k += 2;
 746
 747       a0 = a1 = h->hash_seeds[0];
 748       b0 = b1 = h->hash_seeds[1];
 749       c0 = c1 = h->hash_seeds[2];
 750       a0 ^= k0;
 751       a1 ^= k1;
 752 #if uword_bits == 64
 753       b0 ^= k0 >> 32;
 754       b1 ^= k1 >> 32;
 755 #endif
 756
 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);
 763
 764       bi0 = c0 & bucket_mask;
 765       bi1 = c1 & bucket_mask;
 766
 767       h0 = hash_keys + bi0;
 768       h1 = hash_keys + bi1;
 769
 770       /* Search two buckets. */
 771       valid0 = qhash_get_valid_elt_mask (h, bi0);
 772       valid1 = qhash_get_valid_elt_mask (h, bi1);
 773
 774       match0 = qhash_search_bucket (h0, k0, valid0);
 775       match1 = qhash_search_bucket (h1, k1, valid1);
 776
 777       n_elts -= (match0 != 0) + (match1 != 0);
 778
 779       if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID
 780                          || valid1 == QHASH_ALL_VALID))
 781         goto slow_path2;
 782
 783       valid0 ^= match0;
 784       qhash_set_valid_elt_mask (h, bi0, valid0);
 785
 786       valid1 = bi0 == bi1 ? valid0 : valid1;
 787       valid1 ^= match1;
 788
 789       qhash_set_valid_elt_mask (h, bi1, valid1);
 790
 791       r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
 792       r[1] = match1 ? bi1 + qhash_min_log2 (match1) : ~0;
 793       r += 2;
 794       continue;
 795
 796     slow_path2:
 797       r[0] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0, &n_elts);
 798       if (bi0 == bi1)
 799         {
 800           /* Search again in same bucket to test new overflow element. */
 801           valid1 = qhash_get_valid_elt_mask (h, bi0);
 802           if (!match1)
 803             {
 804               match1 = qhash_search_bucket (h1, k1, valid1);
 805               n_elts -= (match1 != 0);
 806             }
 807         }
 808       r[1] = unset_slow_path (v, elt_bytes, k1, bi1, valid1, match1, &n_elts);
 809       r += 2;
 810     }
 811
 812   while (n_left >= 1)
 813     {
 814       u32 a0, b0, c0, bi0, match0, valid0;
 815       uword k0, *h0;
 816
 817       k0 = k[0];
 818       n_left -= 1;
 819       k += 1;
 820
 821       a0 = h->hash_seeds[0];
 822       b0 = h->hash_seeds[1];
 823       c0 = h->hash_seeds[2];
 824       a0 ^= k0;
 825 #if uword_bits == 64
 826       b0 ^= k0 >> 32;
 827 #endif
 828
 829       hash_mix32 (a0, b0, c0);
 830
 831       bi0 = c0 & bucket_mask;
 832
 833       h0 = hash_keys + bi0;
 834
 835       valid0 = qhash_get_valid_elt_mask (h, bi0);
 836
 837       match0 = qhash_search_bucket (h0, k0, valid0);
 838       n_elts -= (match0 != 0);
 839       qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
 840
 841       r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
 842       r += 1;
 843
 844       if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID))
 845         r[-1] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0,
 846                                  &n_elts);
 847     }
 848
 849   h->n_elts = n_elts;
 850 }
 851
 852 /*
 853  * fd.io coding-style-patch-verification: ON
 854  *
 855  * Local Variables:
 856  * eval: (c-set-style "gnu")
 857  * End:
 858  */