FD.io VPP  v21.06-3-gbb25fbf28
Vector Packet Processing
qhash.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) 2006 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_qhash_h
39 #define included_qhash_h
40 
41 #include <vppinfra/cache.h>
42 #include <vppinfra/hash.h>
43 
44 /* Word hash tables. */
45 typedef struct
46 {
47  /* Number of elements in hash. */
49 
51 
52  /* Jenkins hash seeds. */
53  u32 hash_seeds[3];
54 
55  /* Fall back CLIB hash for overflow in fixed sized buckets. */
57 
58  u32 *overflow_counts, *overflow_free_indices;
59 
61 
63 } qhash_t;
64 
66 qhash_header (void *v)
67 {
68  return vec_header (v, sizeof (qhash_t));
69 }
70 
72 qhash_elts (void *v)
73 {
74  return v ? qhash_header (v)->n_elts : 0;
75 }
76 
79 {
80  return v ? hash_elts (qhash_header (v)->overflow_hash) : 0;
81 }
82 
83 #define QHASH_LOG2_KEYS_PER_BUCKET 2
84 #define QHASH_KEYS_PER_BUCKET (1 << QHASH_LOG2_KEYS_PER_BUCKET)
85 
88 {
89  u32 a, b, c;
90 
91  a = h->hash_seeds[0];
92  b = h->hash_seeds[1];
93  c = h->hash_seeds[2];
94 
95  a ^= key;
96 #if uword_bits == 64
97  b ^= key >> 32;
98 #endif
99 
100  hash_mix32 (a, b, c);
101 
102  return c & pow2_mask (h->log2_hash_size);
103 }
104 
105 #define qhash_resize(v,n) (v) = _qhash_resize ((v), (n), sizeof ((v)[0]))
106 
107 #define qhash_foreach(var,v,body)
108 
109 #define qhash_set_multiple(v,keys,n,results) \
110  (v) = _qhash_set_multiple ((v), sizeof ((v)[0]), (keys), (n), (results))
111 
112 #define qhash_unset_multiple(v,keys,n,results) \
113  _qhash_unset_multiple ((v), sizeof ((v)[0]), (keys), (n), (results))
114 
115 #define qhash_get(v,key) \
116 ({ \
117  uword _qhash_get_k = (key); \
118  qhash_get_first_match ((v), &_qhash_get_k, 1, &_qhash_get_k); \
119 })
120 
121 #define qhash_set(v,k) \
122 ({ \
123  uword _qhash_set_k = (k); \
124  qhash_set_multiple ((v), &_qhash_set_k, 1, &_qhash_set_k); \
125  _qhash_set_k; \
126 })
127 
128 #define qhash_unset(v,k) \
129 ({ \
130  uword _qhash_unset_k = (k); \
131  qhash_unset_multiple ((v), &_qhash_unset_k, 1, &_qhash_unset_k); \
132  _qhash_unset_k; \
133 })
134 
135 void *_qhash_resize (void *v, uword length, uword elt_bytes);
136 
137 /* Lookup multiple keys in the same hash table. */
138 void
139 qhash_get_multiple (void *v,
140  uword * search_keys,
141  uword n_search_keys, u32 * result_indices);
142 
143 /* Lookup multiple keys in the same hash table.
144  Returns index of first matching key. */
145 u32
146 qhash_get_first_match (void *v,
147  uword * search_keys,
148  uword n_search_keys, uword * matching_key);
149 
150 /* Set/unset helper functions. */
151 void *_qhash_set_multiple (void *v,
152  uword elt_bytes,
153  uword * search_keys,
154  uword n_search_keys, u32 * result_indices);
155 void
156 _qhash_unset_multiple (void *v,
157  uword elt_bytes,
158  uword * search_keys,
159  uword n_search_keys, u32 * result_indices);
160 
161 #endif /* included_qhash_h */
162 
163 /*
164  * fd.io coding-style-patch-verification: ON
165  *
166  * Local Variables:
167  * eval: (c-set-style "gnu")
168  * End:
169  */
qhash_n_overflow
static uword qhash_n_overflow(void *v)
Definition: qhash.h:78
pow2_mask
static uword pow2_mask(uword x)
Definition: clib.h:252
hash_mix32
#define hash_mix32(a0, b0, c0)
Definition: hash.h:538
qhash_elts
static uword qhash_elts(void *v)
Definition: qhash.h:72
h
h
Definition: flowhash_template.h:372
key
typedef key
Definition: ipsec_types.api:88
qhash_get_first_match
u32 qhash_get_first_match(void *v, uword *search_keys, uword n_search_keys, uword *matching_key)
Definition: qhash.c:245
qhash_t::overflow_hash
uword * overflow_hash
Definition: qhash.h:56
qhash_t::log2_hash_size
u32 log2_hash_size
Definition: qhash.h:50
c
svmdb_client_t * c
Definition: vpp_get_metrics.c:48
uword
u64 uword
Definition: types.h:112
vec_header
static void * vec_header(void *v, uword header_bytes)
Find a user vector header.
Definition: vec_bootstrap.h:92
hash_elts
static uword hash_elts(void *v)
Definition: hash.h:118
always_inline
#define always_inline
Definition: rdma_mlx5dv.h:23
cache.h
u32
unsigned int u32
Definition: types.h:88
qhash_get_multiple
void qhash_get_multiple(void *v, uword *search_keys, uword n_search_keys, u32 *result_indices)
Definition: qhash.c:115
qhash_hash_mix
static uword qhash_hash_mix(qhash_t *h, uword key)
Definition: qhash.h:87
qhash_t::hash_keys
uword * hash_keys
Definition: qhash.h:62
qhash_t::hash_key_valid_bitmap
u8 * hash_key_valid_bitmap
Definition: qhash.h:60
length
char const int length
Definition: cJSON.h:163
hash.h
qhash_t::overflow_free_indices
u32 * overflow_free_indices
Definition: qhash.h:58
b
vlib_buffer_t ** b
Definition: nat44_ei_out2in.c:717
u8
unsigned char u8
Definition: types.h:56
a
a
Definition: bitmap.h:544
qhash_header
static qhash_t * qhash_header(void *v)
Definition: qhash.h:66
qhash_t::n_elts
u32 n_elts
Definition: qhash.h:48
qhash_t
Definition: qhash.h:45