FD.io VPP  v18.01.2-1-g9b554f3
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  */
static uword qhash_n_overflow(void *v)
Definition: qhash.h:78
a
Definition: bitmap.h:516
static qhash_t * qhash_header(void *v)
Definition: qhash.h:66
u32 n_elts
Definition: qhash.h:48
#define always_inline
Definition: clib.h:92
static uword pow2_mask(uword x)
Definition: clib.h:265
u32 log2_hash_size
Definition: qhash.h:50
uword * overflow_hash
Definition: qhash.h:56
#define v
Definition: acl.c:341
static uword qhash_hash_mix(qhash_t *h, uword key)
Definition: qhash.h:87
svmdb_client_t * c
vec_header_t h
Definition: buffer.c:282
#define hash_mix32(a0, b0, c0)
Definition: hash.h:538
u32 qhash_get_first_match(void *v, uword *search_keys, uword n_search_keys, uword *matching_key)
Definition: qhash.c:244
static uword hash_elts(void *v)
Definition: hash.h:117
unsigned int u32
Definition: types.h:88
u32 hash_seeds[3]
Definition: qhash.h:53
static uword qhash_elts(void *v)
Definition: qhash.h:72
u64 uword
Definition: types.h:112
unsigned char u8
Definition: types.h:56
Definition: qhash.h:45
uword * hash_keys
Definition: qhash.h:62
static void * vec_header(void *v, uword header_bytes)
Find a user vector header.
Definition: vec_bootstrap.h:92
u32 * overflow_free_indices
Definition: qhash.h:58
u8 * hash_key_valid_bitmap
Definition: qhash.h:60
void qhash_get_multiple(void *v, uword *search_keys, uword n_search_keys, u32 *result_indices)
Definition: qhash.c:115