src/vppinfra/hash.c

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