C Linked List Interface

A linked list library for C modules. More...

Collaboration diagram for C Linked List Interface:

Classes
struct	ll_head
	Linked list struct. More...

Macros
#define	container_of(ptr, type, member)   ((type*)((uintptr_t)(ptr)-offsetof(type, member)))
	Define offsetof if we don't have it already. More...

Typedefs
typedef struct ll_head	ll_t
	Linked list struct. More...

Get Containers
#define	list_entry(ptr, type, member)   container_of(ptr, type, member)
	Get the container for a list entry. More...
#define	list_first_entry(head, type, member)   list_entry((head)->next, type, member)
	Get the container for the first item in the list. More...

Foreach Operations
#define	list_for_each(pos, head)   for(pos = (head)->next; pos != (head); pos = pos->next)
	Declare a foreach loop which iterates over the list. More...
#define	list_for_each_safe(pos, n, head)   for(pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)
	Declare a foreach loop which iterates over the list, copy current node pointer. More...
#define	list_for_each_entry(pos, head, member)
	Declare a for loop which operates on each node in the list using the container value. More...
#define	list_for_each_entry_safe(pos, n, head, member)
	Declare a for loop which operates on each node in the list using a copy of the container value. More...

Initialization
#define	ll_head_INIT(name)
	Initialize a linked list so it points to itself. More...
#define	LIST_INIT(name)   struct ll_head name = ll_head_INIT(name)
	Initialize a linked list. More...

Addition
static void	list_insert (struct ll_head *n, struct ll_head *prev, struct ll_head *next)
	Insert a new element between two existing elements. More...
static void	list_add (struct ll_head *n, struct ll_head *head)
	Add a node to the front of the list. More...
static void	list_add_tail (struct ll_head *n, struct ll_head *head)
	Add a node to the end of the list. More...

Deletion
static void	list_join_nodes (struct ll_head *prev, struct ll_head *next)
	Remove the node between two element pointers. More...
static void	list_del (struct ll_head *entry)
	Remove an entry from the list. More...

Detailed Description

A linked list library for C modules.

---

Class Documentation

ll_head

struct ll_head

Linked list struct.

This is a doubly linked list structure. The ll_t structure should be embedded in a container structure that you want to list.

Example:

typedef struct
{
    ll_t node;
    size_t size;
    char* block;
} alloc_node_t;

Class Members
struct ll_head *	next	Pointer to the next element in the list.
struct ll_head *	prev	Pointer to the previous element in the list.

Macro Definition Documentation

container_of

#define container_of	(		ptr,
			type,
			member
	)		((type*)((uintptr_t)(ptr)-offsetof(type, member)))

Define offsetof if we don't have it already.

Define container_of if we don't have it already

list_entry

#define list_entry	(		ptr,
			type,
			member
	)		container_of(ptr, type, member)

Get the container for a list entry.

Parameters

[in]	ptr	The pointer to the target ll_t node.
[in]	type	The struct type which contains the ll_t node. For this example struct, type would refer to alloc_node_t: typedef struct { ll_t node; size_t size; char* block; } alloc_node_t;
[in]	member	The member which corresponds to the member name of the ll_t entry. For this example struct, member would refer to node. typedef struct { ll_t node; size_t size; char* block; } alloc_node_t;

Returns

a pointer to the struct containing the linked list node at ptr, cast to type type.

list_first_entry

#define list_first_entry	(		head,
			type,
			member
	)		list_entry((head)->next, type, member)

Get the container for the first item in the list.

Parameters

[in]	head	The pointer to the head of the list.
[in]	type	The struct type which contains the ll_t node. For this example struct, type would refer to alloc_node_t: typedef struct { ll_t node; size_t size; char* block; } alloc_node_t;
[in]	member	The member which corresponds to the member name of the ll_t entry. For this example struct, member would refer to node. typedef struct { ll_t node; size_t size; char* block; } alloc_node_t;

Returns

a pointer to the struct containing the linked list node at ptr, cast to type type.

list_for_each

#define list_for_each	(		pos,
			head
	)		for(pos = (head)->next; pos != (head); pos = pos->next)

Declare a foreach loop which iterates over the list.

list_for_each() will run as long as the current object's next pointer is not equal to the head of the list. It's possible for a malformed list to loop forever.

Parameters

[in]	pos	The variable which will hold the current iteration's position value. This variable must be a pointer and should be pre-declared before instantiating the loop. ll_t *b; list_for_each(b, &free_list) { ... }
[in]	head	The head of of the linked list. Input should be a pointer.

list_for_each_entry

#define list_for_each_entry	(		pos,
			head,
			member
	)

Value:

for(pos = list_entry((head)->next, __typeof__(*pos), member); &pos->member != (head); \
        pos = list_entry(pos->member.next, __typeof__(*pos), member))

Declare a for loop which operates on each node in the list using the container value.

Parameters

