src/vppinfra/hash.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) 2001-2005 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/hash.h>
  39 #include <vppinfra/error.h>
  40 #include <vppinfra/mem.h>
  41 #include <vppinfra/byte_order.h>        /* for clib_arch_is_big_endian */
  42
  43 always_inline void
  44 zero_pair (hash_t * h, hash_pair_t * p)
  45 {
  46   memset (p, 0, hash_pair_bytes (h));
  47 }
  48
  49 always_inline void
  50 init_pair (hash_t * h, hash_pair_t * p)
  51 {
  52   memset (p->value, ~0, hash_value_bytes (h));
  53 }
  54
  55 always_inline hash_pair_union_t *
  56 get_pair (void *v, uword i)
  57 {
  58   hash_t *h = hash_header (v);
  59   hash_pair_t *p;
  60   ASSERT (i < vec_len (v));
  61   p = v;
  62   p += i << h->log2_pair_size;
  63   return (hash_pair_union_t *) p;
  64 }
  65
  66 always_inline void
  67 set_is_user (void *v, uword i, uword is_user)
  68 {
  69   hash_t *h = hash_header (v);
  70   uword i0 = i / BITS (h->is_user[0]);
  71   uword i1 = (uword) 1 << (i % BITS (h->is_user[0]));
  72   if (is_user)
  73     h->is_user[i0] |= i1;
  74   else
  75     h->is_user[i0] &= ~i1;
  76 }
  77
  78 static u8 *hash_format_pair_default (u8 * s, va_list * args);
  79
  80 #if uword_bits == 64
  81
  82 static inline u64
  83 zap64 (u64 x, word n)
  84 {
  85 #define _(n) (((u64) 1 << (u64) (8*(n))) - (u64) 1)
  86   static u64 masks_little_endian[] = {
  87     0, _(1), _(2), _(3), _(4), _(5), _(6), _(7),
  88   };
  89   static u64 masks_big_endian[] = {
  90     0, ~_(7), ~_(6), ~_(5), ~_(4), ~_(3), ~_(2), ~_(1),
  91   };
  92 #undef _
  93   if (clib_arch_is_big_endian)
  94     return x & masks_big_endian[n];
  95   else
  96     return x & masks_little_endian[n];
  97 }
  98
  99 /**
 100  * make address-sanitizer skip this:
 101  * clib_mem_unaligned + zap64 casts its input as u64, computes a mask
 102  * according to the input length, and returns the casted maked value.
 103  * Therefore all the 8 Bytes of the u64 are systematically read, which
 104  * rightfully causes address-sanitizer to raise an error on smaller inputs.
 105  *
 106  * However the invalid Bytes are discarded within zap64(), whicj is why
 107  * this can be silenced safely.
 108  */
 109 static inline u64 __attribute__ ((no_sanitize_address))
 110 hash_memory64 (void *p, word n_bytes, u64 state)
 111 {
 112   u64 *q = p;
 113   u64 a, b, c, n;
 114
 115   a = b = 0x9e3779b97f4a7c13LL;
 116   c = state;
 117   n = n_bytes;
 118
 119   while (n >= 3 * sizeof (u64))
 120     {
 121       a += clib_mem_unaligned (q + 0, u64);
 122       b += clib_mem_unaligned (q + 1, u64);
 123       c += clib_mem_unaligned (q + 2, u64);
 124       hash_mix64 (a, b, c);
 125       n -= 3 * sizeof (u64);
 126       q += 3;
 127     }
 128
 129   c += n_bytes;
 130   switch (n / sizeof (u64))
 131     {
 132     case 2:
 133       a += clib_mem_unaligned (q + 0, u64);
 134       b += clib_mem_unaligned (q + 1, u64);
 135       if (n % sizeof (u64))
 136         c += zap64 (clib_mem_unaligned (q + 2, u64), n % sizeof (u64)) << 8;
 137       break;
 138
 139     case 1:
 140       a += clib_mem_unaligned (q + 0, u64);
 141       if (n % sizeof (u64))
 142         b += zap64 (clib_mem_unaligned (q + 1, u64), n % sizeof (u64));
 143       break;
 144
 145     case 0:
 146       if (n % sizeof (u64))
 147         a += zap64 (clib_mem_unaligned (q + 0, u64), n % sizeof (u64));
 148       break;
 149     }
 150
 151   hash_mix64 (a, b, c);
 152
 153   return c;
 154 }
 155
 156 #else /* if uword_bits == 64 */
 157
 158 static inline u32
 159 zap32 (u32 x, word n)
 160 {
 161 #define _(n) (((u32) 1 << (u32) (8*(n))) - (u32) 1)
 162   static u32 masks_little_endian[] = {
 163     0, _(1), _(2), _(3),
 164   };
 165   static u32 masks_big_endian[] = {
 166     0, ~_(3), ~_(2), ~_(1),
 167   };
 168 #undef _
 169   if (clib_arch_is_big_endian)
 170     return x & masks_big_endian[n];
 171   else
 172     return x & masks_little_endian[n];
 173 }
 174
 175 static inline u32
 176 hash_memory32 (void *p, word n_bytes, u32 state)
 177 {
 178   u32 *q = p;
 179   u32 a, b, c, n;
 180
 181   a = b = 0x9e3779b9;
 182   c = state;
 183   n = n_bytes;
 184
 185   while (n >= 3 * sizeof (u32))
 186     {
 187       a += clib_mem_unaligned (q + 0, u32);
 188       b += clib_mem_unaligned (q + 1, u32);
 189       c += clib_mem_unaligned (q + 2, u32);
 190       hash_mix32 (a, b, c);
 191       n -= 3 * sizeof (u32);
 192       q += 3;
 193     }
 194
 195   c += n_bytes;
 196   switch (n / sizeof (u32))
 197     {
 198     case 2:
 199       a += clib_mem_unaligned (q + 0, u32);
 200       b += clib_mem_unaligned (q + 1, u32);
 201       if (n % sizeof (u32))
 202         c += zap32 (clib_mem_unaligned (q + 2, u32), n % sizeof (u32)) << 8;
 203       break;
 204
 205     case 1:
 206       a += clib_mem_unaligned (q + 0, u32);
 207       if (n % sizeof (u32))
 208         b += zap32 (clib_mem_unaligned (q + 1, u32), n % sizeof (u32));
 209       break;
 210
 211     case 0:
 212       if (n % sizeof (u32))
 213         a += zap32 (clib_mem_unaligned (q + 0, u32), n % sizeof (u32));
 214       break;
 215     }
 216
 217   hash_mix32 (a, b, c);
 218
 219   return c;
 220 }
 221 #endif
 222
 223 uword
 224 hash_memory (void *p, word n_bytes, uword state)
 225 {
 226   uword *q = p;
 227
 228 #if uword_bits == 64
 229   return hash_memory64 (q, n_bytes, state);
 230 #else
 231   return hash_memory32 (q, n_bytes, state);
 232 #endif
 233 }
 234
 235 #if uword_bits == 64
 236 always_inline uword
 237 hash_uword (uword x)
 238 {
 239   u64 a, b, c;
 240
 241   a = b = 0x9e3779b97f4a7c13LL;
 242   c = 0;
 243   a += x;
 244   hash_mix64 (a, b, c);
 245   return c;
 246 }
 247 #else
 248 always_inline uword
 249 hash_uword (uword x)
 250 {
 251   u32 a, b, c;
 252
 253   a = b = 0x9e3779b9;
 254   c = 0;
 255   a += x;
 256   hash_mix32 (a, b, c);
 257   return c;
 258 }
 259 #endif
 260
 261 /* Call sum function.  Hash code will be sum function value
 262    modulo the prime length of the hash table. */
 263 always_inline uword
 264 key_sum (hash_t * h, uword key)
 265 {
 266   uword sum;
 267   switch (pointer_to_uword ((void *) h->key_sum))
 268     {
 269     case KEY_FUNC_NONE:
 270       sum = hash_uword (key);
 271       break;
 272
 273     case KEY_FUNC_POINTER_UWORD:
 274       sum = hash_uword (*uword_to_pointer (key, uword *));
 275       break;
 276
 277     case KEY_FUNC_POINTER_U32:
 278       sum = hash_uword (*uword_to_pointer (key, u32 *));
 279       break;
 280
 281     case KEY_FUNC_STRING:
 282       sum = string_key_sum (h, key);
 283       break;
 284
 285     default:
 286       sum = h->key_sum (h, key);
 287       break;
 288     }
 289
 290   return sum;
 291 }
 292
 293 always_inline uword
 294 key_equal1 (hash_t * h, uword key1, uword key2, uword e)
 295 {
 296   switch (pointer_to_uword ((void *) h->key_equal))
 297     {
 298     case KEY_FUNC_NONE:
 299       break;
 300
 301     case KEY_FUNC_POINTER_UWORD:
 302       e =
 303         *uword_to_pointer (key1, uword *) == *uword_to_pointer (key2,
 304                                                                 uword *);
 305       break;
 306
 307     case KEY_FUNC_POINTER_U32:
 308       e = *uword_to_pointer (key1, u32 *) == *uword_to_pointer (key2, u32 *);
 309       break;
 310
 311     case KEY_FUNC_STRING:
 312       e = string_key_equal (h, key1, key2);
 313       break;
 314
 315     default:
 316       e = h->key_equal (h, key1, key2);
 317       break;
 318     }
 319   return e;
 320 }
 321
 322 /* Compares two keys: returns 1 if equal, 0 if not. */
 323 always_inline uword
 324 key_equal (hash_t * h, uword key1, uword key2)
 325 {
 326   uword e = key1 == key2;
 327   if (CLIB_DEBUG > 0 && key1 == key2)
 328     ASSERT (key_equal1 (h, key1, key2, e));
 329   if (!e)
 330     e = key_equal1 (h, key1, key2, e);
 331   return e;
 332 }
 333
 334 static hash_pair_union_t *
 335 get_indirect (void *v, hash_pair_indirect_t * pi, uword key)
 336 {
 337   hash_t *h = hash_header (v);
 338   hash_pair_t *p0, *p1;
 339
 340   p0 = p1 = pi->pairs;
 341   if (h->log2_pair_size > 0)
 342     p1 = hash_forward (h, p0, indirect_pair_get_len (pi));
 343   else
 344     p1 += vec_len (p0);
 345
 346   while (p0 < p1)
 347     {
 348       if (key_equal (h, p0->key, key))
 349         return (hash_pair_union_t *) p0;
 350       p0 = hash_forward1 (h, p0);
 351     }
 352
 353   return (hash_pair_union_t *) 0;
 354 }
 355
 356 static hash_pair_union_t *
 357 set_indirect_is_user (void *v, uword i, hash_pair_union_t * p, uword key)
 358 {
 359   hash_t *h = hash_header (v);
 360   hash_pair_t *q;
 361   hash_pair_indirect_t *pi = &p->indirect;
 362   uword log2_bytes = 0;
 363
 364   if (h->log2_pair_size == 0)
 365     q = vec_new (hash_pair_t, 2);
 366   else
 367     {
 368       log2_bytes = 1 + hash_pair_log2_bytes (h);
 369       q = clib_mem_alloc (1ULL << log2_bytes);
 370     }
 371   clib_memcpy (q, &p->direct, hash_pair_bytes (h));
 372
 373   pi->pairs = q;
 374   if (h->log2_pair_size > 0)
 375     indirect_pair_set (pi, log2_bytes, 2);
 376
 377   set_is_user (v, i, 0);
 378
 379   /* First element is used by existing pair, second will be used by caller. */
 380   q = hash_forward1 (h, q);
 381   q->key = key;
 382   init_pair (h, q);
 383   return (hash_pair_union_t *) q;
 384 }
 385
 386 static hash_pair_union_t *
 387 set_indirect (void *v, hash_pair_indirect_t * pi, uword key,
 388               uword * found_key)
 389 {
 390   hash_t *h = hash_header (v);
 391   hash_pair_t *new_pair;
 392   hash_pair_union_t *q;
 393
 394   q = get_indirect (v, pi, key);
 395   if (q)
 396     {
 397       *found_key = 1;
 398       return q;
 399     }
 400
 401   if (h->log2_pair_size == 0)
 402     vec_add2 (pi->pairs, new_pair, 1);
 403   else
 404     {
 405       uword len, new_len, log2_bytes;
 406
 407       len = indirect_pair_get_len (pi);
 408       log2_bytes = indirect_pair_get_log2_bytes (pi);
 409
 410       new_len = len + 1;
 411       if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes))
 412         {
 413           pi->pairs = clib_mem_realloc (pi->pairs,
 414                                         1ULL << (log2_bytes + 1),
 415                                         1ULL << log2_bytes);
 416           log2_bytes++;
 417         }
 418
 419       indirect_pair_set (pi, log2_bytes, new_len);
 420       new_pair = pi->pairs + (len << h->log2_pair_size);
 421     }
 422   new_pair->key = key;
 423   init_pair (h, new_pair);
 424   *found_key = 0;
 425   return (hash_pair_union_t *) new_pair;
 426 }
 427
 428 static void
 429 unset_indirect (void *v, uword i, hash_pair_t * q)
 430 {
 431   hash_t *h = hash_header (v);
 432   hash_pair_union_t *p = get_pair (v, i);
 433   hash_pair_t *e;
 434   hash_pair_indirect_t *pi = &p->indirect;
 435   uword len, is_vec;
 436
 437   is_vec = h->log2_pair_size == 0;
 438
 439   ASSERT (!hash_is_user (v, i));
 440   len = is_vec ? vec_len (pi->pairs) : indirect_pair_get_len (pi);
 441   e = hash_forward (h, pi->pairs, len - 1);
 442   ASSERT (q >= pi->pairs && q <= e);
 443
 444   /* We have two or fewer pairs and we are delete one pair.
 445      Make indirect pointer direct and free indirect memory. */
 446   if (len <= 2)
 447     {
 448       hash_pair_t *r = pi->pairs;
 449
 450       if (len == 2)
 451         {
 452           clib_memcpy (p, q == r ? hash_forward1 (h, r) : r,
 453                        hash_pair_bytes (h));
 454           set_is_user (v, i, 1);
 455         }
 456       else
 457         zero_pair (h, &p->direct);
 458
 459       if (is_vec)
 460         vec_free (r);
 461       else if (r)
 462         clib_mem_free (r);
 463     }
 464   else
 465     {
 466       /* If deleting a pair we need to keep non-null pairs together. */
 467       if (q < e)
 468         clib_memcpy (q, e, hash_pair_bytes (h));
 469       else
 470         zero_pair (h, q);
 471       if (is_vec)
 472         _vec_len (pi->pairs) -= 1;
 473       else
 474         indirect_pair_set (pi, indirect_pair_get_log2_bytes (pi), len - 1);
 475     }
 476 }
 477
 478 enum lookup_opcode
 479 {
 480   GET = 1,
 481   SET = 2,
 482   UNSET = 3,
 483 };
 484
 485 static hash_pair_t *
 486 lookup (void *v, uword key, enum lookup_opcode op,
 487         void *new_value, void *old_value)
 488 {
 489   hash_t *h = hash_header (v);
 490   hash_pair_union_t *p = 0;
 491   uword found_key = 0;
 492   uword i;
 493
 494   if (!v)
 495     return 0;
 496
 497   i = key_sum (h, key) & (_vec_len (v) - 1);
 498   p = get_pair (v, i);
 499
 500   if (hash_is_user (v, i))
 501     {
 502       found_key = key_equal (h, p->direct.key, key);
 503       if (found_key)
 504         {
 505           if (op == UNSET)
 506             {
 507               set_is_user (v, i, 0);
 508               if (old_value)
 509                 clib_memcpy (old_value, p->direct.value,
 510                              hash_value_bytes (h));
 511               zero_pair (h, &p->direct);
 512             }
 513         }
 514       else
 515         {
 516           if (op == SET)
 517             p = set_indirect_is_user (v, i, p, key);
 518           else
 519             p = 0;
 520         }
 521     }
 522   else
 523     {
 524       hash_pair_indirect_t *pi = &p->indirect;
 525
 526       if (op == SET)
 527         {
 528           if (!pi->pairs)
 529             {
 530               p->direct.key = key;
 531               set_is_user (v, i, 1);
 532             }
 533           else
 534             p = set_indirect (v, pi, key, &found_key);
 535         }
 536       else
 537         {
 538           p = get_indirect (v, pi, key);
 539           found_key = p != 0;
 540           if (found_key && op == UNSET)
 541             {
 542               if (old_value)
 543                 clib_memcpy (old_value, &p->direct.value,
 544                              hash_value_bytes (h));
 545
 546               unset_indirect (v, i, &p->direct);
 547
 548               /* Nullify p (since it's just been deleted).
 549                  Otherwise we might be tempted to play with it. */
 550               p = 0;
 551             }
 552         }
 553     }
 554
 555   if (op == SET && p != 0)
 556     {
 557       /* Save away old value for caller. */
 558       if (old_value && found_key)
 559         clib_memcpy (old_value, &p->direct.value, hash_value_bytes (h));
 560       clib_memcpy (&p->direct.value, new_value, hash_value_bytes (h));
 561     }
 562
 563   if (op == SET)
 564     h->elts += !found_key;
 565   if (op == UNSET)
 566     h->elts -= found_key;
 567
 568   return &p->direct;
 569 }
 570
 571 /* Fetch value of key. */
 572 uword *
 573 _hash_get (void *v, uword key)
 574 {
 575   hash_t *h = hash_header (v);
 576   hash_pair_t *p;
 577
 578   /* Don't even search table if its empty. */
 579   if (!v || h->elts == 0)
 580     return 0;
 581
 582   p = lookup (v, key, GET, 0, 0);
 583   if (!p)
 584     return 0;
 585   if (h->log2_pair_size == 0)
 586     return &p->key;
 587   else
 588     return &p->value[0];
 589 }
 590
 591 hash_pair_t *
 592 _hash_get_pair (void *v, uword key)
 593 {
 594   return lookup (v, key, GET, 0, 0);
 595 }
 596
 597 hash_pair_t *
 598 hash_next (void *v, hash_next_t * hn)
 599 {
 600   hash_t *h = hash_header (v);
 601   hash_pair_t *p;
 602
 603   while (1)
 604     {
 605       if (hn->i == 0 && hn->j == 0)
 606         {
 607           /* Save flags. */
 608           hn->f = h->flags;
 609
 610           /* Prevent others from re-sizing hash table. */
 611           h->flags |=
 612             (HASH_FLAG_NO_AUTO_GROW
 613              | HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_HASH_NEXT_IN_PROGRESS);
 614         }
 615       else if (hn->i >= hash_capacity (v))
 616         {
 617           /* Restore flags. */
 618           h->flags = hn->f;
 619           memset (hn, 0, sizeof (hn[0]));
 620           return 0;
 621         }
 622
 623       p = hash_forward (h, v, hn->i);
 624       if (hash_is_user (v, hn->i))
 625         {
 626           hn->i++;
 627           return p;
 628         }
 629       else
 630         {
 631           hash_pair_indirect_t *pi = (void *) p;
 632           uword n;
 633
 634           if (h->log2_pair_size > 0)
 635             n = indirect_pair_get_len (pi);
 636           else
 637             n = vec_len (pi->pairs);
 638
 639           if (hn->j >= n)
 640             {
 641               hn->i++;
 642               hn->j = 0;
 643             }
 644           else
 645             return hash_forward (h, pi->pairs, hn->j++);
 646         }
 647     }
 648 }
 649
 650 /* Remove key from table. */
 651 void *
 652 _hash_unset (void *v, uword key, void *old_value)
 653 {
 654   hash_t *h;
 655
 656   if (!v)
 657     return v;
 658
 659   (void) lookup (v, key, UNSET, 0, old_value);
 660
 661   h = hash_header (v);
 662   if (!(h->flags & HASH_FLAG_NO_AUTO_SHRINK))
 663     {
 664       /* Resize when 1/4 full. */
 665       if (h->elts > 32 && 4 * (h->elts + 1) < vec_len (v))
 666         v = hash_resize (v, vec_len (v) / 2);
 667     }
 668
 669   return v;
 670 }
 671
 672 void *
 673 _hash_create (uword elts, hash_t * h_user)
 674 {
 675   hash_t *h;
 676   uword log2_pair_size;
 677   void *v;
 678
 679   /* Size of hash is power of 2 >= ELTS and larger than
 680      number of bits in is_user bitmap elements. */
 681   elts = clib_max (elts, BITS (h->is_user[0]));
 682   elts = 1ULL << max_log2 (elts);
 683
 684   log2_pair_size = 1;
 685   if (h_user)
 686     log2_pair_size = h_user->log2_pair_size;
 687
 688   v = _vec_resize ((void *) 0,
 689                    /* vec len: */ elts,
 690                    /* data bytes: */
 691                    (elts << log2_pair_size) * sizeof (hash_pair_t),
 692                    /* header bytes: */
 693                    sizeof (h[0]) +
 694                    (elts / BITS (h->is_user[0])) * sizeof (h->is_user[0]),
 695                    /* alignment */ sizeof (hash_pair_t));
 696   h = hash_header (v);
 697
 698   if (h_user)
 699     h[0] = h_user[0];
 700
 701   h->log2_pair_size = log2_pair_size;
 702   h->elts = 0;
 703
 704   /* Default flags to never shrinking hash tables.
 705      Shrinking tables can cause "jackpot" cases. */
 706   if (!h_user)
 707     h->flags = HASH_FLAG_NO_AUTO_SHRINK;
 708
 709   if (!h->format_pair)
 710     {
 711       h->format_pair = hash_format_pair_default;
 712       h->format_pair_arg = 0;
 713     }
 714
 715   return v;
 716 }
 717
 718 void *
 719 _hash_free (void *v)
 720 {
 721   hash_t *h = hash_header (v);
 722   hash_pair_union_t *p;
 723   uword i;
 724
 725   if (!v)
 726     return v;
 727
 728   /* We zero all freed memory in case user would be tempted to use it. */
 729   for (i = 0; i < hash_capacity (v); i++)
 730     {
 731       if (hash_is_user (v, i))
 732         continue;
 733       p = get_pair (v, i);
 734       if (h->log2_pair_size == 0)
 735         vec_free (p->indirect.pairs);
 736       else if (p->indirect.pairs)
 737         clib_mem_free (p->indirect.pairs);
 738     }
 739
 740   vec_free_header (h);
 741
 742   return 0;
 743 }
 744
 745 static void *
 746 hash_resize_internal (void *old, uword new_size, uword free_old)
 747 {
 748   void *new;
 749   hash_pair_t *p;
 750
 751   new = 0;
 752   if (new_size > 0)
 753     {
 754       hash_t *h = old ? hash_header (old) : 0;
 755       new = _hash_create (new_size, h);
 756       /* *INDENT-OFF* */
 757       hash_foreach_pair (p, old, {
 758         new = _hash_set3 (new, p->key, &p->value[0], 0);
 759       });
 760       /* *INDENT-ON* */
 761     }
 762
 763   if (free_old)
 764     hash_free (old);
 765   return new;
 766 }
 767
 768 void *
 769 hash_resize (void *old, uword new_size)
 770 {
 771   return hash_resize_internal (old, new_size, 1);
 772 }
 773
 774 void *
 775 hash_dup (void *old)
 776 {
 777   return hash_resize_internal (old, vec_len (old), 0);
 778 }
 779
 780 void *
 781 _hash_set3 (void *v, uword key, void *value, void *old_value)
 782 {
 783   hash_t *h;
 784
 785   if (!v)
 786     v = hash_create (0, sizeof (uword));
 787
 788   h = hash_header (v);
 789   (void) lookup (v, key, SET, value, old_value);
 790
 791   if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
 792     {
 793       /* Resize when 3/4 full. */
 794       if (4 * (h->elts + 1) > 3 * vec_len (v))
 795         v = hash_resize (v, 2 * vec_len (v));
 796     }
 797
 798   return v;
 799 }
 800
 801 uword
 802 vec_key_sum (hash_t * h, uword key)
 803 {
 804   void *v = uword_to_pointer (key, void *);
 805   return hash_memory (v, vec_len (v) * h->user, 0);
 806 }
 807
 808 uword
 809 vec_key_equal (hash_t * h, uword key1, uword key2)
 810 {
 811   void *v1 = uword_to_pointer (key1, void *);
 812   void *v2 = uword_to_pointer (key2, void *);
 813   uword l1 = vec_len (v1);
 814   uword l2 = vec_len (v2);
 815   return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user);
 816 }
 817
 818 u8 *
 819 vec_key_format_pair (u8 * s, va_list * args)
 820 {
 821   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 822   void *v = va_arg (*args, void *);
 823   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 824   hash_t *h = hash_header (v);
 825   void *u = uword_to_pointer (p->key, void *);
 826   int i;
 827
 828   switch (h->user)
 829     {
 830     case 1:
 831       s = format (s, "%v", u);
 832       break;
 833
 834     case 2:
 835       {
 836         u16 *w = u;
 837         for (i = 0; i < vec_len (w); i++)
 838           s = format (s, "0x%x, ", w[i]);
 839         break;
 840       }
 841
 842     case 4:
 843       {
 844         u32 *w = u;
 845         for (i = 0; i < vec_len (w); i++)
 846           s = format (s, "0x%x, ", w[i]);
 847         break;
 848       }
 849
 850     case 8:
 851       {
 852         u64 *w = u;
 853         for (i = 0; i < vec_len (w); i++)
 854           s = format (s, "0x%Lx, ", w[i]);
 855         break;
 856       }
 857
 858     default:
 859       s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
 860       break;
 861     }
 862
 863   if (hash_value_bytes (h) > 0)
 864     s = format (s, " -> 0x%wx", p->value[0]);
 865
 866   return s;
 867 }
 868
 869 uword
 870 mem_key_sum (hash_t * h, uword key)
 871 {
 872   uword *v = uword_to_pointer (key, void *);
 873   return hash_memory (v, h->user, 0);
 874 }
 875
 876 uword
 877 mem_key_equal (hash_t * h, uword key1, uword key2)
 878 {
 879   void *v1 = uword_to_pointer (key1, void *);
 880   void *v2 = uword_to_pointer (key2, void *);
 881   return v1 && v2 && 0 == memcmp (v1, v2, h->user);
 882 }
 883
 884 uword
 885 string_key_sum (hash_t * h, uword key)
 886 {
 887   char *v = uword_to_pointer (key, char *);
 888   return hash_memory (v, strlen (v), 0);
 889 }
 890
 891 uword
 892 string_key_equal (hash_t * h, uword key1, uword key2)
 893 {
 894   void *v1 = uword_to_pointer (key1, void *);
 895   void *v2 = uword_to_pointer (key2, void *);
 896   return v1 && v2 && 0 == strcmp (v1, v2);
 897 }
 898
 899 u8 *
 900 string_key_format_pair (u8 * s, va_list * args)
 901 {
 902   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 903   void *v = va_arg (*args, void *);
 904   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 905   hash_t *h = hash_header (v);
 906   void *u = uword_to_pointer (p->key, void *);
 907
 908   s = format (s, "%s", u);
 909
 910   if (hash_value_bytes (h) > 0)
 911     s =
 912       format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
 913               hash_value_bytes (h));
 914
 915   return s;
 916 }
 917
 918 static u8 *
 919 hash_format_pair_default (u8 * s, va_list * args)
 920 {
 921   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 922   void *v = va_arg (*args, void *);
 923   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 924   hash_t *h = hash_header (v);
 925
 926   s = format (s, "0x%08x", p->key);
 927   if (hash_value_bytes (h) > 0)
 928     s =
 929       format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
 930               hash_value_bytes (h));
 931   return s;
 932 }
 933
 934 uword
 935 hash_bytes (void *v)
 936 {
 937   uword i, bytes;
 938   hash_t *h = hash_header (v);
 939
 940   if (!v)
 941     return 0;
 942
 943   bytes = vec_capacity (v, hash_header_bytes (v));
 944
 945   for (i = 0; i < hash_capacity (v); i++)
 946     {
 947       if (!hash_is_user (v, i))
 948         {
 949           hash_pair_union_t *p = get_pair (v, i);
 950           if (h->log2_pair_size > 0)
 951             bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect);
 952           else
 953             bytes += vec_capacity (p->indirect.pairs, 0);
 954         }
 955     }
 956   return bytes;
 957 }
 958
 959 u8 *
 960 format_hash (u8 * s, va_list * va)
 961 {
 962   void *v = va_arg (*va, void *);
 963   int verbose = va_arg (*va, int);
 964   hash_pair_t *p;
 965   hash_t *h = hash_header (v);
 966   uword i;
 967
 968   s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
 969               v, hash_elts (v), hash_capacity (v), hash_bytes (v));
 970
 971   {
 972     uword *occupancy = 0;
 973
 974     /* Count number of buckets with each occupancy. */
 975     for (i = 0; i < hash_capacity (v); i++)
 976       {
 977         uword j;
 978
 979         if (hash_is_user (v, i))
 980           {
 981             j = 1;
 982           }
 983         else
 984           {
 985             hash_pair_union_t *p = get_pair (v, i);
 986             if (h->log2_pair_size > 0)
 987               j = indirect_pair_get_len (&p->indirect);
 988             else
 989               j = vec_len (p->indirect.pairs);
 990           }
 991
 992         vec_validate (occupancy, j);
 993         occupancy[j]++;
 994       }
 995
 996     s = format (s, "  profile ");
 997     for (i = 0; i < vec_len (occupancy); i++)
 998       s = format (s, "%wd%c", occupancy[i],
 999                   i + 1 == vec_len (occupancy) ? '\n' : ' ');
1000
1001     s = format (s, "  lookup # of compares: ");
1002     for (i = 1; i < vec_len (occupancy); i++)
1003       s = format (s, "%wd: .%03d%c", i,
1004                   (1000 * i * occupancy[i]) / hash_elts (v),
1005                   i + 1 == vec_len (occupancy) ? '\n' : ' ');
1006
1007     vec_free (occupancy);
1008   }
1009
1010   if (verbose)
1011     {
1012       /* *INDENT-OFF* */
1013       hash_foreach_pair (p, v, {
1014         s = format (s, "  %U\n", h->format_pair, h->format_pair_arg, v, p);
1015       });
1016       /* *INDENT-ON* */
1017     }
1018
1019   return s;
1020 }
1021
1022 static uword
1023 unformat_hash_string_internal (unformat_input_t * input,
1024                                va_list * va, int is_vec)
1025 {
1026   uword *hash = va_arg (*va, uword *);
1027   int *result = va_arg (*va, int *);
1028   u8 *string = 0;
1029   uword *p;
1030
1031   if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
1032     return 0;
1033
1034   p = hash_get_mem (hash, string);
1035   if (p)
1036     *result = *p;
1037
1038   vec_free (string);
1039   return p ? 1 : 0;
1040 }
1041
1042 uword
1043 unformat_hash_vec_string (unformat_input_t * input, va_list * va)
1044 {
1045   return unformat_hash_string_internal (input, va, /* is_vec */ 1);
1046 }
1047
1048 uword
1049 unformat_hash_string (unformat_input_t * input, va_list * va)
1050 {
1051   return unformat_hash_string_internal (input, va, /* is_vec */ 0);
1052 }
1053
1054 clib_error_t *
1055 hash_validate (void *v)
1056 {
1057   hash_t *h = hash_header (v);
1058   uword i, j;
1059   uword *keys = 0;
1060   clib_error_t *error = 0;
1061
1062 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
1063
1064   for (i = 0; i < hash_capacity (v); i++)
1065     {
1066       hash_pair_union_t *pu = get_pair (v, i);
1067
1068       if (hash_is_user (v, i))
1069         {
1070           CHECK (pu->direct.key != 0);
1071           vec_add1 (keys, pu->direct.key);
1072         }
1073       else
1074         {
1075           hash_pair_t *p;
1076           hash_pair_indirect_t *pi = &pu->indirect;
1077           uword n;
1078
1079           n = h->log2_pair_size > 0
1080             ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
1081
1082           for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
1083             {
1084               /* Assert key uniqueness. */
1085               for (j = 0; j < vec_len (keys); j++)
1086                 CHECK (keys[j] != p->key);
1087               vec_add1 (keys, p->key);
1088             }
1089         }
1090     }
1091
1092   CHECK (vec_len (keys) == h->elts);
1093
1094   vec_free (keys);
1095 done:
1096   return error;
1097 }
1098
1099 /*
1100  * fd.io coding-style-patch-verification: ON
1101  *
1102  * Local Variables:
1103  * eval: (c-set-style "gnu")
1104  * End:
1105  */