Reorganize source tree to use single autotools instance

[vpp.git] / src / vppinfra / test_slist.c

diff --git a/src/vppinfra/test_slist.c b/src/vppinfra/test_slist.c
new file mode 100644 (file)
index 0000000..3c3cbf7
--- /dev/null
+++ b/src/vppinfra/test_slist.c
@@ -0,0 +1,228 @@
+/*
+ * 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 = 100000;
+  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) 4 << 30);
+
+  unformat_init_command_line (&i, argv);
+  ret = test_slist_main (&i);
+  unformat_free (&i);
+
+  return ret;
+}
+#endif /* CLIB_UNIX */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */