p4est  1.1
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
Data Structures | Macros | Typedefs | Functions
sc_containers.h File Reference

Defines lists, arrays, hash tables, etc. More...

#include <sc_obstack.h>

Go to the source code of this file.

Data Structures

struct  sc_array_t
 The sc_array object provides a large array of equal-size elements. More...
 
struct  sc_mempool_t
 The sc_mempool object provides a large pool of equal-size elements. More...
 
struct  sc_link_t
 The sc_link structure is one link of a linked list. More...
 
struct  sc_list_t
 The sc_list object provides a linked list. More...
 
struct  sc_hash_t
 The sc_hash implements a hash table. More...
 
struct  sc_hash_array_data_t
 
struct  sc_hash_array_t
 The sc_hash_array implements an array backed up by a hash table. More...
 
struct  sc_recycle_array_t
 The sc_recycle_array object provides an array of slots that can be reused. More...
 

Macros

#define sc_hash_rot(x, k)   (((x) << (k)) | ((x) >> (32 - (k))))
 
#define sc_hash_mix(a, b, c)
 
#define sc_hash_final(a, b, c)
 
#define SC_ARRAY_IS_OWNER(a)   ((a)->byte_alloc >= 0)
 test whether the sc_array_t owns its array
 
#define SC_ARRAY_BYTE_ALLOC(a)
 the allocated size of the array More...
 

Typedefs

typedef unsigned(* sc_hash_function_t )(const void *v, const void *u)
 Function to compute a hash value of an object. More...
 
typedef int(* sc_equal_function_t )(const void *v1, const void *v2, const void *u)
 Function to check equality of two objects. More...
 
typedef int(* sc_hash_foreach_t )(void **v, const void *u)
 Function to call on every data item of a hash table. More...
 
typedef size_t(* sc_array_type_t )(sc_array_t *array, size_t index, void *data)
 Function to determine the enumerable type of an object in an array. More...
 

Functions

size_t sc_array_memory_used (sc_array_t *array, int is_dynamic)
 Calculate the memory used by an array. More...
 
sc_array_tsc_array_new (size_t elem_size)
 Creates a new array structure with 0 elements. More...
 
sc_array_tsc_array_new_size (size_t elem_size, size_t elem_count)
 Creates a new array structure with a given length (number of elements). More...
 
sc_array_tsc_array_new_view (sc_array_t *array, size_t offset, size_t length)
 Creates a new view of an existing sc_array_t. More...
 
sc_array_tsc_array_new_data (void *base, size_t elem_size, size_t elem_count)
 Creates a new view of an existing plain C array. More...
 
void sc_array_destroy (sc_array_t *array)
 Destroys an array structure. More...
 
void sc_array_init (sc_array_t *array, size_t elem_size)
 Initializes an already allocated (or static) array structure. More...
 
void sc_array_init_size (sc_array_t *array, size_t elem_size, size_t elem_count)
 Initializes an already allocated (or static) array structure and allocates a given number of elements. More...
 
void sc_array_init_view (sc_array_t *view, sc_array_t *array, size_t offset, size_t length)
 Initializes an already allocated (or static) view from existing sc_array_t. More...
 
void sc_array_init_data (sc_array_t *view, void *base, size_t elem_size, size_t elem_count)
 Initializes an already allocated (or static) view from given plain C data. More...
 
void sc_array_reset (sc_array_t *array)
 Sets the array count to zero and frees all elements. More...
 
void sc_array_truncate (sc_array_t *array)
 Sets the array count to zero, but does not free elements. More...
 
void sc_array_resize (sc_array_t *array, size_t new_count)
 Sets the element count to new_count. More...
 
void sc_array_copy (sc_array_t *dest, sc_array_t *src)
 Copy the contents of an array into another. More...
 
void sc_array_sort (sc_array_t *array, int(*compar)(const void *, const void *))
 Sorts the array in ascending order wrt. More...
 
int sc_array_is_sorted (sc_array_t *array, int(*compar)(const void *, const void *))
 Check whether the array is sorted wrt. More...
 
int sc_array_is_equal (sc_array_t *array, sc_array_t *other)
 Check whether two arrays have equal size, count, and content. More...
 
void sc_array_uniq (sc_array_t *array, int(*compar)(const void *, const void *))
 Removed duplicate entries from a sorted array. More...
 
