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