Simple doubly linked lists


Detailed Description

The simplest kind of linked list is a singly-linked list, which has one link per node. This link points to the next node in the list, or to a null value or empty list if it is the final node; e.g. 12 -> 99 -> 37 -> NULL.

A more sophisticated kind of linked list is a doubly-linked list. Each node has two links: one points to the previous node, or points to a null value or empty list if it is the first node; and one points to the next, or points to a null value or empty list if it is the final node; e.g. NULL <- 26 <-> 56 <-> 46 -> NULL.

The list family of functions and macros provide routines to create a list, add, move or remove elements and iterate over the list.


Data Structures

struct  list_head
 list head More...

Defines

#define container_of(ptr, type, member)   ((type *)((char *)(ptr) - offsetof(type, member)))
 get container of list head
#define LIST_NODE_ALLOC(NAME)   NAME = mem_alloc(sizeof(*NAME))
#define list_entry(ptr, type, member)   container_of(ptr, type, member)
 get the struct for this entry
#define list_for_each(pos, head)   for (pos = (head)->next; pos != (head); pos = pos->next)
 iterate over a list
#define list_for_each_prev(pos, head)   for (pos = (head)->prev; pos != (head); pos = pos->prev)
 iterate over a list backwards
#define list_for_each_safe(pos, n, head)
 iterate over a list safe against removal of list entry
#define list_for_each_entry(pos, head, member)
 iterate over list of given type
#define list_for_each_entry_reverse(pos, head, member)
 iterate backwards over list of given type.
#define list_for_each_entry_safe(pos, n, head, member)
 iterate over list of given type safe against removal of list entry
#define list_for_each_entry_safe_reverse(pos, n, head, member)
 iterate backwards over list of given type safe against removal of list entry

Typedefs

typedef list_head list_t
 list head


Define Documentation

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

get container of list head

Definition at line 48 of file list.h.

#define LIST_NODE_ALLOC ( NAME   )     NAME = mem_alloc(sizeof(*NAME))

Definition at line 66 of file list.h.

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

get the struct for this entry

Parameters:
ptr the &list_t pointer
type the type of the struct this is embedded in
member the name of the list_struct within the struct

Definition at line 250 of file list.h.

Referenced by strtok_delete(), strtok_free(), strtok_next(), and strtok_prev().

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

iterate over a list

Parameters:
pos the &list_t to use as a loop counter
head the head for your list

Definition at line 259 of file list.h.

Referenced by strtok_count().

#define list_for_each_prev ( pos,
head   )     for (pos = (head)->prev; pos != (head); pos = pos->prev)

iterate over a list backwards

Parameters:
pos the &list_t to use as a loop counter
head the head for your list

Definition at line 268 of file list.h.

#define list_for_each_safe ( pos,
n,
head   ) 

Value:

for (pos = (head)->next, n = pos->next; pos != (head); \
                pos = n, n = pos->next)
iterate over a list safe against removal of list entry

Parameters:
pos the &list_t to use as a loop counter
n another &list_t to use as temporary storage
head the head for your list

Definition at line 278 of file list.h.

Referenced by strtok_delete(), and strtok_free().

#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))
iterate over list of given type

Parameters:
pos the type * to use as a loop counter
head,: the head for your list
member the name of the list_struct within the struct

Definition at line 289 of file list.h.

#define list_for_each_entry_reverse ( pos,
head,
member   ) 

Value:

for (pos = list_entry((head)->prev, typeof(*pos), member); \
             &pos->member != (head); \
             pos = list_entry(pos->member.prev, typeof(*pos), member))
iterate backwards over list of given type.

Parameters:
pos the type * to use as a loop counter
head the head for your list
member the name of the list_struct within the struct

Definition at line 301 of file list.h.

#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))
iterate over list of given type safe against removal of list entry

Parameters:
pos the type * to use as a loop counter
n another type * to use as temporary storage
head the head for your list
member the name of the list_struct within the struct

Definition at line 314 of file list.h.

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

Value:

for (pos = list_entry((head)->prev, typeof(*pos), member), \
             n = list_entry(pos->member.prev, typeof(*pos), member); \
             &pos->member != (head); \
             pos = n, n = list_entry(n->member.prev, typeof(*n), member))
iterate backwards over list of given type safe against removal of list entry

Parameters:
pos the type * to use as a loop counter
n another type * to use as temporary storage
head the head for your list
member the name of the list_struct within the struct

Definition at line 328 of file list.h.


Typedef Documentation

typedef struct list_head list_t

list head


Generated on Tue Jun 19 20:38:45 2007 for lucid by  doxygen 1.5.2