Line data Source code
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 : #ifndef included_clib_mhash_h
16 : #define included_clib_mhash_h
17 :
18 : /*
19 : Copyright (c) 2010 Eliot Dresselhaus
20 :
21 : Permission is hereby granted, free of charge, to any person obtaining
22 : a copy of this software and associated documentation files (the
23 : "Software"), to deal in the Software without restriction, including
24 : without limitation the rights to use, copy, modify, merge, publish,
25 : distribute, sublicense, and/or sell copies of the Software, and to
26 : permit persons to whom the Software is furnished to do so, subject to
27 : the following conditions:
28 :
29 : The above copyright notice and this permission notice shall be
30 : included in all copies or substantial portions of the Software.
31 :
32 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33 : EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34 : MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35 : NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36 : LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37 : OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38 : WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39 : */
40 :
41 : #include <vppinfra/format.h>
42 : #include <vppinfra/hash.h>
43 : #include <vppinfra/heap.h>
44 :
45 : /* Hash table plus vector of keys. */
46 : typedef struct
47 : {
48 : /* Vector or heap used to store keys. Hash table stores keys as byte
49 : offsets into this vector. */
50 : u8 *key_vector_or_heap;
51 :
52 : /* Byte offsets of free keys in vector (used to store free keys when
53 : n_key_bytes > 1). */
54 : u32 *key_vector_free_indices;
55 :
56 : u8 **key_tmps;
57 :
58 : /* Possibly fixed size of key.
59 : 0 means keys are vectors of u8's.
60 : 1 means keys are null terminated c strings. */
61 : #define MHASH_VEC_STRING_KEY 0
62 : #define MHASH_C_STRING_KEY 1
63 : u32 n_key_bytes;
64 :
65 : /* Seed value for Jenkins hash. */
66 : u32 hash_seed;
67 :
68 : /* Hash table mapping key -> value. */
69 : uword *hash;
70 :
71 : /* Format function for keys. */
72 : format_function_t *format_key;
73 : } mhash_t;
74 :
75 : void mhash_init (mhash_t * h, uword n_value_bytes, uword n_key_bytes);
76 :
77 : always_inline void
78 575 : mhash_init_c_string (mhash_t * h, uword n_value_bytes)
79 : {
80 575 : mhash_init (h, n_value_bytes, MHASH_C_STRING_KEY);
81 575 : }
82 :
83 : always_inline void
84 596 : mhash_init_vec_string (mhash_t * h, uword n_value_bytes)
85 : {
86 596 : mhash_init (h, n_value_bytes, MHASH_VEC_STRING_KEY);
87 596 : }
88 :
89 : always_inline void *
90 235163 : mhash_key_to_mem (mhash_t * h, uword key)
91 : {
92 235163 : if (key == ~0)
93 : {
94 : u8 *key_tmp;
95 :
96 117582 : int my_cpu = os_get_thread_index ();
97 117582 : vec_validate (h->key_tmps, my_cpu);
98 117582 : key_tmp = h->key_tmps[my_cpu];
99 117582 : return key_tmp;
100 : }
101 117581 : return vec_elt_at_index (h->key_vector_or_heap, key);
102 : }
103 :
104 : hash_pair_t *mhash_get_pair (mhash_t * h, const void *key);
105 : uword mhash_set_mem (mhash_t * h, void *key, uword * new_value,
106 : uword * old_value);
107 : uword mhash_unset (mhash_t * h, void *key, uword * old_value);
108 :
109 : always_inline uword *
110 74048 : mhash_get (mhash_t * h, const void *key)
111 : {
112 74048 : hash_pair_t *p = mhash_get_pair (h, key);
113 74048 : return p ? &p->value[0] : 0;
114 : }
115 :
116 : always_inline uword
117 17379 : mhash_set (mhash_t * h, void *key, uword new_value, uword * old_value)
118 : {
119 17379 : return mhash_set_mem (h, key, &new_value, old_value);
120 : }
121 :
122 : always_inline uword
123 : mhash_unset_key (mhash_t * h, uword key, uword * old_value)
124 : {
125 : void *k = mhash_key_to_mem (h, key);
126 : return mhash_unset (h, k, old_value);
127 : }
128 :
129 : always_inline uword
130 : mhash_value_bytes (mhash_t * m)
131 : {
132 : hash_t *h = hash_header (m->hash);
133 : return hash_value_bytes (h);
134 : }
135 :
136 : always_inline uword
137 0 : mhash_elts (mhash_t * m)
138 : {
139 0 : return hash_elts (m->hash);
140 : }
141 :
142 : always_inline uword
143 140169 : mhash_key_vector_is_heap (mhash_t * h)
144 : {
145 140169 : return h->n_key_bytes <= 1;
146 : }
147 :
148 : always_inline void
149 3590 : mhash_free (mhash_t * h)
150 : {
151 3590 : if (mhash_key_vector_is_heap (h))
152 0 : heap_free (h->key_vector_or_heap);
153 : else
154 3590 : vec_free (h->key_vector_or_heap);
155 3590 : vec_free (h->key_vector_free_indices);
156 3590 : hash_free (h->hash);
157 3590 : }
158 :
159 : #define mhash_foreach(k,v,mh,body) \
160 : do { \
161 : hash_pair_t * _mhash_foreach_p; \
162 : hash_foreach_pair (_mhash_foreach_p, (mh)->hash, ({ \
163 : (k) = mhash_key_to_mem ((mh), _mhash_foreach_p->key); \
164 : (v) = &_mhash_foreach_p->value[0]; \
165 : body; \
166 : })); \
167 : } while (0)
168 :
169 : format_function_t format_mhash_key;
170 :
171 : #endif /* included_clib_mhash_h */
172 :
173 : /*
174 : * fd.io coding-style-patch-verification: ON
175 : *
176 : * Local Variables:
177 : * eval: (c-set-style "gnu")
178 : * End:
179 : */
|
