#include <stdlib.h>
#include <assert.h>
#include <float.h>
#include <math.h>
#include <stdio.h>
#include <time.h>
#include <sys/resource.h>
#include <sys/time.h>
#include <pthread.h>
#include <sched.h>
#include <string.h>
#include <malloc.h>
#include <errno.h>
#include <ctype.h>
#include "types.h"

Include dependency graph for util.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
void	set_default_parameters (TREE_PARAMETERS *params)

void	check_parameters (TREE_PARAMETERS *params)

void	dist_insert_batch (FLOAT_TYPE train_patt, INT_TYPE train_idx, FLOAT_TYPE test_patterns, INT_TYPE ntest_patterns, FLOAT_TYPE d_min, INT_TYPE idx_min, INT_TYPE dim, UINT_TYPE K)

FLOAT_TYPE	kd_tree_dist (FLOAT_TYPE a, FLOAT_TYPE b, INT_TYPE dim)

FLOAT_TYPE	squared (FLOAT_TYPE a)

void	kd_tree_insert (FLOAT_TYPE pattern_dist, INT_TYPE pattern_idx, FLOAT_TYPE nearest_dist, INT_TYPE nearest_idx, UINT_TYPE K)

void	cb_init (circular_buffer *cb, INT_TYPE size)

void	cb_free (circular_buffer *cb)

INT_TYPE	cb_is_full (circular_buffer *cb)

void	cb_add_elt (circular_buffer cb, INT_TYPE item)

INT_TYPE	cb_is_empty (circular_buffer *cb)

void	cb_write (circular_buffer cb, INT_TYPE item)

void	cb_read (circular_buffer cb, INT_TYPE item)

INT_TYPE	cb_get_number_items (circular_buffer *cb)

void	cb_read_batch (circular_buffer cb, INT_TYPE items_array, INT_TYPE num_elts_to_remove)

void	cb_read_batch_fast (circular_buffer cb, INT_TYPE items_array, INT_TYPE num_elts_to_remove)

circular_buffer *	cb_double_size (circular_buffer *cb)

char *	readline (FILE *input)

void	read_patterns (const char ifile, FLOAT_TYPE patterns, FLOAT_TYPE labels, INT_TYPE num, INT_TYPE *dim)

double	get_raw_train_mem_device_bytes (TREE_RECORD tree_record, TREE_PARAMETERS params)

double	get_train_mem_with_chunks_device_bytes (TREE_RECORD tree_record, TREE_PARAMETERS params)

double	get_test_tmp_mem_device_bytes (TREE_RECORD tree_record, TREE_PARAMETERS params)

double	get_total_mem_device_bytes (TREE_RECORD tree_record, TREE_PARAMETERS params)

double	get_train_max_buffer_device_bytes (TREE_RECORD tree_record, TREE_PARAMETERS params)

double	get_test_max_buffer_device_bytes (TREE_RECORD tree_record, TREE_PARAMETERS params)

void	partition_array_via_pivot (void *array, INT_TYPE count, INT_TYPE axis, INT_TYPE size_per_elt, FLOAT_TYPE pivot_value)

void	swap_elements (void p1, void p2, int size_elt)

void	copy_element (void dest, const void src, INT_TYPE size_elt)

Function Documentation

void cb_add_elt	(	circular_buffer *	cb,
		INT_TYPE *	item
	)

circular_buffer* cb_double_size ( circular_buffer * cb )

void cb_free ( circular_buffer * cb )

INT_TYPE cb_get_number_items ( circular_buffer * cb )

void cb_init	(	circular_buffer *	cb,
		INT_TYPE	size
	)