ssize_t sc_array_bsearch (sc_array_t *array, const void *key, int(*compar)(const void *, const void *))
 Performs a binary search on an array. More...
 
void sc_array_split (sc_array_t *array, sc_array_t *offsets, size_t num_types, sc_array_type_t type_fn, void *data)
 Compute the offsets of groups of enumerable types in an array. More...
 
int sc_array_is_permutation (sc_array_t *array)
 Determine whether array is an array of size_t's whose entries include every integer 0 <= i < array->elem_count. More...
 
void sc_array_permute (sc_array_t *array, sc_array_t *newindices, int keepperm)
 Given permutation newindices, permute array in place. More...
 
unsigned sc_array_checksum (sc_array_t *array)
 Computes the adler32 checksum of array data (see zlib documentation). More...
 
size_t sc_array_pqueue_add (sc_array_t *array, void *temp, int(*compar)(const void *, const void *))
 Adds an element to a priority queue. More...
 
size_t sc_array_pqueue_pop (sc_array_t *array, void *result, int(*compar)(const void *, const void *))
 Pops the smallest element from a priority queue. More...
 
static void * sc_array_index (sc_array_t *array, size_t iz)
 Returns a pointer to an array element. More...
 
static void * sc_array_index_int (sc_array_t *array, int i)
 Returns a pointer to an array element indexed by a plain int. More...
 
static void * sc_array_index_long (sc_array_t *array, long l)
 Returns a pointer to an array element indexed by a plain long. More...
 
static void * sc_array_index_ssize_t (sc_array_t *array, ssize_t is)
 Returns a pointer to an array element indexed by a ssize_t. More...
 
static void * sc_array_index_int16 (sc_array_t *array, int16_t i16)
 Returns a pointer to an array element indexed by a int16_t. More...
 
static size_t sc_array_position (sc_array_t *array, void *element)
 Return the index of an object in an array identified by a pointer. More...
 
static void * sc_array_pop (sc_array_t *array)
 Remove the last element from an array and return a pointer to it. More...
 
static void * sc_array_push_count (sc_array_t *array, size_t add_count)
 Enlarge an array by a number of elements. More...
 
static void * sc_array_push (sc_array_t *array)
 Enlarge an array by one element. More...
 
size_t sc_mempool_memory_used (sc_mempool_t *mempool)
 Calculate the memory used by a memory pool. More...
 
sc_mempool_tsc_mempool_new (size_t elem_size)
 Creates a new mempool structure. More...
 
void sc_mempool_destroy (sc_mempool_t *mempool)
 Destroys a mempool structure. More...
 
void sc_mempool_truncate (sc_mempool_t *mempool)
 Invalidates all previously returned pointers, resets count to 0.
 
static void * sc_mempool_alloc (sc_mempool_t *mempool)
 Allocate a single element. More...
 
static void sc_mempool_free (sc_mempool_t *mempool, void *elem)
 Return a previously allocated element to the pool. More...
 
size_t sc_list_memory_used (sc_list_t *list, int is_dynamic)
 Calculate the memory used by a list. More...
 
sc_list_tsc_list_new (sc_mempool_t *allocator)
 Allocate a linked list structure. More...
 
void sc_list_destroy (sc_list_t *list)
 Destroy a linked list structure in O(N). More...
 
void sc_list_init (sc_list_t *list, sc_mempool_t *allocator)
 Initializes an already allocated list structure. More...
 
void sc_list_reset (sc_list_t *list)
 Removes all elements from a list in O(N). More...
 
void sc_list_unlink (sc_list_t *list)
 Unliks all list elements without returning them to the mempool. More...
 
void sc_list_prepend (sc_list_t *list, void *data)
 
void sc_list_append (sc_list_t *list, void *data)
 
void sc_list_insert (sc_list_t *list, sc_link_t *pred, void *data)
 Insert an element after a given position. More...
 
void * sc_list_remove (sc_list_t *list, sc_link_t *pred)
 Remove an element after a given position. More...
 
void * sc_list_pop (sc_list_t *list)
 Remove an element from the front of the list. More...
 
unsigned sc_hash_function_string (const void *s, const void *u)
 Compute a hash value from a null-terminated string. More...
 
size_t sc_hash_memory_used (sc_hash_t *hash)
 Calculate the memory used by a hash table. More...
 
sc_hash_tsc_hash_new (sc_hash_function_t hash_fn, sc_equal_function_t equal_fn, void *user_data, sc_mempool_t *allocator)
 Create a new hash table. More...
 
void sc_hash_destroy (sc_hash_t *hash)
 Destroy a hash table. More...
 
void sc_hash_truncate (sc_hash_t *hash)
 Remove all entries from a hash table in O(N). More...
 
void sc_hash_unlink (sc_hash_t *hash)
 Unlink all hash elements without returning them to the mempool. More...
 
void sc_hash_unlink_destroy (sc_hash_t *hash)
 Same effect as unlink and destroy, but in O(1). More...
 
int sc_hash_lookup (sc_hash_t *hash, void *v, void ***found)
 Check if an object is contained in the hash table. More...
 
int sc_hash_insert_unique (sc_hash_t *hash, void *v, void ***found)
 Insert an object into a hash table if it is not contained already. More...
 
int sc_hash_remove (sc_hash_t *hash, void *v, void **found)
 Remove an object from a hash table. More...
 
void sc_hash_foreach (sc_hash_t *hash, sc_hash_foreach_t fn)
 Invoke a callback for every member of the hash table. More...
 
void sc_hash_print_statistics (int package_id, int log_priority, sc_hash_t *hash)
 Compute and print statistical information about the occupancy.
 
size_t sc_hash_array_memory_used (sc_hash_array_t *ha)
 Calculate the memory used by a hash array. More...
 
sc_hash_array_tsc_hash_array_new (size_t elem_size, sc_hash_function_t hash_fn, sc_equal_function_t equal_fn, void *user_data)
 Create a new hash array. More...
 
void sc_hash_array_destroy (sc_hash_array_t *hash_array)
 Destroy a hash array.
 
int sc_hash_array_is_valid (sc_hash_array_t *hash_array)
 Check the internal consistency of a hash array.
 
void sc_hash_array_truncate (sc_hash_array_t *hash_array)
 Remove all elements from the hash array. More...
 
int sc_hash_array_lookup (sc_hash_array_t *hash_array, void *v, size_t *position)
 Check if an object is contained in a hash array. More...
 
void * sc_hash_array_insert_unique (sc_hash_array_t *hash_array, void *v, size_t *position)
 Insert an object into a hash array if it is not contained already. More...
 
void sc_hash_array_rip (sc_hash_array_t *hash_array, sc_array_t *rip)
 Extract the array data from a hash array and destroy everything else. More...
 
void sc_recycle_array_init (sc_recycle_array_t *rec_array, size_t elem_size)
 Initialize a recycle array. More...
 
void sc_recycle_array_reset (sc_recycle_array_t *rec_array)
 Reset a recycle array. More...
 
void * sc_recycle_array_insert (sc_recycle_array_t *rec_array, size_t *position)
 Insert an object into the recycle array. More...
 
void * sc_recycle_array_remove (sc_recycle_array_t *rec_array, size_t position)
 Remove an object from the recycle array. More...
 

Detailed Description

Defines lists, arrays, hash tables, etc.

Macro Definition Documentation

#define SC_ARRAY_BYTE_ALLOC (   a)
Value:
((size_t) \
(SC_ARRAY_IS_OWNER (a) ? (a)->byte_alloc : -((a)->byte_alloc + 1)))
#define SC_ARRAY_IS_OWNER(a)
test whether the sc_array_t owns its array
Definition: sc_containers.h:109

the allocated size of the array

#define sc_hash_final (   a,
  b,
 
)
Value:
((void) \
(c ^= b, c -= sc_hash_rot(b,14), \
a ^= c, a -= sc_hash_rot(c,11), \
b ^= a, b -= sc_hash_rot(a,25), \
c ^= b, c -= sc_hash_rot(b,16), \
a ^= c, a -= sc_hash_rot(c, 4), \
b ^= a, b -= sc_hash_rot(a,14), \
c ^= b, c -= sc_hash_rot(b,24)))
#define sc_hash_mix (   a,
  b,
 
)
Value:
((void) \
(a -= c, a ^= sc_hash_rot(c, 4), c += b, \
b -= a, b ^= sc_hash_rot(a, 6), a += c, \
c -= b, c ^= sc_hash_rot(b, 8), b += a, \
a -= c, a ^= sc_hash_rot(c,16), c += b, \
b -= a, b ^= sc_hash_rot(a,19), a += c, \
c -= b, c ^= sc_hash_rot(b, 4), b += a))

