src/vector.h File Reference

A dynamic array that automatically expands its capacity when necessary and can store either pointers to client data or copies of client data. More...

#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include "cdsa_types.h"

Include dependency graph for vector.h:

Go to the source code of this file.

Defines

#define DEFAULT_VECTOR_CAPACITY

The defalt vector capacity that is used if 0 is specified as the capacity value to vector_new.

Typedefs

typedef struct Vector Vector

The type of a vector.

Functions

cdsa_status_t vector_new (Vector **new_vector, size_t elem_size, size_t capacity, cdsa_destroy_func1_t destroy)

Create a new vector with the given initial capacity.

cdsa_status_t vector_destroy (Vector **v)

Destroy the vector pointed to be v, free its associated memory, setting *v to NULL.

cdsa_status_t vector_capacity (Vector *v, size_t *capacity)

Answer the capacity of the vector, setting *size to the capacity if v is non-NULL.

cdsa_status_t vector_get (Vector *v, unsigned int n, void *ptr)

Answer the nth element in the vector, setting *ptr to the element.

cdsa_status_t vector_put (Vector *v, unsigned int n, void *elem, void *prev)

Put an element in the vector at the nth position, starting from 0, setting *prev to the previous element (set to NULL if none).

cdsa_status_t vector_sort (Vector *v, unsigned int i_low, unsigned int num_elems, cdsa_compare_func_t compare)

Sort num_elems elements of the vector starting with index i_low using the given comparison function.

Detailed Description

A dynamic array that automatically expands its capacity when necessary and can store either pointers to client data or copies of client data.

A vector can be used like a normal array, using vector_get for retrieving elements by index and putting elements into the array by index. Whenever a vector_put request occurs for an index that is too large for the current backing array, the array is automatically resized by expanding it so that its capacity is equal to the next power of two greater than the requested index (i.e., vector_put(v, 100, ptr) on a vector with initial (and current) capacity of 10 would result in the underlying array expanding to be 2^7 = 128 in size). A vector_get request that is greater than the current capacity returns NULL and does not trigger a resize. The first element in the vector has index 0.

If the vector is operated in copy mode, then the pointers that are returned using vector_get are pointers into the backing array, and they are thus only valid until a new value is inserted to replace the old value or the vector is destroyed.

Definition in file vector.h.

Typedef Documentation

Vector

The type of a vector.

Vector is an implementation of a dynamic array, or an array that automatically resizes when more space is needed.

Functions are declared below for creating, destroying and manipulating a vector.

Definition at line 49 of file vector.h.

Function Documentation

cdsa_status_t vector_new	(	Vector **	new_vector,
		size_t	elem_size,
		size_t	capacity,
		cdsa_destroy_func1_t	destroy
	)

Create a new vector with the given initial capacity.

Parameters:

	new_vector	A pointer to a Vector pointer that will be initialized to a new vector upon success.
	elem_size	The size of each element if the vector is to store copies of elements placed in the array, or 0 if the vector should just store pointers.
	capacity	The initial capacity of the backing array, or 0 to use the default initial capacity.
	destroy	An optional function to be called on every element in the vector when vector_destroy is called (or NULL).

cdsa_status_t vector_destroy ( Vector ** v )

Destroy the vector pointed to be v, free its associated memory, setting *v to NULL.

If a non-NULL destroy function was passed when the vector was created, it will be called on all the elements of the vector up to the current capacity. Any elements that haven't been inserted to yet will be just zeros.

The vector is no longer usable after this function returns.

Parameters:

v

A pointer to a Vector pointer, which will be destroyed and set to NULL on success.

cdsa_status_t vector_capacity	(	Vector *	v,
		size_t *	capacity
	)

Answer the capacity of the vector, setting *size to the capacity if v is non-NULL.

The capacity is the current size of the underlying array. It is always resized to a power of two, but may be a non-power of two if it hasn't been resized yet and the user-requested initial_capacity was not a power of two.

Parameters:

	v	A non-NULL vector.
	capacity	A pointer to a size_t variable, which will be set to the capacity of the underlying backing array if v is non-NULL.

cdsa_status_t vector_get	(	Vector *	v,
		unsigned int	n,
		void *	ptr
	)

Answer the nth element in the vector, setting *ptr to the element.

Parameters:

	v	A non-NULL vector.
	n	The index of the element to get, which should be at least 0 and less than the current capacity.
	ptr	A pointer to a pointer that will be set to the given element. The ptr variable is actually a pointer to the client pointer that should be set to the element.

cdsa_status_t vector_put	(	Vector *	v,
		unsigned int	n,
		void *	elem,
		void *	prev
	)

Put an element in the vector at the nth position, starting from 0, setting *prev to the previous element (set to NULL if none).

If n is not within the bound 0 <= n < capacity, then the vector is resized to the smallest power of two equal to or greater than n.

Parameters:

	v	A non-NULL vector.
	n	An index into the vector.
	elem	Pointer of element to be stored (may be NULL if operating in pointer mode).
	prev	A pointer to the client pointer to be set to the previous contents of the given element or NULL (if in pointer mode) or to a pointer for the newly inserted copy (if in copy mode).

cdsa_status_t vector_sort	(	Vector *	v,
		unsigned int	i_low,
		unsigned int	num_elems,
		cdsa_compare_func_t	compare
	)

Sort num_elems elements of the vector starting with index i_low using the given comparison function.

Parameters:

	v	A non-NULL vector.
	i_low	The first index (starting from 0) at which sorting should occur.
	num_elems	The number of elements to be sorted.
	compare	A non-NULL pointer to the function for comparing elements of the vector.


Defines
#define	DEFAULT_VECTOR_CAPACITY
	The defalt vector capacity that is used if 0 is specified as the capacity value to vector_new.
Typedefs
typedef struct Vector	Vector
	The type of a vector.
Functions
cdsa_status_t	vector_new (Vector **new_vector, size_t elem_size, size_t capacity, cdsa_destroy_func1_t destroy)
	Create a new vector with the given initial capacity.
cdsa_status_t	vector_destroy (Vector **v)
	Destroy the vector pointed to be v, free its associated memory, setting *v to NULL.
cdsa_status_t	vector_capacity (Vector v, size_t capacity)
	Answer the capacity of the vector, setting *size to the capacity if v is non-NULL.
cdsa_status_t	vector_get (Vector v, unsigned int n, void ptr)
	Answer the nth element in the vector, setting *ptr to the element.
cdsa_status_t	vector_put (Vector v, unsigned int n, void elem, void *prev)
	Put an element in the vector at the nth position, starting from 0, setting *prev to the previous element (set to NULL if none).
cdsa_status_t	vector_sort (Vector *v, unsigned int i_low, unsigned int num_elems, cdsa_compare_func_t compare)
	Sort num_elems elements of the vector starting with index i_low using the given comparison function.