/*
 * tkArray.h --
 *
 * An array is a sequence of items, stored in a contiguous memory region.
 * Random access to any item is very fast. New items can be either appended
 * or prepended. An array may be traversed in the forward or backward direction.
 *
 * Copyright (c) 2018-2019 by Gregor Cramer.
 *
 * See the file "license.terms" for information on usage and redistribution of
 * this file, and for a DISCLAIMER OF ALL WARRANTIES.
 */

/*
 * Note that this file will not be included in header files, it is the purpose
 * of this file to be included in source files only. Thus we are not using the
 * prefix "Tk_" here for functions, because all the functions have private scope.
 */
 
/*
 * -------------------------------------------------------------------------------
 * Use the array in the following way:
 * -------------------------------------------------------------------------------
 * typedef struct { int key, value; } Pair;
 * TK_PTR_ARRAY_DEFINE(MyArray, Pair);
 * MyArray *arr = NULL;
 * if (MyArray_IsEmpty(arr)) {
 *     MyArray_Append(&arr, MakePair(1, 2));
 *     MyArray_Append(&arr, MakePair(2, 3));
 *     for (i = 0; i < MyArray_Size(arr); ++i) {
 *         Pair *p = MyArray_Get(arr, i);
 *         printf("%d -> %d\n", p->key, p->value);
 *         ckfree(p);
 *     }
 *     MyArray_Free(&arr);
 *     assert(arr == NULL);
 * }
 * -------------------------------------------------------------------------------
 * Or with aggregated elements:
 * -------------------------------------------------------------------------------
 * typedef struct { int key, value; } Pair;
 * TK_ARRAY_DEFINE(MyArray, Pair);
 * Pair p1 = { 1, 2 };
 * Pair p2 = { 2, 3 };
 * MyArray *arr = NULL;
 * if (MyArray_IsEmpty(arr)) {
 *     MyArray_Append(&arr, p1);
 *     MyArray_Append(&arr, p2);
 *     for (i = 0; i < MyArray_Size(arr); ++i) {
 *         const Pair *p = MyArray_Get(arr, i);
 *         printf("%d -> %d\n", p->key, p->value);
 *     }
 *     MyArray_Free(&arr);
 *     assert(arr == NULL);
 * }
 * -------------------------------------------------------------------------------
 */
 
/*************************************************************************/
/*
 * Two array types will be provided:
 * Use TK_ARRAY_DEFINE if your array is aggregating the elements. Use
 * TK_PTR_ARRAY_DEFINE if your array contains pointers to elements. But
 * in latter case the array is not responsible for the lifetime of the
 * elements.
 */
/*************************************************************************/
/*
 * Array_ElemSize: Returns the memory size for one array element.
 */
/*************************************************************************/
/*
 * Array_BufferSize: Returns the memory size for given number of elements.
 */
/*************************************************************************/
/*
 * Array_IsEmpty: Array is empty?
 */
/*************************************************************************/
/*
 * Array_Size: Number of elements in array.
 */
/*************************************************************************/
/*
 * Array_Capacity: Capacity of given array. This is the maximal number of
 * elements fitting into current array memory without resizing the buffer.
 */
/*************************************************************************/
/*
 * Array_SetSize: Set array size, new size must not exceed the capacity of
 * the array. This function has to be used with care when increasing the
 * array size.
 */
/*************************************************************************/
/*
 * Array_First: Returns position of first element in array. Given array
 * may be NULL.
 */
/*************************************************************************/
/*
 * Array_Last: Returns position after last element in array. Given array
 * may be empty.
 */
/*************************************************************************/
/*
 * Array_Front: Returns first element in array. Given array must not be
 * empty.
 */
/*************************************************************************/
/*
 * Array_Back: Returns last element in array. Given array must not be
 * empty.
 */
/*************************************************************************/
/*
 * Array_Resize: Resize buffer of array for given number of elements. The
 * array may grow or shrink. Note that this function is not initializing
 * the increased buffer.
 */
/*************************************************************************/
/*
 * Array_ResizeAndClear: Resize buffer of array for given number of
 * elements. The array may grow or shrink. The increased memory will be
 * filled with zeroes.
 */
/*************************************************************************/
/*
 * Array_Clear: Fill specified range with zeroes.
 */
