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) 2001, 2002, 2003 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 #ifdef CLIB_LINUX_KERNEL
39 #include <linux/unistd.h>
46 #include <vppinfra/time.h>
49 #include <vppinfra/random.h>
50 #include <vppinfra/mem.h>
51 #include <vppinfra/hash.h>
52 #include <vppinfra/error.h>
53 #include <vppinfra/format.h>
54 #include <vppinfra/bitmap.h>
57 #define if_verbose(format,args...) \
58 if (verbose) { clib_warning(format, ## args); }
64 int n_iterations_per_print;
66 /* Number of pairs to insert into hash. */
69 /* True to validate correctness of hash functions. */
70 int n_iterations_per_validate;
72 /* Non-zero if hash table size is to be fixed. */
75 /* Verbosity level for hash formats. */
78 /* Random number seed. */
83 hash_next_test (word * h)
85 hash_next_t hn = { 0 };
87 clib_error_t *error = 0;
90 hash_foreach_pair (p0, h, {
91 p1 = hash_next (h, &hn);
92 error = CLIB_ERROR_ASSERT (p0 == p1);
99 error = CLIB_ERROR_ASSERT (!hash_next (h, &hn));
105 test1_format (u8 * s, va_list * args)
107 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
108 void *v = va_arg (*args, void *);
109 hash_pair_t *p = va_arg (*args, hash_pair_t *);
110 hash_t *h = hash_header (v);
112 return format (s, "0x%8U -> 0x%8U",
113 format_hex_bytes, &p->key, sizeof (p->key),
114 format_hex_bytes, &p->value[0], hash_value_bytes (h));
117 static clib_error_t *
118 test_word_key (hash_test_t * ht)
123 word *keys = 0, *vals = 0;
124 uword *is_inserted = 0;
126 clib_error_t *error = 0;
128 vec_resize (keys, ht->n_pairs);
129 vec_resize (vals, vec_len (keys));
131 h = hash_create (ht->fixed_hash_size, sizeof (vals[0]));
133 hash_set_pair_format (h, test1_format, 0);
134 if (ht->fixed_hash_size)
135 hash_set_flags (h, HASH_FLAG_NO_AUTO_GROW | HASH_FLAG_NO_AUTO_SHRINK);
141 for (i = 0; i < vec_len (keys); i++)
145 k = random_u32 (&ht->seed) & 0xfffff;
147 while (clib_bitmap_get (unique, k));
148 unique = clib_bitmap_ori (unique, k);
153 clib_bitmap_free (unique);
156 for (i = 0; i < ht->n_iterations; i++)
158 u32 vi = random_u32 (&ht->seed) % vec_len (keys);
160 if (clib_bitmap_get (is_inserted, vi))
161 hash_unset (h, keys[vi]);
163 hash_set (h, keys[vi], vals[vi]);
165 is_inserted = clib_bitmap_xori (is_inserted, vi);
167 if (ht->n_iterations_per_print > 0
168 && ((i + 1) % ht->n_iterations_per_print) == 0)
169 if_verbose ("iteration %d\n %U", i + 1, format_hash, h, ht->verbose);
171 if (ht->n_iterations_per_validate == 0
172 || (i + 1) % ht->n_iterations_per_validate)
180 hash_foreach_pair (p, h, {
182 ASSERT (keys[ki] == p->key);
187 if ((error = hash_validate (h)))
190 for (j = 0; j < vec_len (keys); j++)
193 v = hash_get (h, keys[j]);
195 CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
200 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
206 if ((error = hash_next_test (h)))
209 if_verbose ("%U", format_hash, h, ht->verbose);
211 for (i = 0; i < vec_len (keys); i++)
213 if (!clib_bitmap_get (is_inserted, i))
216 hash_unset (h, keys[i]);
217 is_inserted = clib_bitmap_xori (is_inserted, i);
219 if (ht->n_iterations_per_validate == 0
220 || (i + 1) % ht->n_iterations_per_validate)
223 if ((error = hash_validate (h)))
226 for (j = 0; j < vec_len (keys); j++)
229 v = hash_get (h, keys[j]);
231 CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
236 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
246 clib_bitmap_free (is_inserted);
249 fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
255 test2_format (u8 * s, va_list * args)
257 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
258 void *v = va_arg (*args, void *);
259 hash_pair_t *p = va_arg (*args, hash_pair_t *);
260 hash_t *h = hash_header (v);
262 return format (s, "0x%8U <- %v",
263 format_hex_bytes, &p->value[0], hash_value_bytes (h),
267 static clib_error_t *
268 test_string_key (hash_test_t * ht)
274 uword *is_inserted = 0;
278 clib_error_t *error = 0;
280 vec_resize (keys, ht->n_pairs);
281 vec_resize (vals, vec_len (keys));
284 hash_create_vec (ht->fixed_hash_size, sizeof (keys[0][0]),
286 hash_set_pair_format (h, test2_format, 0);
287 if (ht->fixed_hash_size)
288 hash_set_flags (h, HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_NO_AUTO_GROW);
290 for (i = 0; i < vec_len (keys); i++)
292 keys[i] = random_string (&ht->seed, 5 + (random_u32 (&ht->seed) & 0xf));
293 keys[i] = format (keys[i], "%x", i);
294 vals[i] = random_u32 (&ht->seed);
297 for (i = 0; i < ht->n_iterations; i++)
299 u32 vi = random_u32 (&ht->seed) % vec_len (keys);
301 if (clib_bitmap_get (is_inserted, vi))
302 hash_unset_mem (h, keys[vi]);
304 hash_set_mem (h, keys[vi], vals[vi]);
306 is_inserted = clib_bitmap_xori (is_inserted, vi);
308 if (ht->n_iterations_per_print > 0
309 && ((i + 1) % ht->n_iterations_per_print) == 0)
310 if_verbose ("iteration %d\n %U", i + 1, format_hash, h, ht->verbose);
312 if (ht->n_iterations_per_validate == 0
313 || (i + 1) % ht->n_iterations_per_validate)
316 if ((error = hash_validate (h)))
319 for (j = 0; j < vec_len (keys); j++)
322 v = hash_get_mem (h, keys[j]);
324 CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
329 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
335 if ((error = hash_next_test (h)))
338 if_verbose ("%U", format_hash, h, ht->verbose);
340 for (i = 0; i < vec_len (keys); i++)
342 if (!clib_bitmap_get (is_inserted, i))
345 hash_unset_mem (h, keys[i]);
346 is_inserted = clib_bitmap_xori (is_inserted, i);
348 if (ht->n_iterations_per_validate == 0
349 || (i + 1) % ht->n_iterations_per_validate)
352 if ((error = hash_validate (h)))
355 for (j = 0; j < vec_len (keys); j++)
358 v = hash_get_mem (h, keys[j]);
360 CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
365 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
374 clib_bitmap_free (is_inserted);
376 for (i = 0; i < vec_len (keys); i++)
381 fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
387 test_hash_main (unformat_input_t * input)
389 hash_test_t _ht = { 0 }, *ht = &_ht;
392 ht->n_iterations = 100;
394 ht->fixed_hash_size = 0; /* zero means non-fixed size */
396 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
398 if (0 == unformat (input, "iter %d", &ht->n_iterations)
399 && 0 == unformat (input, "print %d", &ht->n_iterations_per_print)
400 && 0 == unformat (input, "elts %d", &ht->n_pairs)
401 && 0 == unformat (input, "size %d", &ht->fixed_hash_size)
402 && 0 == unformat (input, "seed %d", &ht->seed)
403 && 0 == unformat (input, "verbose %=", &ht->verbose, 1)
404 && 0 == unformat (input, "valid %d",
405 &ht->n_iterations_per_validate))
407 clib_warning ("unknown input `%U'", format_unformat_error, input);
413 ht->seed = random_default_seed ();
415 if_verbose ("testing %d iterations, seed %d", ht->n_iterations, ht->seed);
417 error = test_word_key (ht);
419 clib_error_report (error);
421 error = test_string_key (ht);
423 clib_error_report (error);
430 main (int argc, char *argv[])
435 clib_mem_init (0, 3ULL << 30);
437 verbose = (argc > 1);
438 unformat_init_command_line (&i, argv);
439 ret = test_hash_main (&i);
444 #endif /* CLIB_UNIX */
447 * fd.io coding-style-patch-verification: ON
450 * eval: (c-set-style "gnu")