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