vppinfra/vppinfra/hash.h

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16   Copyright (c) 2001-2005 Eliot Dresselhaus
  17
  18   Permission is hereby granted, free of charge, to any person obtaining
  19   a copy of this software and associated documentation files (the
  20   "Software"), to deal in the Software without restriction, including
  21   without limitation the rights to use, copy, modify, merge, publish,
  22   distribute, sublicense, and/or sell copies of the Software, and to
  23   permit persons to whom the Software is furnished to do so, subject to
  24   the following conditions:
  25
  26   The above copyright notice and this permission notice shall be
  27   included in all copies or substantial portions of the Software.
  28
  29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  36 */
  37
  38 #ifndef included_hash_h
  39 #define included_hash_h
  40
  41 #include <vppinfra/error.h>
  42 #include <vppinfra/format.h>
  43 #include <vppinfra/vec.h>
  44 #include <vppinfra/vector.h>
  45
  46 struct hash_header;
  47
  48 typedef uword (hash_key_sum_function_t)
  49   (struct hash_header *, uword key);
  50 typedef uword (hash_key_equal_function_t)
  51   (struct hash_header *, uword key1, uword key2);
  52
  53 /* Vector header for hash tables. */
  54 typedef struct hash_header {
  55   /* Number of elements in hash table. */
  56   uword elts;
  57
  58   /* Flags as follows. */
  59   u32 flags;
  60
  61   /* Set if user does not want table to auto-resize when sufficiently full. */
  62 #define HASH_FLAG_NO_AUTO_GROW          (1 << 0)
  63   /* Set if user does not want table to auto-resize when sufficiently empty. */
  64 #define HASH_FLAG_NO_AUTO_SHRINK        (1 << 1)
  65   /* Set when hash_next is in the process of iterating through this hash table. */
  66 #define HASH_FLAG_HASH_NEXT_IN_PROGRESS (1 << 2)
  67
  68   u32 log2_pair_size;
  69
  70   /* Function to compute the "sum" of a hash key.
  71      Hash function is this sum modulo the prime size of
  72      the hash table (vec_len (v)). */
  73   hash_key_sum_function_t * key_sum;
  74
  75   /* Special values for key_sum "function". */
  76 #define KEY_FUNC_NONE           (0) /*< sum = key */
  77 #define KEY_FUNC_POINTER_UWORD  (1) /*< sum = *(uword *) key */
  78 #define KEY_FUNC_POINTER_U32    (2) /*< sum = *(u32 *) key */
  79 #define KEY_FUNC_STRING         (3) /*< sum = string_key_sum, etc. */
  80
  81   /* key comparison function */
  82   hash_key_equal_function_t * key_equal;
  83
  84   /* Hook for user's data.  Used to parameterize sum/equal functions. */
  85   any user;
  86
  87   /* Format a (k,v) pair */
  88   format_function_t * format_pair;
  89
  90   /* Format function arg */
  91   void * format_pair_arg;
  92
  93   /* Bit i is set if pair i is a user object (as opposed to being
  94      either zero or an indirect array of pairs). */
  95   uword is_user[0];
  96 } hash_t;
  97
  98 /* Hash header size in bytes */
  99 always_inline uword hash_header_bytes (void * v)
 100 {
 101   hash_t * h;
 102   uword is_user_bytes = (sizeof (h->is_user[0]) * vec_len (v)) / BITS (h->is_user[0]);
 103   return sizeof (h[0]) + is_user_bytes;
 104 }
 105
 106 /* Returns a pointer to the hash header given the vector pointer */
 107 always_inline hash_t * hash_header (void * v)
 108 { return vec_header (v, hash_header_bytes (v)); }
 109
 110 /* Number of elements in the hash table */
 111 always_inline uword hash_elts (void * v)
 112 {
 113   hash_t * h = hash_header (v);
 114   return v ? h->elts : 0;
 115 }
 116
 117 /* Number of elements the hash table can hold */
 118 always_inline uword hash_capacity (void * v)
 119 { return vec_len (v); }
 120
 121 /* Returns 1 if the hash pair contains user data */
 122 always_inline uword hash_is_user (void * v, uword i)
 123 {
 124   hash_t * h = hash_header (v);
 125   uword i0 = i / BITS(h->is_user[0]);
 126   uword i1 = i % BITS(h->is_user[0]);
 127   return (h->is_user[i0] & ((uword) 1 << i1)) != 0;
 128 }
 129
 130 /* Set the format function and format argument for a hash table */
 131 always_inline void
 132 hash_set_pair_format (void * v,
 133                       format_function_t * format_pair,
 134                       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 hash_set_flags (void * v, uword flags)
 143 { hash_header (v)->flags |= flags; }
 144
 145 /* Key value pairs. */
 146 typedef struct {
 147   /* The Key */
 148   uword key;
 149
 150   /* The Value. Length is 2^log2_pair_size - 1. */
 151   uword value[0];
 152 } hash_pair_t;
 153
 154 /* The indirect pair structure
 155
 156     If log2_pair_size > 0 we overload hash pairs
 157     with indirect pairs for buckets with more than one
 158     pair. */
 159 typedef struct {
 160   /* pair vector */
 161   hash_pair_t * pairs;
 162   /* padding */
 163   u8 pad[sizeof(uword) - sizeof (hash_pair_t *)];
 164   /* allocated length */
 165   uword alloc_len;
 166 } hash_pair_indirect_t;
 167
 168 /* Direct / Indirect pair union */
 169 typedef union {
 170     hash_pair_t direct;
 171     hash_pair_indirect_t indirect;
 172 } hash_pair_union_t;
 173
 174 #define LOG2_ALLOC_BITS (5)
 175 #define PAIR_BITS       (BITS (uword) - LOG2_ALLOC_BITS)
 176
 177 /* Log2 number of bytes allocated in pairs array. */
 178 always_inline uword indirect_pair_get_log2_bytes (hash_pair_indirect_t * p)
 179 { return p->alloc_len >> PAIR_BITS; }
 180
 181 /* Get the length of an indirect pair */
 182 always_inline uword
 183 indirect_pair_get_len (hash_pair_indirect_t * p)
 184 {
 185   if (! p->pairs)
 186     return 0;
 187   else
 188     return p->alloc_len & (((uword) 1 << PAIR_BITS) - 1);
 189 }
 190
 191 /* Set the length of an indirect pair */
 192 always_inline void
 193 indirect_pair_set (hash_pair_indirect_t * p,
 194                                uword log2_alloc,
 195                                uword len)
 196 {
 197   ASSERT (len < ((uword) 1 << PAIR_BITS));
 198   ASSERT (log2_alloc < ((uword) 1 << LOG2_ALLOC_BITS));
 199   p->alloc_len = (log2_alloc << PAIR_BITS) | len;
 200 }
 201
 202 /* internal routine to fetch value for given key */
 203 uword * _hash_get (void * v, uword key);
 204
 205 /* internal routine to fetch value (key, value) pair for given key */
 206 hash_pair_t * _hash_get_pair (void * v, uword key);
 207
 208 /* internal routine to unset a (key, value) pair */
 209 void *  _hash_unset (void * v, uword key, void * old_value);
 210
 211 /* internal routine to set a (key, value) pair, return the old value */
 212 void * _hash_set3 (void * v, uword key, void * value, void * old_value);
 213
 214 /* Resize a hash table */
 215 void * hash_resize (void * old, uword new_size);
 216
 217 /* duplicate a hash table */
 218 void * hash_dup (void * old);
 219
 220 /* Returns the number of bytes used by a hash table */
 221 uword hash_bytes (void * v);
 222
 223 /* Public macro to set a (key, value) pair, return the old value */
 224 #define hash_set3(h,key,value,old_value)                                \
 225 ({                                                                      \
 226   uword _v = (uword) (value);                                           \
 227   (h) = _hash_set3 ((h), (uword) (key), (void *) &_v, (old_value));     \
 228 })
 229
 230 /* Public macro to fetch value for given key */
 231 #define hash_get(h,key)         _hash_get ((h), (uword) (key))
 232
 233 /* Public macro to fetch value (key, value) pair for given key */
 234 #define hash_get_pair(h,key)    _hash_get_pair ((h), (uword) (key))
 235
 236 /* Public macro to set a (key, value) pair */
 237 #define hash_set(h,key,value)   hash_set3(h,key,value,0)
 238
 239 /* Public macro to set (key, 0) pair */
 240 #define hash_set1(h,key)        (h) = _hash_set3(h,(uword) (key),0,0)
 241
 242 /* Public macro to unset a (key, value) pair */
 243 #define hash_unset(h,key)       ((h) = _hash_unset ((h), (uword) (key),0))
 244
 245 /* Public macro to unset a (key, value) pair, return the old value */
 246 #define hash_unset3(h,key,old_value) ((h) = _hash_unset ((h), (uword) (key), (void *) (old_value)))
 247
 248 /* get/set/unset for pointer keys. */
 249
 250 /* Public macro to fetch value for given pointer key */
 251 #define hash_get_mem(h,key)     _hash_get ((h), pointer_to_uword (key))
 252
 253 /* Public macro to fetch (key, value) for given pointer key */
 254 #define hash_get_pair_mem(h,key) _hash_get_pair ((h), pointer_to_uword (key))
 255
 256 /* Public macro to set (key, value) for pointer key */
 257 #define hash_set_mem(h,key,value) hash_set3 (h, pointer_to_uword (key), (value), 0)
 258
 259 /* Public macro to set (key, 0) for pointer key */
 260 #define hash_set1_mem(h,key)     hash_set3 ((h), pointer_to_uword (key), 0, 0)
 261
 262 /* Public macro to unset (key, value) for pointer key */
 263 #define hash_unset_mem(h,key)    ((h) = _hash_unset ((h), pointer_to_uword (key),0))
 264
 265 /* internal routine to free a hash table */
 266 extern void * _hash_free (void * v);
 267
 268 /* Public macro to free a hash table */
 269 #define hash_free(h) (h) = _hash_free ((h))
 270
 271 clib_error_t * hash_validate (void * v);
 272
 273 /* Public inline funcion to get the number of value bytes for a hash table */
 274 always_inline uword hash_value_bytes (hash_t * h)
 275 {
 276   hash_pair_t * p;
 277   return (sizeof (p->value[0]) << h->log2_pair_size) - sizeof (p->key);
 278 }
 279
 280 /* Public inline funcion to get log2(size of a (key,value) pair) */
 281 always_inline uword hash_pair_log2_bytes (hash_t * h)
 282 {
 283   uword log2_bytes = h->log2_pair_size;
 284   ASSERT (BITS (hash_pair_t) == 32
 285           || BITS (hash_pair_t) == 64);
 286   if (BITS (hash_pair_t) == 32)
 287     log2_bytes += 2;
 288   else if (BITS (hash_pair_t) == 64)
 289     log2_bytes += 3;
 290   return log2_bytes;
 291 }
 292
 293 /* Public inline funcion to get size of a (key,value) pair */
 294 always_inline uword hash_pair_bytes (hash_t * h)
 295 { return (uword) 1 << hash_pair_log2_bytes (h); }
 296
 297 /* Public inline funcion to advance a pointer past one (key,value) pair */
 298 always_inline void * hash_forward1 (hash_t * h, void * v)
 299 { return (u8 *) v + hash_pair_bytes (h); }
 300
 301 /* Public inline funcion to advance a pointer past N (key,value) pairs */
 302 always_inline void * hash_forward (hash_t * h, void * v, uword n)
 303 { return (u8 *) v + ((n * sizeof (hash_pair_t)) << h->log2_pair_size); }
 304
 305 /* Iterate over hash pairs
 306     @param p the current (key,value) pair
 307     @param v the hash table to iterate
 308     @param body the operation to perform on each (key,value) pair.
 309     executes body with each active hash pair
 310 */
 311 #define hash_foreach_pair(p,v,body)                                         \
 312 do {                                                                        \
 313  __label__ _hash_foreach_done;                                              \
 314   hash_t * _h = hash_header (v);                                            \
 315   hash_pair_union_t * _p;                                                   \
 316   hash_pair_t * _q, * _q_end;                                               \
 317   uword _i, _i1, _id, _pair_increment;                                      \
 318                                                                             \
 319   _p = (hash_pair_union_t *) (v);                                           \
 320   _i = 0;                                                                   \
 321   _pair_increment = 1;                                                      \
 322   if ((v))                                                                  \
 323       _pair_increment = 1 << _h->log2_pair_size;                            \
 324   while (_i < hash_capacity (v))                                            \
 325     {                                                                       \
 326       _id = _h->is_user[_i / BITS (_h->is_user[0])];                        \
 327       _i1 = _i + BITS (_h->is_user[0]);                                     \
 328                                                                             \
 329       do {                                                                  \
 330         if (_id & 1)                                                        \
 331           {                                                                 \
 332             _q = &_p->direct;                                               \
 333             _q_end = _q + _pair_increment;                                  \
 334           }                                                                 \
 335         else                                                                \
 336           {                                                                 \
 337             hash_pair_indirect_t * _pi = &_p->indirect;                     \
 338             _q = _pi->pairs;                                                \
 339             if (_h->log2_pair_size > 0)                                     \
 340               _q_end = hash_forward (_h, _q, indirect_pair_get_len (_pi));  \
 341             else                                                            \
 342               _q_end = vec_end (_q);                                        \
 343           }                                                                 \
 344                                                                             \
 345         /* Loop through all elements in bucket.                             \
 346            Bucket may have 0 1 or more (indirect case) pairs. */            \
 347         while (_q < _q_end)                                                 \
 348           {                                                                 \
 349             uword _break_in_body = 1;                                       \
 350             (p) = _q;                                                       \
 351             do {                                                            \
 352               body;                                                         \
 353               _break_in_body = 0;                                           \
 354             } while (0);                                                    \
 355             if (_break_in_body)                                             \
 356               goto _hash_foreach_done;                                      \
 357             _q += _pair_increment;                                          \
 358           }                                                                 \
 359                                                                             \
 360         _p = (hash_pair_union_t *) (&_p->direct + _pair_increment);         \
 361         _id = _id / 2;                                                      \
 362         _i++;                                                               \
 363       } while (_i < _i1);                                                   \
 364     }                                                                       \
 365   _hash_foreach_done:                                                       \
 366   /* Be silent Mr. Compiler-Warning. */                                     \
 367   ;                                                                         \
 368  } while (0)
 369
 370 /* Iterate over key/value pairs
 371
 372     @param key_var the current key
 373     @param value_var the current value
 374     @param h the hash table to iterate across
 375     @param body the operation to perform on each (key_var,value_var) pair.
 376
 377     calls body with each active hash pair
 378 */
 379 /* Iteratate over key/value pairs. */
 380 #define hash_foreach(key_var,value_var,h,body)                  \
 381 do {                                                            \
 382   hash_pair_t * _r;                                             \
 383   hash_foreach_pair (_r, (h), {                                 \
 384     (key_var) = (__typeof__ (key_var)) _r->key;                 \
 385     (value_var) = (__typeof__ (value_var)) _r->value[0];        \
 386     do { body; } while (0);                                     \
 387   });                                                           \
 388 } while (0)
 389
 390 /* Iterate over key/value pairs for pointer key hash tables
 391
 392     @param key_var the current key
 393     @param value_var the current value
 394     @param h the hash table to iterate across
 395     @param body the operation to perform on each (key_var,value_var) pair.
 396
 397     calls body with each active hash pair
 398 */
 399 #define hash_foreach_mem(key_var,value_var,h,body)                      \
 400 do {                                                                    \
 401   hash_pair_t * _r;                                                     \
 402   hash_foreach_pair (_r, (h), {                                         \
 403     (key_var) = (__typeof__ (key_var)) uword_to_pointer (_r->key, void *); \
 404     (value_var) = (__typeof__ (value_var)) _r->value[0];                \
 405     do { body; } while (0);                                             \
 406   });                                                                   \
 407 } while (0)
 408
 409 /* Support for iteration through hash table. */
 410
 411 /* This struct saves iteration state for hash_next.
 412    None of these fields are meant to be visible to the user.
 413    Hence, the cryptic short-hand names. */
 414 typedef struct {
 415   uword i, j, f;
 416 } hash_next_t;
 417
 418 hash_pair_t * hash_next (void * v, hash_next_t * hn);
 419
 420 void * _hash_create (uword elts, hash_t * h);
 421
 422 always_inline void hash_set_value_bytes (hash_t * h, uword value_bytes)
 423 {
 424   hash_pair_t * p;
 425   h->log2_pair_size =
 426       max_log2 ((sizeof (p->key) + value_bytes + sizeof (p->key) - 1) / sizeof (p->key));
 427 }
 428
 429 #define hash_create2(_elts,_user,_value_bytes,               \
 430                      _key_sum,_key_equal,                    \
 431                      _format_pair,_format_pair_arg)          \
 432 ({                                                           \
 433   hash_t _h;                                                 \
 434   memset (&_h, 0, sizeof (_h));                              \
 435   _h.user = (_user);                                         \
 436   _h.key_sum   = (hash_key_sum_function_t *) (_key_sum);     \
 437   _h.key_equal = (_key_equal);                               \
 438   hash_set_value_bytes (&_h, (_value_bytes));                \
 439   _h.format_pair = (format_function_t *) (_format_pair);     \
 440   _h.format_pair_arg = (_format_pair_arg);                   \
 441   _hash_create ((_elts), &_h);                               \
 442 })
 443
 444 /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
 445    Public domain per: http://www.burtleburtle.net/bob/hash/doobs.html
 446    Thanks, Bob. */
 447
 448 #define hash_mix_step(a,b,c,s0,s1,s2)           \
 449 do {                                            \
 450   (a) -= (b) + (c); (a) ^= (c) >> (s0);         \
 451   (b) -= (c) + (a); (b) ^= (a) << (s1);         \
 452   (c) -= (a) + (b); (c) ^= (b) >> (s2);         \
 453 } while (0)
 454
 455 #define hash_mix32_step_1(a,b,c) hash_mix_step(a,b,c,13,8,13)
 456 #define hash_mix32_step_2(a,b,c) hash_mix_step(a,b,c,12,16,5)
 457 #define hash_mix32_step_3(a,b,c) hash_mix_step(a,b,c,3,10,15)
 458
 459 #define hash_mix64_step_1(a,b,c) hash_mix_step(a,b,c,43,9,8)
 460 #define hash_mix64_step_2(a,b,c) hash_mix_step(a,b,c,38,23,5)
 461 #define hash_mix64_step_3(a,b,c) hash_mix_step(a,b,c,35,49,11)
 462 #define hash_mix64_step_4(a,b,c) hash_mix_step(a,b,c,12,18,22)
 463
 464 /* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
 465    Thanks, Bob. */
 466 #define hash_mix64(a0,b0,c0)                    \
 467 do {                                            \
 468   hash_mix64_step_1 (a0, b0, c0);               \
 469   hash_mix64_step_2 (a0, b0, c0);               \
 470   hash_mix64_step_3 (a0, b0, c0);               \
 471   hash_mix64_step_4 (a0, b0, c0);               \
 472 } while (0)                                     \
 473
 474 #define hash_mix32(a0,b0,c0)                    \
 475 do {                                            \
 476   hash_mix32_step_1 (a0, b0, c0);               \
 477   hash_mix32_step_2 (a0, b0, c0);               \
 478   hash_mix32_step_3 (a0, b0, c0);               \
 479 } while (0)                                     \
 480
 481 /* Finalize from Bob Jenkins lookup3.c */
 482
 483 always_inline uword
 484 hash32_rotate_left (u32 x, u32 i)
 485 { return (x << i) | (x >> (BITS (i) - i)); }
 486
 487 #define hash_v3_mix32(a,b,c)                                    \
 488 do {                                                            \
 489   (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b);   \
 490   (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c);   \
 491   (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a);   \
 492   (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b);   \
 493   (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c);   \
 494   (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a);   \
 495 } while (0)
 496
 497 #define hash_v3_finalize32(a,b,c)                       \
 498 do {                                                    \
 499   (c) ^= (b); (c) -= hash32_rotate_left ((b), 14);      \
 500   (a) ^= (c); (a) -= hash32_rotate_left ((c), 11);      \
 501   (b) ^= (a); (b) -= hash32_rotate_left ((a), 25);      \
 502   (c) ^= (b); (c) -= hash32_rotate_left ((b), 16);      \
 503   (a) ^= (c); (a) -= hash32_rotate_left ((c),  4);      \
 504   (b) ^= (a); (b) -= hash32_rotate_left ((a), 14);      \
 505   (c) ^= (b); (c) -= hash32_rotate_left ((b), 24);      \
 506 } while (0)
 507
 508 /* 32 bit mixing/finalize in steps. */
 509
 510 #define hash_v3_mix32_step1(a,b,c)                              \
 511 do {                                                            \
 512   (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b);   \
 513   (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c);   \
 514 } while (0)
 515
 516 #define hash_v3_mix32_step2(a,b,c)                              \
 517 do {                                                            \
 518   (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a);   \
 519   (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b);   \
 520 } while (0)
 521
 522 #define hash_v3_mix32_step3(a,b,c)                              \
 523 do {                                                            \
 524   (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c);   \
 525   (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a);   \
 526 } while (0)
 527
 528 #define hash_v3_finalize32_step1(a,b,c)                 \
 529 do {                                                    \
 530   (c) ^= (b); (c) -= hash32_rotate_left ((b), 14);      \
 531   (a) ^= (c); (a) -= hash32_rotate_left ((c), 11);      \
 532 } while (0)
 533
 534 #define hash_v3_finalize32_step2(a,b,c)                 \
 535 do {                                                    \
 536   (b) ^= (a); (b) -= hash32_rotate_left ((a), 25);      \
 537   (c) ^= (b); (c) -= hash32_rotate_left ((b), 16);      \
 538 } while (0)
 539
 540 #define hash_v3_finalize32_step3(a,b,c)                 \
 541 do {                                                    \
 542   (a) ^= (c); (a) -= hash32_rotate_left ((c),  4);      \
 543   (b) ^= (a); (b) -= hash32_rotate_left ((a), 14);      \
 544   (c) ^= (b); (c) -= hash32_rotate_left ((b), 24);      \
 545 } while (0)
 546
 547 /* Vector v3 mixing/finalize. */
 548 #define hash_v3_mix_step_1_u32x(a,b,c)                          \
 549 do {                                                            \
 550   (a) -= (c); (a) ^= u32x_irotate_left ((c), 4); (c) += (b);    \
 551   (b) -= (a); (b) ^= u32x_irotate_left ((a), 6); (a) += (c);    \
 552   (c) -= (b); (c) ^= u32x_irotate_left ((b), 8); (b) += (a);    \
 553 } while (0)
 554
 555 #define hash_v3_mix_step_2_u32x(a,b,c)                          \
 556 do {                                                            \
 557   (a) -= (c); (a) ^= u32x_irotate_left ((c),16); (c) += (b);    \
 558   (b) -= (a); (b) ^= u32x_irotate_left ((a),19); (a) += (c);    \
 559   (c) -= (b); (c) ^= u32x_irotate_left ((b), 4); (b) += (a);    \
 560 } while (0)
 561
 562 #define hash_v3_finalize_step_1_u32x(a,b,c)             \
 563 do {                                                    \
 564   (c) ^= (b); (c) -= u32x_irotate_left ((b), 14);       \
 565   (a) ^= (c); (a) -= u32x_irotate_left ((c), 11);       \
 566   (b) ^= (a); (b) -= u32x_irotate_left ((a), 25);       \
 567 } while (0)
 568
 569 #define hash_v3_finalize_step_2_u32x(a,b,c)             \
 570 do {                                                    \
 571   (c) ^= (b); (c) -= u32x_irotate_left ((b), 16);       \
 572   (a) ^= (c); (a) -= u32x_irotate_left ((c),  4);       \
 573   (b) ^= (a); (b) -= u32x_irotate_left ((a), 14);       \
 574   (c) ^= (b); (c) -= u32x_irotate_left ((b), 24);       \
 575 } while (0)
 576
 577 #define hash_v3_mix_u32x(a,b,c)                 \
 578 do {                                            \
 579   hash_v3_mix_step_1_u32x(a,b,c);               \
 580   hash_v3_mix_step_2_u32x(a,b,c);               \
 581 } while (0)
 582
 583 #define hash_v3_finalize_u32x(a,b,c)            \
 584 do {                                            \
 585   hash_v3_finalize_step_1_u32x(a,b,c);          \
 586   hash_v3_finalize_step_2_u32x(a,b,c);          \
 587 } while (0)
 588
 589 extern u64 hash_memory64 (void * p, word n_bytes, u64 state);
 590 extern u32 hash_memory32 (void * p, word n_bytes, u32 state);
 591 extern uword hash_memory (void * p, word n_bytes, uword state);
 592
 593 extern uword mem_key_sum (hash_t * h, uword key);
 594 extern uword mem_key_equal (hash_t * h, uword key1, uword key2);
 595
 596 #define hash_create_mem(elts,key_bytes,value_bytes)     \
 597   hash_create2((elts),(key_bytes),(value_bytes),mem_key_sum,mem_key_equal,0,0)
 598
 599 extern uword vec_key_sum (hash_t * h, uword key);
 600 extern uword vec_key_equal (hash_t * h, uword key1, uword key2);
 601 extern u8 * vec_key_format_pair (u8 * s, va_list * args);
 602
 603 #define hash_create_vec(elts,key_bytes,value_bytes)     \
 604   hash_create2((elts),(key_bytes),(value_bytes),\
 605                vec_key_sum,vec_key_equal,vec_key_format_pair,0)
 606
 607 extern uword string_key_sum (hash_t * h, uword key);
 608 extern uword string_key_equal (hash_t * h, uword key1, uword key2);
 609 extern u8 * string_key_format_pair (u8 * s, va_list * args);
 610
 611 #define hash_create_string(elts,value_bytes)                    \
 612   hash_create2((elts),0,(value_bytes),                          \
 613                (hash_key_sum_function_t *) KEY_FUNC_STRING,     \
 614                (hash_key_equal_function_t *)KEY_FUNC_STRING,    \
 615                0, 0)
 616
 617 #define hash_create(elts,value_bytes)                           \
 618   hash_create2((elts),0,(value_bytes),                          \
 619                (hash_key_sum_function_t *) KEY_FUNC_NONE,       \
 620                (hash_key_equal_function_t *) KEY_FUNC_NONE,     \
 621                0,0)
 622
 623 #define hash_create_uword(elts,value_bytes)                             \
 624   hash_create2((elts),0,(value_bytes),                                  \
 625                (hash_key_sum_function_t *) KEY_FUNC_POINTER_UWORD,      \
 626                (hash_key_equal_function_t *) KEY_FUNC_POINTER_UWORD,    \
 627                0,0)
 628
 629 #define hash_create_u32(elts,value_bytes)                               \
 630   hash_create2((elts),0,(value_bytes),                                  \
 631                (hash_key_sum_function_t *) KEY_FUNC_POINTER_U32,        \
 632                (hash_key_equal_function_t *) KEY_FUNC_POINTER_U32,      \
 633                0,0)
 634
 635 u8 * format_hash (u8 * s, va_list * va);
 636
 637 /* Looks up input in hash table indexed by either vec string or
 638    c string (null terminated). */
 639 unformat_function_t unformat_hash_vec_string;
 640 unformat_function_t unformat_hash_string;
 641
 642 /* Main test routine. */
 643 int test_hash_main (unformat_input_t * input);
 644
 645 #endif /* included_hash_h */