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>
33 test_main_t test_main;
35 #define foreach_simple_test \
42 void run_test (test_main_t *tm)
47 u64 total_compares = 0;
51 * Add a bunch of random numbers to the skip-list,
54 for (i = 0; i < tm->iter; i++)
56 pool_get (tm->random_pool, tv);
57 *tv = random_u32 (&tm->seed);
58 clib_slist_add (&tm->slist, tv, tv - tm->random_pool);
60 /* make sure we can find each one */
61 for (i = 0; i < tm->iter; i++)
64 tv = pool_elt_at_index (tm->random_pool, i);
66 search_result = clib_slist_search (&tm->slist, tv, &ncompares);
67 ASSERT(search_result == i);
69 total_compares +=ncompares;
72 fformat(stdout, "%.2f avg compares/search\n",
73 (f64)total_compares / (f64)i);
75 fformat(stdout, "%U\n", format_slist, &tm->slist,
76 tm->iter < 1000 /* verbose */);
78 /* delete half of them */
79 for (i = tm->iter / 2; i < tm->iter ; i++)
81 tv = pool_elt_at_index (tm->random_pool, i);
82 (void) clib_slist_del (&tm->slist, tv);
85 /* make sure we can find the set we should find, and no others */
86 for (i = 0; i < tm->iter; i++)
89 tv = pool_elt_at_index (tm->random_pool, i);
91 search_result = clib_slist_search (&tm->slist, tv, &ncompares);
93 ASSERT(search_result == (u32)~0);
95 ASSERT(search_result == i);
99 fformat(stdout, "%U\n", format_slist, &tm->slist,
100 tm->iter < 1000 /* verbose */);
102 /* delete the rest */
103 for (i = 0; i < tm->iter; i++)
105 tv = pool_elt_at_index (tm->random_pool, i);
107 (void) clib_slist_del (&tm->slist, tv);
110 fformat(stdout, "%U\n", format_slist, &tm->slist,
111 tm->iter < 1000 /* verbose */);
116 pool_get (tm->random_pool, tv); \
118 clib_slist_add (&tm->slist, tv, tv - tm->random_pool); \
119 fformat(stdout, "%U\n", format_slist, &tm->slist, 1 /* verbose */); \
128 word test_compare (void *key, u32 elt_index)
130 u32 * k = (u32 *)key;
131 u32 elt = test_main.random_pool[elt_index];
140 u8 * test_format (u8 * s, va_list * args)
142 u32 elt_index = va_arg (*args, u32);
143 u32 elt = test_main.random_pool[elt_index];
145 return format (s, "%u", elt);
148 void initialize_slist (test_main_t *tm)
150 clib_slist_init (&tm->slist, tm->branching_factor,
155 int test_slist_main (unformat_input_t *input)
157 test_main_t *tm = &test_main;
160 tm->seed = 0xbabeb00b;
163 tm->branching_factor = 1.0 / 5.0;
165 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
167 if (unformat (input, "seed %d", &tm->seed))
169 else if (unformat (input, "iter %d", &tm->iter))
171 else if (unformat (input, "verbose"))
173 else if (unformat (input, "branch %d", &tmp))
176 tm->branching_factor = 1.0 / (f64) tmp;
178 fformat(stderr, "warning: branch = 0, ignored\n");
182 clib_error ("unknown input `%U'", format_unformat_error, input);
186 initialize_slist (tm);
192 fformat(stderr, "usage: test_slist seed <seed> iter <iter> [verbose]\n");
198 int main (int argc, char * argv[])
203 clib_mem_init (0, (u64)4<<30);
205 unformat_init_command_line (&i, argv);
206 ret = test_slist_main (&i);
211 #endif /* CLIB_UNIX */