tommychain.h File Reference

#include "tommytypes.h"

Go to the source code of this file.

Classes
struct	tommy_chain_struct

Macros
#define	TOMMY_CHAIN_BIT_MAX   32

Typedefs
typedef struct tommy_chain_struct	tommy_chain

Functions
tommy_inline void	tommy_chain_splice (tommy_node *first_before, tommy_node *first_after, tommy_node *second_head, tommy_node *second_tail)
tommy_inline void	tommy_chain_concat (tommy_node *first_tail, tommy_node *second_head)
tommy_inline void	tommy_chain_merge (tommy_chain *first, tommy_chain *second, tommy_compare_func *cmp)
tommy_inline void	tommy_chain_merge_degenerated (tommy_chain *first, tommy_chain *second, tommy_compare_func *cmp)
tommy_inline void	tommy_chain_mergesort (tommy_chain *chain, tommy_compare_func *cmp)

Detailed Description

Chain of nodes. A chain of nodes is an abstraction used to implements complex list operations like sorting.

Do not use this directly. Use lists instead.

Definition in file tommychain.h.

Macro Definition Documentation

TOMMY_CHAIN_BIT_MAX

#define TOMMY_CHAIN_BIT_MAX   32

Max number of elements as a power of 2.

Definition at line 142 of file tommychain.h.

Typedef Documentation

tommy_chain

typedef struct tommy_chain_struct tommy_chain

Chain of nodes. A chain of nodes is a sequence of nodes with the following properties:

• It contains at least one node. A chains of zero nodes cannot exist.
• The next field of the tail is of undefined value.
• The prev field of the head is of undefined value.
• All the other inner prev and next fields are correctly set.

Function Documentation

tommy_chain_concat()

tommy_inline void tommy_chain_concat	(	tommy_node *	first_tail,
		tommy_node *	second_head
	)

Concats two chains.

Definition at line 74 of file tommychain.h.

tommy_chain_merge()

tommy_inline void tommy_chain_merge	(	tommy_chain *	first,
		tommy_chain *	second,
		tommy_compare_func *	cmp
	)

Merges two chains.

Definition at line 86 of file tommychain.h.

tommy_chain_merge_degenerated()

tommy_inline void tommy_chain_merge_degenerated	(	tommy_chain *	first,
		tommy_chain *	second,
		tommy_compare_func *	cmp
	)

Merges two chains managing special degenerated cases. It's funtionally equivalent at tommy_chain_merge() but faster with already ordered chains.

Definition at line 119 of file tommychain.h.

tommy_chain_mergesort()

tommy_inline void tommy_chain_mergesort	(	tommy_chain *	chain,
		tommy_compare_func *	cmp
	)

Sorts a chain. It's a stable merge sort using power of 2 buckets, with O(N*log(N)) complexity, similar at the one used in the SGI STL libraries and in the Linux Kernel, but faster on degenerated cases like already ordered lists.

SGI STL stl_list.h http://www.sgi.com/tech/stl/stl_list.h

Linux Kernel lib/list_sort.c http://lxr.linux.no/#linux+v2.6.36/lib/list_sort.c

Value stored inside the bit bucket. It's used to know which bucket is empty of full.

Definition at line 156 of file tommychain.h.

tommy_chain_splice()

tommy_inline void tommy_chain_splice	(	tommy_node *	first_before,
		tommy_node *	first_after,
		tommy_node *	second_head,
		tommy_node *	second_tail
	)

Splices a chain in the middle of another chain.

Definition at line 60 of file tommychain.h.