1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
@media only all and (prefers-color-scheme: dark) {
.highlight .hll { background-color: #49483e }
.highlight .c { color: #75715e } /* Comment */
.highlight .err { color: #960050; background-color: #1e0010 } /* Error */
.highlight .k { color: #66d9ef } /* Keyword */
.highlight .l { color: #ae81ff } /* Literal */
.highlight .n { color: #f8f8f2 } /* Name */
.highlight .o { color: #f92672 } /* Operator */
.highlight .p { color: #f8f8f2 } /* Punctuation */
.highlight .ch { color: #75715e } /* Comment.Hashbang */
.highlight .cm { color: #75715e } /* Comment.Multiline */
.highlight .cp { color: #75715e } /* Comment.Preproc */
.highlight .cpf { color: #75715e } /* Comment.PreprocFile */
.highlight .c1 { color: #75715e } /* Comment.Single */
.highlight .cs { color: #75715e } /* Comment.Special */
.highlight .gd { color: #f92672 } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gi { color: #a6e22e } /* Generic.Inserted */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #75715e } /* Generic.Subheading */
.highlight .kc { color: #66d9ef } /* Keyword.Constant */
.highlight .kd { color: #66d9ef } /* Keyword.Declaration */
.highlight .kn { color: #f92672 } /* Keyword.Namespace */
.highlight .kp { color: #66d9ef } /* Keyword.Pseudo */
.highlight .kr { color: #66d9ef } /* Keyword.Reserved */
.highlight .kt { color: #66d9ef } /* Keyword.Type */
.highlight .ld { color: #e6db74 } /* Literal.Date */
.highlight .m { color: #ae81ff } /* Literal.Number */
.highlight .s { color: #e6db74 } /* Literal.String */
.highlight .na { color: #a6e22e } /* Name.Attribute */
.highlight .nb { color: #f8f8f2 } /* Name.Builtin */
.highlight .nc { color: #a6e22e } /* Name.Class */
.highlight .no { color: #66d9ef } /* Name.Constant */
.highlight .nd { color: #a6e22e } /* Name.Decorator */
.highlight .ni { color: #f8f8f2 } /* Name.Entity */
.highlight .ne { color: #a6e22e } /* Name.Exception */
.highlight .nf { color: #a6e22e } /* Name.Function */
.highlight .nl { color: #f8f8f2 } /* Name.Label */
.highlight .nn { color: #f8f8f2 } /* Name.Namespace */
.highlight .nx { color: #a6e22e } /* Name.Other */
.highlight .py { color: #f8f8f2 } /* Name.Property */
.highlight .nt { color: #f92672 } /* Name.Tag */
.highlight .nv { color: #f8f8f2 } /* Name.Variable */
.highlight .ow { color: #f92672 } /* Operator.Word */
.highlight .w { color: #f8f8f2 } /* Text.Whitespace */
.highlight .mb { color: #ae81ff } /* Literal.Number.Bin */
.highlight .mf { color: #ae81ff } /* Literal.Number.Float */
.highlight .mh { color: #ae81ff } /* Literal.Number.Hex */
.highlight .mi { color: #ae81ff } /* Literal.Number.Integer */
.highlight .mo { color: #ae81ff } /* Literal.Number.Oct */
.highlight .sa { color: #e6db74 } /* Literal.String.Affix */
.highlight .sb { color: #e6db74 } /* Literal.String.Backtick */
.highlight .sc { color: #e6db74 } /* Literal.String.Char */
.highlight .dl { color: #e6db74 } /* Literal.String.Delimiter */
.highlight .sd { color: #e6db74 } /* Literal.String.Doc */
.highlight .s2 { color: #e6db74 } /* Literal.String.Double */
.highlight .se { color: #ae81ff } /* Literal.String.Escape */
.highlight .sh { color: #e6db74 } /* Literal.String.Heredoc */
.highlight .si { color: #e6db74 } /* Literal.String.Interpol */
.highlight .sx { color: #e6db74 } /* Literal.String.Other */
.highlight .sr { color: #e6db74 } /* Literal.String.Regex */
.highlight .s1 { color: #e6db74 } /* Literal.String.Single */
.highlight .ss { color: #e6db74 } /* Literal.String.Symbol */
.highlight .bp { color: #f8f8f2 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #a6e22e } /* Name.Function.Magic */
.highlight .vc { color: #f8f8f2 } /* Name.Variable.Class */
.highlight .vg { color: #f8f8f2 } /* Name.Variable.Global */
.highlight .vi { color: #f8f8f2 } /* Name.Variable.Instance */
.highlight .vm { color: #f8f8f2 } /* Name.Variable.Magic */
.highlight .il { color: #ae81ff } /* Literal.Number.Integer.Long */
}
@media (prefers-color-scheme: light) {
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: /*
* 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:
*/
|