--- /dev/null
+/*
+ * Copyright (c) 2015 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifdef CLIB_UNIX
+# include <unistd.h>
+# include <stdlib.h>
+# include <stdio.h>
+#endif
+
+#include <vppinfra/slist.h>
+
+typedef struct {
+ u32 *random_pool;
+ u32 seed;
+ u32 iter;
+ u32 verbose;
+ f64 branching_factor;
+ clib_slist_t slist;
+} test_main_t;
+
+test_main_t test_main;
+
+#define foreach_simple_test \
+_(2) \
+_(4) \
+_(3) \
+_(1)
+
+
+void run_test (test_main_t *tm)
+{
+ int i;
+ u32 * tv;
+ u32 ncompares;
+ u64 total_compares = 0;
+
+ if (1) {
+ /*
+ * Add a bunch of random numbers to the skip-list,
+ * sorting them.
+ */
+ for (i = 0; i < tm->iter; i++)
+ {
+ pool_get (tm->random_pool, tv);
+ *tv = random_u32 (&tm->seed);
+ clib_slist_add (&tm->slist, tv, tv - tm->random_pool);
+ }
+ /* make sure we can find each one */
+ for (i = 0; i < tm->iter; i++)
+ {
+ u32 search_result;
+ tv = pool_elt_at_index (tm->random_pool, i);
+
+ search_result = clib_slist_search (&tm->slist, tv, &ncompares);
+ ASSERT(search_result == i);
+
+ total_compares +=ncompares;
+ }
+
+ fformat(stdout, "%.2f avg compares/search\n",
+ (f64)total_compares / (f64)i);
+
+ fformat(stdout, "%U\n", format_slist, &tm->slist,
+ tm->iter < 1000 /* verbose */);
+
+ /* delete half of them */
+ for (i = tm->iter / 2; i < tm->iter ; i++)
+ {
+ tv = pool_elt_at_index (tm->random_pool, i);
+ (void) clib_slist_del (&tm->slist, tv);
+ }
+
+ /* make sure we can find the set we should find, and no others */
+ for (i = 0; i < tm->iter; i++)
+ {
+ u32 search_result;
+ tv = pool_elt_at_index (tm->random_pool, i);
+
+ search_result = clib_slist_search (&tm->slist, tv, &ncompares);
+ if (i >= tm->iter/2)
+ ASSERT(search_result == (u32)~0);
+ else
+ ASSERT(search_result == i);
+
+ }
+
+ fformat(stdout, "%U\n", format_slist, &tm->slist,
+ tm->iter < 1000 /* verbose */);
+
+ /* delete the rest */
+ for (i = 0; i < tm->iter; i++)
+ {
+ tv = pool_elt_at_index (tm->random_pool, i);
+
+ (void) clib_slist_del (&tm->slist, tv);
+ }
+
+ fformat(stdout, "%U\n", format_slist, &tm->slist,
+ tm->iter < 1000 /* verbose */);
+ } else {
+
+#define _(n) \
+ do { \
+ pool_get (tm->random_pool, tv); \
+ *tv = n; \
+ clib_slist_add (&tm->slist, tv, tv - tm->random_pool); \
+ fformat(stdout, "%U\n", format_slist, &tm->slist, 1 /* verbose */); \
+ } while (0);
+ foreach_simple_test;
+#undef _
+ }
+
+ return;
+}
+
+word test_compare (void *key, u32 elt_index)
+{
+ u32 * k = (u32 *)key;
+ u32 elt = test_main.random_pool[elt_index];
+
+ if (*k < elt)
+ return -1;
+ if (*k > elt)
+ return 1;
+ return 0;
+}
+
+u8 * test_format (u8 * s, va_list * args)
+{
+ u32 elt_index = va_arg (*args, u32);
+ u32 elt = test_main.random_pool[elt_index];
+
+ return format (s, "%u", elt);
+}
+
+void initialize_slist (test_main_t *tm)
+{
+ clib_slist_init (&tm->slist, tm->branching_factor,
+ test_compare,
+ test_format);
+}
+
+int test_slist_main (unformat_input_t *input)
+{
+ test_main_t *tm = &test_main;
+ u32 tmp;
+
+ tm->seed = 0xbabeb00b;
+ tm->iter = 10000000;
+ tm->verbose = 1;
+ tm->branching_factor = 1.0 / 5.0;
+
+ while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
+ {
+ if (unformat (input, "seed %d", &tm->seed))
+ continue;
+ else if (unformat (input, "iter %d", &tm->iter))
+ continue;
+ else if (unformat (input, "verbose"))
+ tm->verbose = 1;
+ else if (unformat (input, "branch %d", &tmp))
+ {
+ if (tmp > 0)
+ tm->branching_factor = 1.0 / (f64) tmp;
+ else
+ fformat(stderr, "warning: branch = 0, ignored\n");
+ }
+ else
+ {
+ clib_error ("unknown input `%U'", format_unformat_error, input);
+ goto usage;
+ }
+ }
+ initialize_slist (tm);
+ run_test (tm);
+
+ return 0;
+
+ usage:
+ fformat(stderr, "usage: test_slist seed <seed> iter <iter> [verbose]\n");
+ return 1;
+
+}
+
+#ifdef CLIB_UNIX
+int main (int argc, char * argv[])
+{
+ unformat_input_t i;
+ int ret;
+
+ clib_mem_init (0, (u64)8<<30);
+
+ unformat_init_command_line (&i, argv);
+ ret = test_slist_main (&i);
+ unformat_free (&i);
+
+ return ret;
+}
+#endif /* CLIB_UNIX */
Code Review / vpp.git / blobdiff