path: root/src/vppinfra/test_slist.c

/*
 * 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:
 */