gp_list.h File Reference

A linked list implementation. More...

#include <core/gp_common.h>

Go to the source code of this file.

Data Structures
struct	gp_list_head
	A linked list header. More...
struct	gp_dlist_head
	A double linked list header. More...
struct	gp_list
	A linked list pointers. More...
struct	gp_dlist
	A double linked list pointers. More...

Macros
#define	GP_LIST_ENTRY(ptr, structure, member)    GP_CONTAINER_OF(ptr, structure, member)
	Converts between list pointer and structure pointer.
#define	GP_LIST_FOREACH(list, entry)    for (entry = (list)->head; entry; entry = entry->next)
	A for loop over all list entries.
#define	GP_DLIST_REV_FOREACH(list, entry)    for (entry = (list)->tail; entry; entry = entry->prev)
	A reverse for loop over all list entries.

Typedefs
typedef struct gp_list_head	gp_list_head
	A linked list header.
typedef struct gp_dlist_head	gp_dlist_head
	A double linked list header.
typedef struct gp_list	gp_list
	A linked list pointers.
typedef struct gp_dlist	gp_dlist
	A double linked list pointers.

Functions
static void	gp_list_push_head (gp_list *list, gp_list_head *entry)
	Pushes into head of linked list.
static void	gp_dlist_push_head (gp_dlist *list, gp_dlist_head *entry)
	Pushes into head of double linked list.
static void	gp_list_push_tail (gp_list *list, gp_list_head *entry)
	Pushes into tail of linked list.
static void	gp_dlist_push_tail (gp_dlist *list, gp_dlist_head *entry)
	Pushes into tail of double linked list.
static void	gp_dlist_push_after (gp_dlist *list, gp_dlist_head *after, gp_dlist_head *entry)
	Pushes an entry into a double linked list after an entry.
static void	gp_dlist_push_before (gp_dlist *list, gp_dlist_head *before, gp_dlist_head *entry)
	Pushes an entry into a double linked list before an entry.
static gp_list_head *	gp_list_pop_head (gp_list *list)
	Pops from a head of a linked list.
static gp_dlist_head *	gp_dlist_pop_head (gp_dlist *list)
	Pops from a head of a double linked list.
static gp_dlist_head *	gp_dlist_pop_tail (gp_dlist *list)
	Pops from a tail of a double linked list.
static void	gp_dlist_rem (gp_dlist *list, gp_dlist_head *entry)
	Removes a entry from a double linked list.
static void	gp_list_sort (gp_list *list, int(*cmp)(const void *, const void *))
	Sorts a linked list given a element comparsion function.
static void	gp_dlist_sort (gp_dlist *list, int(*cmp)(const void *, const void *))
	Sorts a double linked list given a compare function.

Detailed Description

A linked list implementation.

Definition in file gp_list.h.

Macro Definition Documentation

GP_DLIST_REV_FOREACH

#define GP_DLIST_REV_FOREACH	(		list,
			entry
	)		for (entry = (list)->tail; entry; entry = entry->prev)

A reverse for loop over all list entries.

Works only for double linked lists since it uses gp_dlist_head::prev pointers.

Example:

struct foo {
     gp_dlist_head lh;
};
 
static gp_dlist foos;
 
...
     gp_dlist_head *i;
 
     GP_DLIST_REV_FOREACH(&foos, i) {
        struct foo *f = GP_LIST_ENTRY(i, struct foo, lh);
        ...
     }
...

Parameters

list	A gp_dlist.
entry	An iterator entry a pointer to gp_dlist_head.

Definition at line 130 of file gp_list.h.

GP_LIST_ENTRY

#define GP_LIST_ENTRY	(		ptr,
			structure,
			member
	)		GP_CONTAINER_OF(ptr, structure, member)

Converts between list pointer and structure pointer.

Parameters

ptr	A list head pointer.
structure	A structure the list head pointer is embedded into.
member	A name of the list head in the structure.

Definition at line 72 of file gp_list.h.

GP_LIST_FOREACH

#define GP_LIST_FOREACH	(		list,
			entry
	)		for (entry = (list)->head; entry; entry = entry->next)

A for loop over all list entries.

Example:

struct foo {
     gp_list_head lh;
};
 
static gp_list foos;
 
...
     gp_list_head *i;
 
     GP_LIST_FOREACH(&foos, i) {
        struct foo *f = GP_LIST_ENTRY(i, struct foo, lh);
        ...
     }
...

Parameters

list	A gp_list or gp_dlist.
entry	An iterator entry a pointer to gp_list_head or gp_dlist_head.

Definition at line 100 of file gp_list.h.

Typedef Documentation

gp_dlist_head

typedef struct gp_dlist_head gp_dlist_head

A double linked list header.

This is embedded in the structures that are going to be inserted into a list.

gp_list_head

typedef struct gp_list_head gp_list_head

A linked list header.

This is embedded in the structures that are going to be inserted into a list.

Function Documentation

gp_dlist_pop_head()

static gp_dlist_head * gp_dlist_pop_head ( gp_dlist *  list )

inlinestatic

Pops from a head of a double linked list.

The returned pointer has to be converted to a structure by gp_list_entry().

Parameters

list	A double linked list.

Returns

Entry list head or NULL on empty list.

Definition at line 283 of file gp_list.h.

References gp_list_pop_head(), gp_dlist_head::next, and gp_dlist_head::prev.

gp_dlist_pop_tail()

static gp_dlist_head * gp_dlist_pop_tail ( gp_dlist *  list )

inlinestatic

Pops from a tail of a double linked list.

The returned pointer has to be converted to a structure by gp_list_entry().

Parameters

list	A double linked list.

Returns

Entry list head or NULL on empty list.

Definition at line 303 of file gp_list.h.

References gp_dlist::cnt, gp_dlist::head, gp_dlist_head::next, gp_dlist_head::prev, and gp_dlist::tail.

gp_dlist_push_after()

static void gp_dlist_push_after ( gp_dlist *  list, gp_dlist_head *  after, gp_dlist_head *  entry  )

inlinestatic

Pushes an entry into a double linked list after an entry.

Parameters

list	A double linked list.
after	The entry to be pushed after.
entry	An entry to be pushed.

Definition at line 214 of file gp_list.h.

References gp_dlist::cnt, gp_dlist_head::next, gp_dlist_head::prev, and gp_dlist::tail.

gp_dlist_push_before()

static void gp_dlist_push_before ( gp_dlist *  list, gp_dlist_head *  before, gp_dlist_head *  entry  )

inlinestatic

Pushes an entry into a double linked list before an entry.

Parameters

list	A double linked list.
before	The entry to be pushed before.
entry	An entry to be pushed.

Definition at line 236 of file gp_list.h.

References gp_dlist::cnt, gp_dlist::head, gp_dlist_head::next, and gp_dlist_head::prev.

gp_dlist_push_head()

static void gp_dlist_push_head ( gp_dlist *  list, gp_dlist_head *  entry  )

inlinestatic

Pushes into head of double linked list.

Parameters

list	A double linked list.
entry	An entry to be pushed.

Definition at line 156 of file gp_list.h.

References gp_list_push_head(), gp_dlist_head::next, and gp_dlist_head::prev.

gp_dlist_push_tail()

static void gp_dlist_push_tail ( gp_dlist *  list, gp_dlist_head *  entry  )

inlinestatic

Pushes into tail of double linked list.

Parameters

list	A double linked list.
entry	An entry to be pushed.

Definition at line 199 of file gp_list.h.

References gp_dlist_head::prev, and gp_dlist::tail.

gp_dlist_rem()

static void gp_dlist_rem ( gp_dlist *  list, gp_dlist_head *  entry  )

inlinestatic

Removes a entry from a double linked list.

The entry must be present in the list!

Parameters

list	A double linked list.
entry	An entry to remove.

Definition at line 330 of file gp_list.h.

References gp_dlist::cnt, gp_dlist::head, gp_dlist_head::next, gp_dlist_head::prev, and gp_dlist::tail.

gp_dlist_sort()

static void gp_dlist_sort ( gp_dlist *  list, int(*)(const void *, const void *)  cmp  )

inlinestatic

Sorts a double linked list given a compare function.

See gp_list_sort() for detailed description.

Parameters

list	A double linked list.
cmp	A compare function.

Definition at line 443 of file gp_list.h.

References gp_dlist::head, gp_dlist_head::next, gp_dlist_head::prev, and gp_dlist::tail.

gp_list_pop_head()

static gp_list_head * gp_list_pop_head ( gp_list *  list )

inlinestatic

Pops from a head of a linked list.

The returned pointer has to be converted to a structure by gp_list_entry().

Parameters

list	A linked list.

Returns

Entry list head or NULL on empty list.

Definition at line 259 of file gp_list.h.

References gp_list::cnt, gp_list::head, gp_list_head::next, and gp_list::tail.

Referenced by gp_dlist_pop_head().

gp_list_push_head()

static void gp_list_push_head ( gp_list *  list, gp_list_head *  entry  )

inlinestatic

Pushes into head of linked list.

Parameters

list	A linked list.
entry	An entry to be pushed.

Definition at line 139 of file gp_list.h.

References gp_list::cnt, gp_list::head, gp_list_head::next, and gp_list::tail.

Referenced by gp_dlist_push_head().

gp_list_push_tail()

static void gp_list_push_tail ( gp_list *  list, gp_list_head *  entry  )

inlinestatic

Pushes into tail of linked list.

Parameters

list	A linked list.
entry	An entry to be pushed.

Definition at line 186 of file gp_list.h.

References gp_list::tail.

gp_list_sort()

static void gp_list_sort ( gp_list *  list, int(*)(const void *, const void *)  cmp  )

inlinestatic

Sorts a linked list given a element comparsion function.

The compare function works the same as a in the qsort() system function, however the pointers passed are pointers to list head structure. Use gp_list_entry() macro to get the pointers to the structures instead.

Example compare function would look like:

struct foo {
     int i;
     gp_list_head head;
};
 
static int cmp(const void *a, const void *b)
{
     struct foo *fa = gp_list_entry(a, struct foo, head);
     struct foo *fb = gp_list_entry(b, struct foo, head);
 
     return fa->i - fb->i;
}

Parameters

list	A linked list.
cmp	A compare function.

Definition at line 420 of file gp_list.h.

References gp_list::head, gp_list_head::next, and gp_list::tail.