libsc  1.6.0
Data Structures | Defines | Typedefs | Functions
src/sc_containers.h File Reference

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

#include <sc_obstack.h>
Include dependency graph for sc_containers.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

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

Defines

#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

Typedefs

typedef unsigned(* sc_hash_function_t )(const void *v, const void *u)
 Function to compute a hash value of an object.
typedef int(* sc_equal_function_t )(const void *v1, const void *v2, const void *u)
 Function to check equality of two objects.
typedef int(* sc_hash_foreach_t )(void **v, const void *u)
 Function to call on every data item of a hash table.
typedef struct sc_array sc_array_t
 The sc_array object provides a large array of equal-size elements.
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.
typedef struct sc_mempool sc_mempool_t
 The sc_mempool object provides a large pool of equal-size elements.
typedef struct sc_link sc_link_t
 The sc_link structure is one link of a linked list.
typedef struct sc_list sc_list_t
 The sc_list object provides a linked list.
typedef struct sc_hash sc_hash_t
 The sc_hash implements a hash table.
typedef struct sc_hash_array_data sc_hash_array_data_t
typedef struct sc_hash_array sc_hash_array_t
 The sc_hash_array implements an array backed up by a hash table.
typedef struct sc_recycle_array sc_recycle_array_t
 The sc_recycle_array object provides an array of slots that can be reused.

Functions

size_t sc_array_memory_used (sc_array_t *array, int is_dynamic)
 Calculate the memory used by an array.
sc_array_tsc_array_new (size_t elem_size)
 Creates a new array structure with 0 elements.
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).
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.
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.
void sc_array_destroy (sc_array_t *array)
 Destroys an array structure.
void sc_array_init (sc_array_t *array, size_t elem_size)
 Initializes an already allocated (or static) array structure.
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.
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.
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.
void sc_array_reset (sc_array_t *array)
 Sets the array count to zero and frees all elements.
void sc_array_truncate (sc_array_t *array)
 Sets the array count to zero, but does not free elements.
void sc_array_resize (sc_array_t *array, size_t new_count)
 Sets the element count to new_count.
void sc_array_copy (sc_array_t *dest, sc_array_t *src)
 Copy the contents of an array into another.
void sc_array_sort (sc_array_t *array, int(*compar)(const void *, const void *))
 Sorts the array in ascending order wrt.
int sc_array_is_sorted (sc_array_t *array, int(*compar)(const void *, const void *))
 Check whether the array is sorted wrt.
int sc_array_is_equal (sc_array_t *array, sc_array_t *other)
 Check whether two arrays have equal size, count, and content.
void sc_array_uniq (sc_array_t *array, int(*compar)(const void *, const void *))
 Removed duplicate entries from a sorted array.
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.
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.
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.
void sc_array_permute (sc_array_t *array, sc_array_t *newindices, int keepperm)
 Given permutation newindices, permute array in place.
unsigned sc_array_checksum (sc_array_t *array)
 Computes the adler32 checksum of array data (see zlib documentation).
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.
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.
size_t sc_mempool_memory_used (sc_mempool_t *mempool)
 Calculate the memory used by a memory pool.
sc_mempool_tsc_mempool_new (size_t elem_size)
 Creates a new mempool structure.
void sc_mempool_destroy (sc_mempool_t *mempool)
 Destroys a mempool structure.
void sc_mempool_truncate (sc_mempool_t *mempool)
 Invalidates all previously returned pointers, resets count to 0.
size_t sc_list_memory_used (sc_list_t *list, int is_dynamic)
 Calculate the memory used by a list.
sc_list_tsc_list_new (sc_mempool_t *allocator)
 Allocate a linked list structure.
void sc_list_destroy (sc_list_t *list)
 Destroy a linked list structure in O(N).
void sc_list_init (sc_list_t *list, sc_mempool_t *allocator)
 Initializes an already allocated list structure.
void sc_list_reset (sc_list_t *list)
 Removes all elements from a list in O(N).
void sc_list_unlink (sc_list_t *list)
 Unliks all list elements without returning them to the mempool.
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.
void * sc_list_remove (sc_list_t *list, sc_link_t *pred)
 Remove an element after a given position.
void * sc_list_pop (sc_list_t *list)
 Remove an element from the front of the list.
unsigned sc_hash_function_string (const void *s, const void *u)
 Compute a hash value from a null-terminated string.
size_t sc_hash_memory_used (sc_hash_t *hash)
 Calculate the memory used by a hash table.
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.
void sc_hash_destroy (sc_hash_t *hash)
 Destroy a hash table.
