vector implementation More...

#include "cgul_common.h"
#include "cgul_exception.h"
#include "cgul_int.h"

Include dependency graph for cgul_vector.h:

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

Typedefs
typedef typedefCGUL_BEGIN_C struct cgul_vector *	cgul_vector_t

typedef int(*	cgul_vector__compare_t) (const void value1, const void value2)

typedef cgul_uint32_t(*	cgul_vector__next_in_range_t) (cgul_exception_t cex, void prng, cgul_uint32_t range_max)

typedef int(*	cgul_vector__fold_t) (cgul_exception_t cex, void value, void *data)

Functions
CGUL_EXPORT cgul_vector_t	cgul_vector__new (cgul_exception_t *cex)

CGUL_EXPORT void	cgul_vector__delete (cgul_vector_t v)

CGUL_EXPORT void	cgul_vector__free_values (cgul_vector_t v)

CGUL_EXPORT int	cgul_vector__is_empty (cgul_exception_t *cex, cgul_vector_t v)

CGUL_EXPORT void	cgul_vector__assign (cgul_exception_t cex, cgul_vector_t v, size_t index, const void ptr)

CGUL_EXPORT void	cgul_vector__insert (cgul_exception_t cex, cgul_vector_t v, size_t index, const void ptr)

CGUL_EXPORT void	cgul_vector__erase (cgul_exception_t *cex, cgul_vector_t v, size_t index)

CGUL_EXPORT void	cgul_vector__erase_unordered (cgul_exception_t *cex, cgul_vector_t v, size_t index)

CGUL_EXPORT void *	cgul_vector__at (cgul_exception_t *cex, cgul_vector_t v, size_t index)

CGUL_EXPORT void	cgul_vector__push_back (cgul_exception_t cex, cgul_vector_t v, const void ptr)

CGUL_EXPORT void *	cgul_vector__get_back (cgul_exception_t *cex, cgul_vector_t v)

CGUL_EXPORT void *	cgul_vector__pop_back (cgul_exception_t *cex, cgul_vector_t v)

CGUL_EXPORT void	cgul_vector__sort (cgul_exception_t *cex, cgul_vector_t v, cgul_vector__compare_t f)

CGUL_EXPORT void	cgul_vector__shuffle (cgul_exception_t cex, cgul_vector_t v, cgul_vector__next_in_range_t f, void prng)

CGUL_EXPORT void	cgul_vector__clear (cgul_exception_t *cex, cgul_vector_t v)

CGUL_EXPORT void **	cgul_vector__get_array (cgul_exception_t *cex, cgul_vector_t v)

CGUL_EXPORT void **	cgul_vector__take_array (cgul_exception_t *cex, cgul_vector_t v)

CGUL_EXPORT size_t	cgul_vector__get_size (cgul_exception_t *cex, cgul_vector_t v)

CGUL_EXPORT void	cgul_vector__trim (cgul_exception_t *cex, cgul_vector_t v)

CGUL_EXPORT size_t	cgul_vector__get_minimum_capacity (cgul_exception_t *cex, cgul_vector_t v)

CGUL_EXPORT void	cgul_vector__set_minimum_capacity (cgul_exception_t *cex, cgul_vector_t v, size_t minimum_capacity)

CGUL_EXPORT void	cgul_vector__swap (cgul_exception_t *cex, cgul_vector_t v1, cgul_vector_t v2)

CGUL_EXPORT void	cgul_vector__foldl (cgul_exception_t cex, cgul_vector_t v, cgul_vector__fold_t f, void data)

CGUL_EXPORT void	cgul_vector__foldr (cgul_exception_t cex, cgul_vector_t v, cgul_vector__fold_t f, void data)

Detailed Description

Vector implementation.

Author: Paul Serice

Typedef Documentation

§ cgul_vector_t

typedef typedefCGUL_BEGIN_C struct cgul_vector* cgul_vector_t

Opaque pointer to a cgul_vector instance.

§ cgul_vector__compare_t

typedef int(* cgul_vector__compare_t) (const void *value1, const void *value2)

This typedef is the interface for the comparison function used by cgul_vector__sort(). When you define your comparison function, you should compare value1 to value2 and return less than zero, zero, or greater than zero if value1 is less than, equal to, or greater than value2.

Parameters

[in]	value1	first value
[in]	value2	second value

Returns: result of comparison

§ cgul_vector__next_in_range_t

typedef cgul_uint32_t(* cgul_vector__next_in_range_t) (cgul_exception_t *cex, void *prng, cgul_uint32_t range_max)

This type definition defines the interface to a pseudo-random number generator (PRNG) which cgul_vector__shuffle() uses to generate pseudo-random numbers that are used to shuffle the elements of the vector. The quality of the shuffle depends entirely upon the quality of the pseudo-random numbers returned.

