#include "examples_common.h"
#include <math.h>

Classes
struct	employee_example_opts_st_
struct	employee_obj_st_
struct	employee_example_input_st_
struct	employee_ctx_st_
struct	employee_walk_ctx_st_
Defines
#define	MAX_NAME_LEN 100
Typedefs
typedef enum employee_dist_e_	employee_dist_e
typedef struct employee_example_opts_st_	employee_example_opts_st
typedef struct employee_obj_st_	employee_obj_st
typedef struct employee_example_input_st_	employee_example_input_st
typedef struct employee_ctx_st_	employee_ctx_st
typedef struct employee_walk_ctx_st_	employee_walk_ctx_st
typedef enum employee_example_key_e_	employee_example_key_e
Enumerations
enum	employee_dist_e_ { EMPLOYEE_DIST_E_UNIFORM, EMPLOYEE_DIST_E_ZIPF, EMPLOYEE_DIST_E_MAX }
enum	employee_example_key_e_ { EMPLOYEE_EXAMPLE_KEY_E_ID, EMPLOYEE_EXAMPLE_KEY_E_LNAME_ID, EMPLOYEE_EXAMPLE_KEY_E_MAX }
Functions
static uint32_t	zipf (double alpha, uint32_t n)
static void	print_usage (bool do_exit, int32_t exit_val)
static void	print_opts (employee_example_opts_st *opts)
static void	parse_command_line (int argc, char *argv, employee_example_opts_st opts)
static int32_t	employee_cmp_by_id (const void item1, const void item2, void *context)
static int32_t	employee_cmp_by_last_name (const void item1, const void item2, void *context)
static bool	generate_employee (employee_example_input_st input, employee_obj_st *obj)
static void	display_employee (employee_obj_st *obj)
static mkavl_rc_e	free_employee (void item, void context)
static void	lookup_employees_by_last_name (employee_example_input_st input, const char last_name, uint32_t max_records, bool find_all, bool do_print)
static mkavl_rc_e	last_name_walk_cb (void item, void tree_context, void walk_context, bool stop_walk)
static void	run_employee_example (employee_example_input_st *input)
int	main (int argc, char *argv[])
Variables
static const uint32_t	default_employee_cnt = 1000
static const uint32_t	default_run_cnt = 1
static const uint8_t	default_verbosity = 0
static const employee_dist_e	default_last_name_dist = EMPLOYEE_DIST_E_UNIFORM
static const double	default_zipf_alpha = 1.0
static const char *	first_names []
static const char *	last_names []
static mkavl_compare_fn	cmp_fn_array []

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

This is an example of how the mkavl library can be used. This example consists of a DB of employees where their unique ID and first and last name is stored. The first names of employees are chosen uniformly at random from a list of 100 popular names. The last names of employees are, by default, chosen uniformly at random from a list of 100 common names. There is a command-line option to use a Zipf distribution instead for the last name to give significantly more weight towards choosing the most popular names.

Running the example gives two phases: functionality and performance.

For functionality:

Choose ten IDs uniformly at random and lookup the employee objects.
Choose a last name uniformly at random and lookup up to the first ten employees with that last name. Note that this is done in O(lg N) time.
Change the last name of an employee and show that all the lookups happen as expected.

For performance:

Choose 30 last names uniformly at random. Lookup all the employees with each last name using the mkavl tree keyed by last name and ID (O(lg N)). Then, lookup all the employees with each last name in the tree by walking through all nodes (as would typically be done for a non-key field) (O(N)).
Compare the wall clock time (i.e., from gettimeofday()) for both lookup methods and the total number of nodes walked for each method.

Performance results show for 1000 employees and 100 last names, the keyed lookup shows an improvement by a factor of 10 for uniformly distributed last names. For a Zipf distribution, a majority of the runs show about a factor of 20 improvement. However, some Zipf runs only show an improvement of about 3 (presumably when some of the most popular names are randomly chosen and there are just inherently a lot of employees to lookup for that name).

   Example of using mkavl for an employee DB
   
   Usage:
   -s <seed>
      The starting seed for the RNG (default=seeded by time()).
   -n <employees>
      The number of nodes to place in the trees (default=1000).
   -r <runs>
      The number of runs to do (default=1).
   -v <verbosity level>
      A higher number gives more output (default=0).
   -z
      Use Zipf distribution for last names (default=uniform).
   -a <Zipf alpha>
      If using a Zipf distribution, the alpha value to    
      parameterize the distribution (default=1.000000).
   -h
      Display this help message.

