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   vec_attr_t va = { .hdr_sz = sizeof (h[0]), .align = sizeof (hash_pair_t) };
 552
 553   /* Size of hash is power of 2 >= ELTS and larger than
 554      number of bits in is_user bitmap elements. */
 555   elts = clib_max (elts, BITS (h->is_user[0]));
 556   elts = 1ULL << max_log2 (elts);
 557
 558   log2_pair_size = 1;
 559   if (h_user)
 560     log2_pair_size = h_user->log2_pair_size;
 561
 562   va.elt_sz = (1 << log2_pair_size) * sizeof (hash_pair_t),
 563   v = _vec_alloc_internal (elts, &va);
 564   h = hash_header (v);
 565
 566   if (h_user)
 567     {
 568       h[0] = h_user[0];
 569       h->is_user = 0;
 570     }
 571
 572   vec_validate_aligned (
 573     h->is_user, ((elts / BITS (h->is_user[0])) * sizeof (h->is_user[0])) - 1,
 574     CLIB_CACHE_LINE_BYTES);
 575   h->log2_pair_size = log2_pair_size;
 576   h->elts = 0;
 577
 578   /* Default flags to never shrinking hash tables.
 579      Shrinking tables can cause "jackpot" cases. */
 580   if (!h_user)
 581     h->flags = HASH_FLAG_NO_AUTO_SHRINK;
 582
 583   if (!h->format_pair)
 584     {
 585       h->format_pair = hash_format_pair_default;
 586       h->format_pair_arg = 0;
 587     }
 588
 589   return v;
 590 }
 591
 592 __clib_export void *
 593 _hash_free (void *v)
 594 {
 595   hash_t *h = hash_header (v);
 596   hash_pair_union_t *p;
 597   uword i;
 598
 599   if (!v)
 600     return v;
 601
 602   /* We zero all freed memory in case user would be tempted to use it. */
 603   for (i = 0; i < hash_capacity (v); i++)
 604     {
 605       if (hash_is_user (v, i))
 606         continue;
 607       p = get_pair (v, i);
 608       if (h->log2_pair_size == 0)
 609         vec_free (p->indirect.pairs);
 610       else if (p->indirect.pairs)
 611         clib_mem_free (p->indirect.pairs);
 612     }
 613
 614   vec_free (h->is_user);
 615   vec_free_header (h);
 616
 617   return 0;
 618 }
 619
 620 static void *
 621 hash_resize_internal (void *old, uword new_size, uword free_old)
 622 {
 623   void *new;
 624   hash_pair_t *p;
 625
 626   new = 0;
 627   if (new_size > 0)
 628     {
 629       hash_t *h = old ? hash_header (old) : 0;
 630       new = _hash_create (new_size, h);
 631       hash_foreach_pair (p, old, {
 632         new = _hash_set3 (new, p->key, &p->value[0], 0);
 633       });
 634     }
 635
 636   if (free_old)
 637     hash_free (old);
 638   return new;
 639 }
 640
 641 __clib_export void *
 642 hash_resize (void *old, uword new_size)
 643 {
 644   return hash_resize_internal (old, new_size, 1);
 645 }
 646
 647 __clib_export void *
 648 hash_dup (void *old)
 649 {
 650   return hash_resize_internal (old, vec_len (old), 0);
 651 }
 652
 653 __clib_export void *
 654 _hash_set3 (void *v, uword key, void *value, void *old_value)
 655 {
 656   hash_t *h;
 657
 658   if (!v)
 659     v = hash_create (0, sizeof (uword));
 660
 661   h = hash_header (v);
 662   (void) lookup (v, key, SET, value, old_value);
 663
 664   if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
 665     {
 666       /* Resize when 3/4 full. */
 667       if (4 * (h->elts + 1) > 3 * vec_len (v))
 668         v = hash_resize (v, 2 * vec_len (v));
 669     }
 670
 671   return v;
 672 }
 673
 674 __clib_export uword
 675 vec_key_sum (hash_t * h, uword key)
 676 {
 677   void *v = uword_to_pointer (key, void *);
 678   return hash_memory (v, vec_len (v) * h->user, 0);
 679 }
 680
 681 __clib_export uword
 682 vec_key_equal (hash_t * h, uword key1, uword key2)
 683 {
 684   void *v1 = uword_to_pointer (key1, void *);
 685   void *v2 = uword_to_pointer (key2, void *);
 686   uword l1 = vec_len (v1);
 687   uword l2 = vec_len (v2);
 688   return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user);
 689 }
 690
 691 __clib_export u8 *
 692 vec_key_format_pair (u8 * s, va_list * args)
 693 {
 694   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 695   void *v = va_arg (*args, void *);
 696   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 697   hash_t *h = hash_header (v);
 698   void *u = uword_to_pointer (p->key, void *);
 699   int i;
 700
 701   switch (h->user)
 702     {
 703     case 1:
 704       s = format (s, "%v", u);
 705       break;
 706
 707     case 2:
 708       {
 709         u16 *w = u;
 710         for (i = 0; i < vec_len (w); i++)
 711           s = format (s, "0x%x, ", w[i]);
 712         break;
 713       }
 714
 715     case 4:
 716       {
 717         u32 *w = u;
 718         for (i = 0; i < vec_len (w); i++)
 719           s = format (s, "0x%x, ", w[i]);
 720         break;
 721       }
 722
 723     case 8:
 724       {
 725         u64 *w = u;
 726         for (i = 0; i < vec_len (w); i++)
 727           s = format (s, "0x%Lx, ", w[i]);
 728         break;
 729       }
 730
 731     default:
 732       s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
 733       break;
 734     }
 735
 736   if (hash_value_bytes (h) > 0)
 737     s = format (s, " -> 0x%wx", p->value[0]);
 738
 739   return s;
 740 }
 741
 742 __clib_export uword
 743 mem_key_sum (hash_t * h, uword key)
 744 {
 745   uword *v = uword_to_pointer (key, void *);
 746   return hash_memory (v, h->user, 0);
 747 }
 748
 749 __clib_export uword
 750 mem_key_equal (hash_t * h, uword key1, uword key2)
 751 {
 752   void *v1 = uword_to_pointer (key1, void *);
 753   void *v2 = uword_to_pointer (key2, void *);
 754   return v1 && v2 && 0 == memcmp (v1, v2, h->user);
 755 }
 756
 757 uword
 758 string_key_sum (hash_t * h, uword key)
 759 {
 760   char *v = uword_to_pointer (key, char *);
 761   return hash_memory (v, strlen (v), 0);
 762 }
 763
 764 uword
 765 string_key_equal (hash_t * h, uword key1, uword key2)
 766 {
 767   void *v1 = uword_to_pointer (key1, void *);
 768   void *v2 = uword_to_pointer (key2, void *);
 769   return v1 && v2 && 0 == strcmp (v1, v2);
 770 }
 771
 772 u8 *
 773 string_key_format_pair (u8 * s, va_list * args)
 774 {
 775   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 776   void *v = va_arg (*args, void *);
 777   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 778   hash_t *h = hash_header (v);
 779   void *u = uword_to_pointer (p->key, void *);
 780
 781   s = format (s, "%s", u);
 782
 783   if (hash_value_bytes (h) > 0)
 784     s =
 785       format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
 786               hash_value_bytes (h));
 787
 788   return s;
 789 }
 790
 791 static u8 *
 792 hash_format_pair_default (u8 * s, va_list * args)
 793 {
 794   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 795   void *v = va_arg (*args, void *);
 796   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 797   hash_t *h = hash_header (v);
 798
 799   s = format (s, "0x%08x", p->key);
 800   if (hash_value_bytes (h) > 0)
 801     s =
 802       format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
 803               hash_value_bytes (h));
 804   return s;
 805 }
 806
 807 __clib_export uword
 808 hash_bytes (void *v)
 809 {
 810   uword i, bytes;
 811   hash_t *h = hash_header (v);
 812
 813   if (!v)
 814     return 0;
 815
 816   bytes = vec_mem_size (v);
 817
 818   for (i = 0; i < hash_capacity (v); i++)
 819     {
 820       if (!hash_is_user (v, i))
 821         {
 822           hash_pair_union_t *p = get_pair (v, i);
 823           if (h->log2_pair_size > 0)
 824             bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect);
 825           else
 826             bytes += vec_mem_size (p->indirect.pairs);
 827         }
 828     }
 829   return bytes;
 830 }
 831
 832 __clib_export u8 *
 833 format_hash (u8 *s, va_list *va)
 834 {
 835   void *v = va_arg (*va, void *);
 836   int verbose = va_arg (*va, int);
 837   hash_pair_t *p;
 838   hash_t *h = hash_header (v);
 839   uword i;
 840
 841   s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
 842               v, hash_elts (v), hash_capacity (v), hash_bytes (v));
 843
 844   {
 845     uword *occupancy = 0;
 846
 847     /* Count number of buckets with each occupancy. */
 848     for (i = 0; i < hash_capacity (v); i++)
 849       {
 850         uword j;
 851
 852         if (hash_is_user (v, i))
 853           {
 854             j = 1;
 855           }
 856         else
 857           {
 858             hash_pair_union_t *p = get_pair (v, i);
 859             if (h->log2_pair_size > 0)
 860               j = indirect_pair_get_len (&p->indirect);
 861             else
 862               j = vec_len (p->indirect.pairs);
 863           }
 864
 865         vec_validate (occupancy, j);
 866         occupancy[j]++;
 867       }
 868
 869     s = format (s, "  profile ");
 870     for (i = 0; i < vec_len (occupancy); i++)
 871       s = format (s, "%wd%c", occupancy[i],
 872                   i + 1 == vec_len (occupancy) ? '\n' : ' ');
 873
 874     s = format (s, "  lookup # of compares: ");
 875     for (i = 1; i < vec_len (occupancy); i++)
 876       s = format (s, "%wd: .%03d%c", i,
 877                   (1000 * i * occupancy[i]) / hash_elts (v),
 878                   i + 1 == vec_len (occupancy) ? '\n' : ' ');
 879
 880     vec_free (occupancy);
 881   }
 882
 883   if (verbose)
 884     {
 885       hash_foreach_pair (p, v, {
 886         s = format (s, "  %U\n", h->format_pair, h->format_pair_arg, v, p);
 887       });
 888     }
 889
 890   return s;
 891 }
 892
 893 static uword
 894 unformat_hash_string_internal (unformat_input_t * input,
 895                                va_list * va, int is_vec)
 896 {
 897   uword *hash = va_arg (*va, uword *);
 898   int *result = va_arg (*va, int *);
 899   u8 *string = 0;
 900   uword *p;
 901
 902   if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
 903     return 0;
 904
 905   p = hash_get_mem (hash, string);
 906   if (p)
 907     *result = *p;
 908
 909   vec_free (string);
 910   return p ? 1 : 0;
 911 }
 912
 913 __clib_export uword
 914 unformat_hash_vec_string (unformat_input_t * input, va_list * va)
 915 {
 916   return unformat_hash_string_internal (input, va, /* is_vec */ 1);
 917 }
 918
 919 __clib_export uword
 920 unformat_hash_string (unformat_input_t * input, va_list * va)
 921 {
 922   return unformat_hash_string_internal (input, va, /* is_vec */ 0);
 923 }
 924
 925 __clib_export clib_error_t *
 926 hash_validate (void *v)
 927 {
 928   hash_t *h = hash_header (v);
 929   uword i, j;
 930   uword *keys = 0;
 931   clib_error_t *error = 0;
 932
 933 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
 934
 935   for (i = 0; i < hash_capacity (v); i++)
 936     {
 937       hash_pair_union_t *pu = get_pair (v, i);
 938
 939       if (hash_is_user (v, i))
 940         {
 941           CHECK (pu->direct.key != 0);
 942           vec_add1 (keys, pu->direct.key);
 943         }
 944       else
 945         {
 946           hash_pair_t *p;
 947           hash_pair_indirect_t *pi = &pu->indirect;
 948           uword n;
 949
 950           n = h->log2_pair_size > 0
 951             ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
 952
 953           for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
 954             {
 955               /* Assert key uniqueness. */
 956               for (j = 0; j < vec_len (keys); j++)
 957                 CHECK (keys[j] != p->key);
 958               vec_add1 (keys, p->key);
 959             }
 960         }
 961     }
 962
 963   CHECK (vec_len (keys) == h->elts);
 964
 965   vec_free (keys);
 966 done:
 967   return error;
 968 }
 969
 970 /*
 971  * fd.io coding-style-patch-verification: ON
 972  *
 973  * Local Variables:
 974  * eval: (c-set-style "gnu")
 975  * End:
 976  */