Typedef Documentation

typedef size_t(* sc_array_type_t)(sc_array_t *array, size_t index, void *data)

Function to determine the enumerable type of an object in an array.

Parameters
[in]arrayArray containing the object.
[in]indexThe location of the object.
[in]dataArbitrary user data.
typedef int(* sc_equal_function_t)(const void *v1, const void *v2, const void *u)

Function to check equality of two objects.

Parameters
[in]uArbitrary user data.
Returns
Returns false if *v1 is unequal *v2 and true otherwise.
typedef int(* sc_hash_foreach_t)(void **v, const void *u)

Function to call on every data item of a hash table.

Parameters
[in]vThe address of the pointer to the current object.
[in]uArbitrary user data.
Returns
Return true if the traversal should continue, false to stop.
typedef unsigned(* sc_hash_function_t)(const void *v, const void *u)

Function to compute a hash value of an object.

Parameters
[in]vThe object to hash.
[in]uArbitrary user data.
Returns
Returns an unsigned integer.

Function Documentation

ssize_t sc_array_bsearch ( sc_array_t array,
const void *  key,
int(*)(const void *, const void *)  compar 
)

Performs a binary search on an array.

The array must be sorted.

Parameters
[in]arrayA sorted array to search in.
[in]keyAn element to be searched for.
[in]comparThe comparison function to be used.
Returns
Returns the index into array for the item found, or -1.
unsigned sc_array_checksum ( sc_array_t array)

Computes the adler32 checksum of array data (see zlib documentation).

This is a faster checksum than crc32, and it works with zeros as data.

void sc_array_copy ( sc_array_t dest,
sc_array_t src 
)

Copy the contents of an array into another.

Both arrays must have equal element sizes.

Parameters
[in]destArray (not a view) will be resized and get new data.
[in]srcArray used as source of new data, will not be changed.
void sc_array_destroy ( sc_array_t array)

Destroys an array structure.

Parameters
[in]arrayThe array to be destroyed.
static void* sc_array_index ( sc_array_t array,
size_t  iz 
)
inlinestatic

Returns a pointer to an array element.

Parameters
[in]indexneeds to be in [0]..[elem_count-1].
static void* sc_array_index_int ( sc_array_t array,
int  i 
)
inlinestatic

Returns a pointer to an array element indexed by a plain int.

Parameters
[in]indexneeds to be in [0]..[elem_count-1].
static void* sc_array_index_int16 ( sc_array_t array,
int16_t  i16 
)
inlinestatic

Returns a pointer to an array element indexed by a int16_t.

Parameters
[in]indexneeds to be in [0]..[elem_count-1].
static void* sc_array_index_long ( sc_array_t array,
long  l 
)
inlinestatic

Returns a pointer to an array element indexed by a plain long.

Parameters
[in]indexneeds to be in [0]..[elem_count-1].
static void* sc_array_index_ssize_t ( sc_array_t array,
ssize_t  is 
)
inlinestatic

Returns a pointer to an array element indexed by a ssize_t.

Parameters
[in]indexneeds to be in [0]..[elem_count-1].
void sc_array_init ( sc_array_t array,
size_t  elem_size 
)

Initializes an already allocated (or static) array structure.

Parameters
[in,out]arrayArray structure to be initialized.
[in]elem_sizeSize of one array element in bytes.
void sc_array_init_data ( sc_array_t view,
void *  base,
size_t  elem_size,
size_t  elem_count 
)

Initializes an already allocated (or static) view from given plain C data.

Parameters
[in,out]viewArray structure to be initialized.
[in]baseThe data must not be moved while view is alive.
[in]elem_sizeSize of one array element in bytes.
[in]elem_countThe length of the view in element units. The view cannot be resized to exceed this length.
void sc_array_init_size ( sc_array_t array,
size_t  elem_size,
size_t  elem_count 
)

Initializes an already allocated (or static) array structure and allocates a given number of elements.

Parameters
[in,out]arrayArray structure to be initialized.
[in]elem_sizeSize of one array element in bytes.
[in]elem_countNumber of initial array elements.
void sc_array_init_view ( sc_array_t view,
sc_array_t array,
size_t  offset,
size_t  length 
)

Initializes an already allocated (or static) view from existing sc_array_t.

Parameters
[in,out]viewArray structure to be initialized.
[in]arrayThe array must not be resized while view is alive.
[in]offsetThe offset of the viewed section in element units. This offset cannot be changed until the view is reset.
[in]lengthThe length of the view in element units. The view cannot be resized to exceed this length.
int sc_array_is_equal ( sc_array_t array,
sc_array_t other 
)

Check whether two arrays have equal size, count, and content.

Either array may be a view. Both arrays will not be changed.

Parameters
[in]arrayOne array to be compared.
[in]otherA second array to be compared.
Returns
True if array and other are equal, false otherwise.
int sc_array_is_permutation ( sc_array_t array)

Determine whether array is an array of size_t's whose entries include every integer 0 <= i < array->elem_count.

Parameters
[in]arrayAn array.
Returns
Returns 1 if array contains size_t elements whose entries include every integer 0 <= i < array->elem_count, 0 otherwise.
int sc_array_is_sorted ( sc_array_t array,
int(*)(const void *, const void *)  compar 
)

Check whether the array is sorted wrt.

the comparison function.

Parameters
[in]arrayThe array to check.
[in]comparThe comparison function to be used.
Returns
True if array is sorted, false otherwise.
size_t sc_array_memory_used ( sc_array_t array,
int  is_dynamic 
)

Calculate the memory used by an array.

Parameters
[in]arrayThe array.
[in]is_dynamicTrue if created with sc_array_new, false if initialized with sc_array_init
Returns
Memory used in bytes.
sc_array_t* sc_array_new ( size_t  elem_size)

Creates a new array structure with 0 elements.

Parameters
[in]elem_sizeSize of one array element in bytes.
Returns
Return an allocated array of zero length.
sc_array_t* sc_array_new_data ( void *  base,
size_t  elem_size,
size_t  elem_count 
)

Creates a new view of an existing plain C array.

Parameters
[in]baseThe data must not be moved while view is alive.
[in]elem_sizeSize of one array element in bytes.
[in]elem_countThe length of the view in element units. The view cannot be resized to exceed this length.
sc_array_t* sc_array_new_size ( size_t  elem_size,
size_t  elem_count 
)

Creates a new array structure with a given length (number of elements).

Parameters
[in]elem_sizeSize of one array element in bytes.
[in]elem_countInitial number of array elements.
Returns
Return an allocated array with allocated but uninitialized elements.
sc_array_t* sc_array_new_view ( sc_array_t array,
size_t  offset,
size_t  length 
)

Creates a new view of an existing sc_array_t.

Parameters
[in]arrayThe array must not be resized while view is alive.
[in]offsetThe offset of the viewed section in element units. This offset cannot be changed until the view is reset.
[in]lengthThe length of the viewed section in element units. The view cannot be resized to exceed this length.
void sc_array_permute ( sc_array_t array,
sc_array_t newindices,
int  keepperm 
)

Given permutation newindices, permute array in place.

The data that on input is contained in array[i] will be contained in array[newindices[i]] on output. The entries of newindices will be altered unless keepperm is true.

Parameters
[in,out]arrayAn array.
[in,out]newindicesPermutation array (see sc_array_is_permutation).
[in]keeppermIf true, newindices will be unchanged by the algorithm; if false, newindices will be the identity permutation on output, but the algorithm will only use O(1) space.
static void* sc_array_pop ( sc_array_t array)
inlinestatic

Remove the last element from an array and return a pointer to it.

This function is not allowed for views.

Returns
The pointer to the removed object. Will be valid as long as no other function is called on this array.
static size_t sc_array_position ( sc_array_t array,
void *  element 
)
inlinestatic

Return the index of an object in an array identified by a pointer.

Parameters
[in]elementneeds to be the address of an element in array.
size_t sc_array_pqueue_add ( sc_array_t array,
void *  temp,
int(*)(const void *, const void *)  compar 
)