/*************************************************************************/
/*
 * Array_Free: Resize array to size zero. This function will release the
 * array buffer.
 */
/*************************************************************************/
/*
 * Array_Append: Insert given element after end of array.
 */
/*************************************************************************/
/*
 * Array_PopBack: Shrink array by one element. Given array must not be
 * empty.
 */
/*************************************************************************/
/*
 * Array_Get: Random access to array element at given position. The given
 * index must not exceed current array size.
 */
/*************************************************************************/
/*
 * Array_Set: Replace array element at given position with new value. The
 * given index must not exceed current array size.
 */
/*************************************************************************/
/*
 * Array_Find: Return index position of element which matches given
 * argument. If not found then -1 will be returned.
 */
/*************************************************************************/
 
#ifndef TK_ARRAY_DEFINED
#define TK_ARRAY_DEFINED

#include "tkInt.h"

#if defined(__GNUC__) || defined(__clang__)
# define __TK_ARRAY_UNUSED __attribute__((unused))
#else
# define __TK_ARRAY_UNUSED
#endif

#define TK_ARRAY_DEFINE(AT, ElemType) /* AT = type of array */			\
/* ------------------------------------------------------------------------- */	\
typedef struct AT {								\
    size_t size;								\
    size_t capacity;								\
    ElemType buf[1];								\
} AT;										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_Init(AT *arr)								\
{										\
    assert(arr);								\
    arr->size = 0;								\
    arr->capacity = 0;								\
}										\
										\
__TK_ARRAY_UNUSED								\
static size_t									\
AT##_ElemSize()									\
{										\
    return sizeof(ElemType);							\
}										\
										\
__TK_ARRAY_UNUSED								\
static size_t									\
AT##_BufferSize(size_t numElems)						\
{										\
    return numElems*sizeof(ElemType);						\
}										\
										\
__TK_ARRAY_UNUSED								\
static int									\
AT##_IsEmpty(const AT *arr)							\
{										\
    assert(!arr || arr->size != 0xdeadbeef);					\
    return !arr || arr->size == 0u;						\
}										\
										\
__TK_ARRAY_UNUSED								\
static size_t									\
AT##_Size(const AT *arr)							\
{										\
    assert(!arr || arr->size != 0xdeadbeef);					\
    return arr ? arr->size : 0u;						\
}										\
										\
__TK_ARRAY_UNUSED								\
static size_t									\
AT##_Capacity(const AT *arr)							\
{										\
    assert(!arr || arr->size != 0xdeadbeef);					\
    return arr ? arr->capacity : 0u;						\
}										\
										\
__TK_ARRAY_UNUSED								\
static ElemType *								\
AT##_First(AT *arr)								\
{										\
    assert(!arr || arr->size != 0xdeadbeef);					\
    return arr ? arr->buf : NULL;						\
}										\
										\
__TK_ARRAY_UNUSED								\
static ElemType *								\
AT##_Last(AT *arr)								\
{										\
    assert(!arr || arr->size != 0xdeadbeef);					\
    return arr ? arr->buf + arr->size : NULL;					\
}										\
										\
