#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
#include <errno.h>
#include <time.h>
#include <stdio.h>
#include "../mkavl.h"

Classes
struct	test_mkavl_opts_st_
struct	mkavl_test_input_st_
struct	mkavl_test_ctx_st_
struct	mkavl_test_walk_ctx_st_
Defines
#define	LOG_FAIL(fmt, args...)
#define	NELEMS(x) (sizeof(x) / sizeof(x[0]))
#define	CT_ASSERT(e) extern char (CT_ASSERT(void)) [sizeof(char[1 - 2!(e)])]
#define	MKAVL_TEST_RUNAWAY_SANITY 100000
#define	MKAVL_TEST_MAGIC 0x1234ABCD
Typedefs
typedef struct test_mkavl_opts_st_	test_mkavl_opts_st
typedef struct mkavl_test_input_st_	mkavl_test_input_st
typedef struct mkavl_test_ctx_st_	mkavl_test_ctx_st
typedef enum mkavl_test_key_e_	mkavl_test_key_e
typedef struct mkavl_test_walk_ctx_st_	mkavl_test_walk_ctx_st
Enumerations
enum	mkavl_test_key_e_ { MKAVL_TEST_KEY_E_ASC, MKAVL_TEST_KEY_E_DESC, MKAVL_TEST_KEY_E_MAX }
Functions
static void	print_usage (bool do_exit, int32_t exit_val)
static void	print_opts (test_mkavl_opts_st *opts)
static void	parse_command_line (int argc, char *argv, test_mkavl_opts_st opts)
static void	permute_array (const uint32_t src_array, uint32_t dst_array, size_t num_elem)
static int	uint32_t_cmp (const void a, const void b)
static uint32_t	get_unique_count (uint32_t *array, size_t num_elem)
static bool	run_mkavl_test (mkavl_test_input_st *input)
int	main (int argc, char *argv[])
static void *	mkavl_test_copy_malloc (size_t size, void *context)
static void	mkavl_test_copy_free (void ptr, void context)
static int32_t	mkavl_cmp_fn1 (const void item1, const void item2, void *context)
static int32_t	mkavl_cmp_fn2 (const void item1, const void item2, void *context)
static bool	mkavl_test_new_error (void)
static bool	mkavl_test_new (mkavl_test_input_st input, mkavl_allocator_st allocator)
static mkavl_rc_e	mkavl_test_delete_context (void *context)
static bool	mkavl_test_delete (mkavl_test_input_st *input, mkavl_item_fn item_fn, mkavl_delete_context_fn delete_context_fn, mkavl_delete_context_fn delete_copy_context_fn)
static bool	mkavl_test_add_error (mkavl_test_input_st *input)
static bool	mkavl_test_add (mkavl_test_input_st *input)
static uint32_t *	mkavl_test_find_val (mkavl_test_input_st *input, uint32_t val, mkavl_find_type_e type)
static bool	mkavl_test_find (mkavl_test_input_st *input, mkavl_find_type_e type)
static bool	mkavl_test_find_error (mkavl_test_input_st *input)
static bool	mkavl_test_add_remove_key (mkavl_test_input_st *input)
static bool	mkavl_test_add_key_error (mkavl_test_input_st *input)
static bool	mkavl_test_remove_key_error (mkavl_test_input_st *input)
static void *	mkavl_test_copy_fn (void item, void context)
static bool	mkavl_test_copy (mkavl_test_input_st *input)
static bool	mkavl_test_iterator (mkavl_test_input_st *input)
static mkavl_rc_e	mkavl_test_walk_cb (void item, void tree_context, void walk_context, bool stop_walk)
static bool	mkavl_test_walk (mkavl_test_input_st *input)
static bool	mkavl_test_remove (mkavl_test_input_st *input)
static mkavl_rc_e	mkavl_test_item_fn (void item, void context)
Variables
static const uint32_t	default_node_cnt = 15
static const uint32_t	default_run_cnt = 15
static const uint8_t	default_verbosity = 0
static const uint32_t	default_range_start = 0
static const uint32_t	default_range_end = 100
static mkavl_allocator_st	copy_allocator
static const mkavl_test_key_e	mkavl_key_opposite []
static mkavl_compare_fn	cmp_fn_array [] = { mkavl_cmp_fn1 , mkavl_cmp_fn2 }
static const mkavl_find_type_e	mkavl_key_find_type [MKAVL_TEST_KEY_E_MAX][(MKAVL_FIND_TYPE_E_MAX+1)]

Detailed Description

Author:: Matt Miller <matt@matthewjmiller.net>

LICENSE

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.

DESCRIPTION

Unit test for mkavl library.

    Test the mkavl structure
  
    Usage:
    -s <seed>
       The starting seed for the RNG (default=seeded by time()).
    -n <nodes>
       The number of nodes to place in the trees (default=15).
    -b <range beginning>
       The smallest (inclusive ) possible data value in the range of values
       (default=0).
    -e <range ending>
       The largest (exclusive) possible data value in the range of values
       (default=100).
    -r <runs>
       The number of runs to do (default=15).
    -v <verbosity level>
       A higher number gives more output (default=0).
   -h
      Display this help message.

Definition in file test_mkavl.c.

Define Documentation

#define CT_ASSERT ( e ) extern char (*CT_ASSERT(void)) [sizeof(char[1 - 2*!(e)])]

Compile time assert macro from: http://www.pixelbeat.org/programming/gcc/static_assert.html

Definition at line 75 of file test_mkavl.c.

#define LOG_FAIL	(	fmt,
		args...
	)

Value:

do { \
    printf("FAILURE(%s:%u): " fmt "\n", __FUNCTION__, __LINE__, ##args); \
} while (0)

Display a failure message.

Definition at line 58 of file test_mkavl.c.

#define MKAVL_TEST_MAGIC 0x1234ABCD

Magic value for sanity checks

Definition at line 451 of file test_mkavl.c.

#define MKAVL_TEST_RUNAWAY_SANITY 100000

Sanity check for infinite loops.

Definition at line 81 of file test_mkavl.c.

#define NELEMS ( x ) (sizeof(x) / sizeof(x[0]))

Determine the number of elements in an array.

Definition at line 67 of file test_mkavl.c.

Typedef Documentation

typedef struct mkavl_test_ctx_st_ mkavl_test_ctx_st

The context storted for a tree.

typedef struct mkavl_test_input_st_ mkavl_test_input_st

The input structure to pass test parameters to functions.

typedef enum mkavl_test_key_e_ mkavl_test_key_e

The values for the key ordering.

typedef struct mkavl_test_walk_ctx_st_ mkavl_test_walk_ctx_st

The context for mkavl_walk()

typedef struct test_mkavl_opts_st_ test_mkavl_opts_st

State for the current test execution.

Enumeration Type Documentation

enum mkavl_test_key_e_

The values for the key ordering.

Enumerator:

MKAVL_TEST_KEY_E_ASC	Ascending order
MKAVL_TEST_KEY_E_DESC	Descending order
MKAVL_TEST_KEY_E_MAX	Max value for boundary testing

Definition at line 582 of file test_mkavl.c.

Function Documentation

static uint32_t get_unique_count	(	uint32_t *	array,
		size_t	num_elem
	)		`[static]`

Get a count of the number of unique items in the array. This assumes the input array is sorted.

Parameters:

array	The sorted array.
num_elem	The number of elements in the array.

Returns:: The unique number of elements in the array.

Definition at line 317 of file test_mkavl.c.

int main	(	int	argc,
		char *	argv[]
	)

Main function to test objects.

Definition at line 370 of file test_mkavl.c.

static int32_t mkavl_cmp_fn1	(	const void *	item1,
		const void *	item2,
		void *	context
	)		`[static]`

Simply compare the uint32_t values.

Parameters:

item1	Item to compare
item2	Item to compare
context	Context for the tree

Returns:: Comparison result

Definition at line 528 of file test_mkavl.c.

static int32_t mkavl_cmp_fn2	(	const void *	item1,
		const void *	item2,
		void *	context
	)		`[static]`

Reverse the values of the items.

Parameters:

item1	Item to compare
item2	Item to compare
context	Context for the tree

Returns:: Comparison result

Definition at line 558 of file test_mkavl.c.

static bool mkavl_test_add ( mkavl_test_input_st * input ) [static]

Test mkavl_add().

Parameters:

input The input state for the test.

Returns:: True if test passed.

Definition at line 788 of file test_mkavl.c.

static bool mkavl_test_add_error ( mkavl_test_input_st * input ) [static]

Test mkavl_add() for error handling.

Parameters:

input The input state for the test.

Returns:: True if test passed.

Definition at line 753 of file test_mkavl.c.

static bool mkavl_test_add_key_error ( mkavl_test_input_st * input ) [static]

Test mkavl_add_key() for error handling.

Parameters:

input The input state for the test.

Returns:: True if test passed.

Definition at line 1214 of file test_mkavl.c.

static bool mkavl_test_add_remove_key ( mkavl_test_input_st * input ) [static]

Test mkavl_remove_key() and mkavl_add_key().

Parameters:

input The input state for the test.

Returns:: True if test passed.

Definition at line 1110 of file test_mkavl.c.

static bool mkavl_test_copy ( mkavl_test_input_st * input ) [static]

Test mkavl_copy().

Parameters:

input The input state for the test.

Returns:: True if test passed.

Definition at line 1330 of file test_mkavl.c.

static void* mkavl_test_copy_fn	(	void *	item,
		void *	context
	)		`[static]`

The callback for mkavl_copy().

Parameters:

item	The original item being copied.
context	The context for the tree.

Returns:: The item to place in the copied tree.

Definition at line 1309 of file test_mkavl.c.

static void mkavl_test_copy_free	(	void *	ptr,
		void *	context
	)		`[static]`

The free function for the copied tree.

Parameters:

ptr	The memory to free.
context	The tree context.

Definition at line 498 of file test_mkavl.c.

static void* mkavl_test_copy_malloc	(	size_t	size,
		void *	context
	)		`[static]`

The malloc function for the copied tree.

Parameters:

size	Size of memory to allocate.
context	The tree context.

Returns:: A pointer to the memory or NULL if allocation was not possible.

Definition at line 477 of file test_mkavl.c.

static bool mkavl_test_delete	(	mkavl_test_input_st *	input,
		mkavl_item_fn	item_fn,
		mkavl_delete_context_fn	delete_context_fn,
		mkavl_delete_context_fn	delete_copy_context_fn
	)		`[static]`

Test mkavl_delete().

Parameters:

input	The input state for the test.
item_fn	The function to apply to deleted items.
delete_context_fn	The function to apply to the tree's context.
delete_copy_context_fn	The function to apply to the copied tree's context.

Returns:: True if test passed.

Definition at line 720 of file test_mkavl.c.

static mkavl_rc_e mkavl_test_delete_context ( void * context ) [static]

The callback for freeing the context memory.

Parameters:

context The context to free.

Returns:: The return code

Definition at line 695 of file test_mkavl.c.

static bool mkavl_test_find	(	mkavl_test_input_st *	input,
		mkavl_find_type_e	type
	)		`[static]`

Test mkavl_find().

Parameters:

input	The input state for the test.
type	The type of find.

Returns:: True if test passed.

Definition at line 938 of file test_mkavl.c.

static bool mkavl_test_find_error ( mkavl_test_input_st * input ) [static]

Test mkavl_find() for error handling.

Parameters:

input The input state for the test.

Returns:: True if test passed.

Definition at line 1058 of file test_mkavl.c.

static uint32_t* mkavl_test_find_val	(	mkavl_test_input_st *	input,
		uint32_t	val,
		mkavl_find_type_e	type
	)		`[static]`

Test mkavl_find().

Parameters:

input	The input state for the test.
val	The value on which to search.
type	The type of find.

Returns:: True if test passed.

Definition at line 832 of file test_mkavl.c.

static mkavl_rc_e mkavl_test_item_fn	(	void *	item,
		void *	context
	)		`[static]`

The callback for per-item functions.

Parameters:

item	The current item.
context	The tree's context.

Returns:: The return code

Definition at line 1743 of file test_mkavl.c.

static bool mkavl_test_iterator ( mkavl_test_input_st * input ) [static]

Test mkavl iterators.

Parameters:

input The input state for the test.

Returns:: True if test passed.

Definition at line 1380 of file test_mkavl.c.

static bool mkavl_test_new	(	mkavl_test_input_st *	input,
		mkavl_allocator_st *	allocator
	)		`[static]`

Test mkavl_new().

Parameters:

input	The input state for the test.
allocator	The allocator to use.

Returns:: True if test passed.

Definition at line 666 of file test_mkavl.c.

static bool mkavl_test_new_error ( void ) [static]

Test mkavl_new() for error handling.

Returns:: True if test passed.

Definition at line 625 of file test_mkavl.c.

static bool mkavl_test_remove ( mkavl_test_input_st * input ) [static]

Test mkavl_remove().

Parameters:

input The input state for the test.

Returns:: True if test passed.

Definition at line 1700 of file test_mkavl.c.

static bool mkavl_test_remove_key_error ( mkavl_test_input_st * input ) [static]

Test mkavl_remove_key() for error handling.

Parameters:

input The input state for the test.

Returns:: True if test passed.

Definition at line 1261 of file test_mkavl.c.

static bool mkavl_test_walk ( mkavl_test_input_st * input ) [static]

Test mkavl_walk().

Parameters:

input The input state for the test.

Returns:: True if test passed.

Definition at line 1653 of file test_mkavl.c.

static mkavl_rc_e mkavl_test_walk_cb	(	void *	item,
		void *	tree_context,
		void *	walk_context,
		bool *	stop_walk
	)		`[static]`

The callback for mkavl_walk().

Parameters:

item	The current item in the walk.
tree_context	The tree's context.
walk_context	The walks' context.
stop_walk	Can be set true to stop the walk upon return.

Returns:: The return code

Definition at line 1625 of file test_mkavl.c.

static void parse_command_line	(	int	argc,
		char **	argv,
		test_mkavl_opts_st *	opts
	)		`[static]`

Store the command line options into a local structure.

Parameters:

argc	The number of options
argv	The string for the options.
opts	The local structure in which to store the parsed info.

Definition at line 175 of file test_mkavl.c.

static void permute_array	(	const uint32_t *	src_array,
		uint32_t *	dst_array,
		size_t	num_elem
	)		`[static]`

Create a permutation of the given array.

Parameters:

src_array	The array to permute.
dst_array	The output location of the permuted array.
num_elem	The number of array elements in the arrays.

Definition at line 267 of file test_mkavl.c.

static void print_opts ( test_mkavl_opts_st * opts ) [static]

Utility function to output the value of the options.

Parameters:

opts	The options to output.

Definition at line 155 of file test_mkavl.c.

static void print_usage	(	bool	do_exit,
		int32_t	exit_val
	)		`[static]`

Display the program's help screen and exit as needed.

Parameters:

do_exit	Whether to exit after the output.
exit_val	If exiting the value with which to exit.

Definition at line 119 of file test_mkavl.c.

static bool run_mkavl_test ( mkavl_test_input_st * input ) [static]

Runs all of the tests.

Parameters:

input The input state for the test.

Returns:: True if test passed.

Definition at line 1764 of file test_mkavl.c.

static int uint32_t_cmp	(	const void *	a,
		const void *	b
	)		`[static]`

Callback to compare two pointers to uint32_t's.

Parameters:

a	An item to compare.
b	The other item to compare.

Returns:: 0 if equal, -1 if a < b, and 1 if a > b

Definition at line 294 of file test_mkavl.c.

Variable Documentation

mkavl_compare_fn cmp_fn_array[] = { mkavl_cmp_fn1 , mkavl_cmp_fn2 } [static]

The comparison functions to use

Definition at line 598 of file test_mkavl.c.

mkavl_allocator_st copy_allocator [static]

Initial value:

 {
    mkavl_test_copy_malloc,
    mkavl_test_copy_free
}

Allocators to use for the copied tree.

Definition at line 514 of file test_mkavl.c.

const uint32_t default_node_cnt = 15 [static]

The default node count for runs

Definition at line 84 of file test_mkavl.c.

const uint32_t default_range_end = 100 [static]

The default end of the range for node data values

Definition at line 92 of file test_mkavl.c.

const uint32_t default_range_start = 0 [static]

The default start of the range for node data values

Definition at line 90 of file test_mkavl.c.

const uint32_t default_run_cnt = 15 [static]

The default number of test runs

Definition at line 86 of file test_mkavl.c.

const uint8_t default_verbosity = 0 [static]

The default verbosity level of messages displayed

Definition at line 88 of file test_mkavl.c.

const mkavl_find_type_e mkavl_key_find_type[MKAVL_TEST_KEY_E_MAX][(MKAVL_FIND_TYPE_E_MAX+1)] [static]

Initial value:

 {
    { MKAVL_FIND_TYPE_E_INVALID, MKAVL_FIND_TYPE_E_EQUAL,
      MKAVL_FIND_TYPE_E_GT, MKAVL_FIND_TYPE_E_LT,
      MKAVL_FIND_TYPE_E_GE, MKAVL_FIND_TYPE_E_LE,
      MKAVL_FIND_TYPE_E_MAX },
    { MKAVL_FIND_TYPE_E_INVALID, MKAVL_FIND_TYPE_E_EQUAL,
      MKAVL_FIND_TYPE_E_LT, MKAVL_FIND_TYPE_E_GT,
      MKAVL_FIND_TYPE_E_LE, MKAVL_FIND_TYPE_E_GE,
      MKAVL_FIND_TYPE_E_MAX }
}

The type to use for find lookups for the key types.

Definition at line 609 of file test_mkavl.c.

const mkavl_test_key_e mkavl_key_opposite[] [static]

Initial value:

 {
    MKAVL_TEST_KEY_E_DESC,
    MKAVL_TEST_KEY_E_ASC,
}

The opposite key, used for certain find operations

Definition at line 592 of file test_mkavl.c.

Classes

Defines

Typedefs

Enumerations

Functions

Variables

Detailed Description

LICENSE

DESCRIPTION

Define Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation