src/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   clib_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       clib_memset (result_indices, ~0,
 127                    sizeof (result_indices[0]) * n_search_keys);
 128       return;
 129     }
 130
 131   bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
 132
 133   k = search_keys;
 134   n_left = n_search_keys;
 135   hash_keys = h->hash_keys;
 136   r = result_indices;
 137
 138   while (n_left >= 2)
 139     {
 140       u32 a0, b0, c0, bi0, valid0, match0;
 141       u32 a1, b1, c1, bi1, valid1, match1;
 142       uword k0, k1, *h0, *h1;
 143
 144       k0 = k[0];
 145       k1 = k[1];
 146       n_left -= 2;
 147       k += 2;
 148
 149       a0 = a1 = h->hash_seeds[0];
 150       b0 = b1 = h->hash_seeds[1];
 151       c0 = c1 = h->hash_seeds[2];
 152       a0 ^= k0;
 153       a1 ^= k1;
 154 #if uword_bits == 64
 155       b0 ^= k0 >> 32;
 156       b1 ^= k1 >> 32;
 157 #endif
 158
 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);
 165
 166       bi0 = c0 & bucket_mask;
 167       bi1 = c1 & bucket_mask;
 168
 169       h0 = hash_keys + bi0;
 170       h1 = hash_keys + bi1;
 171
 172       /* Search two buckets. */
 173       valid0 = qhash_get_valid_elt_mask (h, bi0);
 174       valid1 = qhash_get_valid_elt_mask (h, bi1);
 175
 176       match0 = qhash_search_bucket (h0, k0, valid0);
 177       match1 = qhash_search_bucket (h1, k1, valid1);
 178
 179       bi0 += qhash_min_log2 (match0);
 180       bi1 += qhash_min_log2 (match1);
 181
 182       r[0] = match0 ? bi0 : ~0;
 183       r[1] = match1 ? bi1 : ~0;
 184       r += 2;
 185
 186       /* Full buckets trigger search of overflow hash. */
 187       if (PREDICT_FALSE (!match0 && valid0 == QHASH_ALL_VALID))
 188         {
 189           uword *p = hash_get (h->overflow_hash, k0);
 190           r[-2] = p ? p[0] : ~0;
 191         }
 192
 193       /* Full buckets trigger search of overflow hash. */
 194       if (PREDICT_FALSE (!match1 && valid1 == QHASH_ALL_VALID))
 195         {
 196           uword *p = hash_get (h->overflow_hash, k1);
 197           r[-1] = p ? p[0] : ~0;
 198         }
 199     }
 200
 201   while (n_left >= 1)
 202     {
 203       u32 a0, b0, c0, bi0, valid0, match0;
 204       uword k0, *h0;
 205
 206       k0 = k[0];
 207       n_left -= 1;
 208       k += 1;
 209
 210       a0 = h->hash_seeds[0];
 211       b0 = h->hash_seeds[1];
 212       c0 = h->hash_seeds[2];
 213       a0 ^= k0;
 214 #if uword_bits == 64
 215       b0 ^= k0 >> 32;
 216 #endif
 217
 218       hash_mix32 (a0, b0, c0);
 219
 220       bi0 = c0 & bucket_mask;
 221
 222       h0 = hash_keys + bi0;
 223
 224       /* Search one bucket. */
 225       valid0 = qhash_get_valid_elt_mask (h, bi0);
 226       match0 = qhash_search_bucket (h0, k0, valid0);
 227
 228       bi0 += qhash_min_log2 (match0);
 229
 230       r[0] = match0 ? bi0 : ~0;
 231       r += 1;
 232
 233       /* Full buckets trigger search of overflow hash. */
 234       if (PREDICT_FALSE (!match0 && valid0 == QHASH_ALL_VALID))
 235         {
 236           uword *p = hash_get (h->overflow_hash, k0);
 237           r[-1] = p ? p[0] : ~0;
 238         }
 239     }
 240 }
 241
 242 /* Lookup multiple keys in the same hash table.
 243    Returns index of first matching key. */
 244 u32
 245 qhash_get_first_match (void *v,
 246                        uword * search_keys,
 247                        uword n_search_keys, uword * matching_key)
 248 {
 249   qhash_t *h = qhash_header (v);
 250   uword *k, *hash_keys;
 251   uword n_left, match_mask, bucket_mask;
 252
 253   if (!v)
 254     return ~0;
 255
 256   match_mask = 0;
 257   bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
 258
 259   k = search_keys;
 260   n_left = n_search_keys;
 261   hash_keys = h->hash_keys;
 262   while (n_left >= 2)
 263     {
 264       u32 a0, b0, c0, bi0, valid0;
 265       u32 a1, b1, c1, bi1, valid1;
 266       uword k0, k1, *h0, *h1;
 267
 268       k0 = k[0];
 269       k1 = k[1];
 270       n_left -= 2;
 271       k += 2;
 272
 273       a0 = a1 = h->hash_seeds[0];
 274       b0 = b1 = h->hash_seeds[1];
 275       c0 = c1 = h->hash_seeds[2];
 276       a0 ^= k0;
 277       a1 ^= k1;
 278 #if uword_bits == 64
 279       b0 ^= k0 >> 32;
 280       b1 ^= k1 >> 32;
 281 #endif
 282
 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);
 289
 290       bi0 = c0 & bucket_mask;
 291       bi1 = c1 & bucket_mask;
 292
 293       h0 = hash_keys + bi0;
 294       h1 = hash_keys + bi1;
 295
 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);
 302       if (match_mask)
 303         {
 304           uword bi, is_match1;
 305
 306           bi = qhash_min_log2 (match_mask);
 307           is_match1 = bi >= QHASH_KEYS_PER_BUCKET;
 308
 309           bi += ((is_match1 ? bi1 : bi0)
 310                  - (is_match1 << QHASH_LOG2_KEYS_PER_BUCKET));
 311           *matching_key = (k - 2 - search_keys) + is_match1;
 312           return bi;
 313         }
 314
 315       /* Full buckets trigger search of overflow hash. */
 316       if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID
 317                          || valid1 == QHASH_ALL_VALID))
 318         {
 319           uword *p = 0;
 320           uword ki = k - 2 - search_keys;
 321
 322           if (valid0 == QHASH_ALL_VALID)
 323             p = hash_get (h->overflow_hash, k0);
 324
 325           if (!p && valid1 == QHASH_ALL_VALID)
 326             {
 327               p = hash_get (h->overflow_hash, k1);
 328               ki++;
 329             }
 330
 331           if (p)
 332             {
 333               *matching_key = ki;
 334               return p[0];
 335             }
 336         }
 337     }
 338
 339   while (n_left >= 1)
 340     {
 341       u32 a0, b0, c0, bi0, valid0;
 342       uword k0, *h0;
 343
 344       k0 = k[0];
 345       n_left -= 1;
 346       k += 1;
 347
 348       a0 = h->hash_seeds[0];
 349       b0 = h->hash_seeds[1];
 350       c0 = h->hash_seeds[2];
 351       a0 ^= k0;
 352 #if uword_bits == 64
 353       b0 ^= k0 >> 32;
 354 #endif
 355
 356       hash_mix32 (a0, b0, c0);
 357
 358       bi0 = c0 & bucket_mask;
 359
 360       h0 = hash_keys + bi0;
 361
 362       /* Search one bucket. */
 363       valid0 = qhash_get_valid_elt_mask (h, bi0);
 364       match_mask = qhash_search_bucket (h0, k0, valid0);
 365       if (match_mask)
 366         {
 367           uword bi;
 368           bi = bi0 + qhash_min_log2 (match_mask);
 369           *matching_key = (k - 1 - search_keys);
 370           return bi;
 371         }
 372
 373       /* Full buckets trigger search of overflow hash. */
 374       if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID))
 375         {
 376           uword *p = hash_get (h->overflow_hash, k0);
 377           if (p)
 378             {
 379               *matching_key = (k - 1 - search_keys);
 380               return p[0];
 381             }
 382         }
 383     }
 384
 385   return ~0;
 386 }
 387
 388 static void *
 389 qhash_set_overflow (void *v, uword elt_bytes,
 390                     uword key, uword bi, uword * n_elts, u32 * result)
 391 {
 392   qhash_t *h = qhash_header (v);
 393   uword *p = hash_get (h->overflow_hash, key);
 394   uword i;
 395
 396   bi /= QHASH_KEYS_PER_BUCKET;
 397
 398   if (p)
 399     i = p[0];
 400   else
 401     {
 402       uword l = vec_len (h->overflow_free_indices);
 403       if (l > 0)
 404         {
 405           i = h->overflow_free_indices[l - 1];
 406           _vec_len (h->overflow_free_indices) = l - 1;
 407         }
 408       else
 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;
 413       *n_elts += 1;
 414
 415       l = vec_len (v);
 416       if (i >= l)
 417         {
 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);
 422         }
 423     }
 424
 425   *result = i;
 426
 427   return v;
 428 }
 429
 430 static uword
 431 qhash_unset_overflow (void *v, uword key, uword bi, uword * n_elts)
 432 {
 433   qhash_t *h = qhash_header (v);
 434   uword *p = hash_get (h->overflow_hash, key);
 435   uword result;
 436
 437   bi /= QHASH_KEYS_PER_BUCKET;
 438
 439   if (p)
 440     {
 441       result = p[0];
 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;
 448       *n_elts -= 1;
 449     }
 450   else
 451     result = ~0;
 452
 453   return result;
 454 }
 455
 456 always_inline uword
 457 qhash_find_free (uword i, uword valid_mask)
 458 {
 459   return first_set (~valid_mask & pow2_mask (QHASH_KEYS_PER_BUCKET));
 460 }
 461
 462 void *
 463 _qhash_set_multiple (void *v,
 464                      uword elt_bytes,
 465                      uword * search_keys,
 466                      uword n_search_keys, u32 * result_indices)
 467 {
 468   qhash_t *h = qhash_header (v);
 469   uword *k, *hash_keys;
 470   uword n_left, n_elts, bucket_mask;
 471   u32 *r;
 472
 473   if (vec_len (v) < n_search_keys)
 474     v = _qhash_resize (v, n_search_keys, elt_bytes);
 475
 476   if (qhash_min_log2 (2) != 1)
 477     {
 478       qhash_min_log2_init ();
 479       ASSERT (qhash_min_log2 (2) == 1);
 480     }
 481
 482   ASSERT (v != 0);
 483
 484   bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
 485
 486   hash_keys = h->hash_keys;
 487   k = search_keys;
 488   r = result_indices;
 489   n_left = n_search_keys;
 490   n_elts = h->n_elts;
 491
 492   while (n_left >= 2)
 493     {
 494       u32 a0, b0, c0, bi0, match0, valid0, free0;
 495       u32 a1, b1, c1, bi1, match1, valid1, free1;
 496       uword k0, *h0;
 497       uword k1, *h1;
 498
 499       k0 = k[0];
 500       k1 = k[1];
 501
 502       /* Keys must be unique. */
 503       ASSERT (k0 != k1);
 504
 505       n_left -= 2;
 506       k += 2;
 507
 508       a0 = a1 = h->hash_seeds[0];
 509       b0 = b1 = h->hash_seeds[1];
 510       c0 = c1 = h->hash_seeds[2];
 511       a0 ^= k0;
 512       a1 ^= k1;
 513 #if uword_bits == 64
 514       b0 ^= k0 >> 32;
 515       b1 ^= k1 >> 32;
 516 #endif
 517
 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);
 524
 525       bi0 = c0 & bucket_mask;
 526       bi1 = c1 & bucket_mask;
 527
 528       h0 = hash_keys + bi0;
 529       h1 = hash_keys + bi1;
 530
 531       /* Search two buckets. */
 532       valid0 = qhash_get_valid_elt_mask (h, bi0);
 533       valid1 = qhash_get_valid_elt_mask (h, bi1);
 534
 535       match0 = qhash_search_bucket (h0, k0, valid0);
 536       match1 = qhash_search_bucket (h1, k1, valid1);
 537
 538       /* Find first free element starting at hash offset into bucket. */
 539       free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
 540
 541       valid1 = valid1 | (bi0 == bi1 ? free0 : 0);
 542       free1 = qhash_find_free (c1 & (QHASH_KEYS_PER_BUCKET - 1), valid1);
 543
 544       n_elts += (match0 == 0) + (match1 == 0);
 545
 546       match0 = match0 ? match0 : free0;
 547       match1 = match1 ? match1 : free1;
 548
 549       valid0 |= match0;
 550       valid1 |= match1;
 551
 552       h0 += qhash_min_log2 (match0);
 553       h1 += qhash_min_log2 (match1);
 554
 555       if (PREDICT_FALSE (!match0 || !match1))
 556         goto slow_path2;
 557
 558       h0[0] = k0;
 559       h1[0] = k1;
 560       r[0] = h0 - hash_keys;
 561       r[1] = h1 - hash_keys;
 562       r += 2;
 563       qhash_set_valid_elt_mask (h, bi0, valid0);
 564       qhash_set_valid_elt_mask (h, bi1, valid1);
 565       continue;
 566
 567     slow_path2:
 568       if (!match0)
 569         {
 570           n_elts -= 1;
 571           v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
 572         }
 573       else
 574         {
 575           h0[0] = k0;
 576           r[0] = h0 - hash_keys;
 577           qhash_set_valid_elt_mask (h, bi0, valid0);
 578         }
 579       if (!match1)
 580         {
 581           n_elts -= 1;
 582           v = qhash_set_overflow (v, elt_bytes, k1, bi1, &n_elts, &r[1]);
 583         }
 584       else
 585         {
 586           h1[0] = k1;
 587           r[1] = h1 - hash_keys;
 588           qhash_set_valid_elt_mask (h, bi1, valid1);
 589         }
 590       r += 2;
 591     }
 592
 593   while (n_left >= 1)
 594     {
 595       u32 a0, b0, c0, bi0, match0, valid0, free0;
 596       uword k0, *h0;
 597
 598       k0 = k[0];
 599       n_left -= 1;
 600       k += 1;
 601
 602       a0 = h->hash_seeds[0];
 603       b0 = h->hash_seeds[1];
 604       c0 = h->hash_seeds[2];
 605       a0 ^= k0;
 606 #if uword_bits == 64
 607       b0 ^= k0 >> 32;
 608 #endif
 609
 610       hash_mix32 (a0, b0, c0);
 611
 612       bi0 = c0 & bucket_mask;
 613
 614       h0 = hash_keys + bi0;
 615
 616       valid0 = qhash_get_valid_elt_mask (h, bi0);
 617
 618       /* Find first free element starting at hash offset into bucket. */
 619       free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
 620
 621       match0 = qhash_search_bucket (h0, k0, valid0);
 622
 623       n_elts += (match0 == 0);
 624
 625       match0 = match0 ? match0 : free0;
 626
 627       valid0 |= match0;
 628
 629       h0 += qhash_min_log2 (match0);
 630
 631       if (PREDICT_FALSE (!match0))
 632         goto slow_path1;
 633
 634       h0[0] = k0;
 635       r[0] = h0 - hash_keys;
 636       r += 1;
 637       qhash_set_valid_elt_mask (h, bi0, valid0);
 638       continue;
 639
 640     slow_path1:
 641       n_elts -= 1;
 642       v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
 643       r += 1;
 644     }
 645
 646   h = qhash_header (v);
 647   h->n_elts = n_elts;
 648
 649   return v;
 650 }
 651
 652 static uword
 653 unset_slow_path (void *v, uword elt_bytes,
 654                  uword k0, uword bi0, uword valid0, uword match0,
 655                  uword * n_elts)
 656 {
 657   qhash_t *h = qhash_header (v);
 658   uword i, j = 0, k, l, t = ~0;
 659   hash_pair_t *p, *found;
 660
 661   if (!match0)
 662     {
 663       if (valid0 == QHASH_ALL_VALID)
 664         t = qhash_unset_overflow (v, k0, bi0, n_elts);
 665       return t;
 666     }
 667
 668   i = bi0 / QHASH_KEYS_PER_BUCKET;
 669   t = bi0 + qhash_min_log2 (match0);
 670
 671   if (valid0 == QHASH_ALL_VALID
 672       && i < vec_len (h->overflow_counts) && h->overflow_counts[i] > 0)
 673     {
 674       found = 0;
 675       /* *INDENT-OFF* */
 676       hash_foreach_pair (p, h->overflow_hash, ({
 677         j = qhash_hash_mix (h, p->key) / QHASH_KEYS_PER_BUCKET;
 678         if (j == i)
 679           {
 680             found = p;
 681             break;
 682           }
 683       }));
 684       /* *INDENT-ON* */
 685       ASSERT (found != 0);
 686       ASSERT (j == i);
 687
 688       l = found->value[0];
 689       k = found->key;
 690       hash_unset3 (h->overflow_hash, k, &j);
 691       vec_add1 (h->overflow_free_indices, j);
 692       h->overflow_counts[i] -= 1;
 693
 694       qhash_set_valid_elt_mask (h, bi0, valid0);
 695
 696       h->hash_keys[t] = k;
 697       clib_memswap (v + t * elt_bytes, v + l * elt_bytes, elt_bytes);
 698       t = l;
 699     }
 700   else
 701     qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
 702
 703   return t;
 704 }
 705
 706 void
 707 _qhash_unset_multiple (void *v,
 708                        uword elt_bytes,
 709                        uword * search_keys,
 710                        uword n_search_keys, u32 * result_indices)
 711 {
 712   qhash_t *h = qhash_header (v);
 713   uword *k, *hash_keys;
 714   uword n_left, n_elts, bucket_mask;
 715   u32 *r;
 716
 717   if (!v)
 718     {
 719       uword i;
 720       for (i = 0; i < n_search_keys; i++)
 721         result_indices[i] = ~0;
 722     }
 723
 724   bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
 725
 726   hash_keys = h->hash_keys;
 727   k = search_keys;
 728   r = result_indices;
 729   n_left = n_search_keys;
 730   n_elts = h->n_elts;
 731
 732   while (n_left >= 2)
 733     {
 734       u32 a0, b0, c0, bi0, match0, valid0;
 735       u32 a1, b1, c1, bi1, match1, valid1;
 736       uword k0, *h0;
 737       uword k1, *h1;
 738
 739       k0 = k[0];
 740       k1 = k[1];
 741
 742       /* Keys must be unique. */
 743       ASSERT (k0 != k1);
 744
 745       n_left -= 2;
 746       k += 2;
 747
 748       a0 = a1 = h->hash_seeds[0];
 749       b0 = b1 = h->hash_seeds[1];
 750       c0 = c1 = h->hash_seeds[2];
 751       a0 ^= k0;
 752       a1 ^= k1;
 753 #if uword_bits == 64
 754       b0 ^= k0 >> 32;
 755       b1 ^= k1 >> 32;
 756 #endif
 757
 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);
 764
 765       bi0 = c0 & bucket_mask;
 766       bi1 = c1 & bucket_mask;
 767
 768       h0 = hash_keys + bi0;
 769       h1 = hash_keys + bi1;
 770
 771       /* Search two buckets. */
 772       valid0 = qhash_get_valid_elt_mask (h, bi0);
 773       valid1 = qhash_get_valid_elt_mask (h, bi1);
 774
 775       match0 = qhash_search_bucket (h0, k0, valid0);
 776       match1 = qhash_search_bucket (h1, k1, valid1);
 777
 778       n_elts -= (match0 != 0) + (match1 != 0);
 779
 780       if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID
 781                          || valid1 == QHASH_ALL_VALID))
 782         goto slow_path2;
 783
 784       valid0 ^= match0;
 785       qhash_set_valid_elt_mask (h, bi0, valid0);
 786
 787       valid1 = bi0 == bi1 ? valid0 : valid1;
 788       valid1 ^= match1;
 789
 790       qhash_set_valid_elt_mask (h, bi1, valid1);
 791
 792       r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
 793       r[1] = match1 ? bi1 + qhash_min_log2 (match1) : ~0;
 794       r += 2;
 795       continue;
 796
 797     slow_path2:
 798       r[0] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0, &n_elts);
 799       if (bi0 == bi1)
 800         {
 801           /* Search again in same bucket to test new overflow element. */
 802           valid1 = qhash_get_valid_elt_mask (h, bi0);
 803           if (!match1)
 804             {
 805               match1 = qhash_search_bucket (h1, k1, valid1);
 806               n_elts -= (match1 != 0);
 807             }
 808         }
 809       r[1] = unset_slow_path (v, elt_bytes, k1, bi1, valid1, match1, &n_elts);
 810       r += 2;
 811     }
 812
 813   while (n_left >= 1)
 814     {
 815       u32 a0, b0, c0, bi0, match0, valid0;
 816       uword k0, *h0;
 817
 818       k0 = k[0];
 819       n_left -= 1;
 820       k += 1;
 821
 822       a0 = h->hash_seeds[0];
 823       b0 = h->hash_seeds[1];
 824       c0 = h->hash_seeds[2];
 825       a0 ^= k0;
 826 #if uword_bits == 64
 827       b0 ^= k0 >> 32;
 828 #endif
 829
 830       hash_mix32 (a0, b0, c0);
 831
 832       bi0 = c0 & bucket_mask;
 833
 834       h0 = hash_keys + bi0;
 835
 836       valid0 = qhash_get_valid_elt_mask (h, bi0);
 837
 838       match0 = qhash_search_bucket (h0, k0, valid0);
 839       n_elts -= (match0 != 0);
 840       qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
 841
 842       r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
 843       r += 1;
 844
 845       if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID))
 846         r[-1] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0,
 847                                  &n_elts);
 848     }
 849
 850   h->n_elts = n_elts;
 851 }
 852
 853 /*
 854  * fd.io coding-style-patch-verification: ON
 855  *
 856  * Local Variables:
 857  * eval: (c-set-style "gnu")
 858  * End:
 859  */