Typedefs | Functions

tommyds/tommylist.h File Reference

Double linked list for collisions into hashtables. More...

Go to the source code of this file.

Typedefs

typedef tommy_nodetommy_list
 Double linked list type.

Functions

void tommy_list_init (tommy_list *list)
 Initializes the list.
tommy_nodetommy_list_head (tommy_list *list)
 Gets the head of the list.
tommy_nodetommy_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.
void tommy_list_insert_tail (tommy_list *list, tommy_node *node, void *data)
 Inserts an element at the tail of a list.
void * tommy_list_remove_existing (tommy_list *list, tommy_node *node)
 Removes an element from the list.
void tommy_list_concat (tommy_list *first, tommy_list *second)
 Concats two lists.
void tommy_list_sort (tommy_list *list, tommy_compare_func *cmp)
 Sorts a list.
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.
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.

Detailed Description

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.

 tommy_list list;

 tommy_list_init(&list); // initializes the list

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.

 struct object {
     int value;
     // other fields
     tommy_node node;
 };

 struct object* obj = malloc(sizeof(struct object)); // creates the object

 obj->value = ...; // initializes the object

 tommy_list_insert_tail(&list, &obj->node, obj); // inserts the object

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.

 tommy_node* i = tommy_list_head(&list);
 while (i) {
     struct object* obj = i->data; // gets the object pointer

     printf("%d\n", obj->value); // process the object

     i = i->next; // go to the next element
 }

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.

 // deallocates all the objects iterating the list
 tommy_list_foreach(&list, free);

Typedef Documentation

Double linked list type.


Function Documentation

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.

Returns:
The head node. For empty lists 0 is returned.
tommy_node* tommy_list_tail ( tommy_list list)

Gets the tail of the list.

Returns:
The tail node. For empty lists 0 is returned.
void tommy_list_insert_head ( tommy_list list,
tommy_node node,
void *  data 
)

Inserts an element at the head of a list.

Parameters:
nodeThe node to insert.
dataThe 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.

Parameters:
nodeThe node to insert.
dataThe 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.

Note:
The node content is left unchanged, including the tommy_node::next and tommy_node::prev fields that still contain pointers at the list.
Parameters:
nodeThe node to remove. The node must be in the list.
Returns:
The tommy_node::data field of the node removed.
void tommy_list_concat ( tommy_list first,
tommy_list second 
)

Concats two lists.

The second list is concatenated at the first list.

Parameters:
firstThe first list.
secondThe 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.

Parameters:
cmpCompare 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.

Returns:
If the list is empty.
tommy_count_t tommy_list_count ( tommy_list list)

Gets the number of elements.

Note:
This operation is O(n).
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.

 tommy_list list;

 // initializes the list
 tommy_list_init(&list);

 ...

 // creates an object
 struct object* obj = malloc(sizeof(struct object));

 ...

 // insert it in the list
 tommy_list_insert_tail(&list, &obj->node, obj);

 ...

 // deallocates all the objects iterating the list
 tommy_list_foreach(&list, free);
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.