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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 Copyright (c) 2006 Eliot Dresselhaus
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:
26 The above copyright notice and this permission notice shall be
27 included in all copies or substantial portions of the Software.
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.
38 #ifndef included_qhash_h
39 #define included_qhash_h
41 #include <vppinfra/cache.h>
42 #include <vppinfra/hash.h>
44 /* Word hash tables. */
46 /* Number of elements in hash. */
51 /* Jenkins hash seeds. */
54 /* Fall back CLIB hash for overflow in fixed sized buckets. */
55 uword * overflow_hash;
57 u32 * overflow_counts, * overflow_free_indices;
59 u8 * hash_key_valid_bitmap;
64 always_inline qhash_t *
65 qhash_header (void * v)
66 { return vec_header (v, sizeof (qhash_t)); }
70 { return v ? qhash_header (v)->n_elts : 0; }
73 qhash_n_overflow (void * v)
74 { return v ? hash_elts (qhash_header (v)->overflow_hash) : 0; }
76 #define QHASH_LOG2_KEYS_PER_BUCKET 2
77 #define QHASH_KEYS_PER_BUCKET (1 << QHASH_LOG2_KEYS_PER_BUCKET)
80 qhash_hash_mix (qhash_t * h, uword key)
95 return c & pow2_mask (h->log2_hash_size);
98 #define qhash_resize(v,n) (v) = _qhash_resize ((v), (n), sizeof ((v)[0]))
101 #define qhash_foreach(var,v,body)
103 #define qhash_set_multiple(v,keys,n,results) \
104 (v) = _qhash_set_multiple ((v), sizeof ((v)[0]), (keys), (n), (results))
106 #define qhash_unset_multiple(v,keys,n,results) \
107 _qhash_unset_multiple ((v), sizeof ((v)[0]), (keys), (n), (results))
109 #define qhash_get(v,key) \
111 uword _qhash_get_k = (key); \
112 qhash_get_first_match ((v), &_qhash_get_k, 1, &_qhash_get_k); \
115 #define qhash_set(v,k) \
117 uword _qhash_set_k = (k); \
118 qhash_set_multiple ((v), &_qhash_set_k, 1, &_qhash_set_k); \
122 #define qhash_unset(v,k) \
124 uword _qhash_unset_k = (k); \
125 qhash_unset_multiple ((v), &_qhash_unset_k, 1, &_qhash_unset_k); \
130 _qhash_resize (void * v, uword length, uword elt_bytes);
132 /* Lookup multiple keys in the same hash table. */
134 qhash_get_multiple (void * v,
137 u32 * result_indices);
139 /* Lookup multiple keys in the same hash table.
140 Returns index of first matching key. */
142 qhash_get_first_match (void * v,
145 uword * matching_key);
147 /* Set/unset helper functions. */
149 _qhash_set_multiple (void * v,
153 u32 * result_indices);
155 _qhash_unset_multiple (void * v,
159 u32 * result_indices);
161 #endif /* included_qhash_h */