The circular buffer implementation is partly based on code taken from Wikipedia (http://en.wikipedia.org/wiki/Circular_buffer).

INT_TYPE cb_is_empty ( circular_buffer * cb )

INT_TYPE cb_is_full ( circular_buffer * cb )

void cb_read	(	circular_buffer *	cb,
		INT_TYPE *	item
	)

void cb_read_batch	(	circular_buffer *	cb,
		INT_TYPE *	items_array,
		INT_TYPE	num_elts_to_remove
	)

void cb_read_batch_fast	(	circular_buffer *	cb,
		INT_TYPE *	items_array,
		INT_TYPE	num_elts_to_remove
	)

void cb_write	(	circular_buffer *	cb,
		INT_TYPE *	item
	)

void check_parameters ( TREE_PARAMETERS * params )

Sanity check for parameters

Parameters

*params Struct containing the tree parameters

void copy_element	(	void *	dest,
		const void *	src,
		INT_TYPE	size_elt
	)

inline

Copies an element (used by kd_tree_split_training_patterns_via_pivot)

Parameters

*dest	Pointer to the destination
*src	Pointer to the source element
size_elt	Number of bytes per element

void dist_insert_batch	(	FLOAT_TYPE *	train_patt,
		INT_TYPE	train_idx,
		FLOAT_TYPE *	test_patterns,
		INT_TYPE	ntest_patterns,
		FLOAT_TYPE *	d_min,
		INT_TYPE *	idx_min,
		INT_TYPE	dim,
		UINT_TYPE	K
	)

Computes the distances between a training pattern (train_patt) and several test pattern (test_patterns). The results are inserted in the two lists d_min and idx_min.

Parameters

*train_patt	The training pattern
train_idx	The index of the training pattern
*test_patterns	Pointer to array containing test patterns
ntest_patterns	Number of test patterns
*d_min	Array to store the distances
*idx_min	Array to store the indices
dim	Dimensionality of patterns
K	Number of nearest neighbors

double get_raw_train_mem_device_bytes	(	TREE_RECORD *	tree_record,
		TREE_PARAMETERS *	params
	)

Returns amount of overall memory taken by training data.

Parameters

*tree_record	The tree model stored in a struct
*params	A struct containing the parameters

Returns: Number of bytes

double get_test_max_buffer_device_bytes	(	TREE_RECORD *	tree_record,
		TREE_PARAMETERS *	params
	)

Returns the number of bytes needed by the largest single test buffer

Parameters

*tree_record	The tree model stored in a struct
*params	A struct containing the parameters

Returns: Number of bytes

double get_test_tmp_mem_device_bytes	(	TREE_RECORD *	tree_record,
		TREE_PARAMETERS *	params
	)

Returns amount of temporary test data on device

Parameters

*tree_record	The tree model stored in a struct
*params	A struct containing the parameters

Returns: Number of bytes

double get_total_mem_device_bytes	(	TREE_RECORD *	tree_record,
		TREE_PARAMETERS *	params
	)

Returns total amount of memory on device

Parameters

*tree_record	The tree model stored in a struct
*params	A struct containing the parameters

Returns: Number of bytes

double get_train_max_buffer_device_bytes	(	TREE_RECORD *	tree_record,
		TREE_PARAMETERS *	params
	)

Returns the number of bytes needed by the largest single training buffer

Parameters

*tree_record	The tree model stored in a struct
*params	A struct containing the parameters

Returns: Number of bytes

double get_train_mem_with_chunks_device_bytes	(	TREE_RECORD *	tree_record,
		TREE_PARAMETERS *	params
	)

Returns amount of training data per chunk in bytes.

Parameters

*tree_record	The tree model stored in a struct
*params	A struct containing the parameters

Returns: Number of bytes

FLOAT_TYPE kd_tree_dist	(	FLOAT_TYPE *	a,
		FLOAT_TYPE *	b,
		INT_TYPE	dim
	)

Computes the distance between point a and b in R^dim

Parameters

*a	Pointer to first point
*b	Pointer to second point
dim	Dimensionality of points

void kd_tree_insert	(	FLOAT_TYPE	pattern_dist,
		INT_TYPE	pattern_idx,
		FLOAT_TYPE *	nearest_dist,
		INT_TYPE *	nearest_idx,
		UINT_TYPE	K
	)

Inserts the value pattern_dist with index pattern_idx in the list nearest_dist of FLOAT_TYPEs and the list nearest_idx of indices. Both lists contain at most K elements.

Parameters

pattern_dist	Distance to the (current) pattern
pattern_idx	The index of the (current) pattern
*nearest_dist	The array of floats to be updated
*nearest_idx	The array of indices to be updated
K	The number of nearest neighbors

void partition_array_via_pivot	(	void *	array,
		INT_TYPE	count,
		INT_TYPE	axis,
		INT_TYPE	size_per_elt,
		FLOAT_TYPE	pivot_value
	)

Partitions a given array based on a pivot element and a given axis

Parameters

*array	The array that shall be processed
count	The number of elements in the array
axis	The axis that shall be used
size_per_elt	Number of bytes a single element occupies
pivot_value	The pivot element (FLOAT_TYPE)

void read_patterns	(	const char *	ifile,
		FLOAT_TYPE **	patterns,
		FLOAT_TYPE **	labels,
		INT_TYPE *	num,
		INT_TYPE *	dim
	)

char* readline ( FILE * input )

void set_default_parameters ( TREE_PARAMETERS * params )

Sets default parameters.

Parameters

*params Struct containing the tree parameters

FLOAT_TYPE squared ( FLOAT_TYPE a )

inline

Computes the square value a*a for a given a.

Parameters

a	The value to be squared

void swap_elements	(	void *	p1,
		void *	p2,
		int	size_elt
	)

inline

Swaps two elements (used by kd_tree_split_training_patterns_via_pivot)

Parameters

*p1	Pointer to first element
*p2	Pointer to second element
size_elt	Number of bytes per element

Functions

Function Documentation