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