Functions that implement this interface will be passed the same PRNG prng that is passed into the shuffle function. The return value should be a pseudo-random integer in the half-open interval [0, range_max). If an error occurs when this function is called, the client should propagate the error via cex.

Note that this interface closely resembles the signature of the cgul_random_*__next_in_range() functions. So closely in fact, that it is usually not necessary to write a special callback to implement this function. Instead, this interface can be satisfied by casting cgul_random_*__next_in_range() to have cgul_vector__next_in_range_t function type and pass in your PRNG object as prng.

Parameters

[in,out]	cex	c-style exception
[in]	prng	PRNG
[in]	range_max	maximum, non-negative range for pseudo-random numbers

Returns: pseudo-random integer in the half-open interval [0, range_max)

§ cgul_vector__fold_t

typedef int(* cgul_vector__fold_t) (cgul_exception_t *cex, void *value, void *data)

This typedef is the interface for the combining function used by the following methods:

    cgul_vector__foldl()
    cgul_vector__foldr()

Parameters

[in,out]	cex	c-style exception
[in]	value	value
[in]	data	client data

Returns: whether to continue

Function Documentation

§ cgul_vector__new()

CGUL_EXPORT cgul_vector_t cgul_vector__new ( cgul_exception_t * cex )

Create a new cgul_vector object. The caller is responsible for freeing the object by calling cgul_vector__delete(). If memory cannot be allocated, NULL is returned, and an exception is thrown.

Parameters

[in,out] cex c-style exception

Returns: new cgul_vector instance

Referenced by cgul_vector_cxx::cgul_vector_cxx().

§ cgul_vector__delete()

CGUL_EXPORT void cgul_vector__delete ( cgul_vector_t v )

This method frees all internally allocated memory. This method does not free the elements stored in the vector. The caller allocated those elements so the caller is responsible for freeing them. Do not try to access v after calling this method.

Parameters

[in] v cgul_vector instance

See also: cgul_vector__free_values()

Referenced by cgul_vector_cxx::set_obj(), and cgul_vector_cxx::~cgul_vector_cxx().

§ cgul_vector__free_values()

CGUL_EXPORT void cgul_vector__free_values ( cgul_vector_t v )

This method calls free() on all the values in the vector v. Because this is such a common operation, it is an exception to the rule that cgul containers never free values. This method should only ever be called immediately before calling cgul_vector__delete() because it otherwise invalidates the vector. Because this function is basically an extension of cgul_vector__delete(), it does not accept a cgul_exception object as an input parameter.

Parameters

[in] v cgul_vector instance

Referenced by cgul_vector_cxx::free_values().

§ cgul_vector__is_empty()

CGUL_EXPORT int cgul_vector__is_empty	(	cgul_exception_t *	cex,
		cgul_vector_t	v
	)

Return true if the vector v is empty.

Parameters

[in]	cex	c-style exception
[in]	v	`cgul_vector` instance

Returns: whether v is empty

Referenced by cgul_vector_cxx::is_empty().

§ cgul_vector__assign()

CGUL_EXPORT void cgul_vector__assign	(	cgul_exception_t *	cex,
		cgul_vector_t	v,
		size_t	index,
		const void *	ptr
	)

Assign ptr to v[index]. If index is out of bounds, an exception is thrown. Indexing is zero-based.

Parameters

[in,out]	cex	c-style exception
[in]	v	`cgul_vector` instance
[in]	index	index into `v`
[in]	ptr	pointer to assign to `v[index]`

Referenced by cgul_vector_cxx::assign().

§ cgul_vector__insert()

CGUL_EXPORT void cgul_vector__insert	(	cgul_exception_t *	cex,
		cgul_vector_t	v,
		size_t	index,
		const void *	ptr
	)

Insert ptr at v[index] shifting other pointers to the right as necessary. If index is out of bounds or if memory cannot be allocated, an exception is thrown. Indexing is zero-based.

It is legal to insert at the end of the vector such that index is one beyond the last element. Typically, you will use cgul_vector__push_back() for inserting at the end however.

Parameters

[in,out]	cex	c-style exception
[in]	v	`cgul_vector` instance
[in]	index	index into `v`
[in]	ptr	pointer to insert at `v[index]`

Referenced by cgul_vector_cxx::insert().

§ cgul_vector__erase()

CGUL_EXPORT void cgul_vector__erase	(	cgul_exception_t *	cex,
		cgul_vector_t	v,
		size_t	index
	)

Erase the element at v[index] shifting other pointers to the left as necessary. If index is out of bounds, an exception is thrown. Indexing is zero-based.

If it is not necessary to keep the elements in the underlying array in order, it is generally more efficient to call cgul_vector__erase_unordered().

Parameters

[in,out]	cex	c-style exception
[in]	v	`cgul_vector` instance
[in]	index	index into `v`

