epk_vector.h File Reference

Dynamic array data structure. More...


Typedefs

typedef struct EpkVector_struct EpkVector
typedef int(* epk_vec_cmp_f )(const void *value, const void *item)
typedef void(* epk_vec_proc_f )(void *item)

Functions

Dynamic array functions
EpkVectorepk_vector_create ()
EpkVectorepk_vector_create_size (size_t capacity)
void epk_vector_free (EpkVector *instance)
size_t epk_vector_size (const EpkVector *instance)
int epk_vector_empty (const EpkVector *instance)
size_t epk_vector_capacity (const EpkVector *instance)
void epk_vector_reserve (EpkVector *instance, size_t capacity)
void epk_vector_resize (EpkVector *instance, size_t size)
void * epk_vector_at (const EpkVector *instance, size_t index)
void epk_vector_set (EpkVector *instance, size_t index, void *item)
void * epk_vector_front (const EpkVector *instance)
void * epk_vector_back (const EpkVector *instance)
void ** epk_vector_begin (const EpkVector *instance)
void ** epk_vector_end (const EpkVector *instance)
void epk_vector_push_back (EpkVector *instance, void *item)
void epk_vector_pop_back (EpkVector *instance)
void epk_vector_insert (EpkVector *instance, size_t index, void *item)
void epk_vector_erase (EpkVector *instance, size_t index)
void epk_vector_clear (EpkVector *instance)
int epk_vector_find (const EpkVector *instance, const void *value, epk_vec_cmp_f cmpfunc, size_t *index)
int epk_vector_lower_bound (const EpkVector *instance, const void *value, epk_vec_cmp_f cmpfunc, size_t *index)
int epk_vector_upper_bound (const EpkVector *instance, const void *value, epk_vec_cmp_f cmpfunc, size_t *index)
void epk_vector_foreach (const EpkVector *instance, epk_vec_proc_f procfunc)


Detailed Description

This file provides type definitions and function prototypes for a generic dynamic array data structure. Although its programming interface tries to resemble the interface of the C++ STL class template vector, this implementation can only store void pointers as its elements due to the lacking template support in C.

Nevertheless, the epk_vector module follows an object-oriented style. That is, each function (except the two create functions) takes a pointer to an instance of type EpkVector as their first argument, which is the object (i.e., the data structure) they operate on.

Note:
This module uses the assert() macro to check various conditions (especially the values of given parameters) at runtime, which can cause a performance penalty.

Typedef Documentation

typedef int(* epk_vec_cmp_f)(const void *value, const void *item)

Pointer-to-function type describing comparison functions that can be used with epk_vector_find() or epk_vector_lower_bound(). It has to return 0 if value equals item, a negative value if value is less than item, or a positive value if value is greater than item.

Parameters:
value Searched value
item Current array element
Returns:
Zero if value is equal to item, a negative value if value < item, and a positive value if value > item.

typedef void(* epk_vec_proc_f)(void *item)

Pointer-to-function type describing unary processing functions that can be used with epk_vector_foreach(). Here, the current array element will be passed as parameter item.

Parameters:
item Current array element

typedef struct EpkVector_struct EpkVector

Opaque data structure representing an dynamic array.


Function Documentation

void* epk_vector_at ( const EpkVector instance,
size_t  index 
)

Returns the element stored at entry index in the given EpkVector instance.

Parameters:
instance Queried object
index Index of the element
Returns:
Requested element

void* epk_vector_back ( const EpkVector instance  ) 

Returns the last element stored in the given EpkVector instance.

Parameters:
instance Queried object
Returns:
Last element

void** epk_vector_begin ( const EpkVector instance  ) 

Returns an "iterator" for (i.e., an pointer to) the first element stored in the given EpkVector instance.

Parameters:
instance Queried object
Returns:
Iterator for first element

size_t epk_vector_capacity ( const EpkVector instance  ) 

Returns the current capacity of the given EpkVector instance.

Parameters:
instance Queried object
Returns:
Current capacity

void epk_vector_clear ( EpkVector instance  ) 

Removes all elements stored in the given EpkVector instance. However, it does not release the memory occupied by the items themselves.

Parameters:
instance Object to remove items from

EpkVector* epk_vector_create (  ) 

Creates and returns an empty instance of EpkVector with an initial capacity of zero elements. If the memory allocation request can not be fulfilled, an error message is printed and the program is aborted.

Returns:
Pointer to new instance

EpkVector* epk_vector_create_size ( size_t  capacity  ) 

Creates and returns an instance of EpkVector with the given initial capacity. If the memory allocation request can not be fulfilled, an error message is printed and the program is aborted.

Parameters:
capacity Initial capacity
Returns:
Pointer to new instance

int epk_vector_empty ( const EpkVector instance  ) 

Returns whether the given EpkVector instance is empty.

Parameters:
instance Queried object
Returns:
Non-zero value if instance if empty; zero otherwise

void** epk_vector_end ( const EpkVector instance  ) 

Returns an "iterator" for (i.e., an pointer to) the position after the last element stored in the given EpkVector instance.

Parameters:
instance Queried object
Returns:
Iterator for the position after the last element

void epk_vector_erase ( EpkVector instance,
size_t  index 
)

Removes the element stored at entry index in the given EpkVector instance. However, it does not release the memory occupied by the item itself.

Parameters:
instance Object from which the item should be removed
index Index of item to remove

int epk_vector_find ( const EpkVector instance,
const void *  value,
epk_vec_cmp_f  cmpfunc,
size_t *  index 
)

