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