void sc_hash_truncate (sc_hash_t *hash)
 Remove all entries from a hash table in O(N).
void sc_hash_unlink (sc_hash_t *hash)
 Unlink all hash elements without returning them to the mempool.
void sc_hash_unlink_destroy (sc_hash_t *hash)
 Same effect as unlink and destroy, but in O(1).
int sc_hash_lookup (sc_hash_t *hash, void *v, void ***found)
 Check if an object is contained in the hash table.
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.
int sc_hash_remove (sc_hash_t *hash, void *v, void **found)
 Remove an object from a hash table.
void sc_hash_foreach (sc_hash_t *hash, sc_hash_foreach_t fn)
 Invoke a callback for every member of the hash table.
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.
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.
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.
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.
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.
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.
void sc_recycle_array_init (sc_recycle_array_t *rec_array, size_t elem_size)
 Initialize a recycle array.
void sc_recycle_array_reset (sc_recycle_array_t *rec_array)
 Reset a recycle array.
void * sc_recycle_array_insert (sc_recycle_array_t *rec_array, size_t *position)
 Insert an object into the recycle array.
void * sc_recycle_array_remove (sc_recycle_array_t *rec_array, size_t position)
 Remove an object from the recycle array.

Detailed Description

Defines lists, arrays, hash tables, etc.


Define Documentation

#define SC_ARRAY_BYTE_ALLOC (   a)
Value:
((size_t) \
         (SC_ARRAY_IS_OWNER (a) ? (a)->byte_alloc : -((a)->byte_alloc + 1)))

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 struct sc_array sc_array_t

The sc_array object provides a large array of equal-size elements.

The array can be resized. Elements are accessed by their 0-based index, their address may change. The size (== elem_count) of the array can be changed by array_resize. Elements can be sorted with array_sort. If the array is sorted elements can be binary searched with array_bsearch. A priority queue is implemented with pqueue_add and pqueue_pop. Use sort and search whenever possible, they are faster than the pqueue.

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.

The sc_hash_array implements an array backed up by a hash table.

This enables O(1) access for array elements.

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.
typedef struct sc_hash sc_hash_t

The sc_hash implements a hash table.

It uses an array which has linked lists as elements.

typedef struct sc_mempool sc_mempool_t

The sc_mempool object provides a large pool of equal-size elements.

The pool grows dynamically for element allocation. Elements are referenced by their address which never changes. Elements can be freed (that is, returned to the pool) and are transparently reused.

The sc_recycle_array object provides an array of slots that can be reused.

It keeps a list of free slots in the array which will be used for insertion while available. Otherwise, the array is grown.


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.
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.

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.

Given permutation newindices, permute array in place.

newind[i] is the new index for the data that is currently at index i. entries in newind will be altered by this procedure

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.
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.

The point of this algorithm is to put offsets[i] into its final position for i = 0,...,num_types, where the final position of offsets[i] is the unique index k such that type_fn (array, j, data) < i for all j < k and type_fn (array, j, data) >= i for all j >= k.

The invariants of the loop are: 1) if i < step, then offsets[i] <= low, and offsets[i] is final. 2) if i >= step, then low is less than or equal to the final value of offsets[i]. 3) for 0 <= i <= num_types, offsets[i] is greater than or equal to its final value. 4) for every index k in the array with k < low, type_fn (array, k, data) < step, 5) for 0 <= i < num_types, for every index k in the array with k >= offsets[i], type_fn (array, k, data) >= i. 6) if i < j, offsets[i] <= offsets[j].

Initializing offsets[0] = 0, offsets[i] = count for i > 0, low = 0, and step = 1, the invariants are trivially satisfied.

Because count > 0 we can add another invariant: 7) if step < num_types, low < high = offsets[step].

If type < step, then we can set low = guess + 1 and still satisfy invariant (4). Also, because guess < high, we are assured low <= high.

If type >= step, then setting offsets[i] = guess for i = step,..., type still satisfies invariant (5). Because guess >= low, we are assured low <= high, and we maintain invariant (6).

If low = (high = offsets[step]), then by invariants (2) and (3) offsets[step] is in its final position, so we can increment step and still satisfy invariant (1).

If step = num_types, then by invariant (1) we have found the final positions for offsets[i] for i < num_types, and offsets[num_types] = count in all situations, so we are done.

To reach this point it must be true that low < high, so we preserve invariant (7).

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.

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.

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.
void sc_mempool_destroy ( sc_mempool_t mempool)

Destroys a mempool structure.

All elements that are still in use are invalidated.

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.

Reset a recycle array.

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

 All Data Structures Files Functions Variables Typedefs Defines