Definition in file employee_example.c.

Define Documentation

#define MAX_NAME_LEN 100

Upper bound on name string lengths.

Definition at line 109 of file employee_example.c.

Typedef Documentation

typedef struct employee_ctx_st_ employee_ctx_st

The context associated with the employee AVLs.

typedef enum employee_dist_e_ employee_dist_e

Probability distributions used within example.

typedef struct employee_example_input_st_ employee_example_input_st

The input structure to pass test parameters to functions.

typedef enum employee_example_key_e_ employee_example_key_e

The values for the key ordering.

typedef struct employee_example_opts_st_ employee_example_opts_st

State for the current test execution.

typedef struct employee_obj_st_ employee_obj_st

The data stored for employees.

typedef struct employee_walk_ctx_st_ employee_walk_ctx_st

Context for the walk of the employee AVLs.

Enumeration Type Documentation

enum employee_dist_e_

Probability distributions used within example.

Enumerator:

EMPLOYEE_DIST_E_UNIFORM	Uniform distribution
EMPLOYEE_DIST_E_ZIPF	Zipf distribution
EMPLOYEE_DIST_E_MAX	Max value for boundary checking

Definition at line 86 of file employee_example.c.

enum employee_example_key_e_

The values for the key ordering.

Enumerator:

EMPLOYEE_EXAMPLE_KEY_E_ID	Ordered by ID
EMPLOYEE_EXAMPLE_KEY_E_LNAME_ID	Ordered by last name + ID
EMPLOYEE_EXAMPLE_KEY_E_MAX	Max value for boundary testing

Definition at line 474 of file employee_example.c.

Function Documentation

static void display_employee ( employee_obj_st * obj ) [static]

Display the given employee object.

Parameters:

obj	The object to display.

Definition at line 549 of file employee_example.c.

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

Compare employees by ID.

Parameters:

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

Returns:: Comparison result

Definition at line 412 of file employee_example.c.

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

Compare employees by last name and ID.

Parameters:

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

Returns:: Comparison result

Definition at line 439 of file employee_example.c.

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

Callback to free the given employee object.

Parameters:

item	The pointer to the object.
context	Context for the tree.

Returns:: The return code

Definition at line 567 of file employee_example.c.

static bool generate_employee	(	employee_example_input_st *	input,
		employee_obj_st **	obj
	)		`[static]`

Allocate and fill in the data for an employee object. The ID of the employee is a unique value for the employee. The first name is chosen from a uniform distribution of 100 names. The last name is chosen according to the given distribution of 100 names.

Parameters:

input	The input parameters.
obj	A pointer to fill in with the newly allocated object.

Returns:: true if the creation was successful.

Definition at line 504 of file employee_example.c.

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

Callback for walking the tree to find all records for a given last name.

Parameters:

item	The current employee object.
tree_context	The context for the tree.
walk_context	The context for the walk.
stop_walk	Setting to true will stop the walk immediately upon return.

Returns:: The return code.

Definition at line 641 of file employee_example.c.

static void lookup_employees_by_last_name	(	employee_example_input_st *	input,
		const char *	last_name,
		uint32_t	max_records,
		bool	find_all,
		bool	do_print
	)		`[static]`

Look up a (sub)set of employees by their last name.

Parameters:

input	The input parameters for the run.
last_name	The last name for which to search.
max_records	The maximum number of records to find (if find_all is false).
find_all	If true, then find all employee records for the given last name (max_records is ignored in this case).
do_print	Whether to print the info for each record.

Definition at line 590 of file employee_example.c.

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

Main function to test objects.

Definition at line 875 of file employee_example.c.