Adds an element to a priority queue.

PQUEUE FUNCTIONS ARE UNTESTED AND CURRENTLY DISABLED. This function is not allowed for views. The priority queue is implemented as a heap in ascending order. A heap is a binary tree where the children are not less than their parent. Assumes that elements [0]..[elem_count-2] form a valid heap. Then propagates [elem_count-1] upward by swapping if necessary.

Parameters
[in]tempPointer to unused allocated memory of elem_size.
[in]comparThe comparison function to be used.
Returns
Returns the number of swap operations.
Note
If the return value is zero for all elements in an array, the array is sorted linearly and unchanged.
size_t sc_array_pqueue_pop ( sc_array_t array,
void *  result,
int(*)(const void *, const void *)  compar 
)

Pops the smallest element from a priority queue.

PQUEUE FUNCTIONS ARE UNTESTED AND CURRENTLY DISABLED. This function is not allowed for views. This function assumes that the array forms a valid heap in ascending order.

Parameters
[out]resultPointer to unused allocated memory of elem_size.
[in]comparThe comparison function to be used.
Returns
Returns the number of swap operations.
Note
This function resizes the array to elem_count-1.
static void* sc_array_push ( sc_array_t array)
inlinestatic

Enlarge an array by one element.

Grows the array if necessary. This function is not allowed for views.

Returns
Returns a pointer to the uninitialized newly added element.
static void* sc_array_push_count ( sc_array_t array,
size_t  add_count 
)
inlinestatic

Enlarge an array by a number of elements.

Grows the array if necessary. This function is not allowed for views.

Returns
Returns a pointer to the uninitialized newly added elements.
void sc_array_reset ( sc_array_t array)

Sets the array count to zero and frees all elements.

This function turns a view into a newly initialized array.

Parameters
[in,out]arrayArray structure to be reset.
Note
Calling sc_array_init, then any array operations, then sc_array_reset is memory neutral.
void sc_array_resize ( sc_array_t array,
size_t  new_count 
)

Sets the element count to new_count.

If this a view, new_count cannot be greater than the elem_count of the view when it was created. The original offset of the view cannot be changed. If this is an array, reallocation takes place only occasionally, so this function is usually fast.

void sc_array_sort ( sc_array_t array,
int(*)(const void *, const void *)  compar 
)

Sorts the array in ascending order wrt.

the comparison function.

Parameters
[in]arrayThe array to sort.
[in]comparThe comparison function to be used.
void sc_array_split ( sc_array_t array,
sc_array_t offsets,
size_t  num_types,
sc_array_type_t  type_fn,
void *  data 
)

Compute the offsets of groups of enumerable types in an array.

Parameters
[in]arrayArray that is sorted in ascending order by type. If k indexes array, then 0 <= type_fn (array, k, data) < num_types.
[in,out]offsetsAn initialized array of type size_t that is resized to num_types + 1 entries. The indices j of array that contain objects of type k are offsets[k] <= j < offsets[k + 1]. If there are no objects of type k, then offsets[k] = offset[k + 1].
[in]num_typesThe number of possible types of objects in array.
[in]type_fnReturns the type of an object in the array.
[in]dataArbitrary user data passed to type_fn.
void sc_array_truncate ( sc_array_t array)

Sets the array count to zero, but does not free elements.

Not allowed for views.

Parameters
[in,out]arrayArray structure to be truncated.
Note
This is intended to allow an sc_array to be used as a reusable buffer, where the "high water mark" of the buffer is preserved, so that O(log (max n)) reallocs occur over the life of the buffer.
void sc_array_uniq ( sc_array_t array,
int(*)(const void *, const void *)  compar 
)

Removed duplicate entries from a sorted array.

This function is not allowed for views.

Parameters
[in,out]arrayThe array size will be reduced as necessary.
[in]comparThe comparison function to be used.
void* sc_hash_array_insert_unique ( sc_hash_array_t hash_array,
void *  v,
size_t *  position 
)

Insert an object into a hash array if it is not contained already.

The object is not copied into the array. Use the return value for that. New objects are guaranteed to be added at the end of the array.