Referenced by cgul_vector_cxx::erase().

§ cgul_vector__erase_unordered()

CGUL_EXPORT void cgul_vector__erase_unordered	(	cgul_exception_t *	cex,
		cgul_vector_t	v,
		size_t	index
	)

Erase the element at v[index] replacing it with the element at the back of the underlying array. If index is out of bounds, an exception is thrown. Indexing is zero-based.

If it is necessary to keep the elements in the underlying array in order, cgul_vector__erase() should be used instead of this method.

Parameters

[in,out]	cex	c-style exception
[in]	v	`cgul_vector` instance
[in]	index	index into `v`

Referenced by cgul_vector_cxx::erase_unordered().

§ cgul_vector__at()

CGUL_EXPORT void* cgul_vector__at	(	cgul_exception_t *	cex,
		cgul_vector_t	v,
		size_t	index
	)

This method returns the element at v[index]. If index is out of bounds, NULL is returned and an exception is thrown. Indexing is zero-based.

Parameters

[in,out]	cex	c-style exception
[in]	v	`cgul_vector` instance
[in]	index	index into `v`

Returns: element at v[index]

Referenced by cgul_vector_cxx::at().

§ cgul_vector__push_back()

CGUL_EXPORT void cgul_vector__push_back	(	cgul_exception_t *	cex,
		cgul_vector_t	v,
		const void *	ptr
	)

Append ptr to the end of v. If memory cannot be allocated, an exception will be thrown.

Parameters

[in,out]	cex	c-style exception
[in]	v	`cgul_vector` instance
[in]	ptr	pointer to add to the back of `v`

Referenced by cgul_vector_cxx::push_back().

§ cgul_vector__get_back()

CGUL_EXPORT void* cgul_vector__get_back	(	cgul_exception_t *	cex,
		cgul_vector_t	v
	)

Returns the pointer held in the last element of v without removing it from v. If there are no more elements, NULL is returned. If you want to remove the last element from v, see cgul_vector__pop_back().

Parameters

[in]	cex	c-style exception
[in]	v	`cgul_vector` instance

Returns: last element of v

Referenced by cgul_vector_cxx::get_back().

§ cgul_vector__pop_back()

CGUL_EXPORT void* cgul_vector__pop_back	(	cgul_exception_t *	cex,
		cgul_vector_t	v
	)

Return and remove the pointer held in the last element of v. If there are no more elements, NULL is returned. If you want to inspect the last element without removing it, see cgul_vector__get_back().

Parameters

[in]	cex	c-style exception
[in]	v	`cgul_vector` instance

Returns: last element of v

Referenced by cgul_vector_cxx::pop_back().

§ cgul_vector__sort()

CGUL_EXPORT void cgul_vector__sort	(	cgul_exception_t *	cex,
		cgul_vector_t	v,
		cgul_vector__compare_t	f
	)

Sort the elements of the vector v using the comparison function f.

Parameters

[in]	cex	c-style exception
[in]	v	`cgul_vector` instance
[in]	f	comparison function

Referenced by cgul_vector_cxx::sort().

§ cgul_vector__shuffle()

CGUL_EXPORT void cgul_vector__shuffle	(	cgul_exception_t *	cex,
		cgul_vector_t	v,
		cgul_vector__next_in_range_t	f,
		void *	prng
	)

Shuffle the elements of the vector v using the function f to generate the pseudo-random numbers that will be used to shuffle the vector. The PRNG prng will be passed through to the PRNG callback function f without modification. If an error occurs, an exception is thrown.

For an example of how to use this method, see the following test program that accompanies the cgul source

    tests/main_vector_shuffle.c

Parameters

[in]	cex	c-style exception
[in]	v	`cgul_vector` instance
[in]	f	PRNG callback
[in]	prng	PRNG

Referenced by cgul_vector_cxx::shuffle().

§ cgul_vector__clear()

CGUL_EXPORT void cgul_vector__clear	(	cgul_exception_t *	cex,
		cgul_vector_t	v
	)

Remove all elements from the vector v.

Parameters

[in]	cex	c-style exception
[in]	v	`cgul_vector` instance

Referenced by cgul_vector_cxx::clear().

§ cgul_vector__get_array()

CGUL_EXPORT void** cgul_vector__get_array	(	cgul_exception_t *	cex,
		cgul_vector_t	v
	)

Get the internal array. The client must not free the pointer that is returned because it is still owned by v. The pointer returned is only valid until the next insert operation.

Parameters

[in]	cex	c-style exception
[in]	v	`cgul_vector` instance

Returns: array of pointers

Referenced by cgul_vector_cxx::get_array(), and cgul_vector_cxx::operator[]().

§ cgul_vector__take_array()

