FD.io VPP  v17.07-30-g839fa73
Vector Packet Processing
phash.h
Go to the documentation of this file.
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) 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_phash_h
39 #define included_phash_h
40 
41 #include <vppinfra/hash.h> /* for Bob's mixing functions */
42 
43 typedef struct
44 {
45  /* Maybe either pointer to vector or inline word. */
47 
48  /* Hash code (A, B). */
49  u32 a, b;
50 } phash_key_t;
51 
52 /* Table indexed by B. */
53 typedef struct
54 {
55  /* Vector of key indices with this same value of B. */
57 
58  /* hash=a^tabb[b].val_b */
60 
61  /* High watermark of who has visited this map node. */
63 } phash_tabb_t;
64 
65 always_inline void
67 {
68  vec_free (b->keys);
69  b->val_b = b->water_b = 0;
70 }
71 
72 typedef struct
73 {
74  /* b that currently occupies this hash */
76 
77  /* Queue position of parent that could use this hash. */
79 
80  /* What to change parent tab[b] to use this hash. */
82 
83  /* Original value of tab[b]. */
85 } phash_tabq_t;
86 
87 typedef struct
88 {
89  u8 a_bits, b_bits, s_bits, a_shift;
91  u32 *tab;
93 
94  /* Seed value for hash mixer. */
96 
98 
99  /* Key functions want 64 bit keys.
100  Use hash_mix64 rather than hash_mix32. */
101 #define PHASH_FLAG_MIX64 (1 << 0)
102 #define PHASH_FLAG_MIX32 (0 << 0)
103 
104  /* When b_bits is large enough (>= 12) we scramble. */
105 #define PHASH_FLAG_USE_SCRAMBLE (1 << 1)
106 
107  /* Slow mode gives smaller tables but at the expense of more run time. */
108 #define PHASH_FLAG_SLOW_MODE (0 << 2)
109 #define PHASH_FLAG_FAST_MODE (1 << 2)
110 
111  /* Generate minimal perfect hash instead of perfect hash. */
112 #define PHASH_FLAG_NON_MINIMAL (0 << 3)
113 #define PHASH_FLAG_MINIMAL (1 << 3)
114 
115  /* vec_len (keys) for minimal hash;
116  1 << s_bits for non-minimal hash. */
118 
119  /* Vector of keys. */
121 
122  /* Used by callbacks to identify keys. */
123  void *private;
124 
125  /* Key comparison callback. */
126  int (*key_is_equal) (void *private, uword key1, uword key2);
127 
128  /* Callback to reduce single key -> hash seeds. */
129  void (*key_seed1) (void *private, uword key, void *seed);
130 
131  /* Callback to reduce two key2 -> hash seeds. */
132  void (*key_seed2) (void *private, uword key1, uword key2, void *seed);
133 
134  /* Stuff used to compute perfect hash. */
136 
137  /* Stuff indexed by B. */
139 
140  /* Table of B ordered by number of keys in tabb[b]. */
142 
143  /* Unique key (or ~0 if none) for a given hash
144  H = A ^ scramble[tab[B].val_b]. */
146 
147  /* Stuff indexed by q. */
149 
150  /* Stats. */
151  u32 n_seed_trials, n_perfect_calls;
152 } phash_main_t;
153 
154 always_inline void
156 {
157  vec_free (pm->tabb);
158  vec_free (pm->tabq);
159  vec_free (pm->tabh);
160  vec_free (pm->tabb_sort);
161  if (!(pm->flags & PHASH_FLAG_USE_SCRAMBLE))
162  vec_free (pm->scramble);
163 }
164 
165 always_inline void
167 {
169  vec_free (pm->tab);
170  vec_free (pm->keys);
171  memset (pm, 0, sizeof (pm[0]));
172 }
173 
174 /* Slow hash computation for general keys. */
176 
177 /* Main routine to compute perfect hash. */
179 
180 /* Validates that hash is indeed perfect. */
182 
183 /* Unit test. */
184 int phash_test_main (unformat_input_t * input);
185 
186 #endif /* included_phash_h */
187 
188 /*
189  * fd.io coding-style-patch-verification: ON
190  *
191  * Local Variables:
192  * eval: (c-set-style "gnu")
193  * End:
194  */
u32 water_b
Definition: phash.h:62
a
Definition: bitmap.h:516
clib_error_t * phash_find_perfect_hash(phash_main_t *pm)
Definition: phash.c:822
u32 random_seed
Definition: phash.h:135
uword key
Definition: phash.h:46
u32 * tab
Definition: phash.h:91
u32 b
Definition: phash.h:49
u32 parent_q
Definition: phash.h:78
static void phash_main_free_working_memory(phash_main_t *pm)
Definition: phash.h:155
u32 * tabh
Definition: phash.h:145
u32 oldval_q
Definition: phash.h:84
#define always_inline
Definition: clib.h:84
unsigned long u64
Definition: types.h:89
u32 n_seed_trials
Definition: phash.h:151
u8 s_bits
Definition: phash.h:89
struct _unformat_input_t unformat_input_t
phash_key_t * keys
Definition: phash.h:120
u32 hash_max
Definition: phash.h:117
u32 flags
Definition: phash.h:97
u32 val_b
Definition: phash.h:59
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:340
u64 hash_seed
Definition: phash.h:95
u32 * keys
Definition: phash.h:56
uword phash_hash_slow(phash_main_t *pm, uword key)
Definition: phash.c:924
int phash_test_main(unformat_input_t *input)
clib_error_t * phash_validate(phash_main_t *pm)
Definition: phash.c:981
unsigned int u32
Definition: types.h:88
phash_tabq_t * tabq
Definition: phash.h:148
u32 b_mask
Definition: phash.h:90
u64 uword
Definition: types.h:112
u32 b_q
Definition: phash.h:75
unsigned char u8
Definition: types.h:56
static void phash_main_free(phash_main_t *pm)
Definition: phash.h:166
u32 * tabb_sort
Definition: phash.h:141
u32 newval_q
Definition: phash.h:81
#define PHASH_FLAG_USE_SCRAMBLE
Definition: phash.h:105
phash_tabb_t * tabb
Definition: phash.h:138
static void phash_tabb_free(phash_tabb_t *b)
Definition: phash.h:66
u32 * scramble
Definition: phash.h:92