Parameters
[in]vA pointer to the object. Used for search only.
[out]positionIf position != NULL, *position is set to the array position of the already contained, or if not present, the new object.
Returns
Returns NULL if the object is already contained. Otherwise returns its new address in the array.
int sc_hash_array_lookup ( sc_hash_array_t hash_array,
void *  v,
size_t *  position 
)

Check if an object is contained in a hash array.

Parameters
[in]vA pointer to the object.
[out]positionIf position != NULL, *position is set to the array position of the already contained object if found.
Returns
Returns true if object is found, false otherwise.
size_t sc_hash_array_memory_used ( sc_hash_array_t ha)

Calculate the memory used by a hash array.

Parameters
[in]haThe hash array.
Returns
Memory used in bytes.
sc_hash_array_t* sc_hash_array_new ( size_t  elem_size,
sc_hash_function_t  hash_fn,
sc_equal_function_t  equal_fn,
void *  user_data 
)

Create a new hash array.

Parameters
[in]elem_sizeSize of one array element in bytes.
[in]hash_fnFunction to compute the hash value.
[in]equal_fnFunction to test two objects for equality.
void sc_hash_array_rip ( sc_hash_array_t hash_array,
sc_array_t rip 
)

Extract the array data from a hash array and destroy everything else.

Parameters
[in]hash_arrayThe hash array is destroyed after extraction.
[in]ripArray structure that will be overwritten. All previous array data (if any) will be leaked. The filled array can be freed with sc_array_reset.
void sc_hash_array_truncate ( sc_hash_array_t hash_array)

Remove all elements from the hash array.

Parameters
[in,out]hash_arrayHash array to truncate.
void sc_hash_destroy ( sc_hash_t hash)

Destroy a hash table.

If the allocator is owned, this runs in O(1), otherwise in O(N).

Note
If allocator was provided in sc_hash_new, it will not be destroyed.
void sc_hash_foreach ( sc_hash_t hash,
sc_hash_foreach_t  fn 
)

Invoke a callback for every member of the hash table.

The functions hash_fn and equal_fn are not called by this function.

unsigned sc_hash_function_string ( const void *  s,
const void *  u 
)

Compute a hash value from a null-terminated string.

This hash function is NOT cryptographically safe! Use libcrypt then.

Parameters
[in]sNull-terminated string to be hashed.
[in]uNot used.
Returns
The computed hash value as an unsigned integer.
int sc_hash_insert_unique ( sc_hash_t hash,
void *  v,
void ***  found 
)

Insert an object into a hash table if it is not contained already.

Parameters
[in]vThe object to be inserted.
[out]foundIf found != NULL, *found is set to the address of the pointer to the already contained, or if not present, the new object. You can assign to **found to override.
Returns
Returns true if object is added, false if it is already contained.
int sc_hash_lookup ( sc_hash_t hash,
void *  v,
void ***  found 
)

Check if an object is contained in the hash table.

Parameters
[in]vThe object to be looked up.
[out]foundIf found != NULL, *found is set to the address of the pointer to the already contained object if the object is found. You can assign to **found to override.
Returns
Returns true if object is found, false otherwise.
size_t sc_hash_memory_used ( sc_hash_t hash)

Calculate the memory used by a hash table.

Parameters
[in]hashThe hash table.
Returns
Memory used in bytes.
sc_hash_t* sc_hash_new ( sc_hash_function_t  hash_fn,
sc_equal_function_t  equal_fn,
void *  user_data,
sc_mempool_t allocator 
)

Create a new hash table.

The number of hash slots is chosen dynamically.

Parameters
[in]hash_fnFunction to compute the hash value.
[in]equal_fnFunction to test two objects for equality.
[in]user_dataUser data passed through to the hash function.
[in]allocatorMemory allocator for sc_link_t, can be NULL.
int sc_hash_remove ( sc_hash_t hash,
void *  v,
void **  found 
)

Remove an object from a hash table.

Parameters
[in]vThe object to be removed.
[out]foundIf found != NULL, *found is set to the object that is removed if that exists.
Returns
Returns true if object is found, false if is not contained.
void sc_hash_truncate ( sc_hash_t hash)

Remove all entries from a hash table in O(N).

If the allocator is owned, it calls sc_hash_unlink and sc_mempool_truncate. Otherwise, it calls sc_list_reset on every hash slot which is slower.

void sc_hash_unlink ( sc_hash_t hash)

