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