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
124 mhash_key_sum_c_string (hash_t * h, uword key)
126 mhash_t * hv = uword_to_pointer (h->user, mhash_t *);
127 void * k = mhash_key_to_mem (hv, key);
128 return mhash_key_sum_inline (k, strlen (k), hv->hash_seed);
132 mhash_key_equal_c_string (hash_t * h, uword key1, uword key2)
134 mhash_t * hv = uword_to_pointer (h->user, mhash_t *);
135 void * k1 = mhash_key_to_mem (hv, key1);
136 void * k2 = mhash_key_to_mem (hv, key2);
137 return strcmp (k1, k2) == 0;
141 mhash_key_sum_vec_string (hash_t * h, uword key)
143 mhash_t * hv = uword_to_pointer (h->user, mhash_t *);
144 void * k = mhash_key_to_mem (hv, key);
145 return mhash_key_sum_inline (k, vec_len (k), hv->hash_seed);
149 mhash_key_equal_vec_string (hash_t * h, uword key1, uword key2)
151 mhash_t * hv = uword_to_pointer (h->user, mhash_t *);
152 void * k1 = mhash_key_to_mem (hv, key1);
153 void * k2 = mhash_key_to_mem (hv, key2);
154 return vec_len (k1) == vec_len (k2) && memcmp (k1, k2, vec_len (k1)) == 0;
157 /* The CLIB hash user pointer must always point to a valid mhash_t.
158 Now, the address of mhash_t can change (think vec_resize).
159 So we must always be careful that it points to the correct
162 mhash_sanitize_hash_user (mhash_t * mh)
164 uword * hash = mh->hash;
165 hash_t * h = hash_header (hash);
166 h->user = pointer_to_uword (mh);
169 void 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;
175 #define _(N_KEY_BYTES) \
177 .key_sum = mhash_key_sum_##N_KEY_BYTES, \
178 .key_equal = mhash_key_equal_##N_KEY_BYTES, \
181 foreach_mhash_key_size
185 [MHASH_C_STRING_KEY] = {
186 .key_sum = mhash_key_sum_c_string,
187 .key_equal = mhash_key_equal_c_string,
190 [MHASH_VEC_STRING_KEY] = {
191 .key_sum = mhash_key_sum_vec_string,
192 .key_equal = mhash_key_equal_vec_string,
196 if (mhash_key_vector_is_heap (h))
197 heap_free (h->key_vector_or_heap);
199 vec_free (h->key_vector_or_heap);
200 vec_free (h->key_vector_free_indices);
203 for (i = 0; i < vec_len (h->key_tmps); i++)
204 vec_free (h->key_tmps[i]);
206 vec_free (h->key_tmps);
209 memset (h, 0, sizeof (h[0]));
210 h->n_key_bytes = n_key_bytes;
213 if (h->n_key_bytes > 0)
215 vec_validate (h->key_tmp, h->n_key_bytes-1);
216 _vec_len(h->key_tmp) = 0;
220 ASSERT (n_key_bytes < ARRAY_LEN (t));
221 h->hash = hash_create2 (/* elts */ 0,
222 /* user */ pointer_to_uword (h),
223 /* value_bytes */ n_value_bytes,
224 t[n_key_bytes].key_sum,
225 t[n_key_bytes].key_equal,
226 /* format pair/arg */
230 static uword mhash_set_tmp_key (mhash_t * h, void * key)
233 int my_cpu = os_get_cpu_number();
235 vec_validate(h->key_tmps, my_cpu);
236 key_tmp = h->key_tmps[my_cpu];
238 vec_reset_length (key_tmp);
240 if (mhash_key_vector_is_heap (h))
242 uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
245 vec_add (key_tmp, key, strlen (key) + 1);
247 vec_add (key_tmp, key, vec_len (key));
250 vec_add (key_tmp, key, h->n_key_bytes);
252 h->key_tmps[my_cpu] = key_tmp;
257 hash_pair_t * mhash_get_pair (mhash_t * h, void * key)
260 mhash_sanitize_hash_user (h);
261 ikey = mhash_set_tmp_key (h, key);
262 return hash_get_pair (h->hash, ikey);
268 /* Must conincide with vec_header. */
270 } mhash_string_key_t;
272 uword mhash_set_mem (mhash_t * h, void * key, uword * new_value, uword * old_value)
275 uword ikey, i, l=0, n_key_bytes, old_n_elts, key_alloc_from_free_list = 0;
277 mhash_sanitize_hash_user (h);
279 if (mhash_key_vector_is_heap (h))
281 mhash_string_key_t * sk;
282 uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
285 n_key_bytes = is_c_string ? (strlen (key) + 1) : vec_len (key);
286 i = heap_alloc (h->key_vector_or_heap, n_key_bytes + sizeof (sk[0]), handle);
288 sk = (void *) (h->key_vector_or_heap + i);
289 sk->heap_handle = handle;
290 sk->vec.len = n_key_bytes;
291 memcpy (sk->vec.vector_data, key, n_key_bytes);
293 /* Advance key past vector header. */
298 key_alloc_from_free_list = (l = vec_len (h->key_vector_free_indices)) > 0;
299 if (key_alloc_from_free_list)
301 i = h->key_vector_free_indices[l - 1];
302 k = vec_elt_at_index (h->key_vector_or_heap, i);
303 _vec_len (h->key_vector_free_indices) = l - 1;
307 vec_add2 (h->key_vector_or_heap, k, h->n_key_bytes);
308 i = k - h->key_vector_or_heap;
311 n_key_bytes = h->n_key_bytes;
312 memcpy (k, key, n_key_bytes);
316 old_n_elts = hash_elts (h->hash);
317 h->hash = _hash_set3 (h->hash, ikey, new_value, old_value);
319 /* If element already existed remove duplicate key. */
320 if (hash_elts (h->hash) == old_n_elts)
324 /* Fetch old key for return value. */
325 p = hash_get_pair (h->hash, ikey);
328 /* Remove duplicate key. */
329 if (mhash_key_vector_is_heap (h))
331 mhash_string_key_t * sk;
332 sk = (void *) (h->key_vector_or_heap + i - sizeof (sk[0]));
333 heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
337 if (key_alloc_from_free_list)
339 h->key_vector_free_indices[l] = i;
340 _vec_len (h->key_vector_free_indices) = l + 1;
343 _vec_len (h->key_vector_or_heap) -= h->n_key_bytes;
350 uword mhash_unset (mhash_t * h, void * key, uword * old_value)
355 mhash_sanitize_hash_user (h);
356 i = mhash_set_tmp_key (h, key);
358 p = hash_get_pair (h->hash, i);
362 ASSERT (p->key != ~0);
365 if (mhash_key_vector_is_heap (h))
367 mhash_string_key_t * sk;
368 sk = (void *) (h->key_vector_or_heap + i) - sizeof (sk[0]);
369 heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
372 vec_add1 (h->key_vector_free_indices, i);
374 hash_unset3 (h->hash, i, old_value);
378 u8 * format_mhash_key (u8 * s, va_list * va)
380 mhash_t * h = va_arg (*va, mhash_t *);
381 u32 ki = va_arg (*va, u32);
382 void * k = mhash_key_to_mem (h, ki);
384 if (mhash_key_vector_is_heap (h))
386 uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
387 u32 l = is_c_string ? strlen (k) : vec_len (k);
390 else if (h->format_key)
391 s = format (s, "%U", h->format_key, k);
393 s = format (s, "%U", format_hex_bytes, k, h->n_key_bytes);