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