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,
  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,
  62                                                  CLIB_CACHE_LINE_BYTES);
  63   vec_resize (h->hash_key_valid_bitmap,
  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
  73 qhash_min_log2 (uword x)
  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
  87 always_inline uword
  88 qhash_get_valid_elt_mask (qhash_t * h, uword i)
  89 { return h->hash_key_valid_bitmap[i / QHASH_KEYS_PER_BUCKET]; }
  90
  91 always_inline void
  92 qhash_set_valid_elt_mask (qhash_t * h, uword i, uword mask)
  93 { h->hash_key_valid_bitmap[i / QHASH_KEYS_PER_BUCKET] = mask; }
  94
  95 always_inline uword
  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
 113 qhash_get_multiple (void * v,
 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
 243 qhash_get_first_match (void * v,
 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)
 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,
 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     {
 403       uword l = vec_len (h->overflow_free_indices);
 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
 459 always_inline uword
 460 qhash_find_free (uword i, uword valid_mask)
 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     {
 480       qhash_min_log2_init ();
 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;
 678       hash_foreach_pair (p, h->overflow_hash, ({
 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);
 692       vec_add1 (h->overflow_free_indices, 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 }