Unlink all hash elements without returning them to the mempool.

If the allocator is not owned, this runs faster than sc_hash_truncate, but is dangerous because of potential memory leaks.

Parameters
[in,out]hashHash structure to be unlinked.
void sc_hash_unlink_destroy ( sc_hash_t hash)

Same effect as unlink and destroy, but in O(1).

This is dangerous because of potential memory leaks.

Parameters
[in]hashHash structure to be unlinked and destroyed.
void sc_list_destroy ( sc_list_t list)

Destroy a linked list structure in O(N).

Note
If allocator was provided in sc_list_new, it will not be destroyed.
void sc_list_init ( sc_list_t list,
sc_mempool_t allocator 
)

Initializes an already allocated list structure.

Parameters
[in,out]listList structure to be initialized.
[in]allocatorExternal memory allocator for sc_link_t.
void sc_list_insert ( sc_list_t list,
sc_link_t pred,
void *  data 
)

Insert an element after a given position.

Parameters
[in]predThe predecessor of the element to be inserted.
size_t sc_list_memory_used ( sc_list_t list,
int  is_dynamic 
)

Calculate the memory used by a list.

Parameters
[in]listThe list.
[in]is_dynamicTrue if created with sc_list_new, false if initialized with sc_list_init
Returns
Memory used in bytes.
sc_list_t* sc_list_new ( sc_mempool_t allocator)

Allocate a linked list structure.

Parameters
[in]allocatorMemory allocator for sc_link_t, can be NULL.
void* sc_list_pop ( sc_list_t list)

Remove an element from the front of the list.

Returns
Returns the data of the removed first list element.
void* sc_list_remove ( sc_list_t list,
sc_link_t pred 
)

Remove an element after a given position.

Parameters
[in]predThe predecessor of the element to be removed. If pred == NULL, the first element is removed.
Returns
Returns the data of the removed element.
void sc_list_reset ( sc_list_t list)

Removes all elements from a list in O(N).

Parameters
[in,out]listList structure to be resetted.
Note
Calling sc_list_init, then any list operations, then sc_list_reset is memory neutral.
void sc_list_unlink ( sc_list_t list)

Unliks all list elements without returning them to the mempool.

This runs in O(1) but is dangerous because of potential memory leaks.

Parameters
[in,out]listList structure to be unlinked.
static void* sc_mempool_alloc ( sc_mempool_t mempool)
inlinestatic

Allocate a single element.

Elements previously returned to the pool are recycled.

Returns
Returns a new or recycled element pointer.
void sc_mempool_destroy ( sc_mempool_t mempool)

Destroys a mempool structure.

All elements that are still in use are invalidated.

static void sc_mempool_free ( sc_mempool_t mempool,
void *  elem 
)
inlinestatic

Return a previously allocated element to the pool.

Parameters
[in]elemThe element to be returned to the pool.
size_t sc_mempool_memory_used ( sc_mempool_t mempool)

Calculate the memory used by a memory pool.

Parameters
[in]arrayThe memory pool.
Returns
Memory used in bytes.
sc_mempool_t* sc_mempool_new ( size_t  elem_size)

Creates a new mempool structure.

Parameters
[in]elem_sizeSize of one element in bytes.
Returns
Returns an allocated and initialized memory pool.
void sc_recycle_array_init ( sc_recycle_array_t rec_array,
size_t  elem_size 
)

Initialize a recycle array.

Parameters
[in]elem_sizeSize of the objects to be stored in the array.
void* sc_recycle_array_insert ( sc_recycle_array_t rec_array,
size_t *  position 
)

Insert an object into the recycle array.

The object is not copied into the array. Use the return value for that.

Parameters
[out]positionIf position != NULL, *position is set to the array position of the inserted object.
Returns
Returns the new address of the object in the array.
void* sc_recycle_array_remove ( sc_recycle_array_t rec_array,
size_t  position 
)

Remove an object from the recycle array.

It must be valid.

Parameters
[in]positionIndex into the array for the object to remove.
Returns
The pointer to the removed object. Will be valid as long as no other function is called on this recycle array.
void sc_recycle_array_reset ( sc_recycle_array_t rec_array)

Reset a recycle array.

As with all _reset functions, calling _init, then any array operations, then _reset is memory neutral.