__TK_ARRAY_UNUSED								\
static ElemType *								\
AT##_Front(AT *arr)								\
{										\
    assert(arr);								\
    assert(arr->size != 0xdeadbeef);						\
    assert(!AT##_IsEmpty(arr));							\
    return &arr->buf[0];							\
}										\
										\
__TK_ARRAY_UNUSED								\
static ElemType *								\
AT##_Back(AT *arr)								\
{										\
    assert(arr);								\
    assert(arr->size != 0xdeadbeef);						\
    assert(!AT##_IsEmpty(arr));							\
    return &arr->buf[arr->size - 1];						\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_Resize(AT **arrp, size_t newSize)						\
{										\
    assert(arrp);								\
    assert(!*arrp || (*arrp)->size != 0xdeadbeef);				\
    if (newSize == 0) {								\
	assert(!*arrp || ((*arrp)->size = 0xdeadbeef));				\
	ckfree(*arrp);								\
	*arrp = NULL;								\
    } else {									\
	int init = *arrp == NULL;						\
	size_t memSize = AT##_BufferSize(newSize - 1) + sizeof(AT);		\
	*arrp = ckrealloc(*arrp, memSize);					\
	if (init) {								\
	    (*arrp)->size = 0;							\
	} else if (newSize < (*arrp)->size) {					\
	    (*arrp)->size = newSize;						\
	}									\
	(*arrp)->capacity = newSize;						\
    }										\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_Clear(AT *arr, size_t from, size_t to)					\
{										\
    assert(arr);								\
    assert(arr->size != 0xdeadbeef);						\
    assert(to <= AT##_Capacity(arr));						\
    assert(from <= to);								\
    memset(arr->buf + from, 0, AT##_BufferSize(to - from));			\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_ResizeAndClear(AT **arrp, size_t newSize)					\
{										\
    size_t oldCapacity;								\
    assert(arrp);								\
    oldCapacity = *arrp ? (*arrp)->capacity : 0;				\
    AT##_Resize(arrp, newSize);							\
    if (newSize > oldCapacity) {						\
	AT##_Clear(*arrp, oldCapacity, newSize);				\
    }										\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_SetSize(AT *arr, size_t newSize)						\
{										\
    assert(newSize <= AT##_Capacity(arr));					\
    assert(!arr || arr->size != 0xdeadbeef);					\
    if (arr) {									\
	arr->size = newSize;							\
    }										\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_Append(AT **arrp, ElemType *elem)						\
{										\
    assert(arrp);								\
    if (!*arrp) {								\
	AT##_Resize(arrp, 1);							\
    } else if ((*arrp)->size == (*arrp)->capacity) {				\
	AT##_Resize(arrp, (*arrp)->capacity + ((*arrp)->capacity + 1)/2);	\
    }										\
    (*arrp)->buf[(*arrp)->size++] = *elem;					\
}										\
										\
__TK_ARRAY_UNUSED								\
static size_t									\
AT##_PopBack(AT *arr)								\
{										\
    assert(!AT##_IsEmpty(arr));							\
    return arr->size -= 1;							\
}										\
										\
__TK_ARRAY_UNUSED								\
static ElemType *								\
AT##_Get(const AT *arr, size_t at)						\
{										\
    assert(arr);								\
    assert(at < AT##_Size(arr));						\
    return (ElemType *) &arr->buf[at];						\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_Set(AT *arr, size_t at, ElemType *elem)					\
{										\
    assert(arr);								\
    assert(at < AT##_Size(arr));						\
    arr->buf[at] = *elem;							\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_Free(AT **arrp)								\
{										\
    AT##_Resize(arrp, 0);							\
}										\
										\
__TK_ARRAY_UNUSED								\
static int									\
AT##_Find(const AT *arr, const ElemType *elem)					\
{										\
    assert(!arr || arr->size != 0xdeadbeef);					\
    if (arr) {									\
	const ElemType *buf = arr->buf;						\
	size_t i;								\
	for (i = 0; i < arr->size; ++i) {					\
	    if (memcmp(&buf[i], elem, sizeof(ElemType)) == 0) {			\
		return (int) i;							\
	    }									\
	}									\
    }										\
    return -1;									\
}										\
										\
__TK_ARRAY_UNUSED								\
static int									\
AT##_Contains(const AT *arr, const ElemType *elem)				\
{										\
    return AT##_Find(arr, elem) != -1;						\
}										\
/* ------------------------------------------------------------------------- */
 
#define TK_PTR_ARRAY_DEFINE(AT, ElemType) /* AT = type of array */		\
/* ------------------------------------------------------------------------- */	\
typedef struct AT {								\
    size_t size;								\
    size_t capacity;								\
    ElemType *buf[1];								\
} AT;										\
										\
__TK_ARRAY_UNUSED								\
static size_t									\
AT##_ElemSize()									\
{										\
    return sizeof(ElemType);							\
}										\
										\
__TK_ARRAY_UNUSED								\
static size_t									\
AT##_BufferSize(size_t numElems)						\
{										\
    return numElems*sizeof(ElemType *);						\
}										\
										\
__TK_ARRAY_UNUSED								\
static int									\
AT##_IsEmpty(const AT *arr)							\
{										\
    assert(!arr || arr->size != 0xdeadbeef);					\
    return !arr || arr->size == 0;						\
}										\
										\
__TK_ARRAY_UNUSED								\
static ElemType **								\
AT##_First(AT *arr)								\
{										\
    assert(!arr || arr->size != 0xdeadbeef);					\
    return arr ? arr->buf : NULL;						\
}										\
										\
__TK_ARRAY_UNUSED								\
static ElemType **								\
AT##_Last(AT *arr)								\
{										\
    assert(!arr || arr->size != 0xdeadbeef);					\
    return arr ? arr->buf + arr->size : NULL;					\
}										\
										\
__TK_ARRAY_UNUSED								\
static ElemType *								\
AT##_Front(AT *arr)								\
{										\
    assert(arr);								\
    assert(arr->size != 0xdeadbeef);						\
    assert(!AT##_IsEmpty(arr));							\
    return arr->buf[0];								\
}										\
										\
__TK_ARRAY_UNUSED								\
static ElemType *								\
AT##_Back(AT *arr)								\
{										\
    assert(arr);								\
    assert(arr->size != 0xdeadbeef);						\
    assert(!AT##_IsEmpty(arr));							\
    return arr->buf[arr->size - 1];						\
}										\
										\
__TK_ARRAY_UNUSED								\
static size_t									\
AT##_Size(const AT *arr)							\
{										\
    assert(!arr || arr->size != 0xdeadbeef);					\
    return arr ? arr->size : 0;							\
}										\
										\
__TK_ARRAY_UNUSED								\
static size_t									\
AT##_Capacity(const AT *arr)							\
{										\
    assert(!arr || arr->size != 0xdeadbeef);					\
    return arr ? arr->capacity : 0;						\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_Resize(AT **arrp, size_t newCapacity)					\
{										\
    assert(arrp);								\
    assert(!*arrp || (*arrp)->size != 0xdeadbeef);				\
    if (newCapacity == 0) {							\
	assert(!*arrp || ((*arrp)->size = 0xdeadbeef));				\
	ckfree(*arrp);								\
	*arrp = NULL;								\
    } else {									\
	int init = *arrp == NULL;						\
	size_t memSize = AT##_BufferSize(newCapacity - 1) + sizeof(AT);		\
	*arrp = ckrealloc(*arrp, memSize);					\
	if (init) {								\
	    (*arrp)->size = 0;							\
	} else if (newCapacity < (*arrp)->size) {				\
	    (*arrp)->size = newCapacity;					\
	}									\
	(*arrp)->capacity = newCapacity;					\
    }										\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_Clear(AT *arr, size_t from, size_t to)					\
{										\
    assert(arr);								\
    assert(arr->size != 0xdeadbeef);						\
    assert(to <= AT##_Capacity(arr));						\
    assert(from <= to);								\
    memset(arr->buf + from, 0, AT##_BufferSize(to - from));			\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_ResizeAndClear(AT **arrp, size_t newCapacity)				\
{										\
    size_t oldCapacity;								\
    assert(arrp);								\
    oldCapacity = *arrp ? (*arrp)->capacity : 0;				\
    AT##_Resize(arrp, newCapacity);						\
    if (newCapacity > oldCapacity) {						\
	AT##_Clear(*arrp, oldCapacity, newCapacity);				\
    }										\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_SetSize(AT *arr, size_t newSize)						\
{										\
    assert(arr);								\
    assert(newSize <= AT##_Capacity(arr));					\
    arr->size = newSize;							\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_Append(AT **arrp, ElemType *elem)						\
{										\
    assert(arrp);								\
    if (!*arrp) {								\
	AT##_Resize(arrp, 1);							\
    } else if ((*arrp)->size == (*arrp)->capacity) {				\
	AT##_Resize(arrp, (*arrp)->capacity + ((*arrp)->capacity + 1)/2);	\
    }										\
    (*arrp)->buf[(*arrp)->size++] = elem;					\
}										\
										\
__TK_ARRAY_UNUSED								\
static size_t									\
AT##_PopBack(AT *arr)								\
{										\
    assert(!AT##_IsEmpty(arr));							\
    return arr->size -= 1;							\
}										\
										\
__TK_ARRAY_UNUSED								\
static ElemType *								\
AT##_Get(const AT *arr, size_t at)						\
{										\
    assert(arr);								\
    assert(at < AT##_Size(arr));						\
    return arr->buf[at];							\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_Set(AT *arr, size_t at, ElemType *elem)					\
{										\
    assert(arr);								\
    assert(at < AT##_Size(arr));						\
    arr->buf[at] = elem;							\
}										\
										\
__TK_ARRAY_UNUSED								\
static void									\
AT##_Free(AT **arrp)								\
{										\
    AT##_Resize(arrp, 0);							\
}										\
										\
__TK_ARRAY_UNUSED								\
static int									\
AT##_Find(const AT *arr, const ElemType *elem)					\
{										\
    assert(!arr || arr->size != 0xdeadbeef);					\
    if (arr) {									\
	ElemType *const *buf = arr->buf;					\
	size_t i;								\
	for (i = 0; i < arr->size; ++i) {					\
	    if (buf[i] == elem) {						\
		return (int) i;							\
	    }									\
	}									\
    }										\
    return -1;									\
}										\
										\
__TK_ARRAY_UNUSED								\
static int									\
AT##_Contains(const AT *arr, const ElemType *elem)				\
{										\
    return AT##_Find(arr, elem) != -1;						\
}										\
/* ------------------------------------------------------------------------- */
 
#endif /* TK_ARRAY_DEFINED */
 
/*
 * Local Variables:
 * mode: c
 * c-basic-offset: 4
 * fill-column: 105
 * End:
 * vi:set ts=8 sw=4:
 */

/*
 * tkDList.h --
 *
 * A list is headed by pointers to first and last element. The elements
 * are doubly linked so that an arbitrary element can be removed without
 * a need to traverse the list. New elements can be added to the list
 * before or after an existing element or at the head/tail of the list.
 * A list may be traversed in the forward or backward direction.
 *
 * Copyright (c) 2018 by Gregor Cramer.
 *
 * See the file "license.terms" for information on usage and redistribution of
 * this file, and for a DISCLAIMER OF ALL WARRANTIES.
 */

/*
 * Note that this file will not be included in header files, it is the purpose
 * of this file to be included in source files only. Thus we are not using the
 * prefix "Tk_" here for functions, because all the functions have private scope.
 */
 
/*
 * -------------------------------------------------------------------------------
 * Use the double linked list in the following way:
 * -------------------------------------------------------------------------------
 * typedef struct MyListEntry { TK_DLIST_LINKS(MyListEntry); int value; } MyListEntry;
 * TK_DLIST_DEFINE(MyList, MyListEntry);
 * MyList listHdr = TK_DLIST_LIST_INITIALIZER; // or MyList_Init(&listHdr)
 * MyListEntry *p;
 * int i = 0;
 * MyList_Append(&listHdr, ckalloc(sizeof(MyListEntry)));
 * MyList_Append(&listHdr, ckalloc(sizeof(MyListEntry)));
 * TK_DLIST_FOREACH(p, &listHdr) { p->value = i++; }
 * // ...
 * MyList_RemoveHead(&listHdr);
 * MyList_RemoveHead(&listHdr);
 * MyList_Clear(MyListEntry, &listHdr); // invokes ckfree() for each element
 * -------------------------------------------------------------------------------
 * IMPORTANT NOTE: TK_DLIST_LINKS must be used at start of struct!
 */
 
#ifndef TK_DLIST_DEFINED
#define TK_DLIST_DEFINED

#include "tkInt.h"

/*
 * List definitions.
 */

#define TK_DLIST_LINKS(ElemType)						\
struct {									\
    struct ElemType *prev;	/* previous element */				\
    struct ElemType *next;	/* next element */				\
} _dl_

#define TK_DLIST_LIST_INITIALIZER { NULL, NULL }
#define TK_DLIST_ELEM_INITIALIZER { NULL, NULL }

/*************************************************************************/
/*
 * DList_Init: Initialize list header. This can also be used to clear the
 * list.
 *
 * See also: DList_Clear()
 */
/*************************************************************************/
/*
 * DList_ElemInit: Initialize a list element.
 */
/*************************************************************************/
/*
 * DList_InsertAfter: Insert 'elem' after 'listElem'. 'elem' must not
 * be linked, but 'listElem' must be linked.
 */
/*************************************************************************/
/*
 * DList_InsertBefore: Insert 'elem' before 'listElem'. 'elem' must not
 * be linked, but 'listElem' must be linked.
 */
/*************************************************************************/
/*
 * DList_Prepend: Insert 'elem' at start of list. This element must not
 * be linked.
 *
 * See also: DList_Append()
 */
/*************************************************************************/
/*
 * DList_Append: Append 'elem' to end of list. This element must not
 * be linked.
 *
 * See also: DList_Prepend()
 */
/*************************************************************************/
/*
 * DList_Move: Append all list items of 'src' to end of 'dst'.
 */
/*************************************************************************/
/*
 * DList_Remove: Remove 'elem' from list. This element must be linked.
 *
 * See also: DList_Free()
 */
/*************************************************************************/
/*
 * DList_Free: Remove 'elem' from list and free it. This element must
 * be linked.
 *
 * See also: DList_Remove()
 */
/*************************************************************************/
/*
 * DList_RemoveHead: Remove first element from list. The list must
 * not be empty.
 *
 * See also: DList_FreeHead()
 */
/*************************************************************************/
/*
 * DList_RemoveTail: Remove last element from list. The list must
 * not be empty.
 *
 * See also: DList_FreeTail()
 */
/*************************************************************************/
/*
 * DList_FreeHead: Remove first element from list and free it.
 * The list must not be empty.
 *
 * See also: DList_RemoveHead()
 */
/*************************************************************************/
/*
 * DList_FreeTail: Remove last element from list and free it.
 * The list must not be empty.
 *
 * See also: DList_RemoveTail()
 */
/*************************************************************************/
/*
 * DList_SwapElems: Swap positions of given elements 'lhs' and 'rhs'.
 * Both elements must be linked, and must belong to same list.
 */
/*************************************************************************/
/*
 * DList_Clear: Clear whole list and free all elements.
 *
 * See also: DList_Init
 */
/*************************************************************************/
/*
 * DList_Traverse: Iterate over all elements in list from first to last.
 * Call given function func(head, elem) for each element. The function has
 * to return the next element in list to traverse, normally this is
 * DList_Next(elem).
 *
 * See also: TK_DLIST_FOREACH, TK_DLIST_FOREACH_REVERSE
 */
/*************************************************************************/
/*
 * DList_First: Return pointer of first element in list, maybe it's NULL.
 */
/*************************************************************************/
/*
 * DList_Last: Return pointer of last element in list, maybe it's NULL.
 */
/*************************************************************************/
/*
 * DList_Next: Return pointer of next element after 'elem', maybe it's NULL.
 *
 * See also: DList_Prev()
 */
/*************************************************************************/
/*
 * DList_Prev: Return pointer of previous element before 'elem', maybe it's
 * NULL.
 *
 * See also: DList_Next()
 */
/*************************************************************************/
/*
 * DList_IsEmpty: Test whether given list is empty.
 */
/*************************************************************************/
/*
 * DList_IsLinked: Test whether given element is linked.
 */
/*************************************************************************/
/*
 * DList_IsFirst: Test whether given element is first element in list.
 * Note that 'elem' must be linked.
 *
 * See also: DList_IsLast(), DList_IsLinked()
 */
/*************************************************************************/
/*
 * DList_IsLast: Test whether given element is last element in list.
 * Note that 'elem' must be linked.
 *
 * See also: DList_IsFirst(), DList_IsLinked()
 */
/*************************************************************************/
/*
 * DList_Size: Count number of elements in given list.
 */
/*************************************************************************/
/*
 * TK_DLIST_FOREACH: Iterate over all elements in list from first to last.
 * 'var' is the name of the variable which points to current element.
 *
 * See also: TK_DLIST_FOREACH_REVERSE, DList_Traverse()
 */
/*************************************************************************/
/*
 * TK_DLIST_FOREACH_REVERSE: Iterate over all elements in list from last
 * to first (backwards). 'var' is the name of the variable which points to
 * current element.
 */
/*************************************************************************/
 
#if defined(__GNUC__) || defined(__clang__)
# define __TK_DLIST_UNUSED __attribute__((unused))
#else
# define __TK_DLIST_UNUSED
#endif

#define TK_DLIST_DEFINE(LT, ElemType) /* LT = type of head/list */		\
/* ------------------------------------------------------------------------- */	\
typedef struct LT {								\
    struct ElemType *first;	/* first element */				\
    struct ElemType *last;	/* last element */				\
} LT;										\
										\
typedef struct ElemType *(LT##_Func)(LT *head, struct ElemType *elem);		\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_Init(LT *head)								\
{										\
    assert(head);								\
    head->first = NULL;								\
    head->last = NULL;								\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_ElemInit(struct ElemType *elem)						\
{										\
    assert(elem);								\
    elem->_dl_.next = NULL;							\
    elem->_dl_.prev = NULL;							\
}										\
										\
__TK_DLIST_UNUSED								\
static int									\
LT##_IsEmpty(LT *head)								\
{										\
    assert(head);								\
    return head->first == NULL;							\
}										\
										\
__TK_DLIST_UNUSED								\
static int									\
LT##_IsLinked(struct ElemType *elem)						\
{										\
    assert(elem);								\
    return elem->_dl_.next && elem->_dl_.prev;					\
}										\
										\
__TK_DLIST_UNUSED								\
static int									\
LT##_IsFirst(struct ElemType *elem)						\
{										\
    assert(LT##_IsLinked(elem));						\
    return elem->_dl_.prev->_dl_.prev == elem;					\
}										\
										\
__TK_DLIST_UNUSED								\
static int									\
LT##_IsLast(struct ElemType *elem)						\
{										\
    assert(LT##_IsLinked(elem));						\
    return elem->_dl_.next->_dl_.next == elem;					\
}										\
										\
__TK_DLIST_UNUSED								\
static struct ElemType *							\
LT##_First(LT *head)								\
{										\
    assert(head);								\
    return head->first;								\
}										\
										\
__TK_DLIST_UNUSED								\
static struct ElemType *							\
LT##_Last(LT *head)								\
{										\
    assert(head);								\
    return head->last;								\
}										\
										\
__TK_DLIST_UNUSED								\
static struct ElemType *							\
LT##_Next(struct ElemType *elem)						\
{										\
    assert(elem);								\
    return LT##_IsLast(elem) ? NULL : elem->_dl_.next;				\
}										\
										\
__TK_DLIST_UNUSED								\
static struct ElemType *							\
LT##_Prev(struct ElemType *elem)						\
{										\
    assert(elem);								\
    return LT##_IsFirst(elem) ? NULL : elem->_dl_.prev;				\
}										\
										\
__TK_DLIST_UNUSED								\
static unsigned									\
LT##_Size(const LT *head)							\
{										\
    const struct ElemType *elem;						\
    unsigned size = 0;								\
    assert(head);								\
    if ((elem = head->first)) {							\
	for ( ; elem != (void *) head; elem = elem->_dl_.next) {		\
	    ++size;								\
	}									\
    }										\
    return size;								\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_InsertAfter(struct ElemType *listElem, struct ElemType *elem)		\
{										\
    assert(listElem);								\
    assert(elem);								\
    elem->_dl_.next = listElem->_dl_.next;					\
    elem->_dl_.prev = listElem;							\
    listElem->_dl_.next->_dl_.prev = elem;					\
    listElem->_dl_.next = elem;							\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_InsertBefore(struct ElemType *listElem, struct ElemType *elem)		\
{										\
    assert(listElem);								\
    assert(elem);								\
    elem->_dl_.next = listElem;							\
    elem->_dl_.prev = listElem->_dl_.prev;;					\
    listElem->_dl_.prev->_dl_.next = elem;					\
    listElem->_dl_.prev = elem;							\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_Prepend(LT *head, struct ElemType *elem)					\
{										\
    assert(head);								\
    assert(elem);								\
    elem->_dl_.prev = (void *) head;						\
    if (!head->first) {								\
	elem->_dl_.next = (void *) head;					\
	head->last = elem;							\
    } else {									\
	elem->_dl_.next = head->first;						\
	head->first->_dl_.prev = elem;						\
    }										\
    head->first = elem;								\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_Append(LT *head, struct ElemType *elem)					\
{										\
    assert(head);								\
    assert(elem);								\
    elem->_dl_.next = (void *) head;						\
    if (!head->first) {								\
	elem->_dl_.prev = (void *) head;					\
	head->first = elem;							\
    } else {									\
	elem->_dl_.prev = head->last;						\
	head->last->_dl_.next = elem;						\
    }										\
    head->last = elem;								\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_Move(LT *dst, LT *src)							\
{										\
    assert(dst);								\
    assert(src);								\
    if (src->first) {								\
	if (dst->first) {							\
	    dst->last->_dl_.next = src->first;					\
	    src->first->_dl_.prev = dst->last;					\
	    dst->last = src->last;						\
	} else {								\
	    *dst = *src;							\
	    dst->first->_dl_.prev = (void *) dst;				\
	}									\
	dst->last->_dl_.next = (void *) dst;					\
	LT##_Init(src);								\
    }										\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_Remove(struct ElemType *elem)						\
{										\
    int isFirst, isLast;							\
    assert(LT##_IsLinked(elem));						\
    isFirst = LT##_IsFirst(elem);						\
    isLast = LT##_IsLast(elem);							\
    if (isFirst && isLast) {							\
	((LT *) elem->_dl_.prev)->first = NULL;					\
	((LT *) elem->_dl_.next)->last = NULL;					\
    } else {									\
	if (isFirst) {								\
	    ((LT *) elem->_dl_.prev)->first = elem->_dl_.next;			\
	} else {								\
	    elem->_dl_.prev->_dl_.next = elem->_dl_.next;			\
	}									\
	if (isLast) {								\
	    ((LT *) elem->_dl_.next)->last = elem->_dl_.prev;			\
	} else {								\
	    elem->_dl_.next->_dl_.prev = elem->_dl_.prev;			\
	}									\
    }										\
    LT##_ElemInit(elem);							\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_Free(struct ElemType *elem)						\
{										\
    LT##_Remove(elem);								\
    ckfree((void *) elem);							\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_RemoveHead(LT *head)							\
{										\
    assert(!LT##_IsEmpty(head));						\
    LT##_Remove(head->first);							\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_RemoveTail(LT *head)							\
{										\
    assert(!LT##_IsEmpty(head));						\
    LT##_Remove(head->last);							\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_FreeHead(LT *head)								\
{										\
    assert(!LT##_IsEmpty(head));						\
    LT##_Free(head->first);							\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_FreeTail(LT *head)								\
{										\
    assert(!LT##_IsEmpty(head));						\
    LT##_Free(head->last);							\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_SwapElems(struct ElemType *lhs, struct ElemType *rhs)			\
{										\
    assert(lhs);								\
    assert(rhs);								\
    if (lhs != rhs) {								\
	struct ElemType tmp;							\
	if (LT##_IsFirst(lhs))  {						\
	    ((LT *) lhs->_dl_.prev)->first = rhs;				\
	} else if (LT##_IsFirst(rhs)) {						\
	    ((LT *) rhs->_dl_.prev)->first = lhs;				\
	}									\
	if (LT##_IsLast(lhs))  {						\
	    ((LT *) lhs->_dl_.next)->last = rhs;				\
	} else if (LT##_IsLast(rhs)) {						\
	    ((LT *) rhs->_dl_.next)->last = lhs;				\
	}									\
	tmp._dl_ = lhs->_dl_;							\
	lhs->_dl_ = rhs->_dl_;							\
	rhs->_dl_ = tmp._dl_;							\
    }										\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_Clear(LT *head)								\
{										\
    struct ElemType *p;								\
    struct ElemType *next;							\
    assert(head);								\
    for (p = head->first; p; p = next) {					\
	next = LT##_Next(p);							\
	ckfree((void *) p);							\
    }										\
    LT##_Init(head);								\
}										\
										\
__TK_DLIST_UNUSED								\
static void									\
LT##_Traverse(LT *head, LT##_Func func)						\
{										\
    struct ElemType *next;							\
    struct ElemType *p;								\
    assert(head);								\
    for (p = head->first; p; p = next) {					\
	next = func(head, p);							\
    }										\
}										\
/* ------------------------------------------------------------------------- */

#define TK_DLIST_FOREACH(var, head)						\
    assert(head);								\
    for (var = head->first ? head->first : (void *) head; var != (void *) head; var = var->_dl_.next)

#define TK_DLIST_FOREACH_REVERSE(var, head)					\
    assert(head);								\
    for (var = head->last ? head->last : (void *) head; var != (void *) head; var = var->_dl_.prev)
 
#endif /* TK_DLIST_DEFINED */
 
/*
 * Local Variables:
 * mode: c
 * c-basic-offset: 4
 * fill-column: 105
 * End:
 * vi:set ts=8 sw=4:
 */