epk_vector.h File Reference

Dynamic array data structure. More...


Typedefs

typedef struct EpkVector_struct EpkVector
 Opaque data structure representing an dynamic array.
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().
typedef void(* epk_vec_proc_f )(void *item)
 Pointer-to-function type describing unary processing functions that can be used with epk_vector_foreach().

Functions

Dynamic array functions
EXTERN EpkVectorepk_vector_create ()
 Creates and returns an empty instance of EpkVector with an initial capacity of zero elements.
EXTERN EpkVectorepk_vector_create_size (size_t capacity)
 Creates and returns an instance of EpkVector with the given initial capacity.
EXTERN void epk_vector_free (EpkVector *instance)
 Destroys the given instance of EpkVector and releases the allocated memory.
EXTERN size_t epk_vector_size (const EpkVector *instance)
 Returns the actual number of elements stored in the given EpkVector instance.
EXTERN int epk_vector_empty (const EpkVector *instance)
 Returns whether the given EpkVector instance is empty.
EXTERN size_t epk_vector_capacity (const EpkVector *instance)
 Returns the current capacity of the given EpkVector instance.
EXTERN void epk_vector_reserve (EpkVector *instance, size_t capacity)
 Resizes the EpkVector instance to provide the given capacity.
EXTERN void epk_vector_resize (EpkVector *instance, size_t size)
 Resizes the EpkVector instance to provide the given size.
EXTERN void * epk_vector_at (const EpkVector *instance, size_t index)
 Returns the element stored at entry index in the given EpkVector instance.
EXTERN void epk_vector_set (EpkVector *instance, size_t index, void *item)
 Stores the given item at position index in the EpkVector instance.
EXTERN void * epk_vector_front (const EpkVector *instance)
 Returns the first element stored in the given EpkVector instance.
EXTERN void * epk_vector_back (const EpkVector *instance)
 Returns the last element stored in the given EpkVector instance.
EXTERN 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.
EXTERN 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.
EXTERN 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.
EXTERN void epk_vector_pop_back (EpkVector *instance)
 Removes the last element stored in the given EpkVector instance.
EXTERN 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.
EXTERN void epk_vector_erase (EpkVector *instance, size_t index)
 Removes the element stored at entry index in the given EpkVector instance.
EXTERN void epk_vector_clear (EpkVector *instance)
 Removes all elements stored in the given EpkVector instance.
EXTERN 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).
EXTERN 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).
EXTERN 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).
EXTERN 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.


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)

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)

Here, the current array element will be passed as parameter item.

Parameters:
item Current array element

typedef struct EpkVector_struct EpkVector


Function Documentation

EXTERN void* epk_vector_at ( const EpkVector instance,
size_t  index 
)

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

EXTERN void* epk_vector_back ( const EpkVector instance  ) 

Parameters:
instance Queried object
Returns:
Last element

EXTERN void** epk_vector_begin ( const EpkVector instance  ) 

Parameters:
instance Queried object
Returns:
Iterator for first element

EXTERN size_t epk_vector_capacity ( const EpkVector instance  ) 

Parameters:
instance Queried object
Returns:
Current capacity

EXTERN void epk_vector_clear ( EpkVector instance  ) 

However, it does not release the memory occupied by the items themselves.

Parameters:
instance Object to remove items from

EXTERN EpkVector* epk_vector_create (  ) 

If the memory allocation request can not be fulfilled, an error message is printed and the program is aborted.

Returns:
Pointer to new instance

EXTERN EpkVector* epk_vector_create_size ( size_t  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

EXTERN int epk_vector_empty ( const EpkVector instance  ) 

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

EXTERN void** epk_vector_end ( const EpkVector instance  ) 

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

EXTERN void epk_vector_erase ( EpkVector instance,
size_t  index 
)

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

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

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

EXTERN void epk_vector_foreach ( const EpkVector instance,
epk_vec_proc_f  procfunc 
)

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

EXTERN void epk_vector_free ( EpkVector instance  ) 

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

EXTERN void* epk_vector_front ( const EpkVector instance  ) 

Parameters:
instance Queried object
Returns:
First element

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

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

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

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

EXTERN void epk_vector_pop_back ( EpkVector instance  ) 

However, it does not release the memory occupied by the item itself.

Parameters:
instance Object from which the item should be removed

EXTERN void epk_vector_push_back ( EpkVector instance,
void *  item 
)

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

EXTERN void epk_vector_reserve ( EpkVector instance,
size_t  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

EXTERN void epk_vector_resize ( EpkVector instance,
size_t  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

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

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

EXTERN size_t epk_vector_size ( const EpkVector instance  ) 

Parameters:
instance Queried object
Returns:
Number of elements stored

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

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–2010 Forschungszentrum Jülich, Jülich Supercomputing Centre