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;
89 hash_foreach_pair (p0, h, {
90 p1 = hash_next (h, &hn);
91 error = CLIB_ERROR_ASSERT (p0 == p1);
97 error = CLIB_ERROR_ASSERT (!hash_next (h, &hn));
103 test1_format (u8 * s, va_list * args)
105 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
106 void *v = va_arg (*args, void *);
107 hash_pair_t *p = va_arg (*args, hash_pair_t *);
108 hash_t *h = hash_header (v);
110 return format (s, "0x%8U -> 0x%8U",
111 format_hex_bytes, &p->key, sizeof (p->key),
112 format_hex_bytes, &p->value[0], hash_value_bytes (h));
115 static clib_error_t *
116 test_word_key (hash_test_t * ht)
121 word *keys = 0, *vals = 0;
122 uword *is_inserted = 0;
124 clib_error_t *error = 0;
126 vec_resize (keys, ht->n_pairs);
127 vec_resize (vals, vec_len (keys));
129 h = hash_create (ht->fixed_hash_size, sizeof (vals[0]));
131 hash_set_pair_format (h, test1_format, 0);
132 if (ht->fixed_hash_size)
133 hash_set_flags (h, HASH_FLAG_NO_AUTO_GROW | HASH_FLAG_NO_AUTO_SHRINK);
139 for (i = 0; i < vec_len (keys); i++)
143 k = random_u32 (&ht->seed) & 0xfffff;
145 while (clib_bitmap_get (unique, k));
146 unique = clib_bitmap_ori (unique, k);
151 clib_bitmap_free (unique);
154 for (i = 0; i < ht->n_iterations; i++)
156 u32 vi = random_u32 (&ht->seed) % vec_len (keys);
158 if (clib_bitmap_get (is_inserted, vi))
159 hash_unset (h, keys[vi]);
161 hash_set (h, keys[vi], vals[vi]);
163 is_inserted = clib_bitmap_xori (is_inserted, vi);
165 if (ht->n_iterations_per_print > 0
166 && ((i + 1) % ht->n_iterations_per_print) == 0)
167 if_verbose ("iteration %d\n %U", i + 1, format_hash, h, ht->verbose);
169 if (ht->n_iterations_per_validate == 0
170 || (i + 1) % ht->n_iterations_per_validate)
177 hash_foreach_pair (p, h, {
179 ASSERT (keys[ki] == p->key);
183 if ((error = hash_validate (h)))
186 for (j = 0; j < vec_len (keys); j++)
189 v = hash_get (h, keys[j]);
191 CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
196 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
202 if ((error = hash_next_test (h)))
205 if_verbose ("%U", format_hash, h, ht->verbose);
207 for (i = 0; i < vec_len (keys); i++)
209 if (!clib_bitmap_get (is_inserted, i))
212 hash_unset (h, keys[i]);
213 is_inserted = clib_bitmap_xori (is_inserted, i);
215 if (ht->n_iterations_per_validate == 0
216 || (i + 1) % ht->n_iterations_per_validate)
219 if ((error = hash_validate (h)))
222 for (j = 0; j < vec_len (keys); j++)
225 v = hash_get (h, keys[j]);
227 CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
232 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
242 clib_bitmap_free (is_inserted);
245 fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
251 test2_format (u8 * s, va_list * args)
253 void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
254 void *v = va_arg (*args, void *);
255 hash_pair_t *p = va_arg (*args, hash_pair_t *);
256 hash_t *h = hash_header (v);
258 return format (s, "0x%8U <- %v",
259 format_hex_bytes, &p->value[0], hash_value_bytes (h),
263 static clib_error_t *
264 test_string_key (hash_test_t * ht)
270 uword *is_inserted = 0;
274 clib_error_t *error = 0;
276 vec_resize (keys, ht->n_pairs);
277 vec_resize (vals, vec_len (keys));
280 hash_create_vec (ht->fixed_hash_size, sizeof (keys[0][0]),
282 hash_set_pair_format (h, test2_format, 0);
283 if (ht->fixed_hash_size)
284 hash_set_flags (h, HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_NO_AUTO_GROW);
286 for (i = 0; i < vec_len (keys); i++)
288 keys[i] = random_string (&ht->seed, 5 + (random_u32 (&ht->seed) & 0xf));
289 keys[i] = format (keys[i], "%x", i);
290 vals[i] = random_u32 (&ht->seed);
293 for (i = 0; i < ht->n_iterations; i++)
295 u32 vi = random_u32 (&ht->seed) % vec_len (keys);
297 if (clib_bitmap_get (is_inserted, vi))
298 hash_unset_mem (h, keys[vi]);
300 hash_set_mem (h, keys[vi], vals[vi]);
302 is_inserted = clib_bitmap_xori (is_inserted, vi);
304 if (ht->n_iterations_per_print > 0
305 && ((i + 1) % ht->n_iterations_per_print) == 0)
306 if_verbose ("iteration %d\n %U", i + 1, format_hash, h, ht->verbose);
308 if (ht->n_iterations_per_validate == 0
309 || (i + 1) % ht->n_iterations_per_validate)
312 if ((error = hash_validate (h)))
315 for (j = 0; j < vec_len (keys); j++)
318 v = hash_get_mem (h, keys[j]);
320 CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
325 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
331 if ((error = hash_next_test (h)))
334 if_verbose ("%U", format_hash, h, ht->verbose);
336 for (i = 0; i < vec_len (keys); i++)
338 if (!clib_bitmap_get (is_inserted, i))
341 hash_unset_mem (h, keys[i]);
342 is_inserted = clib_bitmap_xori (is_inserted, i);
344 if (ht->n_iterations_per_validate == 0
345 || (i + 1) % ht->n_iterations_per_validate)
348 if ((error = hash_validate (h)))
351 for (j = 0; j < vec_len (keys); j++)
354 v = hash_get_mem (h, keys[j]);
356 CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
361 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
370 clib_bitmap_free (is_inserted);
372 for (i = 0; i < vec_len (keys); i++)
377 fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
383 test_hash_main (unformat_input_t * input)
385 hash_test_t _ht = { 0 }, *ht = &_ht;
388 ht->n_iterations = 100;
390 ht->fixed_hash_size = 0; /* zero means non-fixed size */
392 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
394 if (0 == unformat (input, "iter %d", &ht->n_iterations)
395 && 0 == unformat (input, "print %d", &ht->n_iterations_per_print)
396 && 0 == unformat (input, "elts %d", &ht->n_pairs)
397 && 0 == unformat (input, "size %d", &ht->fixed_hash_size)
398 && 0 == unformat (input, "seed %d", &ht->seed)
399 && 0 == unformat (input, "verbose %=", &ht->verbose, 1)
400 && 0 == unformat (input, "valid %d",
401 &ht->n_iterations_per_validate))
403 clib_warning ("unknown input `%U'", format_unformat_error, input);
409 ht->seed = random_default_seed ();
411 if_verbose ("testing %d iterations, seed %d", ht->n_iterations, ht->seed);
413 error = test_word_key (ht);
415 clib_error_report (error);
417 error = test_string_key (ht);
419 clib_error_report (error);
426 main (int argc, char *argv[])
431 clib_mem_init (0, 3ULL << 30);
433 verbose = (argc > 1);
434 unformat_init_command_line (&i, argv);
435 ret = test_hash_main (&i);
440 #endif /* CLIB_UNIX */
443 * fd.io coding-style-patch-verification: ON
446 * eval: (c-set-style "gnu")