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