tommylist.h File Reference

#include "tommytypes.h"

Go to the source code of this file.

Typedefs
typedef tommy_node *	tommy_list

Functions
tommy_inline void	tommy_list_init (tommy_list *list)
tommy_inline tommy_node *	tommy_list_head (tommy_list *list)
tommy_inline tommy_node *	tommy_list_tail (tommy_list *list)
tommy_inline void	tommy_list_insert_first (tommy_list *list, tommy_node *node)
tommy_inline void	tommy_list_insert_head_not_empty (tommy_list *list, tommy_node *node)
tommy_inline void	tommy_list_insert_tail_not_empty (tommy_node *head, tommy_node *node)
tommy_inline void	tommy_list_insert_head (tommy_list *list, tommy_node *node, void *data)
tommy_inline void	tommy_list_insert_tail (tommy_list *list, tommy_node *node, void *data)
tommy_inline tommy_node *	tommy_list_remove_head_not_empty (tommy_list *list)
tommy_inline void *	tommy_list_remove_existing (tommy_list *list, tommy_node *node)
void	tommy_list_concat (tommy_list *first, tommy_list *second)
void	tommy_list_sort (tommy_list *list, tommy_compare_func *cmp)
tommy_inline tommy_bool_t	tommy_list_empty (tommy_list *list)
tommy_inline void	tommy_list_foreach (tommy_list *list, tommy_foreach_func *func)
tommy_inline void	tommy_list_foreach_arg (tommy_list *list, tommy_foreach_arg_func *func, void *arg)

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 {
    tommy_node node;
    // other fields
    int value;
};

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);

Definition in file tommylist.h.

Typedef Documentation

tommy_list

typedef tommy_node* tommy_list

Double linked list type.

Definition at line 108 of file tommylist.h.

Function Documentation

tommy_list_concat()

void tommy_list_concat	(	tommy_list *	first,
		tommy_list *	second
	)

Concats two lists. The second list is concatenated at the first list.

Parameters

first	The first list.
second	The second list. After this call the list content is undefined, and you should not use it anymore.

tommy_list_empty()

tommy_inline tommy_bool_t tommy_list_empty

(

tommy_list *

list

)

Checks if empty.

Returns

If the list is empty.

Definition at line 296 of file tommylist.h.

tommy_list_foreach()

tommy_inline void tommy_list_foreach	(	tommy_list *	list,
		tommy_foreach_func *	func
	)

Calls the specified function for each element in the list.

You can use this function to deallocate all the elements inserted in a list.

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);

Definition at line 329 of file tommylist.h.

tommy_list_foreach_arg()

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

Definition at line 343 of file tommylist.h.

tommy_list_head()

tommy_inline tommy_node* tommy_list_head

(

tommy_list *

list

)

Gets the head of the list.

Returns

The head node. For empty lists 0 is returned.

Definition at line 123 of file tommylist.h.

tommy_list_init()

tommy_inline void tommy_list_init

(

tommy_list *

list

)

Initializes the list. The list is completely inplace, so it doesn't need to be deinitialized.

Definition at line 114 of file tommylist.h.

tommy_list_insert_first()

tommy_inline void tommy_list_insert_first	(	tommy_list *	list,
		tommy_node *	node
	)

Definition at line 147 of file tommylist.h.

tommy_list_insert_head()

tommy_inline void tommy_list_insert_head	(	tommy_list *	list,
		tommy_node *	node,
		void *	data
	)

Inserts an element at the head of a list.

Parameters

node	The node to insert.
data	The object containing the node. It's used to set the tommy_node::data field of the node.

Definition at line 200 of file tommylist.h.

tommy_list_insert_head_not_empty()

tommy_inline void tommy_list_insert_head_not_empty	(	tommy_list *	list,
		tommy_node *	node
	)

Definition at line 164 of file tommylist.h.

tommy_list_insert_tail()

tommy_inline void tommy_list_insert_tail	(	tommy_list *	list,
		tommy_node *	node,
		void *	data
	)

Inserts an element at the tail of a list.

Parameters

node	The node to insert.
data	The object containing the node. It's used to set the tommy_node::data field of the node.

Definition at line 217 of file tommylist.h.

tommy_list_insert_tail_not_empty()

tommy_inline void tommy_list_insert_tail_not_empty	(	tommy_node *	head,
		tommy_node *	node
	)

Definition at line 184 of file tommylist.h.

tommy_list_remove_existing()

tommy_inline 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

node	The node to remove. The node must be in the list.

Returns

The tommy_node::data field of the node removed.

Definition at line 255 of file tommylist.h.

tommy_list_remove_head_not_empty()

tommy_inline tommy_node* tommy_list_remove_head_not_empty

(

tommy_list *

list

)

Definition at line 234 of file tommylist.h.

tommy_list_sort()

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

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_list_tail()

tommy_inline tommy_node* tommy_list_tail

(

tommy_list *

list

)

Gets the tail of the list.

Returns

The tail node. For empty lists 0 is returned.

Definition at line 132 of file tommylist.h.