vppinfra/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 macro to set (key, 0) for pointer key */
 277 #define hash_set1_mem(h,key)     hash_set3 ((h), pointer_to_uword (key), 0, 0)
 278
 279 /* Public macro to unset (key, value) for pointer key */
 280 #define hash_unset_mem(h,key)    ((h) = _hash_unset ((h), pointer_to_uword (key),0))
 281
 282 /* internal routine to free a hash table */
 283 extern void *_hash_free (void *v);
 284
 285 /* Public macro to free a hash table */
 286 #define hash_free(h) (h) = _hash_free ((h))
 287
 288 clib_error_t *hash_validate (void *v);
 289
 290 /* Public inline funcion to get the number of value bytes for a hash table */
 291 always_inline uword
 292 hash_value_bytes (hash_t * h)
 293 {
 294   hash_pair_t *p;
 295   return (sizeof (p->value[0]) << h->log2_pair_size) - sizeof (p->key);
 296 }
 297
 298 /* Public inline funcion to get log2(size of a (key,value) pair) */
 299 always_inline uword
 300 hash_pair_log2_bytes (hash_t * h)
 301 {
 302   uword log2_bytes = h->log2_pair_size;
 303   ASSERT (BITS (hash_pair_t) == 32 || BITS (hash_pair_t) == 64);
 304   if (BITS (hash_pair_t) == 32)
 305     log2_bytes += 2;
 306   else if (BITS (hash_pair_t) == 64)
 307     log2_bytes += 3;
 308   return log2_bytes;
 309 }
 310
 311 /* Public inline funcion to get size of a (key,value) pair */
 312 always_inline uword
 313 hash_pair_bytes (hash_t * h)
 314 {
 315   return (uword) 1 << hash_pair_log2_bytes (h);
 316 }
 317
 318 /* Public inline funcion to advance a pointer past one (key,value) pair */
 319 always_inline void *
 320 hash_forward1 (hash_t * h, void *v)
 321 {
 322   return (u8 *) v + hash_pair_bytes (h);
 323 }
 324
 325 /* Public inline funcion to advance a pointer past N (key,value) pairs */
 326 always_inline void *
 327 hash_forward (hash_t * h, void *v, uword n)
 328 {
 329   return (u8 *) v + ((n * sizeof (hash_pair_t)) << h->log2_pair_size);
 330 }
 331
 332 /* Iterate over hash pairs
 333     @param p the current (key,value) pair
 334     @param v the hash table to iterate
 335     @param body the operation to perform on each (key,value) pair.
 336     executes body with each active hash pair
 337 */
 338 #define hash_foreach_pair(p,v,body)                                         \
 339 do {                                                                        \
 340  __label__ _hash_foreach_done;                                              \
 341   hash_t * _h = hash_header (v);                                            \
 342   hash_pair_union_t * _p;                                                   \
 343   hash_pair_t * _q, * _q_end;                                               \
 344   uword _i, _i1, _id, _pair_increment;                                      \
 345                                                                             \
 346   _p = (hash_pair_union_t *) (v);                                           \
 347   _i = 0;                                                                   \
 348   _pair_increment = 1;                                                      \
 349   if ((v))                                                                  \
 350       _pair_increment = 1 << _h->log2_pair_size;                            \
 351   while (_i < hash_capacity (v))                                            \
 352     {                                                                       \
 353       _id = _h->is_user[_i / BITS (_h->is_user[0])];                        \
 354       _i1 = _i + BITS (_h->is_user[0]);                                     \
 355                                                                             \
 356       do {                                                                  \
 357         if (_id & 1)                                                        \
 358           {                                                                 \
 359             _q = &_p->direct;                                               \
 360             _q_end = _q + _pair_increment;                                  \
 361           }                                                                 \
 362         else                                                                \
 363           {                                                                 \
 364             hash_pair_indirect_t * _pi = &_p->indirect;                     \
 365             _q = _pi->pairs;                                                \
 366             if (_h->log2_pair_size > 0)                                     \
 367               _q_end = hash_forward (_h, _q, indirect_pair_get_len (_pi));  \
 368             else                                                            \
 369               _q_end = vec_end (_q);                                        \
 370           }                                                                 \
 371                                                                             \
 372         /* Loop through all elements in bucket.                             \
 373            Bucket may have 0 1 or more (indirect case) pairs. */            \
 374         while (_q < _q_end)                                                 \
 375           {                                                                 \
 376             uword _break_in_body = 1;                                       \
 377             (p) = _q;                                                       \
 378             do {                                                            \
 379               body;                                                         \
 380               _break_in_body = 0;                                           \
 381             } while (0);                                                    \
 382             if (_break_in_body)                                             \
 383               goto _hash_foreach_done;                                      \
 384             _q += _pair_increment;                                          \
 385           }                                                                 \
 386                                                                             \
 387         _p = (hash_pair_union_t *) (&_p->direct + _pair_increment);         \
 388         _id = _id / 2;                                                      \
 389         _i++;                                                               \
 390       } while (_i < _i1);                                                   \
 391     }                                                                       \
 392   _hash_foreach_done:                                                       \
 393   /* Be silent Mr. Compiler-Warning. */                                     \
 394   ;                                                                         \
 395  } while (0)
 396
 397 /* Iterate over key/value pairs
 398
 399     @param key_var the current key
 400     @param value_var the current value
 401     @param h the hash table to iterate across
 402     @param body the operation to perform on each (key_var,value_var) pair.
 403
 404     calls body with each active hash pair
 405 */
 406 /* Iteratate over key/value pairs. */
 407 #define hash_foreach(key_var,value_var,h,body)                  \
 408 do {                                                            \
 409   hash_pair_t * _r;                                             \
 410   hash_foreach_pair (_r, (h), {                                 \
 411     (key_var) = (__typeof__ (key_var)) _r->key;                 \
 412     (value_var) = (__typeof__ (value_var)) _r->value[0];        \
 413     do { body; } while (0);                                     \
 414   });                                                           \
 415 } while (0)
 416
 417 /* Iterate over key/value pairs for pointer key hash tables
 418
 419     @param key_var the current key
 420     @param value_var the current value
 421     @param h the hash table to iterate across
 422     @param body the operation to perform on each (key_var,value_var) pair.
 423
 424     calls body with each active hash pair
 425 */
 426 #define hash_foreach_mem(key_var,value_var,h,body)                      \
 427 do {                                                                    \
 428   hash_pair_t * _r;                                                     \
 429   hash_foreach_pair (_r, (h), {                                         \
 430     (key_var) = (__typeof__ (key_var)) uword_to_pointer (_r->key, void *); \
 431     (value_var) = (__typeof__ (value_var)) _r->value[0];                \
 432     do { body; } while (0);                                             \
 433   });                                                                   \
 434 } while (0)
 435
 436 /* Support for iteration through hash table. */
 437
 438 /* This struct saves iteration state for hash_next.
 439    None of these fields are meant to be visible to the user.
 440    Hence, the cryptic short-hand names. */
 441 typedef struct
 442 {
 443   uword i, j, f;
 444 } hash_next_t;
 445
 446 hash_pair_t *hash_next (void *v, hash_next_t * hn);
 447
 448 void *_hash_create (uword elts, hash_t * h);
 449
 450 always_inline void
 451 hash_set_value_bytes (hash_t * h, uword value_bytes)
 452 {
 453   hash_pair_t *p;
 454   h->log2_pair_size =
 455     max_log2 ((sizeof (p->key) + value_bytes + sizeof (p->key) -
 456                1) / sizeof (p->key));
 457 }
 458
 459 #define hash_create2(_elts,_user,_value_bytes,               \
 460                      _key_sum,_key_equal,                    \
 461                      _format_pair,_format_pair_arg)          \
 462 ({                                                           \
 463   hash_t _h;                                                 \
 464   memset (&_h, 0, sizeof (_h));                              \
 465   _h.user = (_user);                                         \
 466   _h.key_sum   = (hash_key_sum_function_t *) (_key_sum);     \
 467   _h.key_equal = (_key_equal);                               \
 468   hash_set_value_bytes (&_h, (_value_bytes));                \
 469   _h.format_pair = (format_function_t *) (_format_pair);     \
 470   _h.format_pair_arg = (_format_pair_arg);                   \
 471   _hash_create ((_elts), &_h);                               \
 472 })
 473
 474 /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
 475    Public domain per: http://www.burtleburtle.net/bob/hash/doobs.html
 476    Thanks, Bob. */
 477
 478 #define hash_mix_step(a,b,c,s0,s1,s2)           \
 479 do {                                            \
 480   (a) -= (b) + (c); (a) ^= (c) >> (s0);         \
 481   (b) -= (c) + (a); (b) ^= (a) << (s1);         \
 482   (c) -= (a) + (b); (c) ^= (b) >> (s2);         \
 483 } while (0)
 484
 485 #define hash_mix32_step_1(a,b,c) hash_mix_step(a,b,c,13,8,13)
 486 #define hash_mix32_step_2(a,b,c) hash_mix_step(a,b,c,12,16,5)
 487 #define hash_mix32_step_3(a,b,c) hash_mix_step(a,b,c,3,10,15)
 488
 489 #define hash_mix64_step_1(a,b,c) hash_mix_step(a,b,c,43,9,8)
 490 #define hash_mix64_step_2(a,b,c) hash_mix_step(a,b,c,38,23,5)
 491 #define hash_mix64_step_3(a,b,c) hash_mix_step(a,b,c,35,49,11)
 492 #define hash_mix64_step_4(a,b,c) hash_mix_step(a,b,c,12,18,22)
 493
 494 /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
 495    Thanks, Bob. */
 496 #define hash_mix64(a0,b0,c0)                    \
 497 do {                                            \
 498   hash_mix64_step_1 (a0, b0, c0);               \
 499   hash_mix64_step_2 (a0, b0, c0);               \
 500   hash_mix64_step_3 (a0, b0, c0);               \
 501   hash_mix64_step_4 (a0, b0, c0);               \
 502 } while (0)                                     \
 503
 504 #define hash_mix32(a0,b0,c0)                    \
 505 do {                                            \
 506   hash_mix32_step_1 (a0, b0, c0);               \
 507   hash_mix32_step_2 (a0, b0, c0);               \
 508   hash_mix32_step_3 (a0, b0, c0);               \
 509 } while (0)                                     \
 510
 511 /* Finalize from Bob Jenkins lookup3.c */
 512
 513 always_inline uword
 514 hash32_rotate_left (u32 x, u32 i)
 515 {
 516   return (x << i) | (x >> (BITS (i) - i));
 517 }
 518
 519 #define hash_v3_mix32(a,b,c)                                    \
 520 do {                                                            \
 521   (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b);   \
 522   (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c);   \
 523   (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a);   \
 524   (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b);   \
 525   (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c);   \
 526   (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a);   \
 527 } while (0)
 528
 529 #define hash_v3_finalize32(a,b,c)                       \
 530 do {                                                    \
 531   (c) ^= (b); (c) -= hash32_rotate_left ((b), 14);      \
 532   (a) ^= (c); (a) -= hash32_rotate_left ((c), 11);      \
 533   (b) ^= (a); (b) -= hash32_rotate_left ((a), 25);      \
 534   (c) ^= (b); (c) -= hash32_rotate_left ((b), 16);      \
 535   (a) ^= (c); (a) -= hash32_rotate_left ((c),  4);      \
 536   (b) ^= (a); (b) -= hash32_rotate_left ((a), 14);      \
 537   (c) ^= (b); (c) -= hash32_rotate_left ((b), 24);      \
 538 } while (0)
 539
 540 /* 32 bit mixing/finalize in steps. */
 541
 542 #define hash_v3_mix32_step1(a,b,c)                              \
 543 do {                                                            \
 544   (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b);   \
 545   (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c);   \
 546 } while (0)
 547
 548 #define hash_v3_mix32_step2(a,b,c)                              \
 549 do {                                                            \
 550   (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a);   \
 551   (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b);   \
 552 } while (0)
 553
 554 #define hash_v3_mix32_step3(a,b,c)                              \
 555 do {                                                            \
 556   (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c);   \
 557   (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a);   \
 558 } while (0)
 559
 560 #define hash_v3_finalize32_step1(a,b,c)                 \
 561 do {                                                    \
 562   (c) ^= (b); (c) -= hash32_rotate_left ((b), 14);      \
 563   (a) ^= (c); (a) -= hash32_rotate_left ((c), 11);      \
 564 } while (0)
 565
 566 #define hash_v3_finalize32_step2(a,b,c)                 \
 567 do {                                                    \
 568   (b) ^= (a); (b) -= hash32_rotate_left ((a), 25);      \
 569   (c) ^= (b); (c) -= hash32_rotate_left ((b), 16);      \
 570 } while (0)
 571
 572 #define hash_v3_finalize32_step3(a,b,c)                 \
 573 do {                                                    \
 574   (a) ^= (c); (a) -= hash32_rotate_left ((c),  4);      \
 575   (b) ^= (a); (b) -= hash32_rotate_left ((a), 14);      \
 576   (c) ^= (b); (c) -= hash32_rotate_left ((b), 24);      \
 577 } while (0)
 578
 579 /* Vector v3 mixing/finalize. */
 580 #define hash_v3_mix_step_1_u32x(a,b,c)                          \
 581 do {                                                            \
 582   (a) -= (c); (a) ^= u32x_irotate_left ((c), 4); (c) += (b);    \
 583   (b) -= (a); (b) ^= u32x_irotate_left ((a), 6); (a) += (c);    \
 584   (c) -= (b); (c) ^= u32x_irotate_left ((b), 8); (b) += (a);    \
 585 } while (0)
 586
 587 #define hash_v3_mix_step_2_u32x(a,b,c)                          \
 588 do {                                                            \
 589   (a) -= (c); (a) ^= u32x_irotate_left ((c),16); (c) += (b);    \
 590   (b) -= (a); (b) ^= u32x_irotate_left ((a),19); (a) += (c);    \
 591   (c) -= (b); (c) ^= u32x_irotate_left ((b), 4); (b) += (a);    \
 592 } while (0)
 593
 594 #define hash_v3_finalize_step_1_u32x(a,b,c)             \
 595 do {                                                    \
 596   (c) ^= (b); (c) -= u32x_irotate_left ((b), 14);       \
 597   (a) ^= (c); (a) -= u32x_irotate_left ((c), 11);       \
 598   (b) ^= (a); (b) -= u32x_irotate_left ((a), 25);       \
 599 } while (0)
 600
 601 #define hash_v3_finalize_step_2_u32x(a,b,c)             \
 602 do {                                                    \
 603   (c) ^= (b); (c) -= u32x_irotate_left ((b), 16);       \
 604   (a) ^= (c); (a) -= u32x_irotate_left ((c),  4);       \
 605   (b) ^= (a); (b) -= u32x_irotate_left ((a), 14);       \
 606   (c) ^= (b); (c) -= u32x_irotate_left ((b), 24);       \
 607 } while (0)
 608
 609 #define hash_v3_mix_u32x(a,b,c)                 \
 610 do {                                            \
 611   hash_v3_mix_step_1_u32x(a,b,c);               \
 612   hash_v3_mix_step_2_u32x(a,b,c);               \
 613 } while (0)
 614
 615 #define hash_v3_finalize_u32x(a,b,c)            \
 616 do {                                            \
 617   hash_v3_finalize_step_1_u32x(a,b,c);          \
 618   hash_v3_finalize_step_2_u32x(a,b,c);          \
 619 } while (0)
 620
 621 extern uword hash_memory (void *p, word n_bytes, uword state);
 622
 623 extern uword mem_key_sum (hash_t * h, uword key);
 624 extern uword mem_key_equal (hash_t * h, uword key1, uword key2);
 625
 626 #define hash_create_mem(elts,key_bytes,value_bytes)     \
 627   hash_create2((elts),(key_bytes),(value_bytes),mem_key_sum,mem_key_equal,0,0)
 628
 629 extern uword vec_key_sum (hash_t * h, uword key);
 630 extern uword vec_key_equal (hash_t * h, uword key1, uword key2);
 631 extern u8 *vec_key_format_pair (u8 * s, va_list * args);
 632
 633 #define hash_create_vec(elts,key_bytes,value_bytes)     \
 634   hash_create2((elts),(key_bytes),(value_bytes),\
 635                vec_key_sum,vec_key_equal,vec_key_format_pair,0)
 636
 637 extern uword string_key_sum (hash_t * h, uword key);
 638 extern uword string_key_equal (hash_t * h, uword key1, uword key2);
 639 extern u8 *string_key_format_pair (u8 * s, va_list * args);
 640
 641 #define hash_create_string(elts,value_bytes)                    \
 642   hash_create2((elts),0,(value_bytes),                          \
 643                (hash_key_sum_function_t *) KEY_FUNC_STRING,     \
 644                (hash_key_equal_function_t *)KEY_FUNC_STRING,    \
 645                0, 0)
 646
 647 #define hash_create(elts,value_bytes)                           \
 648   hash_create2((elts),0,(value_bytes),                          \
 649                (hash_key_sum_function_t *) KEY_FUNC_NONE,       \
 650                (hash_key_equal_function_t *) KEY_FUNC_NONE,     \
 651                0,0)
 652
 653 #define hash_create_uword(elts,value_bytes)                             \
 654   hash_create2((elts),0,(value_bytes),                                  \
 655                (hash_key_sum_function_t *) KEY_FUNC_POINTER_UWORD,      \
 656                (hash_key_equal_function_t *) KEY_FUNC_POINTER_UWORD,    \
 657                0,0)
 658
 659 #define hash_create_u32(elts,value_bytes)                               \
 660   hash_create2((elts),0,(value_bytes),                                  \
 661                (hash_key_sum_function_t *) KEY_FUNC_POINTER_U32,        \
 662                (hash_key_equal_function_t *) KEY_FUNC_POINTER_U32,      \
 663                0,0)
 664
 665 u8 *format_hash (u8 * s, va_list * va);
 666
 667 /* Looks up input in hash table indexed by either vec string or
 668    c string (null terminated). */
 669 unformat_function_t unformat_hash_vec_string;
 670 unformat_function_t unformat_hash_string;
 671
 672 /* Main test routine. */
 673 int test_hash_main (unformat_input_t * input);
 674
 675 #endif /* included_hash_h */
 676
 677 /*
 678  * fd.io coding-style-patch-verification: ON
 679  *
 680  * Local Variables:
 681  * eval: (c-set-style "gnu")
 682  * End:
 683  */