Searches for the first occurence of value in the given EpkVector instance, using the binary comparison function cmpfunc (see epk_vec_cmp_f for implementation details). If a matching item could be found, a non-zero value is returned. In addition, if index is non-NULL, the index of the corresponding entry is stored in the memory location pointed to by index. Otherwise, i.e., if no matching item could be found, this function returns zero.

Parameters:
instance Object in which the item is searched
value Item to search for
cmpfunc Binary comparison function
index Memory location where index of matching item is stored (ignored if NULL)
Returns:
Non-zero if matching item cound be found; zero otherwise

void epk_vector_foreach ( const EpkVector instance,
epk_vec_proc_f  procfunc 
)

Calls the unary processing function procfunc for each element of the given EpkVector instance.

Parameters:
instance Object whose entries should be processed
procfunc Unary processing function

void epk_vector_free ( EpkVector instance  ) 

Destroys the given instance of EpkVector and releases the allocated memory.

Note:
Similar to the destructor of C++ STL vector's, this call does not free the memory occupied by the elements since only pointers are stored. This has to be done separately.
Parameters:
instance Object to be freed

void* epk_vector_front ( const EpkVector instance  ) 

Returns the first element stored in the given EpkVector instance.

Parameters:
instance Queried object
Returns:
First element

void epk_vector_insert ( EpkVector instance,
size_t  index,
void *  item 
)

Inserts the given item (which can also be a NULL pointer) at the given position index in the EpkVector instance. If the current capacity does not suffice, the data structure is automatically resized. If this memory reallocation request can not be fulfilled, an error message is printed and the program is aborted.

Parameters:
instance Object to which the item should be inserted
index Index where item should be inserted
item Item to insert

int epk_vector_lower_bound ( const EpkVector instance,
const void *  value,
epk_vec_cmp_f  cmpfunc,
size_t *  index 
)

Determines the index of the first element that has a value greater than or equal to the given value in the EpkVector instance, using the binary comparison function cmpfunc (see epk_vec_cmp_f for implementation details). If a matching item could be found, a non-zero value is returned. In addition, if index is non-NULL, the index of the corresponding entry is stored in the memory location pointed to by index. Otherwise, i.e., if no matching item could be found, this function returns zero.

Note:
For this algorithm to work correctly, the elements in the given EpkVector instance have to be sorted in ascending order with respect to the binary comparison function cmpfunc.
Parameters:
instance Object in which the item is searched
value Item to search for
cmpfunc Binary comparison function
index Memory location where index of matching item is stored (ignored if NULL)
Returns:
Non-zero if matching item cound be found; zero otherwise

void epk_vector_pop_back ( EpkVector instance  ) 

Removes the last element stored in the given EpkVector instance. However, it does not release the memory occupied by the item itself.

Parameters:
instance Object from which the item should be removed

void epk_vector_push_back ( EpkVector instance,
void *  item 
)

Appends the given item (which can also be a NULL pointer) at the end of the EpkVector instance. If the current capacity does not suffice, the data structure is automatically resized. If this memory reallocation request can not be fulfilled, an error message is printed and the program is aborted.

Parameters:
instance Object to which the item should be appended
item Item to append

void epk_vector_reserve ( EpkVector instance,
size_t  capacity 
)

Resizes the EpkVector instance to provide the given capacity. If the memory reallocation request can not be fulfilled, an error message is printed and the program is aborted.

Note:
It is only possible to increase the capacity of an dynamic array. If the current capacity is equal to or larger than the requested capacity, the function call has no effect.
Parameters:
instance Object to be resized
capacity New capacity

void epk_vector_resize ( EpkVector instance,
size_t  size 
)

Resizes the EpkVector instance to provide the given size. Newly created entries will be initialized with NULL. If the memory reallocation request can not be fulfilled, an error message is printed and the program is aborted.

Note:
It is only possible to increase the size of an dynamic array. If the current size is equal to or larger than the requested size, the function call has no effect.
Parameters:
instance Object to be resized
size New size

void epk_vector_set ( EpkVector instance,
size_t  index,
void *  item 
)

Stores the given item at position index in the EpkVector instance.

Parameters:
instance Object to be modified
index Index where the item should be stored
item Item to be stored

size_t epk_vector_size ( const EpkVector instance  ) 

Returns the actual number of elements stored in the given EpkVector instance.

Parameters:
instance Queried object
Returns:
Number of elements stored

int epk_vector_upper_bound ( const EpkVector instance,
const void *  value,
epk_vec_cmp_f  cmpfunc,
size_t *  index 
)

Determines the index of the first element that has a value greater than the given value in the EpkVector instance, using the binary comparison function cmpfunc (see epk_vec_cmp_f for implementation details). If a matching item could be found, a non-zero value is returned. In addition, if index is non-NULL, the index of the corresponding entry is stored in the memory location pointed to by index. Otherwise, i.e., if no matching item could be found, this function returns zero.

Note:
For this algorithm to work correctly, the elements in the given EpkVector instance have to be sorted in ascending order with respect to the binary comparison function cmpfunc.
Parameters:
instance Object in which the item is searched
value Item to search for
cmpfunc Binary comparison function
index Memory location where index of matching item is stored (ignored if NULL)
Returns:
Non-zero if matching item cound be found; zero otherwise


SCALASCA    Copyright © 1998–2009 Forschungszentrum Jülich, Jülich Supercomputing Centre