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