Doubly Linked Lists

Macros for doubly linked lists. More...

Collaboration diagram for Doubly Linked Lists:

Macros
#define	csnip_dlist_Init(head, tail, mprev, mnext)
	Initialize a dlist. More...
#define	csnip_dlist_IsEmpty(head, tail, mprev, mnext)    ((head) == NULL)
	Check if a list is empty. More...
#define	csnip_dlist_PushHead(head, tail, mprev, mnext, el)
	Push an element to the head of a dlist.
#define	csnip_dlist_PopHead(head, tail, mprev, mnext)
	Pop the head of a dlist. More...
#define	csnip_dlist_PushTail(head, tail, mprev, mnext, el)
	Push an element to the tail of a dlist.
#define	csnip_dlist_PopTail(head, tail, mprev, mnext)
	Pop from the tail of a dlist. More...
#define	csnip_dlist_InsertAfter(head, tail, mprev, mnext, loc, el)
	Insert an element after the end of the given location. More...
#define	csnip_dlist_InsertBefore(head, tail, mprev, mnext, loc, el)
	Insert an element before loc. More...
#define	csnip_dlist_Remove(head, tail, mprev, mnext, el)
	Remove an element from the list. More...
#define	CSNIP_DLIST_DECL_FUNCS(scope, prefix, entry_ptr_type, gen_args)
	Declare dlist functions. More...
#define	CSNIP_DLIST_DEF_FUNCS(scope, prefix, entry_ptr_type, gen_args, phead, ptail, mprev, mnext)
	Define a set of dlist functions. More...

Detailed Description

Doubly linked lists (dlists) have pointers to both the previous and the next entry in each entry. Thus, they can be traversed in both directions. Among other things, they provide all the operations of a deque.

All the dlist macros take the 4 initial arguments head, tail, mprev and mnext. head is the lvalue pointing to the head of the list; may be modified by the operations; tail is the lvalue pointing to the tail of the list, again modifiable by the list operations. mprev and mnext are the names of the struct fields containing the pointer to the previous and next elements, respectively.

Simple dlist example (from examples/dlist.c):

#include <stdio.h>
 
#define CSNIP_SHORT_NAMES
#include <csnip/mem.h>
#include <csnip/list.h>
#include <csnip/util.h>
 
struct Entry {
    const char* name;
    struct Entry *prev, *next;
};
 
int main(void)
{
    // Create an empty list:
    struct Entry *head, *tail;
    dlist_Init(head, tail, prev, next);
 
    // Add some stuff to it
    const char* names_to_add[] = {
      "John", "David", "Michael", "Scott"
    };
    for (int i = 0; i < Static_len(names_to_add); ++i) {
        struct Entry* enew;
        mem_Alloc(1, enew, _);
        enew->name = names_to_add[i];
 
        // Add the entry
        dlist_PushTail(head, tail, prev, next, enew);
    }
 
    // Now read out backwards
    struct Entry* p = tail;
    while (p) {
        printf("%s\n", p->name);
        p = p->prev;
    }
 
    return 0;
}

Macro Definition Documentation

CSNIP_DLIST_DECL_FUNCS

#define CSNIP_DLIST_DECL_FUNCS	(		scope,
			prefix,
			entry_ptr_type,
			gen_args
	)

This macro declares a set of dlist functions that wrap the csnip_dlist_* macros; the functions can be defined with CSNIP_DLIST_DEF_FUNCS(). For a description of the macro arguments, see CSNIP_DLIST_DEF_FUNCS().

CSNIP_DLIST_DEF_FUNCS

#define CSNIP_DLIST_DEF_FUNCS	(		scope,
			prefix,
			entry_ptr_type,
			gen_args,
			phead,
			ptail,
			mprev,
			mnext
	)

Parameters

scope	the scope of the function declaration.
prefix	the prefix for the function names.
entry_ptr_type	pointer type to a list entry.
gen_args	generic arguments to specify the list, of the form args(...) or noargs().
phead	lvalue pointer to the list head, can be expressed in terms of the gen_args arguements
ptail	Like phead, but for the list tail.
mprev,mnext	The struct entry names for pointers to the previous, respectively next entry.

The list functions defined, are (without the prefix):

• void init(genargs)
• void push_head(genargs, entry_ptr_type element)
• void pop_head(genargs)
• void push_tail(genargs, entry_ptr_type element)
• void pop_tail(genargs)
• void insert_after(genargs, entry_ptr_type loc, entry_ptr_type element)
• void insert_before(genargs, entry_ptr_type loc, entry_ptr_type element)
• void remove(genargs, entry_ptr_type element)
• entry_ptr_type head(genargs)
• entry_ptr_type tail(genargs)
• entry_ptr_type prev(entry_ptr_type el)
• entry_ptr_type next(entry_ptr_type el)
• char is_empty(genargs)

csnip_dlist_Init

#define csnip_dlist_Init	(		head,
			tail,
			mprev,
			mnext
	)

Value:

    do { \
        (head) = (tail) = NULL; \
    } while (0)

csnip_dlist_InsertAfter

#define csnip_dlist_InsertAfter	(		head,
			tail,
			mprev,
			mnext,
			loc,
			el
	)

Parameters

head,tail,mprev,mnext	list description.
loc	point after which to insert (pointer to a list element).
el	element to insert.

csnip_dlist_InsertBefore

#define csnip_dlist_InsertBefore	(		head,
			tail,
			mprev,
			mnext,
			loc,
			el
	)

Parameters

head,tail,mprev,mnext	list description
loc	point before which to insert (pointer to a list element).
el	element to insert (pointer to element to add).

csnip_dlist_IsEmpty

#define csnip_dlist_IsEmpty	(		head,
			tail,
			mprev,
			mnext
	)		((head) == NULL)

Expression macro to check if a list is empty.

csnip_dlist_PopHead

#define csnip_dlist_PopHead	(		head,
			tail,
			mprev,
			mnext
	)

Underflowing the list results in an assertion failure; therefore, only pop the list if it's known that the list is non-empty.

csnip_dlist_PopTail

#define csnip_dlist_PopTail	(		head,
			tail,
			mprev,
			mnext
	)

Underflowing the list results in an assert failure.

csnip_dlist_Remove

#define csnip_dlist_Remove	(		head,
			tail,
			mprev,
			mnext,
			el
	)

This removes the element from the list; the element itself still exists after the call, and its prev and next pointers are not updated; but it's no longer part of the list.