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 clib_mem_validate ();
189 if ((error = hash_validate (h)))
192 for (j = 0; j < vec_len (keys); j++)
195 v = hash_get (h, keys[j]);
197 CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
202 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
208 if ((error = hash_next_test (h)))
211 if_verbose ("%U", format_hash, h, ht->verbose);
213 for (i = 0; i < vec_len (keys); i++)
215 if (!clib_bitmap_get (is_inserted, i))
218 hash_unset (h, keys[i]);
219 is_inserted = clib_bitmap_xori (is_inserted, i);
221 if (ht->n_iterations_per_validate == 0
222 || (i + 1) % ht->n_iterations_per_validate)
225 clib_mem_validate ();
227 if ((error = hash_validate (h)))
230 for (j = 0; j < vec_len (keys); j++)
233 v = hash_get (h, keys[j]);
235 CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
240 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
250 clib_bitmap_free (is_inserted);
253 fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
259 test2_format (u8 * s, va_list * args)
261 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
262 void *v = va_arg (*args, void *);
263 hash_pair_t *p = va_arg (*args, hash_pair_t *);
264 hash_t *h = hash_header (v);
266 return format (s, "0x%8U <- %v",
267 format_hex_bytes, &p->value[0], hash_value_bytes (h),
271 static clib_error_t *
272 test_string_key (hash_test_t * ht)
278 uword *is_inserted = 0;
282 clib_error_t *error = 0;
284 vec_resize (keys, ht->n_pairs);
285 vec_resize (vals, vec_len (keys));
288 hash_create_vec (ht->fixed_hash_size, sizeof (keys[0][0]),
290 hash_set_pair_format (h, test2_format, 0);
291 if (ht->fixed_hash_size)
292 hash_set_flags (h, HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_NO_AUTO_GROW);
294 for (i = 0; i < vec_len (keys); i++)
296 keys[i] = random_string (&ht->seed, 5 + (random_u32 (&ht->seed) & 0xf));
297 keys[i] = format (keys[i], "%x", i);
298 vals[i] = random_u32 (&ht->seed);
301 for (i = 0; i < ht->n_iterations; i++)
303 u32 vi = random_u32 (&ht->seed) % vec_len (keys);
305 if (clib_bitmap_get (is_inserted, vi))
306 hash_unset_mem (h, keys[vi]);
308 hash_set_mem (h, keys[vi], vals[vi]);
310 is_inserted = clib_bitmap_xori (is_inserted, vi);
312 if (ht->n_iterations_per_print > 0
313 && ((i + 1) % ht->n_iterations_per_print) == 0)
314 if_verbose ("iteration %d\n %U", i + 1, format_hash, h, ht->verbose);
316 if (ht->n_iterations_per_validate == 0
317 || (i + 1) % ht->n_iterations_per_validate)
320 clib_mem_validate ();
322 if ((error = hash_validate (h)))
325 for (j = 0; j < vec_len (keys); j++)
328 v = hash_get_mem (h, keys[j]);
330 CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
335 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
341 if ((error = hash_next_test (h)))
344 if_verbose ("%U", format_hash, h, ht->verbose);
346 for (i = 0; i < vec_len (keys); i++)
348 if (!clib_bitmap_get (is_inserted, i))
351 hash_unset_mem (h, keys[i]);
352 is_inserted = clib_bitmap_xori (is_inserted, i);
354 if (ht->n_iterations_per_validate == 0
355 || (i + 1) % ht->n_iterations_per_validate)
358 clib_mem_validate ();
360 if ((error = hash_validate (h)))
363 for (j = 0; j < vec_len (keys); j++)
366 v = hash_get_mem (h, keys[j]);
368 CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
373 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
382 clib_bitmap_free (is_inserted);
384 for (i = 0; i < vec_len (keys); i++)
389 fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
395 test_hash_main (unformat_input_t * input)
397 hash_test_t _ht = { 0 }, *ht = &_ht;
400 ht->n_iterations = 100;
402 ht->fixed_hash_size = 0; /* zero means non-fixed size */
404 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
406 if (0 == unformat (input, "iter %d", &ht->n_iterations)
407 && 0 == unformat (input, "print %d", &ht->n_iterations_per_print)
408 && 0 == unformat (input, "elts %d", &ht->n_pairs)
409 && 0 == unformat (input, "size %d", &ht->fixed_hash_size)
410 && 0 == unformat (input, "seed %d", &ht->seed)
411 && 0 == unformat (input, "verbose %=", &ht->verbose, 1)
412 && 0 == unformat (input, "valid %d",
413 &ht->n_iterations_per_validate))
415 clib_warning ("unknown input `%U'", format_unformat_error, input);
421 ht->seed = random_default_seed ();
423 if_verbose ("testing %d iterations, seed %d", ht->n_iterations, ht->seed);
425 error = test_word_key (ht);
427 clib_error_report (error);
429 error = test_string_key (ht);
431 clib_error_report (error);
438 main (int argc, char *argv[])
443 verbose = (argc > 1);
444 unformat_init_command_line (&i, argv);
445 ret = test_hash_main (&i);
450 #endif /* CLIB_UNIX */
453 * fd.io coding-style-patch-verification: ON
456 * eval: (c-set-style "gnu")