#include "tommytypes.h"

Include dependency graph for tommychain.h:

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.

Classes

Macros

Typedefs

Functions