aboutsummaryrefslogtreecommitdiffstats
path: root/src/vppinfra/hash.h
diff options
context:
space:
mode:
authorDamjan Marion <damarion@cisco.com>2016-12-19 23:05:39 +0100
committerDamjan Marion <damarion@cisco.com>2016-12-28 12:25:14 +0100
commit7cd468a3d7dee7d6c92f69a0bb7061ae208ec727 (patch)
tree5de62f8dbd3a752f5a676ca600e43d2652d1ff1a /src/vppinfra/hash.h
parent696f1adec0df3b8f161862566dd9c86174302658 (diff)
Reorganize source tree to use single autotools instance
Change-Id: I7b51f88292e057c6443b12224486f2d0c9f8ae23 Signed-off-by: Damjan Marion <damarion@cisco.com>
Diffstat (limited to 'src/vppinfra/hash.h')
-rw-r--r--src/vppinfra/hash.h699
1 files changed, 699 insertions, 0 deletions
diff --git a/src/vppinfra/hash.h b/src/vppinfra/hash.h
new file mode 100644
index 00000000000..3f0efaa727c
--- /dev/null
+++ b/src/vppinfra/hash.h
@@ -0,0 +1,699 @@
+/*
+ * Copyright (c) 2015 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+/*
+ Copyright (c) 2001-2005 Eliot Dresselhaus
+
+ Permission is hereby granted, free of charge, to any person obtaining
+ a copy of this software and associated documentation files (the
+ "Software"), to deal in the Software without restriction, including
+ without limitation the rights to use, copy, modify, merge, publish,
+ distribute, sublicense, and/or sell copies of the Software, and to
+ permit persons to whom the Software is furnished to do so, subject to
+ the following conditions:
+
+ The above copyright notice and this permission notice shall be
+ included in all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+ LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+ OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+ WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+*/
+
+#ifndef included_hash_h
+#define included_hash_h
+
+#include <vppinfra/error.h>
+#include <vppinfra/format.h>
+#include <vppinfra/vec.h>
+#include <vppinfra/vector.h>
+
+struct hash_header;
+
+typedef uword (hash_key_sum_function_t) (struct hash_header *, uword key);
+typedef uword (hash_key_equal_function_t)
+ (struct hash_header *, uword key1, uword key2);
+
+/* Vector header for hash tables. */
+typedef struct hash_header
+{
+ /* Number of elements in hash table. */
+ uword elts;
+
+ /* Flags as follows. */
+ u32 flags;
+
+ /* Set if user does not want table to auto-resize when sufficiently full. */
+#define HASH_FLAG_NO_AUTO_GROW (1 << 0)
+ /* Set if user does not want table to auto-resize when sufficiently empty. */
+#define HASH_FLAG_NO_AUTO_SHRINK (1 << 1)
+ /* Set when hash_next is in the process of iterating through this hash table. */
+#define HASH_FLAG_HASH_NEXT_IN_PROGRESS (1 << 2)
+
+ u32 log2_pair_size;
+
+ /* Function to compute the "sum" of a hash key.
+ Hash function is this sum modulo the prime size of
+ the hash table (vec_len (v)). */
+ hash_key_sum_function_t *key_sum;
+
+ /* Special values for key_sum "function". */
+#define KEY_FUNC_NONE (0) /*< sum = key */
+#define KEY_FUNC_POINTER_UWORD (1) /*< sum = *(uword *) key */
+#define KEY_FUNC_POINTER_U32 (2) /*< sum = *(u32 *) key */
+#define KEY_FUNC_STRING (3) /*< sum = string_key_sum, etc. */
+
+ /* key comparison function */
+ hash_key_equal_function_t *key_equal;
+
+ /* Hook for user's data. Used to parameterize sum/equal functions. */
+ any user;
+
+ /* Format a (k,v) pair */
+ format_function_t *format_pair;
+
+ /* Format function arg */
+ void *format_pair_arg;
+
+ /* Bit i is set if pair i is a user object (as opposed to being
+ either zero or an indirect array of pairs). */
+ uword is_user[0];
+} hash_t;
+
+/* Hash header size in bytes */
+always_inline uword
+hash_header_bytes (void *v)
+{
+ hash_t *h;
+ uword is_user_bytes =
+ (sizeof (h->is_user[0]) * vec_len (v)) / BITS (h->is_user[0]);
+ return sizeof (h[0]) + is_user_bytes;
+}
+
+/* Returns a pointer to the hash header given the vector pointer */
+always_inline hash_t *
+hash_header (void *v)
+{
+ return vec_header (v, hash_header_bytes (v));
+}
+
+/* Number of elements in the hash table */
+always_inline uword
+hash_elts (void *v)
+{
+ hash_t *h = hash_header (v);
+ return v ? h->elts : 0;
+}
+
+/* Number of elements the hash table can hold */
+always_inline uword
+hash_capacity (void *v)
+{
+ return vec_len (v);
+}
+
+/* Returns 1 if the hash pair contains user data */
+always_inline uword
+hash_is_user (void *v, uword i)
+{
+ hash_t *h = hash_header (v);
+ uword i0 = i / BITS (h->is_user[0]);
+ uword i1 = i % BITS (h->is_user[0]);
+ return (h->is_user[i0] & ((uword) 1 << i1)) != 0;
+}
+
+/* Set the format function and format argument for a hash table */
+always_inline void
+hash_set_pair_format (void *v,
+ format_function_t * format_pair, void *format_pair_arg)
+{
+ hash_t *h = hash_header (v);
+ h->format_pair = format_pair;
+ h->format_pair_arg = format_pair_arg;
+}
+
+/* Set hash table flags */
+always_inline void
+hash_set_flags (void *v, uword flags)
+{
+ hash_header (v)->flags |= flags;
+}
+
+/* Key value pairs. */
+typedef struct
+{
+ /* The Key */
+ uword key;
+
+ /* The Value. Length is 2^log2_pair_size - 1. */
+ uword value[0];
+} hash_pair_t;
+
+/* The indirect pair structure
+
+ If log2_pair_size > 0 we overload hash pairs
+ with indirect pairs for buckets with more than one
+ pair. */
+typedef struct
+{
+ /* pair vector */
+ hash_pair_t *pairs;
+ /* padding */
+ u8 pad[sizeof (uword) - sizeof (hash_pair_t *)];
+ /* allocated length */
+ uword alloc_len;
+}
+hash_pair_indirect_t;
+
+/* Direct / Indirect pair union */
+typedef union
+{
+ hash_pair_t direct;
+ hash_pair_indirect_t indirect;
+} hash_pair_union_t;
+
+#define LOG2_ALLOC_BITS (5)
+#define PAIR_BITS (BITS (uword) - LOG2_ALLOC_BITS)
+
+/* Log2 number of bytes allocated in pairs array. */
+always_inline uword
+indirect_pair_get_log2_bytes (hash_pair_indirect_t * p)
+{
+ return p->alloc_len >> PAIR_BITS;
+}
+
+/* Get the length of an indirect pair */
+always_inline uword
+indirect_pair_get_len (hash_pair_indirect_t * p)
+{
+ if (!p->pairs)
+ return 0;
+ else
+ return p->alloc_len & (((uword) 1 << PAIR_BITS) - 1);
+}
+
+/* Set the length of an indirect pair */
+always_inline void
+indirect_pair_set (hash_pair_indirect_t * p, uword log2_alloc, uword len)
+{
+ ASSERT (len < ((uword) 1 << PAIR_BITS));
+ ASSERT (log2_alloc < ((uword) 1 << LOG2_ALLOC_BITS));
+ p->alloc_len = (log2_alloc << PAIR_BITS) | len;
+}
+
+/* internal routine to fetch value for given key */
+uword *_hash_get (void *v, uword key);
+
+/* internal routine to fetch value (key, value) pair for given key */
+hash_pair_t *_hash_get_pair (void *v, uword key);
+
+/* internal routine to unset a (key, value) pair */
+void *_hash_unset (void *v, uword key, void *old_value);
+
+/* internal routine to set a (key, value) pair, return the old value */
+void *_hash_set3 (void *v, uword key, void *value, void *old_value);
+
+/* Resize a hash table */
+void *hash_resize (void *old, uword new_size);
+
+/* duplicate a hash table */
+void *hash_dup (void *old);
+
+/* Returns the number of bytes used by a hash table */
+uword hash_bytes (void *v);
+
+/* Public macro to set a (key, value) pair, return the old value */
+#define hash_set3(h,key,value,old_value) \
+({ \
+ uword _v = (uword) (value); \
+ (h) = _hash_set3 ((h), (uword) (key), (void *) &_v, (old_value)); \
+})
+
+/* Public macro to fetch value for given key */
+#define hash_get(h,key) _hash_get ((h), (uword) (key))
+
+/* Public macro to fetch value (key, value) pair for given key */
+#define hash_get_pair(h,key) _hash_get_pair ((h), (uword) (key))
+
+/* Public macro to set a (key, value) pair */
+#define hash_set(h,key,value) hash_set3(h,key,value,0)
+
+/* Public macro to set (key, 0) pair */
+#define hash_set1(h,key) (h) = _hash_set3(h,(uword) (key),0,0)
+
+/* Public macro to unset a (key, value) pair */
+#define hash_unset(h,key) ((h) = _hash_unset ((h), (uword) (key),0))
+
+/* Public macro to unset a (key, value) pair, return the old value */
+#define hash_unset3(h,key,old_value) ((h) = _hash_unset ((h), (uword) (key), (void *) (old_value)))
+
+/* get/set/unset for pointer keys. */
+
+/* Public macro to fetch value for given pointer key */
+#define hash_get_mem(h,key) _hash_get ((h), pointer_to_uword (key))
+
+/* Public macro to fetch (key, value) for given pointer key */
+#define hash_get_pair_mem(h,key) _hash_get_pair ((h), pointer_to_uword (key))
+
+/* Public macro to set (key, value) for pointer key */
+#define hash_set_mem(h,key,value) hash_set3 (h, pointer_to_uword (key), (value), 0)
+
+/* Public macro to set (key, 0) for pointer key */
+#define hash_set1_mem(h,key) hash_set3 ((h), pointer_to_uword (key), 0, 0)
+
+/* Public macro to unset (key, value) for pointer key */
+#define hash_unset_mem(h,key) ((h) = _hash_unset ((h), pointer_to_uword (key),0))
+
+/* internal routine to free a hash table */
+extern void *_hash_free (void *v);
+
+/* Public macro to free a hash table */
+#define hash_free(h) (h) = _hash_free ((h))
+
+clib_error_t *hash_validate (void *v);
+
+/* Public inline funcion to get the number of value bytes for a hash table */
+always_inline uword
+hash_value_bytes (hash_t * h)
+{
+ hash_pair_t *p;
+ return (sizeof (p->value[0]) << h->log2_pair_size) - sizeof (p->key);
+}
+
+/* Public inline funcion to get log2(size of a (key,value) pair) */
+always_inline uword
+hash_pair_log2_bytes (hash_t * h)
+{
+ uword log2_bytes = h->log2_pair_size;
+ ASSERT (BITS (hash_pair_t) == 32 || BITS (hash_pair_t) == 64);
+ if (BITS (hash_pair_t) == 32)
+ log2_bytes += 2;
+ else if (BITS (hash_pair_t) == 64)
+ log2_bytes += 3;
+ return log2_bytes;
+}
+
+/* Public inline funcion to get size of a (key,value) pair */
+always_inline uword
+hash_pair_bytes (hash_t * h)
+{
+ return (uword) 1 << hash_pair_log2_bytes (h);
+}
+
+/* Public inline funcion to advance a pointer past one (key,value) pair */
+always_inline void *
+hash_forward1 (hash_t * h, void *v)
+{
+ return (u8 *) v + hash_pair_bytes (h);
+}
+
+/* Public inline funcion to advance a pointer past N (key,value) pairs */
+always_inline void *
+hash_forward (hash_t * h, void *v, uword n)
+{
+ return (u8 *) v + ((n * sizeof (hash_pair_t)) << h->log2_pair_size);
+}
+
+/** Iterate over hash pairs.
+
+ @param p The current (key,value) pair. This should be of type
+ <code>(hash_pair_t *)</code>.
+ @param v The hash table to iterate.
+ @param body The operation to perform on each (key,value) pair.
+
+ Executes the expression or code block @c body with each active hash pair.
+*/
+/* A previous version of this macro made use of the hash_pair_union_t
+ * structure; this version does not since that approach mightily upset
+ * the static analysis tool. In the rare chance someone is reading this
+ * code, pretend that _p below is of type hash_pair_union_t and that when
+ * used as an rvalue it's really using one of the union members as the
+ * rvalue. If you were confused before you might be marginally less
+ * confused after.
+ */
+#define hash_foreach_pair(p,v,body) \
+do { \
+ __label__ _hash_foreach_done; \
+ hash_t * _h = hash_header (v); \
+ void * _p; \
+ hash_pair_t * _q, * _q_end; \
+ uword _i, _i1, _id, _pair_increment; \
+ \
+ _p = (v); \
+ _i = 0; \
+ _pair_increment = 1; \
+ if ((v)) \
+ _pair_increment = 1 << _h->log2_pair_size; \
+ while (_i < hash_capacity (v)) \
+ { \
+ _id = _h->is_user[_i / BITS (_h->is_user[0])]; \
+ _i1 = _i + BITS (_h->is_user[0]); \
+ \
+ do { \
+ if (_id & 1) \
+ { \
+ _q = _p; \
+ _q_end = _q + _pair_increment; \
+ } \
+ else \
+ { \
+ hash_pair_indirect_t * _pi = _p; \
+ _q = _pi->pairs; \
+ if (_h->log2_pair_size > 0) \
+ _q_end = hash_forward (_h, _q, indirect_pair_get_len (_pi)); \
+ else \
+ _q_end = vec_end (_q); \
+ } \
+ \
+ /* Loop through all elements in bucket. \
+ Bucket may have 0 1 or more (indirect case) pairs. */ \
+ while (_q < _q_end) \
+ { \
+ uword _break_in_body = 1; \
+ (p) = _q; \
+ do { \
+ body; \
+ _break_in_body = 0; \
+ } while (0); \
+ if (_break_in_body) \
+ goto _hash_foreach_done; \
+ _q += _pair_increment; \
+ } \
+ \
+ _p = (hash_pair_t *)_p + _pair_increment; \
+ _id = _id / 2; \
+ _i++; \
+ } while (_i < _i1); \
+ } \
+ _hash_foreach_done: \
+ /* Be silent Mr. Compiler-Warning. */ \
+ ; \
+ } while (0)
+
+/* Iterate over key/value pairs
+
+ @param key_var the current key
+ @param value_var the current value
+ @param h the hash table to iterate across
+ @param body the operation to perform on each (key_var,value_var) pair.
+
+ calls body with each active hash pair
+*/
+/* Iteratate over key/value pairs. */
+#define hash_foreach(key_var,value_var,h,body) \
+do { \
+ hash_pair_t * _r; \
+ hash_foreach_pair (_r, (h), { \
+ (key_var) = (__typeof__ (key_var)) _r->key; \
+ (value_var) = (__typeof__ (value_var)) _r->value[0]; \
+ do { body; } while (0); \
+ }); \
+} while (0)
+
+/* Iterate over key/value pairs for pointer key hash tables
+
+ @param key_var the current key
+ @param value_var the current value
+ @param h the hash table to iterate across
+ @param body the operation to perform on each (key_var,value_var) pair.
+
+ calls body with each active hash pair
+*/
+#define hash_foreach_mem(key_var,value_var,h,body) \
+do { \
+ hash_pair_t * _r; \
+ hash_foreach_pair (_r, (h), { \
+ (key_var) = (__typeof__ (key_var)) uword_to_pointer (_r->key, void *); \
+ (value_var) = (__typeof__ (value_var)) _r->value[0]; \
+ do { body; } while (0); \
+ }); \
+} while (0)
+
+/* Support for iteration through hash table. */
+
+/* This struct saves iteration state for hash_next.
+ None of these fields are meant to be visible to the user.
+ Hence, the cryptic short-hand names. */
+typedef struct
+{
+ uword i, j, f;
+} hash_next_t;
+
+hash_pair_t *hash_next (void *v, hash_next_t * hn);
+
+void *_hash_create (uword elts, hash_t * h);
+
+always_inline void
+hash_set_value_bytes (hash_t * h, uword value_bytes)
+{
+ hash_pair_t *p;
+ h->log2_pair_size =
+ max_log2 ((sizeof (p->key) + value_bytes + sizeof (p->key) -
+ 1) / sizeof (p->key));
+}
+
+#define hash_create2(_elts,_user,_value_bytes, \
+ _key_sum,_key_equal, \
+ _format_pair,_format_pair_arg) \
+({ \
+ hash_t _h; \
+ memset (&_h, 0, sizeof (_h)); \
+ _h.user = (_user); \
+ _h.key_sum = (hash_key_sum_function_t *) (_key_sum); \
+ _h.key_equal = (_key_equal); \
+ hash_set_value_bytes (&_h, (_value_bytes)); \
+ _h.format_pair = (format_function_t *) (_format_pair); \
+ _h.format_pair_arg = (_format_pair_arg); \
+ _hash_create ((_elts), &_h); \
+})
+
+/* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
+ Public domain per: http://www.burtleburtle.net/bob/hash/doobs.html
+ Thanks, Bob. */
+
+#define hash_mix_step(a,b,c,s0,s1,s2) \
+do { \
+ (a) -= (b) + (c); (a) ^= (c) >> (s0); \
+ (b) -= (c) + (a); (b) ^= (a) << (s1); \
+ (c) -= (a) + (b); (c) ^= (b) >> (s2); \
+} while (0)
+
+#define hash_mix32_step_1(a,b,c) hash_mix_step(a,b,c,13,8,13)
+#define hash_mix32_step_2(a,b,c) hash_mix_step(a,b,c,12,16,5)
+#define hash_mix32_step_3(a,b,c) hash_mix_step(a,b,c,3,10,15)
+
+#define hash_mix64_step_1(a,b,c) hash_mix_step(a,b,c,43,9,8)
+#define hash_mix64_step_2(a,b,c) hash_mix_step(a,b,c,38,23,5)
+#define hash_mix64_step_3(a,b,c) hash_mix_step(a,b,c,35,49,11)
+#define hash_mix64_step_4(a,b,c) hash_mix_step(a,b,c,12,18,22)
+
+/* Hash function based on that of Bob Jenkins (bob_jenkins@compuserve.com).
+ Thanks, Bob. */
+#define hash_mix64(a0,b0,c0) \
+do { \
+ hash_mix64_step_1 (a0, b0, c0); \
+ hash_mix64_step_2 (a0, b0, c0); \
+ hash_mix64_step_3 (a0, b0, c0); \
+ hash_mix64_step_4 (a0, b0, c0); \
+} while (0) \
+
+#define hash_mix32(a0,b0,c0) \
+do { \
+ hash_mix32_step_1 (a0, b0, c0); \
+ hash_mix32_step_2 (a0, b0, c0); \
+ hash_mix32_step_3 (a0, b0, c0); \
+} while (0) \
+
+/* Finalize from Bob Jenkins lookup3.c */
+
+always_inline uword
+hash32_rotate_left (u32 x, u32 i)
+{
+ return (x << i) | (x >> (BITS (i) - i));
+}
+
+#define hash_v3_mix32(a,b,c) \
+do { \
+ (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b); \
+ (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c); \
+ (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a); \
+ (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b); \
+ (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c); \
+ (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a); \
+} while (0)
+
+#define hash_v3_finalize32(a,b,c) \
+do { \
+ (c) ^= (b); (c) -= hash32_rotate_left ((b), 14); \
+ (a) ^= (c); (a) -= hash32_rotate_left ((c), 11); \
+ (b) ^= (a); (b) -= hash32_rotate_left ((a), 25); \
+ (c) ^= (b); (c) -= hash32_rotate_left ((b), 16); \
+ (a) ^= (c); (a) -= hash32_rotate_left ((c), 4); \
+ (b) ^= (a); (b) -= hash32_rotate_left ((a), 14); \
+ (c) ^= (b); (c) -= hash32_rotate_left ((b), 24); \
+} while (0)
+
+/* 32 bit mixing/finalize in steps. */
+
+#define hash_v3_mix32_step1(a,b,c) \
+do { \
+ (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b); \
+ (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c); \
+} while (0)
+
+#define hash_v3_mix32_step2(a,b,c) \
+do { \
+ (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a); \
+ (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b); \
+} while (0)
+
+#define hash_v3_mix32_step3(a,b,c) \
+do { \
+ (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c); \
+ (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a); \
+} while (0)
+
+#define hash_v3_finalize32_step1(a,b,c) \
+do { \
+ (c) ^= (b); (c) -= hash32_rotate_left ((b), 14); \
+ (a) ^= (c); (a) -= hash32_rotate_left ((c), 11); \
+} while (0)
+
+#define hash_v3_finalize32_step2(a,b,c) \
+do { \
+ (b) ^= (a); (b) -= hash32_rotate_left ((a), 25); \
+ (c) ^= (b); (c) -= hash32_rotate_left ((b), 16); \
+} while (0)
+
+#define hash_v3_finalize32_step3(a,b,c) \
+do { \
+ (a) ^= (c); (a) -= hash32_rotate_left ((c), 4); \
+ (b) ^= (a); (b) -= hash32_rotate_left ((a), 14); \
+ (c) ^= (b); (c) -= hash32_rotate_left ((b), 24); \
+} while (0)
+
+/* Vector v3 mixing/finalize. */
+#define hash_v3_mix_step_1_u32x(a,b,c) \
+do { \
+ (a) -= (c); (a) ^= u32x_irotate_left ((c), 4); (c) += (b); \
+ (b) -= (a); (b) ^= u32x_irotate_left ((a), 6); (a) += (c); \
+ (c) -= (b); (c) ^= u32x_irotate_left ((b), 8); (b) += (a); \
+} while (0)
+
+#define hash_v3_mix_step_2_u32x(a,b,c) \
+do { \
+ (a) -= (c); (a) ^= u32x_irotate_left ((c),16); (c) += (b); \
+ (b) -= (a); (b) ^= u32x_irotate_left ((a),19); (a) += (c); \
+ (c) -= (b); (c) ^= u32x_irotate_left ((b), 4); (b) += (a); \
+} while (0)
+
+#define hash_v3_finalize_step_1_u32x(a,b,c) \
+do { \
+ (c) ^= (b); (c) -= u32x_irotate_left ((b), 14); \
+ (a) ^= (c); (a) -= u32x_irotate_left ((c), 11); \
+ (b) ^= (a); (b) -= u32x_irotate_left ((a), 25); \
+} while (0)
+
+#define hash_v3_finalize_step_2_u32x(a,b,c) \
+do { \
+ (c) ^= (b); (c) -= u32x_irotate_left ((b), 16); \
+ (a) ^= (c); (a) -= u32x_irotate_left ((c), 4); \
+ (b) ^= (a); (b) -= u32x_irotate_left ((a), 14); \
+ (c) ^= (b); (c) -= u32x_irotate_left ((b), 24); \
+} while (0)
+
+#define hash_v3_mix_u32x(a,b,c) \
+do { \
+ hash_v3_mix_step_1_u32x(a,b,c); \
+ hash_v3_mix_step_2_u32x(a,b,c); \
+} while (0)
+
+#define hash_v3_finalize_u32x(a,b,c) \
+do { \
+ hash_v3_finalize_step_1_u32x(a,b,c); \
+ hash_v3_finalize_step_2_u32x(a,b,c); \
+} while (0)
+
+extern uword hash_memory (void *p, word n_bytes, uword state);
+
+extern uword mem_key_sum (hash_t * h, uword key);
+extern uword mem_key_equal (hash_t * h, uword key1, uword key2);
+
+#define hash_create_mem(elts,key_bytes,value_bytes) \
+ hash_create2((elts),(key_bytes),(value_bytes),mem_key_sum,mem_key_equal,0,0)
+
+extern uword vec_key_sum (hash_t * h, uword key);
+extern uword vec_key_equal (hash_t * h, uword key1, uword key2);
+extern u8 *vec_key_format_pair (u8 * s, va_list * args);
+
+#define hash_create_vec(elts,key_bytes,value_bytes) \
+ hash_create2((elts),(key_bytes),(value_bytes),\
+ vec_key_sum,vec_key_equal,vec_key_format_pair,0)
+
+extern uword string_key_sum (hash_t * h, uword key);
+extern uword string_key_equal (hash_t * h, uword key1, uword key2);
+extern u8 *string_key_format_pair (u8 * s, va_list * args);
+
+#define hash_create_string(elts,value_bytes) \
+ hash_create2((elts),0,(value_bytes), \
+ (hash_key_sum_function_t *) KEY_FUNC_STRING, \
+ (hash_key_equal_function_t *)KEY_FUNC_STRING, \
+ 0, 0)
+
+#define hash_create(elts,value_bytes) \
+ hash_create2((elts),0,(value_bytes), \
+ (hash_key_sum_function_t *) KEY_FUNC_NONE, \
+ (hash_key_equal_function_t *) KEY_FUNC_NONE, \
+ 0,0)
+
+#define hash_create_uword(elts,value_bytes) \
+ hash_create2((elts),0,(value_bytes), \
+ (hash_key_sum_function_t *) KEY_FUNC_POINTER_UWORD, \
+ (hash_key_equal_function_t *) KEY_FUNC_POINTER_UWORD, \
+ 0,0)
+
+#define hash_create_u32(elts,value_bytes) \
+ hash_create2((elts),0,(value_bytes), \
+ (hash_key_sum_function_t *) KEY_FUNC_POINTER_U32, \
+ (hash_key_equal_function_t *) KEY_FUNC_POINTER_U32, \
+ 0,0)
+
+u8 *format_hash (u8 * s, va_list * va);
+
+/* Looks up input in hash table indexed by either vec string or
+ c string (null terminated). */
+unformat_function_t unformat_hash_vec_string;
+unformat_function_t unformat_hash_string;
+
+/* Main test routine. */
+int test_hash_main (unformat_input_t * input);
+
+static inline void
+hash_delete (void *bob)
+{
+}
+
+#endif /* included_hash_h */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */