src/vppinfra/hash.h

   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 #ifndef included_hash_h
  39 #define included_hash_h
  40
  41 #include <vppinfra/error.h>
  42 #include <vppinfra/format.h>
  43 #include <vppinfra/vec.h>
  44 #include <vppinfra/vector.h>
  45
  46 struct hash_header;
  47
  48 typedef uword (hash_key_sum_function_t) (struct hash_header *, uword key);
  49 typedef uword (hash_key_equal_function_t)
  50   (struct hash_header *, uword key1, uword key2);
  51
  52 /* Vector header for hash tables. */
  53 typedef struct hash_header
  54 {
  55   /* Number of elements in hash table. */
  56   uword elts;
  57
  58   /* Flags as follows. */
  59   u32 flags;
  60
  61   /* Set if user does not want table to auto-resize when sufficiently full. */
  62 #define HASH_FLAG_NO_AUTO_GROW          (1 << 0)
  63   /* Set if user does not want table to auto-resize when sufficiently empty. */
  64 #define HASH_FLAG_NO_AUTO_SHRINK        (1 << 1)
  65   /* Set when hash_next is in the process of iterating through this hash table. */
  66 #define HASH_FLAG_HASH_NEXT_IN_PROGRESS (1 << 2)
  67
  68   u32 log2_pair_size;
  69
  70   /* Function to compute the "sum" of a hash key.
  71      Hash function is this sum modulo the prime size of
  72      the hash table (vec_len (v)). */
  73   hash_key_sum_function_t *key_sum;
  74
  75   /* Special values for key_sum "function". */
  76 #define KEY_FUNC_NONE           (0)     /*< sum = key */
  77 #define KEY_FUNC_POINTER_UWORD  (1)     /*< sum = *(uword *) key */
  78 #define KEY_FUNC_POINTER_U32    (2)     /*< sum = *(u32 *) key */
  79 #define KEY_FUNC_STRING         (3)     /*< sum = string_key_sum, etc. */
  80 #define KEY_FUNC_MEM            (4)     /*< sum = mem_key_sum */
  81
  82   /* key comparison function */
  83   hash_key_equal_function_t *key_equal;
  84
  85   /* Hook for user's data.  Used to parameterize sum/equal functions. */
  86   any user;
  87
  88   /* Format a (k,v) pair */
  89   format_function_t *format_pair;
  90
  91   /* Format function arg */
  92   void *format_pair_arg;
  93
  94   /* Bit i is set if pair i is a user object (as opposed to being
  95      either zero or an indirect array of pairs). */
  96   uword *is_user;
  97 } hash_t;
  98
  99 /* Hash header size in bytes */
 100 always_inline uword
 101 hash_header_bytes (void *v)
 102 {
 103   return sizeof (hash_t);
 104 }
 105
 106 /* Returns a pointer to the hash header given the vector pointer */
 107 always_inline hash_t *
 108 hash_header (void *v)
 109 {
 110   return vec_header (v, hash_header_bytes (v));
 111 }
 112
 113 /* Number of elements in the hash table */
 114 always_inline uword
 115 hash_elts (void *v)
 116 {
 117   hash_t *h = hash_header (v);
 118   return v ? h->elts : 0;
 119 }
 120
 121 /* Number of elements the hash table can hold */
 122 always_inline uword
 123 hash_capacity (void *v)
 124 {
 125   return vec_len (v);
 126 }
 127
 128 /* Returns 1 if the hash pair contains user data */
 129 always_inline uword
 130 hash_is_user (void *v, uword i)
 131 {
 132   hash_t *h = hash_header (v);
 133   uword i0 = i / BITS (h->is_user[0]);
 134   uword i1 = i % BITS (h->is_user[0]);
 135   return (h->is_user[i0] & ((uword) 1 << i1)) != 0;
 136 }
 137
 138 /* Set the format function and format argument for a hash table */
 139 always_inline void
 140 hash_set_pair_format (void *v,
 141                       format_function_t * format_pair, void *format_pair_arg)
 142 {
 143   hash_t *h = hash_header (v);
 144   h->format_pair = format_pair;
 145   h->format_pair_arg = format_pair_arg;
 146 }
 147
 148 /* Set hash table flags */
 149 always_inline void
 150 hash_set_flags (void *v, uword flags)
 151 {
 152   hash_header (v)->flags |= flags;
 153 }
 154
 155 /* Key value pairs. */
 156 typedef struct
 157 {
 158   /* The Key */
 159   uword key;
 160
 161   /* The Value. Length is 2^log2_pair_size - 1. */
 162   uword value[0];
 163 } hash_pair_t;
 164
 165 /* The indirect pair structure
 166
 167     If log2_pair_size > 0 we overload hash pairs
 168     with indirect pairs for buckets with more than one
 169     pair. */
 170 typedef struct
 171 {
 172   /* pair vector */
 173   hash_pair_t *pairs;
 174   /* padding */
 175   u8 pad[sizeof (uword) - sizeof (hash_pair_t *)];
 176   /* allocated length */
 177   uword alloc_len;
 178 }
 179 hash_pair_indirect_t;
 180
 181 /* Direct / Indirect pair union */
 182 typedef union
 183 {
 184   hash_pair_t direct;
 185   hash_pair_indirect_t indirect;
 186 } hash_pair_union_t;
 187
 188 #define LOG2_ALLOC_BITS (5)
 189 #define PAIR_BITS       (BITS (uword) - LOG2_ALLOC_BITS)
 190
 191 /* Log2 number of bytes allocated in pairs array. */
 192 always_inline uword
 193 indirect_pair_get_log2_bytes (hash_pair_indirect_t * p)
 194 {
 195   return p->alloc_len >> PAIR_BITS;
 196 }
 197
 198 /* Get the length of an indirect pair */
 199 always_inline uword
 200 indirect_pair_get_len (hash_pair_indirect_t * p)
 201 {
 202   if (!p->pairs)
 203     return 0;
 204   else
 205     return p->alloc_len & (((uword) 1 << PAIR_BITS) - 1);
 206 }
 207
 208 /* Set the length of an indirect pair */
 209 always_inline void
 210 indirect_pair_set (hash_pair_indirect_t * p, uword log2_alloc, uword len)
 211 {
 212   ASSERT (len < ((uword) 1 << PAIR_BITS));
 213   ASSERT (log2_alloc < ((uword) 1 << LOG2_ALLOC_BITS));
 214   p->alloc_len = (log2_alloc << PAIR_BITS) | len;
 215 }
 216
 217 /* internal routine to fetch value for given key */
 218 uword *_hash_get (void *v, uword key);
 219
 220 /* internal routine to fetch value (key, value) pair for given key */
 221 hash_pair_t *_hash_get_pair (void *v, uword key);
 222
 223 /* internal routine to unset a (key, value) pair */
 224 void *_hash_unset (void *v, uword key, void *old_value);
 225
 226 /* internal routine to set a (key, value) pair, return the old value */
 227 void *_hash_set3 (void *v, uword key, void *value, void *old_value);
 228
 229 /* Resize a hash table */
 230 void *hash_resize (void *old, uword new_size);
 231
 232 /* duplicate a hash table */
 233 void *hash_dup (void *old);
 234
 235 /* Returns the number of bytes used by a hash table */
 236 uword hash_bytes (void *v);
 237
 238 /* Public macro to set a (key, value) pair, return the old value */
 239 #define hash_set3(h,key,value,old_value)                                \
 240 ({                                                                      \
 241   uword _v = (uword) (value);                                           \
 242   (h) = _hash_set3 ((h), (uword) (key), (void *) &_v, (old_value));     \
 243 })
 244
 245 /* Public macro to fetch value for given key */
 246 #define hash_get(h,key)         _hash_get ((h), (uword) (key))
 247
 248 /* Public macro to fetch value (key, value) pair for given key */
 249 #define hash_get_pair(h,key)    _hash_get_pair ((h), (uword) (key))
 250
 251 /* Public macro to set a (key, value) pair */
 252 #define hash_set(h,key,value)   hash_set3(h,key,value,0)
 253
 254 /* Public macro to set (key, 0) pair */
 255 #define hash_set1(h,key)        (h) = _hash_set3(h,(uword) (key),0,0)
 256
 257 /* Public macro to unset a (key, value) pair */
 258 #define hash_unset(h,key)       ((h) = _hash_unset ((h), (uword) (key),0))
 259
 260 /* Public macro to unset a (key, value) pair, return the old value */
 261 #define hash_unset3(h,key,old_value) ((h) = _hash_unset ((h), (uword) (key), (void *) (old_value)))
 262
 263 /* get/set/unset for pointer keys. */
 264
 265 /* Public macro to fetch value for given pointer key */
 266 #define hash_get_mem(h,key)     _hash_get ((h), pointer_to_uword (key))
 267
 268 /* Public macro to fetch (key, value) for given pointer key */
 269 #define hash_get_pair_mem(h,key) _hash_get_pair ((h), pointer_to_uword (key))
 270
 271 /* Public macro to set (key, value) for pointer key */
 272 #define hash_set_mem(h,key,value) hash_set3 (h, pointer_to_uword (key), (value), 0)
 273
 274 /* Public inline function allocate and copy key to use in hash for pointer key */
 275 always_inline void
 276 hash_set_mem_alloc (uword ** h, const void *key, uword v)
 277 {
 278   int objsize = __builtin_object_size (key, 0);
 279   size_t ksz = hash_header (*h)->user;
 280   void *copy;
 281   if (objsize > 0)
 282     {
 283       ASSERT (objsize == ksz);
 284       copy = clib_mem_alloc (objsize);
 285       clib_memcpy_fast (copy, key, objsize);
 286     }
 287   else
 288     {
 289       copy = clib_mem_alloc (ksz);
 290       clib_memcpy_fast (copy, key, ksz);
 291     }
 292   hash_set_mem (*h, copy, v);
 293 }
 294
 295 /* Public macro to set (key, 0) for pointer key */
 296 #define hash_set1_mem(h,key)     hash_set3 ((h), pointer_to_uword (key), 0, 0)
 297
 298 /* Public macro to unset (key, value) for pointer key */
 299 #define hash_unset_mem(h,key)    ((h) = _hash_unset ((h), pointer_to_uword (key),0))
 300
 301 /* Public inline function to unset pointer key and then free the key memory */
 302 always_inline void
 303 hash_unset_mem_free (uword ** h, const void *key)
 304 {
 305   hash_pair_t *hp = hash_get_pair_mem (*h, key);
 306   if (PREDICT_TRUE (hp != NULL))
 307     {
 308       void *_k = uword_to_pointer (hp->key, void *);
 309       hash_unset_mem (*h, _k);
 310       clib_mem_free (_k);
 311     }
 312 }
 313
 314 /* internal routine to free a hash table */
 315 extern void *_hash_free (void *v);
 316
 317 /* Public macro to free a hash table */
 318 #define hash_free(h) (h) = _hash_free ((h))
 319
 320 clib_error_t *hash_validate (void *v);
 321
 322 /* Public inline function to get the number of value bytes for a hash table */
 323 always_inline uword
 324 hash_value_bytes (hash_t * h)
 325 {
 326   hash_pair_t *p;
 327   return (sizeof (p->value[0]) << h->log2_pair_size) - sizeof (p->key);
 328 }
 329
 330 /* Public inline function to get log2(size of a (key,value) pair) */
 331 always_inline uword
 332 hash_pair_log2_bytes (hash_t * h)
 333 {
 334   uword log2_bytes = h->log2_pair_size;
 335   ASSERT (BITS (hash_pair_t) == 32 || BITS (hash_pair_t) == 64);
 336   if (BITS (hash_pair_t) == 32)
 337     log2_bytes += 2;
 338   else if (BITS (hash_pair_t) == 64)
 339     log2_bytes += 3;
 340   return log2_bytes;
 341 }
 342
 343 /* Public inline function to get size of a (key,value) pair */
 344 always_inline uword
 345 hash_pair_bytes (hash_t * h)
 346 {
 347   return (uword) 1 << hash_pair_log2_bytes (h);
 348 }
 349
 350 /* Public inline function to advance a pointer past one (key,value) pair */
 351 always_inline void *
 352 hash_forward1 (hash_t * h, void *v)
 353 {
 354   return (u8 *) v + hash_pair_bytes (h);
 355 }
 356
 357 /* Public inline function to advance a pointer past N (key,value) pairs */
 358 always_inline void *
 359 hash_forward (hash_t * h, void *v, uword n)
 360 {
 361   return (u8 *) v + ((n * sizeof (hash_pair_t)) << h->log2_pair_size);
 362 }
 363
 364 /** Iterate over hash pairs.
 365
 366     @param p    The current (key,value) pair. This should be of type
 367                 <code>(hash_pair_t *)</code>.
 368     @param v    The hash table to iterate.
 369     @param body The operation to perform on each (key,value) pair.
 370
 371     Executes the expression or code block @c body with each active hash pair.
 372 */
 373 /* A previous version of this macro made use of the hash_pair_union_t
 374  * structure; this version does not since that approach mightily upset
 375  * the static analysis tool. In the rare chance someone is reading this
 376  * code, pretend that _p below is of type hash_pair_union_t and that when
 377  * used as an rvalue it's really using one of the union members as the
 378  * rvalue. If you were confused before you might be marginally less
 379  * confused after.
 380  */
 381 #define hash_foreach_pair(p,v,body)                                         \
 382 do {                                                                        \
 383  __label__ _hash_foreach_done;                                              \
 384   hash_t * _h = hash_header (v);                                            \
 385   void * _p;                                                                \
 386   hash_pair_t * _q, * _q_end;                                               \
 387   uword _i, _i1, _id, _pair_increment;                                      \
 388                                                                             \
 389   _p = (v);                                                                 \
 390   _i = 0;                                                                   \
 391   _pair_increment = 1;                                                      \
 392   if ((v))                                                                  \
 393       _pair_increment = 1 << _h->log2_pair_size;                            \
 394   while (_i < hash_capacity (v))                                            \
 395     {                                                                       \
 396       _id = _h->is_user[_i / BITS (_h->is_user[0])];                        \
 397       _i1 = _i + BITS (_h->is_user[0]);                                     \
 398                                                                             \
 399       do {                                                                  \
 400         if (_id & 1)                                                        \
 401           {                                                                 \
 402             _q = _p;                                                        \
 403             _q_end = _q + _pair_increment;                                  \
 404           }                                                                 \
 405         else                                                                \
 406           {                                                                 \
 407             hash_pair_indirect_t * _pi = _p;                                \
 408             _q = _pi->pairs;                                                \
 409             if (_h->log2_pair_size > 0)                                     \
 410               _q_end = hash_forward (_h, _q, indirect_pair_get_len (_pi));  \
 411             else                                                            \
 412               _q_end = vec_end (_q);                                        \
 413           }                                                                 \
 414                                                                             \
 415         /* Loop through all elements in bucket.                             \
 416            Bucket may have 0 1 or more (indirect case) pairs. */            \
 417         while (_q < _q_end)                                                 \
 418           {                                                                 \
 419             uword _break_in_body = 1;                                       \
 420             (p) = _q;                                                       \
 421             do {                                                            \
 422               body;                                                         \
 423               _break_in_body = 0;                                           \
 424             } while (0);                                                    \
 425             if (_break_in_body)                                             \
 426               goto _hash_foreach_done;                                      \
 427             _q += _pair_increment;                                          \
 428           }                                                                 \
 429                                                                             \
 430         _p = (hash_pair_t *)_p + _pair_increment;                           \
 431         _id = _id / 2;                                                      \
 432         _i++;                                                               \
 433       } while (_i < _i1);                                                   \
 434     }                                                                       \
 435   _hash_foreach_done:                                                       \
 436   /* Be silent Mr. Compiler-Warning. */                                     \
 437   ;                                                                         \
 438  } while (0)
 439
 440 /* Iterate over key/value pairs
 441
 442     @param key_var the current key
 443     @param value_var the current value
 444     @param h the hash table to iterate across
 445     @param body the operation to perform on each (key_var,value_var) pair.
 446
 447     calls body with each active hash pair
 448 */
 449 /* Iterate over key/value pairs. */
 450 #define hash_foreach(key_var,value_var,h,body)                  \
 451 do {                                                            \
 452   hash_pair_t * _r;                                             \
 453   hash_foreach_pair (_r, (h), {                                 \
 454     (key_var) = (__typeof__ (key_var)) _r->key;                 \
 455     (value_var) = (__typeof__ (value_var)) _r->value[0];        \
 456     do { body; } while (0);                                     \
 457   });                                                           \
 458 } while (0)
 459
 460 /* Iterate over key/value pairs for pointer key hash tables
 461
 462     @param key_var the current key
 463     @param value_var the current value
 464     @param h the hash table to iterate across
 465     @param body the operation to perform on each (key_var,value_var) pair.
 466
 467     calls body with each active hash pair
 468 */
 469 #define hash_foreach_mem(key_var,value_var,h,body)                      \
 470 do {                                                                    \
 471   hash_pair_t * _r;                                                     \
 472   hash_foreach_pair (_r, (h), {                                         \
 473     (key_var) = (__typeof__ (key_var)) uword_to_pointer (_r->key, void *); \
 474     (value_var) = (__typeof__ (value_var)) _r->value[0];                \
 475     do { body; } while (0);                                             \
 476   });                                                                   \
 477 } while (0)
 478
 479 /* Support for iteration through hash table. */
 480
 481 /* This struct saves iteration state for hash_next.
 482    None of these fields are meant to be visible to the user.
 483    Hence, the cryptic short-hand names. */
 484 typedef struct
 485 {
 486   uword i, j, f;
 487 } hash_next_t;
 488
 489 hash_pair_t *hash_next (void *v, hash_next_t * hn);
 490
 491 void *_hash_create (uword elts, hash_t * h);
 492
 493 always_inline void
 494 hash_set_value_bytes (hash_t * h, uword value_bytes)
 495 {
 496   hash_pair_t *p;
 497   h->log2_pair_size =
 498     max_log2 ((sizeof (p->key) + value_bytes + sizeof (p->key) -
 499                1) / sizeof (p->key));
 500 }
 501
 502 #define hash_create2(_elts,_user,_value_bytes,               \
 503                      _key_sum,_key_equal,                    \
 504                      _format_pair,_format_pair_arg)          \
 505 ({                                                           \
 506   hash_t _h;                                                 \
 507   clib_memset (&_h, 0, sizeof (_h));                                 \
 508   _h.user = (_user);                                         \
 509   _h.key_sum   = (hash_key_sum_function_t *) (_key_sum);     \
 510   _h.key_equal = (_key_equal);                               \
 511   hash_set_value_bytes (&_h, (_value_bytes));                \
 512   _h.format_pair = (format_function_t *) (_format_pair);     \
 513   _h.format_pair_arg = (_format_pair_arg);                   \
 514   _hash_create ((_elts), &_h);                               \
 515 })
 516
 517 /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
 518    Public domain per: http://www.burtleburtle.net/bob/hash/doobs.html
 519    Thanks, Bob. */
 520
 521 #define hash_mix_step(a,b,c,s0,s1,s2)           \
 522 do {                                            \
 523   (a) -= (b) + (c); (a) ^= (c) >> (s0);         \
 524   (b) -= (c) + (a); (b) ^= (a) << (s1);         \
 525   (c) -= (a) + (b); (c) ^= (b) >> (s2);         \
 526 } while (0)
 527
 528 #define hash_mix32_step_1(a,b,c) hash_mix_step(a,b,c,13,8,13)
 529 #define hash_mix32_step_2(a,b,c) hash_mix_step(a,b,c,12,16,5)
 530 #define hash_mix32_step_3(a,b,c) hash_mix_step(a,b,c,3,10,15)
 531
 532 #define hash_mix64_step_1(a,b,c) hash_mix_step(a,b,c,43,9,8)
 533 #define hash_mix64_step_2(a,b,c) hash_mix_step(a,b,c,38,23,5)
 534 #define hash_mix64_step_3(a,b,c) hash_mix_step(a,b,c,35,49,11)
 535 #define hash_mix64_step_4(a,b,c) hash_mix_step(a,b,c,12,18,22)
 536
 537 /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
 538    Thanks, Bob. */
 539 #define hash_mix64(a0,b0,c0)                    \
 540 do {                                            \
 541   hash_mix64_step_1 (a0, b0, c0);               \
 542   hash_mix64_step_2 (a0, b0, c0);               \
 543   hash_mix64_step_3 (a0, b0, c0);               \
 544   hash_mix64_step_4 (a0, b0, c0);               \
 545 } while (0)                                     \
 546
 547 #define hash_mix32(a0,b0,c0)                    \
 548 do {                                            \
 549   hash_mix32_step_1 (a0, b0, c0);               \
 550   hash_mix32_step_2 (a0, b0, c0);               \
 551   hash_mix32_step_3 (a0, b0, c0);               \
 552 } while (0)                                     \
 553
 554 /* Finalize from Bob Jenkins lookup3.c */
 555
 556 always_inline uword
 557 hash32_rotate_left (u32 x, u32 i)
 558 {
 559   return (x << i) | (x >> (BITS (i) - i));
 560 }
 561
 562 #define hash_v3_mix32(a,b,c)                                    \
 563 do {                                                            \
 564   (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b);   \
 565   (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c);   \
 566   (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a);   \
 567   (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b);   \
 568   (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c);   \
 569   (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a);   \
 570 } while (0)
 571
 572 #define hash_v3_finalize32(a,b,c)                       \
 573 do {                                                    \
 574   (c) ^= (b); (c) -= hash32_rotate_left ((b), 14);      \
 575   (a) ^= (c); (a) -= hash32_rotate_left ((c), 11);      \
 576   (b) ^= (a); (b) -= hash32_rotate_left ((a), 25);      \
 577   (c) ^= (b); (c) -= hash32_rotate_left ((b), 16);      \
 578   (a) ^= (c); (a) -= hash32_rotate_left ((c),  4);      \
 579   (b) ^= (a); (b) -= hash32_rotate_left ((a), 14);      \
 580   (c) ^= (b); (c) -= hash32_rotate_left ((b), 24);      \
 581 } while (0)
 582
 583 /* 32 bit mixing/finalize in steps. */
 584
 585 #define hash_v3_mix32_step1(a,b,c)                              \
 586 do {                                                            \
 587   (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b);   \
 588   (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c);   \
 589 } while (0)
 590
 591 #define hash_v3_mix32_step2(a,b,c)                              \
 592 do {                                                            \
 593   (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a);   \
 594   (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b);   \
 595 } while (0)
 596
 597 #define hash_v3_mix32_step3(a,b,c)                              \
 598 do {                                                            \
 599   (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c);   \
 600   (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a);   \
 601 } while (0)
 602
 603 #define hash_v3_finalize32_step1(a,b,c)                 \
 604 do {                                                    \
 605   (c) ^= (b); (c) -= hash32_rotate_left ((b), 14);      \
 606   (a) ^= (c); (a) -= hash32_rotate_left ((c), 11);      \
 607 } while (0)
 608
 609 #define hash_v3_finalize32_step2(a,b,c)                 \
 610 do {                                                    \
 611   (b) ^= (a); (b) -= hash32_rotate_left ((a), 25);      \
 612   (c) ^= (b); (c) -= hash32_rotate_left ((b), 16);      \
 613 } while (0)
 614
 615 #define hash_v3_finalize32_step3(a,b,c)                 \
 616 do {                                                    \
 617   (a) ^= (c); (a) -= hash32_rotate_left ((c),  4);      \
 618   (b) ^= (a); (b) -= hash32_rotate_left ((a), 14);      \
 619   (c) ^= (b); (c) -= hash32_rotate_left ((b), 24);      \
 620 } while (0)
 621
 622 /* Vector v3 mixing/finalize. */
 623 #define hash_v3_mix_step_1_u32x(a,b,c)                          \
 624 do {                                                            \
 625   (a) -= (c); (a) ^= u32x_irotate_left ((c), 4); (c) += (b);    \
 626   (b) -= (a); (b) ^= u32x_irotate_left ((a), 6); (a) += (c);    \
 627   (c) -= (b); (c) ^= u32x_irotate_left ((b), 8); (b) += (a);    \
 628 } while (0)
 629
 630 #define hash_v3_mix_step_2_u32x(a,b,c)                          \
 631 do {                                                            \
 632   (a) -= (c); (a) ^= u32x_irotate_left ((c),16); (c) += (b);    \
 633   (b) -= (a); (b) ^= u32x_irotate_left ((a),19); (a) += (c);    \
 634   (c) -= (b); (c) ^= u32x_irotate_left ((b), 4); (b) += (a);    \
 635 } while (0)
 636
 637 #define hash_v3_finalize_step_1_u32x(a,b,c)             \
 638 do {                                                    \
 639   (c) ^= (b); (c) -= u32x_irotate_left ((b), 14);       \
 640   (a) ^= (c); (a) -= u32x_irotate_left ((c), 11);       \
 641   (b) ^= (a); (b) -= u32x_irotate_left ((a), 25);       \
 642 } while (0)
 643
 644 #define hash_v3_finalize_step_2_u32x(a,b,c)             \
 645 do {                                                    \
 646   (c) ^= (b); (c) -= u32x_irotate_left ((b), 16);       \
 647   (a) ^= (c); (a) -= u32x_irotate_left ((c),  4);       \
 648   (b) ^= (a); (b) -= u32x_irotate_left ((a), 14);       \
 649   (c) ^= (b); (c) -= u32x_irotate_left ((b), 24);       \
 650 } while (0)
 651
 652 #define hash_v3_mix_u32x(a,b,c)                 \
 653 do {                                            \
 654   hash_v3_mix_step_1_u32x(a,b,c);               \
 655   hash_v3_mix_step_2_u32x(a,b,c);               \
 656 } while (0)
 657
 658 #define hash_v3_finalize_u32x(a,b,c)            \
 659 do {                                            \
 660   hash_v3_finalize_step_1_u32x(a,b,c);          \
 661   hash_v3_finalize_step_2_u32x(a,b,c);          \
 662 } while (0)
 663
 664 extern uword hash_memory (void *p, word n_bytes, uword state);
 665
 666 extern uword mem_key_sum (hash_t * h, uword key);
 667 extern uword mem_key_equal (hash_t * h, uword key1, uword key2);
 668
 669 #define hash_create_mem(elts,key_bytes,value_bytes)     \
 670   hash_create2((elts),(key_bytes),(value_bytes),mem_key_sum,mem_key_equal,0,0)
 671
 672 extern uword vec_key_sum (hash_t * h, uword key);
 673 extern uword vec_key_equal (hash_t * h, uword key1, uword key2);
 674 extern u8 *vec_key_format_pair (u8 * s, va_list * args);
 675
 676 #define hash_create_vec(elts,key_bytes,value_bytes)     \
 677   hash_create2((elts),(key_bytes),(value_bytes),\
 678                vec_key_sum,vec_key_equal,vec_key_format_pair,0)
 679
 680 extern uword string_key_sum (hash_t * h, uword key);
 681 extern uword string_key_equal (hash_t * h, uword key1, uword key2);
 682 extern u8 *string_key_format_pair (u8 * s, va_list * args);
 683
 684 /*
 685  * Note: if you plan to put a hash into shared memory,
 686  * the key sum and key equal functions MUST be set to magic constants!
 687  * PIC means that whichever process sets up the hash won't have
 688  * the actual key sum functions at the same place, leading to
 689  * very hard-to-find bugs...
 690  */
 691
 692 #define hash_create_shmem(elts,key_bytes,value_bytes)           \
 693   hash_create2((elts),(key_bytes),(value_bytes),                \
 694                (hash_key_sum_function_t *) KEY_FUNC_MEM,        \
 695                (hash_key_equal_function_t *)KEY_FUNC_MEM,       \
 696                0, 0)
 697
 698 #define hash_create_string(elts,value_bytes)                    \
 699   hash_create2((elts),0,(value_bytes),                          \
 700                (hash_key_sum_function_t *) KEY_FUNC_STRING,     \
 701                (hash_key_equal_function_t *)KEY_FUNC_STRING,    \
 702                0, 0)
 703
 704 #define hash_create(elts,value_bytes)                           \
 705   hash_create2((elts),0,(value_bytes),                          \
 706                (hash_key_sum_function_t *) KEY_FUNC_NONE,       \
 707                (hash_key_equal_function_t *) KEY_FUNC_NONE,     \
 708                0,0)
 709
 710 #define hash_create_uword(elts,value_bytes)                             \
 711   hash_create2((elts),0,(value_bytes),                                  \
 712                (hash_key_sum_function_t *) KEY_FUNC_POINTER_UWORD,      \
 713                (hash_key_equal_function_t *) KEY_FUNC_POINTER_UWORD,    \
 714                0,0)
 715
 716 #define hash_create_u32(elts,value_bytes)                               \
 717   hash_create2((elts),0,(value_bytes),                                  \
 718                (hash_key_sum_function_t *) KEY_FUNC_POINTER_U32,        \
 719                (hash_key_equal_function_t *) KEY_FUNC_POINTER_U32,      \
 720                0,0)
 721
 722 u8 *format_hash (u8 * s, va_list * va);
 723
 724 /* Looks up input in hash table indexed by either vec string or
 725    c string (null terminated). */
 726 unformat_function_t unformat_hash_vec_string;
 727 unformat_function_t unformat_hash_string;
 728
 729 /* Main test routine. */
 730 int test_hash_main (unformat_input_t * input);
 731
 732 #endif /* included_hash_h */
 733
 734 /*
 735  * fd.io coding-style-patch-verification: ON
 736  *
 737  * Local Variables:
 738  * eval: (c-set-style "gnu")
 739  * End:
 740  */