CGUL_EXPORT void** cgul_vector__take_array	(	cgul_exception_t *	cex,
		cgul_vector_t	v
	)

Take ownership of the internal array. The client is responsible for calling free() on the pointer returned.

Just prior to taking ownership, the internal state of v is reset. If an error occurs when attempting to reset v, v is left unaltered, NULL is returned, and an exception is thrown.

Parameters

[in,out]	cex	c-style exception
[in]	v	`cgul_vector` instance

Returns: array of pointers

Referenced by cgul_vector_cxx::take_array().

§ cgul_vector__get_size()

CGUL_EXPORT size_t cgul_vector__get_size	(	cgul_exception_t *	cex,
		cgul_vector_t	v
	)

Return the size of the vector. This is a count of the total number of elements stored in the vector.

Parameters

[in]	cex	c-style exception
[in]	v	`cgul_vector` instance

Returns: size of the vector

Referenced by cgul_vector_cxx::get_size().

§ cgul_vector__trim()

CGUL_EXPORT void cgul_vector__trim	(	cgul_exception_t *	cex,
		cgul_vector_t	v
	)

When you are through adding elements, you can trim any extra allocated space by calling this method.

Parameters

[in]	cex	c-style exception
[in]	v	`cgul_vector` instance

Referenced by cgul_vector_cxx::trim().

§ cgul_vector__get_minimum_capacity()

CGUL_EXPORT size_t cgul_vector__get_minimum_capacity	(	cgul_exception_t *	cex,
		cgul_vector_t	v
	)

Get the minimum capacity. The default value is 128.

Parameters

[in]	cex	c-style exception
[in]	v	`cgul_vector` instance

Returns: minimum capacity

Referenced by cgul_vector_cxx::get_minimum_capacity().

§ cgul_vector__set_minimum_capacity()

CGUL_EXPORT void cgul_vector__set_minimum_capacity	(	cgul_exception_t *	cex,
		cgul_vector_t	v,
		size_t	minimum_capacity
	)

Set the minimum capacity. The default value is 128. Decreasing the capacity will decrease the amount of space used and (typically) also decrease performance. If an error occurs, an exception is thrown.

Parameters

[in,out]	cex	c-style exception
[in]	v	`cgul_vector` instance
[in]	minimum_capacity	minimum capacity

Referenced by cgul_vector_cxx::set_minimum_capacity().

§ cgul_vector__swap()

CGUL_EXPORT void cgul_vector__swap	(	cgul_exception_t *	cex,
		cgul_vector_t	v1,
		cgul_vector_t	v2
	)

Swap the underlying data for v1 and v2. For large vectors, this should be much faster than trying to do the same thing using cgul_vector__push_back().

Parameters

[in]	cex	c-style exception
[in]	v1	`cgul_vector` instance
[in]	v2	`cgul_vector` instance

Referenced by cgul_vector_cxx::swap().

§ cgul_vector__foldl()

CGUL_EXPORT void cgul_vector__foldl	(	cgul_exception_t *	cex,
		cgul_vector_t	v,
		cgul_vector__fold_t	f,
		void *	data
	)

This method performs a left fold of the vector v with the combining function f. f is called once for each value in the vector starting at the front of the vector and iterating forward to the end of the vector.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current value. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	v	`cgul_vector` instance
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_vector__foldr()

CGUL_EXPORT void cgul_vector__foldr	(	cgul_exception_t *	cex,
		cgul_vector_t	v,
		cgul_vector__fold_t	f,
		void *	data
	)

This method performs a right fold of the vector v with the combining function f. f is called once for each value in the vector starting at the back of the vector and iterating backward to the front of the vector.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current value. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	v	`cgul_vector` instance
[in]	f	combining function
[in]	data	client data passed to `f`

Typedefs

Functions

Detailed Description

Typedef Documentation

§ cgul_vector_t

§ cgul_vector__compare_t

§ cgul_vector__next_in_range_t

§ cgul_vector__fold_t

Function Documentation

§ cgul_vector__new()

§ cgul_vector__delete()

§ cgul_vector__free_values()

§ cgul_vector__is_empty()

§ cgul_vector__assign()

§ cgul_vector__insert()

§ cgul_vector__erase()

§ cgul_vector__erase_unordered()

§ cgul_vector__at()

§ cgul_vector__push_back()

§ cgul_vector__get_back()

§ cgul_vector__pop_back()

§ cgul_vector__sort()

§ cgul_vector__shuffle()

§ cgul_vector__clear()

§ cgul_vector__get_array()

§ cgul_vector__take_array()

§ cgul_vector__get_size()

§ cgul_vector__trim()

§ cgul_vector__get_minimum_capacity()

§ cgul_vector__set_minimum_capacity()

§ cgul_vector__swap()

§ cgul_vector__foldl()

§ cgul_vector__foldr()