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