[in]	pos	The variable which will hold the current iteration's position value. This variable must be a pointer and should be pre-declared before instantiating the loop. The pos variable must be the container type. alloc_node_t *b, *t; list_for_each_entry(b, &free_list, node) { ... }
[in]	head	The head of of the linked list. Input should be a pointer.
[in]	member	The member which corresponds to the member name of the ll_t entry. For this example struct, member would refer to node. typedef struct { ll_t node; size_t size; char* block; } alloc_node_t;

list_for_each_entry_safe

#define list_for_each_entry_safe	(		pos,
			n,
			head,
			member
	)

Value:

for(pos = list_entry((head)->next, __typeof__(*pos), member), \
    n = list_entry(pos->member.next, __typeof__(*pos), member);   \
        &pos->member != (head); pos = n, n = list_entry(n->member.next, __typeof__(*n), member))

Declare a for loop which operates on each node in the list using a copy of the container value.

Parameters

[in]	pos	The variable which will hold the current iteration's position value. This variable must be a pointer and should be pre-declared before instantiating the loop. The pos variable must be the container type. alloc_node_t *b, *t; list_for_each_entry(b, &free_list, node) { ... }
[in]	n	The variable which will hold the current iteration's position value copy. This variable must be a pointer and should be pre-declared before instantiating the loop. The n variable must be the container type. typedef struct { ll_t node; size_t size; char* block; } alloc_node_t; alloc_node_t *b, *t; list_for_each_entrysafe(b, t, &free_list, node) { ... }
[in]	head	The head of of the linked list. Input should be a pointer.
[in]	member	The member which corresponds to the member name of the ll_t entry. For this example struct, member would refer to node. typedef struct { ll_t node; size_t size; char* block; } alloc_node_t;

list_for_each_safe

#define list_for_each_safe	(		pos,
			n,
			head
	)		for(pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)

Declare a foreach loop which iterates over the list, copy current node pointer.

list_for_each_safe() will run as long as the current object's next pointer is not equal to the head of the list. It's possible for a malformed list to loop forever.

The list_for_each_safe() variant makes a copy of the current node pointer, enabling the loop to get to the next pointer if there is a deletion.

Parameters

[in]	pos	The variable which will hold the current iteration's position value. This variable must be a pointer should be pre-declared before instantiating the loop. ll_t *b, *t; list_for_each_safe(b, t, &free_list) { ... }
[in]	n	The variable which will hold the current iteration's position value copy. This variable must be a pointer and should be pre-declared before instantiating the loop. alloc_node_t *b, *t; list_for_each_safe(b, t, &free_list) { ... }
[in]	head	The head of of the linked list. Input should be a pointer.

LIST_INIT

#define LIST_INIT

(

name

)

struct ll_head name = ll_head_INIT(name)

Initialize a linked list.

// This macro declares and initializes our linked list
static LIST_INIT(free_list);

Parameters

[in]

name

The name of the linked list object to declare

ll_head_INIT

#define ll_head_INIT

(

name

)

Value:

{                      \
        &(name), &(name)   \
    }

Initialize a linked list so it points to itself.

Parameters

[in]

name

of the linked list object

Typedef Documentation

ll_t

typedef struct ll_head ll_t

Linked list struct.

This is a doubly linked list structure. The ll_t structure should be embedded in a container structure that you want to list.

Example:

typedef struct
{
    ll_t node;
    size_t size;
    char* block;
} alloc_node_t;

Function Documentation

list_add()

static void list_add ( struct ll_head *  n, struct ll_head *  head  )

inlinestatic

Add a node to the front of the list.

Parameters

[in]	n	The node to add to the list.
[in]	head	The head of the list.

References list_insert(), n, and ll_head::next.

Referenced by malloc_addblock().

list_add_tail()

static void list_add_tail ( struct ll_head *  n, struct ll_head *  head  )

inlinestatic

Add a node to the end of the list.

Parameters

[in]	n	The node to add to the list.
[in]	head	The head of the list.

References list_insert(), n, and ll_head::prev.

Referenced by free().

list_del()

static void list_del ( struct ll_head *  entry )

inlinestatic

Remove an entry from the list.

Parameters

[in]

entry

The pointer to the entry to remove from the list.

References entry(), list_join_nodes(), and NULL.

Referenced by defrag_free_list(), and malloc().

list_insert()

static void list_insert ( struct ll_head *  n, struct ll_head *  prev, struct ll_head *  next  )

inlinestatic

Insert a new element between two existing elements.

Parameters

[in]	n	The node to add to the list.
[in]	prev	The pointer to the node before where the new node will be inserted.
[in]	next	The pointer to the new node after where the new node will be inserted.

References n, ll_head::next, next, and ll_head::prev.

Referenced by free(), list_add(), list_add_tail(), and malloc().

list_join_nodes()

static void list_join_nodes ( struct ll_head *  prev, struct ll_head *  next  )

inlinestatic

Remove the node between two element pointers.

Joins the prev and next elements together, effectively removing the element in the middle.

Parameters

[in]	prev	The previous element in the list, which will now be joined to next.
[in]	next	The next element in the list, which will now be joined to prev.

References ll_head::next, next, and ll_head::prev.

Referenced by list_del().