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 memset (h, 0, sizeof (h[0]));
206 h->n_key_bytes = n_key_bytes;
209 if (h->n_key_bytes > 0)
211 vec_validate (h->key_tmp, h->n_key_bytes - 1);
212 _vec_len (h->key_tmp) = 0;
216 ASSERT (n_key_bytes < ARRAY_LEN (t));
217 h->hash = hash_create2 ( /* elts */ 0,
218 /* user */ pointer_to_uword (h),
219 /* value_bytes */ n_value_bytes,
220 t[n_key_bytes].key_sum, t[n_key_bytes].key_equal,
221 /* format pair/arg */
226 mhash_set_tmp_key (mhash_t * h, const void *key)
229 int my_cpu = os_get_cpu_number ();
231 vec_validate (h->key_tmps, my_cpu);
232 key_tmp = h->key_tmps[my_cpu];
234 vec_reset_length (key_tmp);
236 if (mhash_key_vector_is_heap (h))
238 uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
241 vec_add (key_tmp, key, strlen (key) + 1);
243 vec_add (key_tmp, key, vec_len (key));
246 vec_add (key_tmp, key, h->n_key_bytes);
248 h->key_tmps[my_cpu] = key_tmp;
254 mhash_get_pair (mhash_t * h, const void *key)
257 mhash_sanitize_hash_user (h);
258 ikey = mhash_set_tmp_key (h, key);
259 return hash_get_pair (h->hash, ikey);
266 /* Must conincide with vec_header. */
268 } mhash_string_key_t;
271 mhash_set_mem (mhash_t * h, void *key, uword * new_value, uword * old_value)
274 uword ikey, i, l = 0, n_key_bytes, old_n_elts, key_alloc_from_free_list = 0;
276 mhash_sanitize_hash_user (h);
278 if (mhash_key_vector_is_heap (h))
280 mhash_string_key_t *sk;
281 uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
284 n_key_bytes = is_c_string ? (strlen (key) + 1) : vec_len (key);
286 heap_alloc (h->key_vector_or_heap, n_key_bytes + sizeof (sk[0]),
289 sk = (void *) (h->key_vector_or_heap + i);
290 sk->heap_handle = handle;
291 sk->vec.len = n_key_bytes;
292 clib_memcpy (sk->vec.vector_data, key, n_key_bytes);
294 /* Advance key past vector header. */
299 key_alloc_from_free_list = (l =
300 vec_len (h->key_vector_free_indices)) > 0;
301 if (key_alloc_from_free_list)
303 i = h->key_vector_free_indices[l - 1];
304 k = vec_elt_at_index (h->key_vector_or_heap, i);
305 _vec_len (h->key_vector_free_indices) = l - 1;
309 vec_add2 (h->key_vector_or_heap, k, h->n_key_bytes);
310 i = k - h->key_vector_or_heap;
313 n_key_bytes = h->n_key_bytes;
314 clib_memcpy (k, key, n_key_bytes);
318 old_n_elts = hash_elts (h->hash);
319 h->hash = _hash_set3 (h->hash, ikey, new_value, old_value);
321 /* If element already existed remove duplicate key. */
322 if (hash_elts (h->hash) == old_n_elts)
326 /* Fetch old key for return value. */
327 p = hash_get_pair (h->hash, ikey);
330 /* Remove duplicate key. */
331 if (mhash_key_vector_is_heap (h))
333 mhash_string_key_t *sk;
334 sk = (void *) (h->key_vector_or_heap + i - sizeof (sk[0]));
335 heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
339 if (key_alloc_from_free_list)
341 h->key_vector_free_indices[l] = i;
342 _vec_len (h->key_vector_free_indices) = l + 1;
345 _vec_len (h->key_vector_or_heap) -= h->n_key_bytes;
353 mhash_unset (mhash_t * h, void *key, uword * old_value)
358 mhash_sanitize_hash_user (h);
359 i = mhash_set_tmp_key (h, key);
361 p = hash_get_pair (h->hash, i);
365 ASSERT (p->key != ~0);
368 if (mhash_key_vector_is_heap (h))
370 mhash_string_key_t *sk;
371 sk = (void *) (h->key_vector_or_heap + i) - sizeof (sk[0]);
372 heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
375 vec_add1 (h->key_vector_free_indices, i);
377 hash_unset3 (h->hash, i, old_value);
382 format_mhash_key (u8 * s, va_list * va)
384 mhash_t *h = va_arg (*va, mhash_t *);
385 u32 ki = va_arg (*va, u32);
386 void *k = mhash_key_to_mem (h, ki);
388 if (mhash_key_vector_is_heap (h))
390 uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
391 u32 l = is_c_string ? strlen (k) : vec_len (k);
394 else if (h->format_key)
395 s = format (s, "%U", h->format_key, k);
397 s = format (s, "%U", format_hex_bytes, k, h->n_key_bytes);
403 * fd.io coding-style-patch-verification: ON
406 * eval: (c-set-style "gnu")