Doubly linked list base implementation. More...

Classes
struct	dlist_node
	The doubly linked node structure. More...

Macros
#define	DLIST_PNODE_INIT_DATA(pnode) (pnode)->next = (pnode)->prev = pnode
	Initialize node links (pointer version). More...

#define	DLIST_NODE_INIT(node) DLIST_PNODE_INIT_DATA(&(node))
	Initialize node links. More...

#define	DLIST_PNODE_INIT(pnode) DLIST_PNODE_INIT_DATA(pnode)
	Initialize node links (pointer version). More...

#define	dlist_entry(ptr, type, member) ((type )((char )(ptr)-(unsigned long)(&((type *)0)->member)))
	get the pointer to the embedding struct for ptr More...

#define	dlist_for_each(pos, head) for(pos = (head)->next; pos != (head); pos = pos->next)
	iterate over a list More...

#define	dlist_for_each_safe(pos, npos, head)
	safely iterate over a list More...

Typedefs
typedef struct dlist_node	dnode_t
	The doubly linked node structure.

Functions
static void	_dlist_add (dnode_t node, dnode_t prev, dnode_t *next)
	insert a new entry between two known consecutive entries More...

static void	dlist_prepend (dnode_t node, dnode_t head)
	prepend new node to head of list More...

static void	dlist_append (dnode_t node, dnode_t head)
	append a new node to the in of the list More...

static void	_dlist_del (dnode_t prev, dnode_t next)
	delete the node(s) between the prev/next nodes. More...

static void	dlist_delete (dnode_t *node)
	deletes node from list More...

static int	dlist_is_empty (dnode_t *head)
	tests whether a list is empty More...

static void	dlist_splice (dnode_t list, dnode_t head)
	prepend new list at head of given list More...

Detailed Description

Doubly linked list base implementation.

The dlists are intended to be embedded within the parent structure of a specific type. Higher level constructs using the dlist base can build implementations doubly-linked lists, queues, stacks, circular buffers, and binary trees with data of any type.

Some of the internal functions ("_dlist_xxx") are useful when manipulating whole lists rather than single entries, as sometimes we already know the next/prev entries and we can generate better code by using them directly rather than using the generic single-entry routines.

This file has been modified from the original source (see below).

Package: RoadNarrows Robotics Common Library 1

Library: librnr

File: rnr/dlist.h

Author: Robin Knight (robin.nosp@m..kni.nosp@m.ght@r.nosp@m.oadn.nosp@m.arrow.nosp@m.s.co.nosp@m.m)

Copyright: © 2005-2018. RoadNarrows LLC..
http://www.roadnarrows.com
All Rights Reserved

License: MIT

EULA: See the README and EULA files for any copyright and licensing information.

—

Original Source and Copyright

Original Author: Linux 2.6

Original Source Header: Linux header file <linux/list.h>

Definition in file dlist.h.

Macro Definition Documentation

#define dlist_entry	(	ptr,
		type,
		member
	)	((type )((char )(ptr)-(unsigned long)(&((type *)0)->member)))

get the pointer to the embedding struct for ptr

Parameters

ptr	the &dnode_t pointer.
type	the name of the struct the dnode_t is embedded in.
member	the name of the member in type that is the dnode_t.

Returns: pointer to embedding structure

Definition at line 202 of file dlist.h.

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

iterate over a list

Parameters

pos	the dnode_t pointer to use as a loop counter
head	the head of list to iterate over

Definition at line 211 of file dlist.h.

#define dlist_for_each_safe	(	pos,
		npos,
		head
	)

Value:

for(pos = (head)->next, npos = pos->next; pos != (head); \

pos = npos, npos = pos->next)

safely iterate over a list

Parameters

pos	the dnode_t pointer to be use as a loop counter
npos	another dnode_t pointer to use as temporary storage
head	the head of list to iterate over

Note: (Somewhat) safe against removal of list entry. That is, node pos can be deleted, etc and this interator still works. However, this (or the above interator) are not thread safe.

Definition at line 225 of file dlist.h.

Referenced by DListVoidDeleteAllNodes(), DListVoidFindNode(), DListVoidGetNodeAt(), and DListVoidPrint().

#define DLIST_NODE_INIT ( node ) DLIST_PNODE_INIT_DATA(&(node))

Initialize node links.

Parameters

node dnode_t

Definition at line 74 of file dlist.h.

Referenced by DListVoidNew().

#define DLIST_PNODE_INIT ( pnode ) DLIST_PNODE_INIT_DATA(pnode)

Initialize node links (pointer version).

Parameters

pnode pointer to dnode_t

Definition at line 80 of file dlist.h.

Referenced by dlist_delete().

#define DLIST_PNODE_INIT_DATA ( pnode ) (pnode)->next = (pnode)->prev = pnode

Initialize node links (pointer version).

Parameters

pnode pointer to dnode_t

Definition at line 68 of file dlist.h.

Function Documentation

static void _dlist_add	(	dnode_t *	node,
		dnode_t *	prev,
		dnode_t *	next
	)

inlinestatic

insert a new entry between two known consecutive entries

Parameters

node	the new node to be inserted
prev	previous node to new node
next	next node to new node

Note: This is only for internal list manipulation where we know the prev/next entries already!

Definition at line 92 of file dlist.h.

References dlist_node::next, and dlist_node::prev.

Referenced by dlist_append(), dlist_prepend(), and DListVoidInsert().

 {
   next->prev = node;
   node->next = next;
   node->prev = prev;
   prev->next = node;
 }

static void _dlist_del	(	dnode_t *	prev,
		dnode_t *	next
	)

inlinestatic

delete the node(s) between the prev/next nodes.

Parameters

prev	previous node to link to next
next	next node to link with previous

Note: This is only for internal list manipulation where we know the prev/next entries already!

Definition at line 137 of file dlist.h.

References dlist_node::next, and dlist_node::prev.

Referenced by dlist_delete().

 {
   next->prev = prev;
   prev->next = next;
 }

static void dlist_append	(	dnode_t *	node,
		dnode_t *	head
	)

inlinestatic

append a new node to the in of the list

Insert a new node before the specified head. This is useful for implementing queues.

Parameters

node	the new node to be inserted at end of the list
head	list head

Definition at line 123 of file dlist.h.

References _dlist_add(), and dlist_node::prev.

Referenced by DListVoidAppend().

 {
   _dlist_add(node, head->prev, head);
 }

static void dlist_delete ( dnode_t * node )

inlinestatic

deletes node from list

Parameters

node	the node to delete from the list.

Note: Deleted node becomes an orphan (i.e. empty) head node.

Definition at line 150 of file dlist.h.

References _dlist_del(), DLIST_PNODE_INIT, dlist_node::next, and dlist_node::prev.

Referenced by DListVoidDeleteNode(), DListVoidUnlinkDataAt(), and DListVoidUnlinkNodeAt().

 {
   _dlist_del(node->prev, node->next);
   DLIST_PNODE_INIT(node);
 }

static int dlist_is_empty ( dnode_t * head )

inlinestatic

tests whether a list is empty

Parameters

head list head

Returns: non-zero if empty, 0 otherwise

Definition at line 163 of file dlist.h.

References dlist_node::next.

Referenced by dlist_splice().

 {
   return head->next == head;
 }

static void dlist_prepend	(	dnode_t *	node,
		dnode_t *	head
	)

inlinestatic

prepend new node to head of list

Insert a new node after the specified head. This is good for implementing stacks.

Parameters

node	the new node to be inserted at head of the list
head	list head

Definition at line 109 of file dlist.h.

References _dlist_add(), and dlist_node::next.

Referenced by DListVoidPrepend().

 {
   _dlist_add(node, head, head->next);
 }

static void dlist_splice	(	dnode_t *	list,
		dnode_t *	head
	)

inlinestatic

prepend new list at head of given list

Parameters

list	the new list to add
head	list head holding newly spliced lists

Note: The list prev/next pointers are not altered so it is still a valid list.

Definition at line 177 of file dlist.h.

References dlist_is_empty(), dlist_node::next, and dlist_node::prev.

 {
   if( !dlist_is_empty(list) )
   {
     dnode_t *first = list->next;
     dnode_t *last  = list->prev;
     dnode_t *at    = head->next;
 
     first->prev = head;
     head->next  = first;
 
     last->next = at;
     at->prev   = last;
   }
 }

Classes

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

Function Documentation