vppinfra/vppinfra/test_slist.c

   1 /*
   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:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   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.
  14  */
  15
  16 #ifdef CLIB_UNIX
  17 #include <unistd.h>
  18 #include <stdlib.h>
  19 #include <stdio.h>
  20 #endif
  21
  22 #include <vppinfra/slist.h>
  23
  24 typedef struct
  25 {
  26   u32 *random_pool;
  27   u32 seed;
  28   u32 iter;
  29   u32 verbose;
  30   f64 branching_factor;
  31   clib_slist_t slist;
  32 } test_main_t;
  33
  34 test_main_t test_main;
  35
  36 #define foreach_simple_test                     \
  37 _(2)                                            \
  38 _(4)                                            \
  39 _(3)                                            \
  40 _(1)
  41
  42
  43 void
  44 run_test (test_main_t * tm)
  45 {
  46   int i;
  47   u32 *tv;
  48   u32 ncompares;
  49   u64 total_compares = 0;
  50
  51   if (1)
  52     {
  53       /*
  54        * Add a bunch of random numbers to the skip-list,
  55        * sorting them.
  56        */
  57       for (i = 0; i < tm->iter; i++)
  58         {
  59           pool_get (tm->random_pool, tv);
  60           *tv = random_u32 (&tm->seed);
  61           clib_slist_add (&tm->slist, tv, tv - tm->random_pool);
  62         }
  63       /* make sure we can find each one */
  64       for (i = 0; i < tm->iter; i++)
  65         {
  66           u32 search_result;
  67           tv = pool_elt_at_index (tm->random_pool, i);
  68
  69           search_result = clib_slist_search (&tm->slist, tv, &ncompares);
  70           ASSERT (search_result == i);
  71
  72           total_compares += ncompares;
  73         }
  74
  75       fformat (stdout, "%.2f avg compares/search\n",
  76                (f64) total_compares / (f64) i);
  77
  78       fformat (stdout, "%U\n", format_slist, &tm->slist,
  79                tm->iter < 1000 /* verbose */ );
  80
  81       /* delete half of them */
  82       for (i = tm->iter / 2; i < tm->iter; i++)
  83         {
  84           tv = pool_elt_at_index (tm->random_pool, i);
  85           (void) clib_slist_del (&tm->slist, tv);
  86         }
  87
  88       /* make sure we can find the set we should find, and no others */
  89       for (i = 0; i < tm->iter; i++)
  90         {
  91           u32 search_result;
  92           tv = pool_elt_at_index (tm->random_pool, i);
  93
  94           search_result = clib_slist_search (&tm->slist, tv, &ncompares);
  95           if (i >= tm->iter / 2)
  96             ASSERT (search_result == (u32) ~ 0);
  97           else
  98             ASSERT (search_result == i);
  99
 100         }
 101
 102       fformat (stdout, "%U\n", format_slist, &tm->slist,
 103                tm->iter < 1000 /* verbose */ );
 104
 105       /* delete the rest */
 106       for (i = 0; i < tm->iter; i++)
 107         {
 108           tv = pool_elt_at_index (tm->random_pool, i);
 109
 110           (void) clib_slist_del (&tm->slist, tv);
 111         }
 112
 113       fformat (stdout, "%U\n", format_slist, &tm->slist,
 114                tm->iter < 1000 /* verbose */ );
 115     }
 116   else
 117     {
 118
 119 #define _(n)                                                            \
 120     do {                                                                \
 121       pool_get (tm->random_pool, tv);                                   \
 122       *tv = n;                                                          \
 123       clib_slist_add (&tm->slist, tv, tv - tm->random_pool);            \
 124       fformat(stdout, "%U\n", format_slist, &tm->slist, 1 /* verbose */); \
 125     } while (0);
 126       foreach_simple_test;
 127 #undef _
 128     }
 129
 130   return;
 131 }
 132
 133 word
 134 test_compare (void *key, u32 elt_index)
 135 {
 136   u32 *k = (u32 *) key;
 137   u32 elt = test_main.random_pool[elt_index];
 138
 139   if (*k < elt)
 140     return -1;
 141   if (*k > elt)
 142     return 1;
 143   return 0;
 144 }
 145
 146 u8 *
 147 test_format (u8 * s, va_list * args)
 148 {
 149   u32 elt_index = va_arg (*args, u32);
 150   u32 elt = test_main.random_pool[elt_index];
 151
 152   return format (s, "%u", elt);
 153 }
 154
 155 void
 156 initialize_slist (test_main_t * tm)
 157 {
 158   clib_slist_init (&tm->slist, tm->branching_factor,
 159                    test_compare, test_format);
 160 }
 161
 162 int
 163 test_slist_main (unformat_input_t * input)
 164 {
 165   test_main_t *tm = &test_main;
 166   u32 tmp;
 167
 168   tm->seed = 0xbabeb00b;
 169   tm->iter = 100000;
 170   tm->verbose = 1;
 171   tm->branching_factor = 1.0 / 5.0;
 172
 173   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 174     {
 175       if (unformat (input, "seed %d", &tm->seed))
 176         continue;
 177       else if (unformat (input, "iter %d", &tm->iter))
 178         continue;
 179       else if (unformat (input, "verbose"))
 180         tm->verbose = 1;
 181       else if (unformat (input, "branch %d", &tmp))
 182         {
 183           if (tmp > 0)
 184             tm->branching_factor = 1.0 / (f64) tmp;
 185           else
 186             fformat (stderr, "warning: branch = 0, ignored\n");
 187         }
 188       else
 189         {
 190           clib_error ("unknown input `%U'", format_unformat_error, input);
 191           goto usage;
 192         }
 193     }
 194   initialize_slist (tm);
 195   run_test (tm);
 196
 197   return 0;
 198
 199 usage:
 200   fformat (stderr, "usage: test_slist seed <seed> iter <iter> [verbose]\n");
 201   return 1;
 202
 203 }
 204
 205 #ifdef CLIB_UNIX
 206 int
 207 main (int argc, char *argv[])
 208 {
 209   unformat_input_t i;
 210   int ret;
 211
 212   clib_mem_init (0, (u64) 4 << 30);
 213
 214   unformat_init_command_line (&i, argv);
 215   ret = test_slist_main (&i);
 216   unformat_free (&i);
 217
 218   return ret;
 219 }
 220 #endif /* CLIB_UNIX */
 221
 222 /*
 223  * fd.io coding-style-patch-verification: ON
 224  *
 225  * Local Variables:
 226  * eval: (c-set-style "gnu")
 227  * End:
 228  */