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