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.
22 #include <vppinfra/slist.h>
34 test_main_t test_main;
36 #define foreach_simple_test \
44 run_test (test_main_t * tm)
49 u64 total_compares = 0;
54 * Add a bunch of random numbers to the skip-list,
57 for (i = 0; i < tm->iter; i++)
59 pool_get (tm->random_pool, tv);
60 *tv = random_u32 (&tm->seed);
61 clib_slist_add (&tm->slist, tv, tv - tm->random_pool);
63 /* make sure we can find each one */
64 for (i = 0; i < tm->iter; i++)
67 tv = pool_elt_at_index (tm->random_pool, i);
69 search_result = clib_slist_search (&tm->slist, tv, &ncompares);
70 ASSERT (search_result == i);
72 total_compares += ncompares;
75 fformat (stdout, "%.2f avg compares/search\n",
76 (f64) total_compares / (f64) i);
78 fformat (stdout, "%U\n", format_slist, &tm->slist,
79 tm->iter < 1000 /* verbose */ );
81 /* delete half of them */
82 for (i = tm->iter / 2; i < tm->iter; i++)
84 tv = pool_elt_at_index (tm->random_pool, i);
85 (void) clib_slist_del (&tm->slist, tv);
88 /* make sure we can find the set we should find, and no others */
89 for (i = 0; i < tm->iter; i++)
92 tv = pool_elt_at_index (tm->random_pool, i);
94 search_result = clib_slist_search (&tm->slist, tv, &ncompares);
95 if (i >= tm->iter / 2)
96 ASSERT (search_result == (u32) ~ 0);
98 ASSERT (search_result == i);
102 fformat (stdout, "%U\n", format_slist, &tm->slist,
103 tm->iter < 1000 /* verbose */ );
105 /* delete the rest */
106 for (i = 0; i < tm->iter; i++)
108 tv = pool_elt_at_index (tm->random_pool, i);
110 (void) clib_slist_del (&tm->slist, tv);
113 fformat (stdout, "%U\n", format_slist, &tm->slist,
114 tm->iter < 1000 /* verbose */ );
121 pool_get (tm->random_pool, tv); \
123 clib_slist_add (&tm->slist, tv, tv - tm->random_pool); \
124 fformat(stdout, "%U\n", format_slist, &tm->slist, 1 /* verbose */); \
134 test_compare (void *key, u32 elt_index)
136 u32 *k = (u32 *) key;
137 u32 elt = test_main.random_pool[elt_index];
147 test_format (u8 * s, va_list * args)
149 u32 elt_index = va_arg (*args, u32);
150 u32 elt = test_main.random_pool[elt_index];
152 return format (s, "%u", elt);
156 initialize_slist (test_main_t * tm)
158 clib_slist_init (&tm->slist, tm->branching_factor,
159 test_compare, test_format);
163 test_slist_main (unformat_input_t * input)
165 test_main_t *tm = &test_main;
168 tm->seed = 0xbabeb00b;
171 tm->branching_factor = 1.0 / 5.0;
173 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
175 if (unformat (input, "seed %d", &tm->seed))
177 else if (unformat (input, "iter %d", &tm->iter))
179 else if (unformat (input, "verbose"))
181 else if (unformat (input, "branch %d", &tmp))
184 tm->branching_factor = 1.0 / (f64) tmp;
186 fformat (stderr, "warning: branch = 0, ignored\n");
190 clib_error ("unknown input `%U'", format_unformat_error, input);
194 initialize_slist (tm);
200 fformat (stderr, "usage: test_slist seed <seed> iter <iter> [verbose]\n");
207 main (int argc, char *argv[])
212 clib_mem_init (0, (u64) 4 << 30);
214 unformat_init_command_line (&i, argv);
215 ret = test_slist_main (&i);
220 #endif /* CLIB_UNIX */
223 * fd.io coding-style-patch-verification: ON
226 * eval: (c-set-style "gnu")