Double linked list for collisions into hashtables. More...
Go to the source code of this file.
Typedefs | |
typedef tommy_node * | tommy_list |
Double linked list type. More... | |
Functions | |
void | tommy_list_init (tommy_list *list) |
Initializes the list. More... | |
tommy_node * | tommy_list_head (tommy_list *list) |
Gets the head of the list. More... | |
tommy_node * | tommy_list_tail (tommy_list *list) |
Gets the tail of the list. More... | |
void | tommy_list_insert_head (tommy_list *list, tommy_node *node, void *data) |
Inserts an element at the head of a list. More... | |
void | tommy_list_insert_tail (tommy_list *list, tommy_node *node, void *data) |
Inserts an element at the tail of a list. More... | |
void * | tommy_list_remove_existing (tommy_list *list, tommy_node *node) |
Removes an element from the list. More... | |
void | tommy_list_concat (tommy_list *first, tommy_list *second) |
Concats two lists. More... | |
void | tommy_list_sort (tommy_list *list, tommy_compare_func *cmp) |
Sorts a list. More... | |
tommy_bool_t | tommy_list_empty (tommy_list *list) |
Checks if empty. More... | |
tommy_count_t | tommy_list_count (tommy_list *list) |
Gets the number of elements. More... | |
void | tommy_list_foreach (tommy_list *list, tommy_foreach_func *func) |
Calls the specified function for each element in the list. More... | |
void | tommy_list_foreach_arg (tommy_list *list, tommy_foreach_arg_func *func, void *arg) |
Calls the specified function with an argument for each element in the list. More... | |
Double linked list for collisions into hashtables.
This list is a double linked list mainly targetted for handling collisions into an hashtables, but useable also as a generic list.
The main feature of this list is to require only one pointer to represent the list, compared to a classic implementation requiring a head an a tail pointers. This reduces the memory usage in hashtables.
Another feature is to support the insertion at the end of the list. This allow to store collisions in a stable order. Where for stable order we mean that equal elements keep their insertion order.
To initialize the list, you have to call tommy_list_init(), or to simply assign to it NULL, as an empty list is represented by the NULL value.
To insert elements in the list you have to call tommy_list_insert_tail() or tommy_list_insert_head() for each element. In the insertion call you have to specify the address of the node and the address of the object. The address of the object is used to initialize the tommy_node::data field of the node.
To iterate over all the elements in the list you have to call tommy_list_head() to get the head of the list and follow the tommy_node::next pointer until NULL.
To destroy the list you have to remove all the elements, as the list is completely inplace and it doesn't allocate memory. This can be done with the tommy_list_foreach() function.
typedef tommy_node* tommy_list |
Double linked list type.
void tommy_list_init | ( | tommy_list * | list | ) |
Initializes the list.
The list is completely inplace, so it doesn't need to be deinitialized.
tommy_node* tommy_list_head | ( | tommy_list * | list | ) |
Gets the head of the list.
tommy_node* tommy_list_tail | ( | tommy_list * | list | ) |
Gets the tail of the list.
void tommy_list_insert_head | ( | tommy_list * | list, |
tommy_node * | node, | ||
void * | data | ||
) |
Inserts an element at the head of a list.
node | The node to insert. |
data | The object containing the node. It's used to set the tommy_node::data field of the node. |
void tommy_list_insert_tail | ( | tommy_list * | list, |
tommy_node * | node, | ||
void * | data | ||
) |
Inserts an element at the tail of a list.
node | The node to insert. |
data | The object containing the node. It's used to set the tommy_node::data field of the node. |
void* tommy_list_remove_existing | ( | tommy_list * | list, |
tommy_node * | node | ||
) |
Removes an element from the list.
You must already have the address of the element to remove.
node | The node to remove. The node must be in the list. |
void tommy_list_concat | ( | tommy_list * | first, |
tommy_list * | second | ||
) |
Concats two lists.
The second list is concatenated at the first list.
first | The first list. |
second | The second list. After this call the list content is undefined, and you should not use it anymore. |
void tommy_list_sort | ( | tommy_list * | list, |
tommy_compare_func * | cmp | ||
) |
Sorts a list.
It's a stable merge sort with O(N*log(N)) worst complexity. It's faster on degenerated cases like partially ordered lists.
cmp | Compare function called with two elements. The function should return <0 if the first element is less than the second, ==0 if equal, and >0 if greather. |
tommy_bool_t tommy_list_empty | ( | tommy_list * | list | ) |
Checks if empty.
tommy_count_t tommy_list_count | ( | tommy_list * | list | ) |
Gets the number of elements.
void tommy_list_foreach | ( | tommy_list * | list, |
tommy_foreach_func * | func | ||
) |
Calls the specified function for each element in the list.
You cannot add or remove elements from the inside of the callback, but can use it to deallocate them.
void tommy_list_foreach_arg | ( | tommy_list * | list, |
tommy_foreach_arg_func * | func, | ||
void * | arg | ||
) |
Calls the specified function with an argument for each element in the list.