static void parse_command_line	(	int	argc,
		char **	argv,
		employee_example_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 321 of file employee_example.c.

static void print_opts ( employee_example_opts_st * opts ) [static]

Utility function to output the value of the options.

Parameters:

opts	The options to output.

Definition at line 300 of file employee_example.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 264 of file employee_example.c.

static void run_employee_example ( employee_example_input_st * input ) [static]

Run a single instance of an example.

Parameters:

input The input parameters for the run.

Definition at line 669 of file employee_example.c.

static uint32_t zipf	(	double	alpha,
		uint32_t	n
	)		`[static]`

Get a random variable from a Zipf distribution within the range [1,n]. Implementation is from: http://www.cse.usf.edu/~christen/tools/genzipf.c

Parameters:

alpha	The alpha paremeter for the distribution.
n	The maximum value (inclusive) for the random variable.

Returns:: A value between 1 and n (inclusive).

Definition at line 215 of file employee_example.c.

Variable Documentation

mkavl_compare_fn cmp_fn_array[] [static]

Initial value:

 { 
    employee_cmp_by_id, 
    employee_cmp_by_last_name 
}

The comparison functions to use

Definition at line 484 of file employee_example.c.

const uint32_t default_employee_cnt = 1000 [static]

The default employee count for runs

Definition at line 96 of file employee_example.c.

const employee_dist_e default_last_name_dist = EMPLOYEE_DIST_E_UNIFORM [static]

The default last name distribution function

Definition at line 102 of file employee_example.c.

const uint32_t default_run_cnt = 1 [static]

The default number of test runs

Definition at line 98 of file employee_example.c.

const uint8_t default_verbosity = 0 [static]

The default verbosity level of messages displayed

Definition at line 100 of file employee_example.c.

const double default_zipf_alpha = 1.0 [static]

The default alpha parameter for the Zipf distribution

Definition at line 104 of file employee_example.c.

const char* first_names[] [static]

Initial value:

 {
    "Jacob", "Isabella", "Ethan", "Sophia", "Michael", "Emma", "Jayden",
    "Olivia", "William", "Ava", "Alexander", "Emily", "Noah", "Abigail",
    "Daniel", "Madison", "Aiden", "Chloe", "Anthony", "Mia", "Joshua",
    "Addison", "Mason", "Elizabeth", "Christopher", "Ella", "Andrew", "Natalie",
    "David", "Samantha", "Matthew", "Alexis", "Logan", "Lily", "Elijah",
    "Grace", "James", "Hailey", "Joseph", "Alyssa", "Gabriel", "Lillian",
    "Benjamin", "Hannah", "Ryan", "Avery", "Samuel", "Leah", "Jackson",
    "Nevaeh", "John", "Sofia", "Nathan", "Ashley", "Jonathan", "Anna",
    "Christian", "Brianna", "Liam", "Sarah", "Dylan", "Zoe", "Landon",
    "Victoria", "Caleb", "Gabriella", "Tyler", "Brooklyn", "Lucas", "Kaylee",
    "Evan", "Taylor", "Gavin", "Layla", "Nicholas", "Allison", "Isaac",
    "Evelyn", "Brayden", "Riley", "Luke", "Amelia", "Angel", "Khloe", "Brandon",
    "Makayla", "Jack", "Aubrey", "Isaiah", "Charlotte", "Jordan", "Savannah",
    "Owen", "Zoey", "Carter", "Bella", "Connor", "Kayla", "Justin", "Alexa"
}

List of first names to choose from employees

Definition at line 130 of file employee_example.c.

const char* last_names[] [static]

Initial value:

 {
    "Smith", "Johnson", "Williams", "Jones", "Brown", "Davis", "Miller",
    "Wilson", "Moore", "Taylor", "Anderson", "Thomas", "Jackson", "White",
    "Harris", "Martin", "Thompson", "Garcia", "Martinez", "Robinson", "Clark",
    "Rodriguez", "Lewis", "Lee", "Walker", "Hall", "Allen", "Young",
    "Hernandez", "King", "Wright", "Lopez", "Hill", "Scott", "Green", "Adams",
    "Baker", "Gonzalez", "Nelson", "Carter", "Mitchell", "Perez", "Roberts",
    "Turner", "Phillips", "Campbell", "Parker", "Evans", "Edwards", "Collins",
    "Stewart", "Sanchez", "Morris", "Rogers", "Reed", "Cook", "Morgan", "Bell",
    "Murphy", "Bailey", "Rivera", "Cooper", "Richardson", "Cox", "Howard",
    "Ward", "Torres", "Peterson", "Gray", "Ramirez", "James", "Watson",
    "Brooks", "Kelly", "Sanders", "Price", "Bennett", "Wood", "Barnes", "Ross",
    "Henderson", "Coleman", "Jenkins", "Perry", "Powell", "Long", "Patterson",
    "Hughes", "Flores", "Washington", "Butler", "Simmons", "Foster", "Gonzales",
    "Bryant", "Alexander", "Russell", "Griffin", "Diaz", "Hayes"
}

List of last names to choose from employees

Definition at line 148 of file employee_example.c.

Classes

Defines

Typedefs

Enumerations

Functions

Variables

Detailed Description

LICENSE

DESCRIPTION

Define Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation