utlist.h File Reference

Macros for basic linked list operations. More...

Detailed Description

Macros for basic linked list operations.

         For in-depth documentation see
         http://troydhanson.github.io/uthash/utlist.html

Definition in file utlist.h.

#include <stddef.h>
#include <assert.h>

Include dependency graph for utlist.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	UTLIST_VERSION   1.9.9
	Version number.

Compiler dependent defines
These macros use decltype or the earlier __typeof GNU extension. As decltype is only available in newer compilers (VS2010 or gcc 4.3+ when compiling c++ code), this code uses whatever method is needed or, for VS2008 where neither is available, uses casting workarounds. For VS2008 we use some workarounds to get around the lack of decltype, namely, we always reassign our tmp variable to the list head if we need to dereference its prev/next pointers, and save/restore the real head.
#define	LDECLTYPE(x)   __typeof(x)
#define	_SV(elt, list)
#define	_NEXT(elt, list, next)   ((elt)->next)
#define	_NEXTASGN(elt, list, to, next)   ((elt)->next)=(to)
#define	_PREVASGN(elt, list, to, prev)   ((elt)->prev)=(to)
#define	_RS(list)
#define	_CASTASGN(a, b)   (a)=(b)

Mergesort based sort macros
The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort Unwieldy variable names used here to avoid shadowing passed-in variables.
#define	LL_SORT(list, cmp)    LL_SORT2(list, cmp, next)
#define	LL_SORT2(list, cmp, next)
#define	DL_SORT(list, cmp)    DL_SORT2(list, cmp, prev, next)
#define	DL_SORT2(list, cmp, prev, next)
#define	CDL_SORT(list, cmp)    CDL_SORT2(list, cmp, prev, next)
#define	CDL_SORT2(list, cmp, prev, next)

Singly linked list macros (non-circular)
#define	LL_PREPEND(head, add)    LL_PREPEND2(head,add,next)
	LL prepend element 'add' to list.
#define	LL_PREPEND2(head, add, next)
	LL prepend to list with alternative next ptr name 'next'. More...
#define	LL_CONCAT(head1, head2)    LL_CONCAT2(head1,head2,next)
	LL concat to append second list to first.
#define	LL_CONCAT2(head1, head2, next)
	LL concat with alternative next ptr name 'next'. More...
#define	LL_APPEND(head, add)    LL_APPEND2(head,add,next)
	LL append to append element 'add' to list.
#define	LL_APPEND2(head, add, next)
	LL append with alternative next ptr name 'next'. More...
#define	LL_DELETE(head, del)    LL_DELETE2(head,del,next)
	LL delete element 'del' from list.
#define	LL_DELETE2(head, del, next)
	LL delete with alternative next ptr name 'name'. More...
#define	LL_APPEND_VS2008(head, add)    LL_APPEND2_VS2008(head,add,next)
#define	LL_APPEND2_VS2008(head, add, next)
#define	LL_DELETE_VS2008(head, del)    LL_DELETE2_VS2008(head,del,next)
#define	LL_DELETE2_VS2008(head, del, next)
#define	LL_COUNT(head, el, counter)    LL_COUNT2(head,el,counter,next) \
	LL count list elements using 'counter'.
#define	LL_COUNT2(head, el, counter, next)
	LL count with alternative next ptr name 'next'. More...
#define	LL_FOREACH(head, el)    LL_FOREACH2(head,el,next)
	LL list iteration.
#define	LL_FOREACH2(head, el, next)    for(el=head;el;el=(el)->next)
	LL list iteration with alternative next ptr name 'next'.
#define	LL_FOREACH_SAFE(head, el, tmp)    LL_FOREACH_SAFE2(head,el,tmp,next)
	LL safe list iteration Use if list elements might be deleted while iterating.
#define	LL_FOREACH_SAFE2(head, el, tmp, next)    for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
	LL safe list iteration with alternative ptr names.
#define	LL_SEARCH_SCALAR(head, out, field, val)    LL_SEARCH_SCALAR2(head,out,field,val,next)
	LL scalar search for element with value 'val' for member 'field'.
#define	LL_SEARCH_SCALAR2(head, out, field, val, next)
	LL scalar search with alternative next ptr name 'next'. More...
#define	LL_SEARCH(head, out, elt, cmp)    LL_SEARCH2(head,out,elt,cmp,next)
	LL search element 'elt' in list using function 'cmp'.
#define	LL_SEARCH2(head, out, elt, cmp, next)
	LL search with alternative next ptr name 'next'. More...
#define	LL_REPLACE_ELEM(head, el, add)
	LL replace element 'el' with element 'add' in list. More...
#define	LL_PREPEND_ELEM(head, el, add)
	LL prepend new element 'add' to element 'el' in list. More...

Doubly linked list macros (non-circular)
#define	DL_PREPEND(head, add)    DL_PREPEND2(head,add,prev,next)
	DL prepend element 'add' to list.
#define	DL_PREPEND2(head, add, prev, next)
	DL prepend to list with alternative ptr names. More...
#define	DL_APPEND(head, add)    DL_APPEND2(head,add,prev,next)
	DL append to append element 'add' to list.
#define	DL_APPEND2(head, add, prev, next)
	DL append with alternative next ptr name 'next'. More...
#define	DL_CONCAT(head1, head2)    DL_CONCAT2(head1,head2,prev,next)
	DL concat to append second list to first.
#define	DL_CONCAT2(head1, head2, prev, next)
	DL concat with alternative next ptr name 'next'. More...
#define	DL_DELETE(head, del)    DL_DELETE2(head,del,prev,next)
	DL delete element 'del' from list.
#define	DL_DELETE2(head, del, prev, next)
	DL delete with alternative ptr names. More...
#define	DL_COUNT(head, el, counter)    DL_COUNT2(head,el,counter,next) \
	DL count list elements using 'counter'.
#define	DL_COUNT2(head, el, counter, next)
	DL count with alternative next ptr name 'next'. More...
#define	DL_FOREACH(head, el)    DL_FOREACH2(head,el,next)
	DL list iteration.
#define	DL_FOREACH2(head, el, next)    for(el=head;el;el=(el)->next)
	DL list iteration with alternative next ptr name 'next'.
#define	DL_FOREACH_SAFE(head, el, tmp)    DL_FOREACH_SAFE2(head,el,tmp,next)
	DL safe list iteration Use if list elements might be deleted while iterating.
#define	DL_FOREACH_SAFE2(head, el, tmp, next)    for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
	DL safe list iteration with alternative ptr names.
#define	DL_SEARCH_SCALAR   LL_SEARCH_SCALAR
	DL scalar search for element with value 'val' for member 'field' Identical to singly-linked counterpart.
#define	DL_SEARCH_SCALAR2   LL_SEARCH_SCALAR2
	DL scalar search with alternative next ptr name 'next' Identical to singly-linked counterpart.
#define	DL_SEARCH   LL_SEARCH
	DL search element 'elt' in list using function 'cmp' Identical to singly-linked counterpart.
#define	DL_SEARCH2   LL_SEARCH2
	DL search with alternative next ptr name 'next' Identical to singly-linked counterpart.
#define	DL_REPLACE_ELEM(head, el, add)
	DL replace element 'el' with element 'add' in list. More...
#define	DL_PREPEND_ELEM(head, el, add)
	DL prepend new element 'add' to element 'el' in list. More...

Circular doubly linked list macros
#define	CDL_PREPEND(head, add)    CDL_PREPEND2(head,add,prev,next)
	CDL prepend element 'add' to list.
#define	CDL_PREPEND2(head, add, prev, next)
	CDL prepend to list with alternative ptr names. More...
#define	CDL_DELETE(head, del)    CDL_DELETE2(head,del,prev,next)
	CDL delete element 'del' from list.
#define	CDL_DELETE2(head, del, prev, next)
	CDL delete with alternative ptr names. More...
#define	CDL_COUNT(head, el, counter)    CDL_COUNT2(head,el,counter,next) \
	CDL count list elements using 'counter'.
#define	CDL_COUNT2(head, el, counter, next)
	CDL count with alternative next ptr name 'next'. More...
#define	CDL_FOREACH(head, el)    CDL_FOREACH2(head,el,next)
	CDL list iteration.
#define	CDL_FOREACH2(head, el, next)    for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
	CDL list iteration with alternative next ptr name 'next'.
#define	CDL_FOREACH_SAFE(head, el, tmp1, tmp2)    CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
	CDL safe list iteration Use if list elements might be deleted while iterating.
#define	CDL_FOREACH_SAFE2(head, el, tmp1, tmp2, prev, next)
	CDL safe list iteration with alternative ptr names. More...
#define	CDL_SEARCH_SCALAR(head, out, field, val)    CDL_SEARCH_SCALAR2(head,out,field,val,next)
	CDL scalar search for element with value 'val' for member 'field'.
#define	CDL_SEARCH_SCALAR2(head, out, field, val, next)
	CDL scalar search with alternative next ptr name 'next'. More...
#define	CDL_SEARCH(head, out, elt, cmp)    CDL_SEARCH2(head,out,elt,cmp,next)
	CDL search element 'elt' in list using function 'cmp'.
#define	CDL_SEARCH2(head, out, elt, cmp, next)
	CDL search with alternative next ptr name 'next'. More...
#define	CDL_REPLACE_ELEM(head, el, add)
	CDL replace element 'el' with element 'add' in list. More...
#define	CDL_PREPEND_ELEM(head, el, add)
	CDL prepend new element 'add' to element 'el' in list. More...