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) 2010 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 #include <vppinfra/mhash.h>
41 load_partial_u32 (void *d, uword n)
44 return ((u32 *) d)[0];
46 return ((u16 *) d)[0] | (((u8 *) d)[2] << 16);
48 return ((u16 *) d)[0];
56 mhash_key_sum_inline (void *data, uword n_data_bytes, u32 seed)
62 n_left = n_data_bytes;
70 hash_v3_mix32 (a, b, c);
77 c += load_partial_u32 (d32 + 2, n_left - 8);
82 b += load_partial_u32 (d32 + 1, n_left - 4);
86 a += load_partial_u32 (d32 + 0, n_left - 0);
88 hash_v3_finalize32 (a, b, c);
93 #define foreach_mhash_key_size \
94 _ (2) _ (3) _ (4) _ (5) _ (6) _ (7) \
95 _ (8) _ (12) _ (16) _ (20) \
96 _ (24) _ (28) _ (32) _ (36) \
97 _ (40) _ (44) _ (48) _ (52) \
100 #define _(N_KEY_BYTES) \
102 mhash_key_sum_##N_KEY_BYTES (hash_t * h, uword key) \
104 mhash_t * hv = uword_to_pointer (h->user, mhash_t *); \
105 return mhash_key_sum_inline (mhash_key_to_mem (hv, key), \
111 mhash_key_equal_##N_KEY_BYTES (hash_t * h, uword key1, uword key2) \
113 mhash_t * hv = uword_to_pointer (h->user, mhash_t *); \
114 void * k1 = mhash_key_to_mem (hv, key1); \
115 void * k2 = mhash_key_to_mem (hv, key2); \
116 return ! memcmp (k1, k2, (N_KEY_BYTES)); \
119 foreach_mhash_key_size
122 mhash_key_sum_c_string (hash_t * h, uword key)
124 mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
125 void *k = mhash_key_to_mem (hv, key);
126 return mhash_key_sum_inline (k, strlen (k), hv->hash_seed);
130 mhash_key_equal_c_string (hash_t * h, uword key1, uword key2)
132 mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
133 void *k1 = mhash_key_to_mem (hv, key1);
134 void *k2 = mhash_key_to_mem (hv, key2);
135 return strcmp (k1, k2) == 0;
139 mhash_key_sum_vec_string (hash_t * h, uword key)
141 mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
142 void *k = mhash_key_to_mem (hv, key);
143 return mhash_key_sum_inline (k, vec_len (k), hv->hash_seed);
147 mhash_key_equal_vec_string (hash_t * h, uword key1, uword key2)
149 mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
150 void *k1 = mhash_key_to_mem (hv, key1);
151 void *k2 = mhash_key_to_mem (hv, key2);
152 return vec_len (k1) == vec_len (k2) && memcmp (k1, k2, vec_len (k1)) == 0;
155 /* The CLIB hash user pointer must always point to a valid mhash_t.
156 Now, the address of mhash_t can change (think vec_resize).
157 So we must always be careful that it points to the correct
160 mhash_sanitize_hash_user (mhash_t * mh)
162 uword *hash = mh->hash;
163 hash_t *h = hash_header (hash);
164 h->user = pointer_to_uword (mh);
168 mhash_init (mhash_t * h, uword n_value_bytes, uword n_key_bytes)
172 hash_key_sum_function_t *key_sum;
173 hash_key_equal_function_t *key_equal;
176 #define _(N_KEY_BYTES) \
178 .key_sum = mhash_key_sum_##N_KEY_BYTES, \
179 .key_equal = mhash_key_equal_##N_KEY_BYTES, \
182 foreach_mhash_key_size
184 [MHASH_C_STRING_KEY] =
186 .key_sum = mhash_key_sum_c_string,.key_equal = mhash_key_equal_c_string,},
187 [MHASH_VEC_STRING_KEY] =
189 .key_sum = mhash_key_sum_vec_string,.key_equal =
190 mhash_key_equal_vec_string,},};
192 if (mhash_key_vector_is_heap (h))
193 heap_free (h->key_vector_or_heap);
195 vec_free (h->key_vector_or_heap);
196 vec_free (h->key_vector_free_indices);
199 for (i = 0; i < vec_len (h->key_tmps); i++)
200 vec_free (h->key_tmps[i]);
202 vec_free (h->key_tmps);
205 clib_memset (h, 0, sizeof (h[0]));
206 h->n_key_bytes = n_key_bytes;
208 vec_validate (h->key_tmps, os_get_nthreads () - 1);
210 ASSERT (n_key_bytes < ARRAY_LEN (t));
211 h->hash = hash_create2 ( /* elts */ 0,
212 /* user */ pointer_to_uword (h),
213 /* value_bytes */ n_value_bytes,
214 t[n_key_bytes].key_sum, t[n_key_bytes].key_equal,
215 /* format pair/arg */
220 mhash_set_tmp_key (mhash_t * h, const void *key)
223 int my_cpu = os_get_thread_index ();
225 key_tmp = h->key_tmps[my_cpu];
227 vec_reset_length (key_tmp);
229 if (mhash_key_vector_is_heap (h))
231 uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
234 vec_add (key_tmp, key, strlen (key) + 1);
236 vec_add (key_tmp, key, vec_len (key));
239 vec_add (key_tmp, key, h->n_key_bytes);
241 h->key_tmps[my_cpu] = key_tmp;
246 __clib_export hash_pair_t *
247 mhash_get_pair (mhash_t * h, const void *key)
250 mhash_sanitize_hash_user (h);
251 ikey = mhash_set_tmp_key (h, key);
252 return hash_get_pair (h->hash, ikey);
259 /* Must coincide with vec_header. */
261 } mhash_string_key_t;
264 mhash_set_mem (mhash_t * h, void *key, uword * new_value, uword * old_value)
267 uword ikey, i, l = 0, n_key_bytes, old_n_elts, key_alloc_from_free_list = 0;
269 mhash_sanitize_hash_user (h);
271 if (mhash_key_vector_is_heap (h))
273 mhash_string_key_t *sk;
274 uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
277 n_key_bytes = is_c_string ? (strlen (key) + 1) : vec_len (key);
279 heap_alloc (h->key_vector_or_heap, n_key_bytes + sizeof (sk[0]),
282 sk = (void *) (h->key_vector_or_heap + i);
283 sk->heap_handle = handle;
284 sk->vec.len = n_key_bytes;
285 clib_memcpy_fast (sk->vec.vector_data, key, n_key_bytes);
287 /* Advance key past vector header. */
292 key_alloc_from_free_list = (l =
293 vec_len (h->key_vector_free_indices)) > 0;
294 if (key_alloc_from_free_list)
296 i = h->key_vector_free_indices[l - 1];
297 k = vec_elt_at_index (h->key_vector_or_heap, i);
298 _vec_len (h->key_vector_free_indices) = l - 1;
302 vec_add2 (h->key_vector_or_heap, k, h->n_key_bytes);
303 i = k - h->key_vector_or_heap;
306 n_key_bytes = h->n_key_bytes;
307 clib_memcpy_fast (k, key, n_key_bytes);
311 old_n_elts = hash_elts (h->hash);
312 h->hash = _hash_set3 (h->hash, ikey, new_value, old_value);
314 /* If element already existed remove duplicate key. */
315 if (hash_elts (h->hash) == old_n_elts)
319 /* Fetch old key for return value. */
320 p = hash_get_pair (h->hash, ikey);
323 /* Remove duplicate key. */
324 if (mhash_key_vector_is_heap (h))
326 mhash_string_key_t *sk;
327 sk = (void *) (h->key_vector_or_heap + i - sizeof (sk[0]));
328 heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
332 if (key_alloc_from_free_list)
334 h->key_vector_free_indices[l] = i;
335 _vec_len (h->key_vector_free_indices) = l + 1;
338 _vec_len (h->key_vector_or_heap) -= h->n_key_bytes;
346 mhash_unset (mhash_t * h, void *key, uword * old_value)
351 mhash_sanitize_hash_user (h);
352 i = mhash_set_tmp_key (h, key);
354 p = hash_get_pair (h->hash, i);
358 ASSERT (p->key != ~0);
361 if (mhash_key_vector_is_heap (h))
363 mhash_string_key_t *sk;
364 sk = (void *) (h->key_vector_or_heap + i) - sizeof (sk[0]);
365 heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
368 vec_add1 (h->key_vector_free_indices, i);
370 hash_unset3 (h->hash, i, old_value);
375 format_mhash_key (u8 * s, va_list * va)
377 mhash_t *h = va_arg (*va, mhash_t *);
378 u32 ki = va_arg (*va, u32);
379 void *k = mhash_key_to_mem (h, ki);
381 if (mhash_key_vector_is_heap (h))
383 uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
384 u32 l = is_c_string ? strlen (k) : vec_len (k);
387 else if (h->format_key)
388 s = format (s, "%U", h->format_key, k);
390 s = format (s, "%U", format_hex_bytes, k, h->n_key_bytes);
396 * fd.io coding-style-patch-verification: ON
399 * eval: (c-set-style "gnu")