commit 6cad680c42d642fd273427cad7482daaa5976479
parent 6e04d43142e407c25d2126e709daf94d0f420ead
Author: Remy Noulin <loader2x@gmail.com>
Date: Sat, 22 Dec 2018 12:13:42 +0100
3 single linked lists
README.md | 24 +++
isingleList.h | 610 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
main.c | 382 ++++++++++++++++++++++++++++++++++++
package.yml | 32 +++
singleList.h | 544 +++++++++++++++++++++++++++++++++++++++++++++++++++
singleListe.h | 599 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 2191 insertions(+)
Diffstat:
| A | README.md | | | 24 | ++++++++++++++++++++++++ |
| A | isingleList.h | | | 610 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | main.c | | | 382 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | package.yml | | | 32 | ++++++++++++++++++++++++++++++++ |
| A | singleList.h | | | 544 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | singleListe.h | | | 599 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
6 files changed, 2191 insertions(+), 0 deletions(-)
diff --git a/README.md b/README.md
@@ -0,0 +1,24 @@
+# Sheepy
+This is a sheepy package for [sheepy](https://github.com/RemyNoulin/sheepy) and using [libsheepy](https://github.com/RemyNoulin/libsheepy)
+
+# single linked list
+
+This package has 3 single linked list versions storing the list nodes in segments to reduce the frequency of memory allocations.
+
+The data can be stored in the list nodes and further reduce the frequency of memory allocations.
+
+- `singleList.h` is a list using pointers to link the nodes. The nodes are stored internally.
+- `singleListe.h` is a list using pointers to link the nodes with external node storage. The node storage is shared between multiple list of identical element type.
+- `isingleList.h` is a list using indexes in an array to link the nodes. The nodes are stored internally and the index size (uint8, uint16, ...) is selected when defining the list. This list is more memory efficient and slower than `singleList.h`.
+
+
+# Usage
+
+Install with spm: `spm install singleList`
+
+Include one header file:
+- `#include "shpPackages/emoji/singleList.h"`
+- `#include "shpPackages/emoji/isingleList.h"`
+- `#include "shpPackages/emoji/singleListe.h"`
+
+Usage examples are on the top of the headers.
diff --git a/isingleList.h b/isingleList.h
@@ -0,0 +1,610 @@
+
+
+/**
+ * \file
+ *
+ * Indexed Single linked list: isingleList
+ *
+ * head 1 <- 2 <- 3 last
+ *
+ * The single linked list can be used as a stack and is not efficient when used as a queue.
+ *
+ * The nodes in isingleList are linked with indexes in the internal dArray, in some cases it saves memory compare to using 64 bit pointers. (isingleList is not compatible with lForEach from libsheepy.h)
+ *
+ * NOTE: The macros in this file are for creating list functions wrapping the macros.
+ *
+ * The number of nodes is defined at list declaration with the index type definition in isingleListT, the nodes are dynamically allocated in segments.
+ *
+ * The element type handled by the list is defined with isingleListT
+ *
+ * The nodes have 2 members: .elem and .prev, .elem is the element data and .prev is the index of the previous node
+ *
+ * use push and pop to stack nodes
+ *
+ * The forEach macros loop on nodes or elements from last node to head node
+ *
+ * use unlinkPrev or unlinkBefore and unlinkLast to unlink nodes anywhere in the list
+ *
+ * use insertBefore, addBefore to insert anywhere in the list, before head and push, insertLast, addLast to insert after last
+ *
+ * use freeUnlinked to free unlinked nodes
+ *
+ * use isingleListDelPrev or isingleListDelBefore, isingleListDelLast or isingleListPop to delete nodes anywhere in the list
+ *
+ * To create a list in reverse order, add the first node with push and then add the nodes with addBefore head
+ *
+ * Example:
+ *
+ * // define list:
+ * isingleListT(slt, u32, u32);
+ *
+ * // declare list:
+ * slt sl;
+ *
+ * // initialize:
+ * isingleListInit(&sl, -1);
+ *
+ * // push element:
+ * isingleListPush(&sl);
+ * isingleListLast(&sl) = 1;
+ *
+ * isingleListPush(&sl);
+ * isingleListLast(&sl) = 2;
+ *
+ * // head element
+ * isingleListHead(&sl) = 0;
+ *
+ * // previous node for last node
+ * u32 prev = isingleListNodePrev(isingleListLastNode(&sl));
+ * u32 prev2 = isingleListLastNode(&sl).prev;
+ * u32 prev3 = isingleListLastPrevIdx(&sl);
+ * u32 prev4 = isingleListPrevIdx(&sl, isingleListLastIdx(&sl));
+ * isingleListNode (&sl, prev).elem = 4;
+ * isingleListPrevAt(&sl, sl.last).elem = 4;
+ *
+ * // pointer to node
+ * isingleListNodeType(&sl) pointer = isingleListPtr(&sl, sl.head);
+ *
+ * // Pop/delLast element:
+ * isingleListPop(&sl);
+ *
+ * // free list
+ * isingleListFree(&sl);
+ */
+
+#include "libsheepyObject.h"
+
+/**
+ * list and node definition
+ *
+ * indexType is the type for storing the single node indexes (size_t, u32, ...)
+ */
+#define isingleListT(typeName, indexType, elementType)\
+ /* node type */\
+ typ struct UNIQVAR(nodet) UNIQVAR(nodet);\
+ struct UNIQVAR(nodet) {\
+ elementType elem;\
+ indexType prev;\
+ };\
+ /* dArray storing the nodes */\
+ dArrayT(UNIQVAR(aNodet), UNIQVAR(nodet));\
+ /* free node list */\
+ dArrayT(UNIQVAR(freeaNodet), indexType);\
+ typ struct {\
+ indexType head; /* first node */\
+ indexType last; /* last node */\
+ indexType null; /* null value for index */\
+ UNIQVAR(aNodet) list; /* node dArray */\
+ UNIQVAR(freeaNodet) freeList; /* free node dArray */\
+ size_t count; /* node count */\
+ } typeName
+
+/**
+ * initialize list
+ *
+ * \param
+ * nullValue -1 or NULL value for indexType
+ * \return
+ * true success, false failed
+ */
+#define isingleListInit(name, nullValue) ({\
+ (name)->head = nullValue;\
+ (name)->last = nullValue;\
+ (name)->null = nullValue;\
+ dArrayInit(&(name)->list);\
+ dArrayInit(&(name)->freeList);\
+ (name)->count = 0;\
+ true;\
+ })
+
+/**
+ * free list
+ * free and reset internal structures
+ */
+#define isingleListFree(name) do{\
+ dArrayFree(&(name)->list);\
+ dArrayFree(&(name)->freeList);\
+ (name)->head = (name)->null;\
+ (name)->last = (name)->null;\
+ (name)->count = 0;\
+ } while(0)
+
+/**
+ * node type for declaring pointers to nodes
+ * */
+#define isingleListNodeType(name) dArrayElemPtrType(&(name)->list)
+
+/**
+ * is list empty
+ */
+#define isingleListIsEmpty(name) (!(name)->count)
+
+/**
+ * element count in list
+ */
+#define isingleListCount(name) (name)->count
+
+/**
+ * push element to list (only allocates node)
+ * use isingleListLast to access the element
+ *
+ * \return
+ * true success, false failed
+ */
+#define isingleListPush(name) ({\
+ /* steps:
+ * check if free node is empty
+ * free list is empty, add a new node
+ * create first node
+ * or link to previous node
+ * reuse a free node
+ * create first node
+ * or link to previous node
+ */\
+ if (dArrayIsEmpty(&(name)->freeList)) {\
+ /* free list is empty, add a new node */\
+ dArrayPush(&(name)->list);\
+ if (isingleListIsEmpty(name)) {\
+ /* first node */\
+ dArrayLast(&(name)->list).prev = (name)->null;\
+ (name)->head = (name)->last = dArrayLastIndex(&(name)->list);\
+ }\
+ else {\
+ /* link to previous node */\
+ dArrayLast(&(name)->list).prev = (name)->last;\
+ (name)->last = dArrayLastIndex(&(name)->list);\
+ }\
+ }\
+ else {\
+ /* reuse a free node */\
+ if (isingleListIsEmpty(name)) {\
+ /* first node */\
+ dArrayAt(&(name)->list, dArrayLast(&(name)->freeList)).prev = (name)->null;\
+ (name)->head = (name)->last = dArrayLast(&(name)->freeList);\
+ }\
+ else {\
+ /* link to previous node */\
+ dArrayAt(&(name)->list, dArrayLast(&(name)->freeList)).prev = (name)->last;\
+ (name)->last = dArrayLast(&(name)->freeList);\
+ }\
+ dArrayDelLast(&(name)->freeList);\
+ }\
+ (name)->count++;\
+ true;\
+ })
+
+/**
+ * pop element from list (only free node)
+ *
+ * \return
+ * true success, false failed: the list is empty
+ */
+#define isingleListPop(name) ({\
+ bool UNIQVAR(res) = true;\
+ if (isingleListIsEmpty(name)) {\
+ /* the list is empty */\
+ UNIQVAR(res) = false;\
+ goto UNIQVAR(ret);\
+ }\
+ /* free last node */\
+ dArrayAppend(&(name)->freeList, (name)->last);\
+ /* previous node becomes last node */\
+ (name)->last = dArrayAt(&(name)->list, (name)->last).prev;\
+ if ((name)->count == 1) /* the list is empty, head is gone */ (name)->head = (name)->null;\
+ (name)->count--;\
+ UNIQVAR(ret):\
+ UNIQVAR(res);\
+ })
+
+#define isingleListDelLast isingleListPop
+
+/**
+ * unlink previous node (use pop or unlinkLast to unlink the last node)
+ *
+ * nodeIndex must be of type indexType
+ *
+ * the node can be freed with isingleListFreeUnlinked or
+ * inserted in the list with isingleListInsertBefore or isingleListInsertLast
+ *
+ * \return
+ * unlinked node index
+ * null index when the list is empty or when nodeIndex is head
+ */
+#define isingleListUnlinkPrev(name, nodeIndex) ({\
+ typeof((name)->null) UNIQVAR(nodeIdx) = nodeIndex;\
+ var UNIQVAR(res) = (name)->null;\
+ if (isingleListIsEmpty(name)) /* list is empty*/ goto UNIQVAR(ret);\
+ if (UNIQVAR(nodeIdx) == (name)->head) {\
+ /* node is head, there is no previous node */\
+ goto UNIQVAR(ret);\
+ }\
+ /* the unlinked node is prev */\
+ UNIQVAR(res) = dArrayAt(&(name)->list, UNIQVAR(nodeIdx)).prev;\
+ if (UNIQVAR(res) == (name)->head) {\
+ /* prev node is head, so nodeIndex is now head and update head */\
+ (name)->head = UNIQVAR(nodeIdx);\
+ dArrayAt(&(name)->list, UNIQVAR(nodeIdx)).prev = (name)->null;\
+ }\
+ else {\
+ /* link previous previous node to node at nodeIndex */\
+ dArrayAt(&(name)->list, UNIQVAR(nodeIdx)).prev = dArrayAt(&(name)->list, UNIQVAR(res)).prev;\
+ }\
+ (name)->count--;\
+ UNIQVAR(ret):\
+ UNIQVAR(res);\
+ })
+
+#define isingleListUnlinkBefore isingleListUnlinkPrev
+
+/**
+ * unlink last node
+ *
+ * the node can be freed with isingleListFreeUnlinked or
+ * inserted in the list with isingleListInsertBefore or isingleListInsertLast
+ *
+ * \return
+ * unlinked node index
+ * null index when the list is empty
+ */
+#define isingleListUnlinkLast(name) ({\
+ var UNIQVAR(res) = (name)->null;\
+ if (isingleListIsEmpty(name)) /* list is empty*/ goto UNIQVAR(ret);\
+ /* last is unlinked */\
+ UNIQVAR(res) = (name)->last;\
+ /* previous node is now last */\
+ (name)->last = isingleListLastPrevIdx(name);\
+ (name)->count--;\
+ /* if the list is empty set head to null */\
+ if (isingleListIsEmpty(name)) (name)->head = (name)->null;\
+ UNIQVAR(ret):\
+ UNIQVAR(res);\
+ })
+
+/**
+ * free unlinked node
+ *
+ * nodeIndex must be of type indexType
+ */
+#define isingleListFreeUnlinked(name, nodeIndex) dArrayAppend(&(name)->freeList, nodeIndex)
+
+/**
+ * delete node
+ *
+ * nodeIndex must be of type indexType
+ *
+ * unlink and free node
+ */
+#define isingleListDelPrev(name, nodeIndex) ({\
+ var UNIQVAR(prev) = isingleListUnlinkPrev(name, nodeIndex);\
+ isingleListFreeUnlinked(name, UNIQVAR(prev));\
+ true;\
+ })
+
+#define isingleListDelBefore isingleListDelPrev
+
+
+
+
+
+/** first element */
+#define isingleListFirst(name) dArrayAt(&(name)->list, (name)->head).elem
+#define isingleListHead isingleListFirst
+
+/** first previous node index (always null) */
+#define isingleListFirstPrevIdx(name) dArrayAt(&(name)->list, (name)->head).prev
+#define isingleListHeadPrev isingleListFirstPrev
+
+/** first node */
+#define isingleListFirstNode(name) dArrayAt(&(name)->list, (name)->head)
+#define isingleListHeadNode isingleListFirstNode
+
+/** first index */
+#define isingleListFirstIdx(name) (name)->head
+#define isingleListHeadIdx isingleListFirstIdx
+
+/** first node pointer */
+#define isingleListFirstPtr(name) dArrayPtr(&(name)->list, (name)->head)
+#define isingleListHeadPtr isingleListFirstPtr
+
+/** last element */
+#define isingleListLast(name) dArrayAt(&(name)->list, (name)->last).elem
+
+/** last previous node index */
+#define isingleListLastPrevIdx(name) dArrayAt(&(name)->list, (name)->last).prev
+
+/** last node */
+#define isingleListLastNode(name) dArrayAt(&(name)->list, (name)->last)
+
+/** last index */
+#define isingleListLastIdx(name) (name)->last
+
+/** last node pointer */
+#define isingleListLastPtr(name) dArrayPtr(&(name)->list, (name)->last)
+
+/** elem at node index */
+#define isingleListElem(name, nodeIndex) dArrayAt(&(name)->list, nodeIndex).elem
+
+/** previous index */
+#define isingleListPrevIdx(name, nodeIndex) dArrayAt(&(name)->list, nodeIndex).prev
+
+/** node at index */
+#define isingleListNode(name, nodeIndex) dArrayAt(&(name)->list, nodeIndex)
+
+/** node pointer at index */
+#define isingleListPtr(name, nodeIndex) dArrayPtr(&(name)->list, nodeIndex)
+
+/** node element (or use node.elem) */
+#define isingleListNodeElem(node) (node).elem
+
+/** previous index in node */
+#define isingleListNodePrev(node) (node).prev
+
+/** node element (or use node.elem) */
+#define isingleListNodePtrElem(node) (node)->elem
+
+/** previous index in node */
+#define isingleListNodePtrPrev(node) (node)->prev
+
+/** previous node at index, index must not be equal to head */
+#define isingleListPrevAt(name, nodeIndex) dArrayAt(&(name)->list, isingleListPrevIdx(name, nodeIndex))
+
+/** previous node */
+#define isingleListPrev(name, node) dArrayAt(&(name)->list, (node).prev)
+
+/** previous node pointer */
+#define isingleListPrevPtr(name, nodePtr) ({\
+ dArrayElemPtrType(&(name)->list) UNIQVAR(res) = NULL;\
+ if ((nodePtr)->prev != (name)->null) {\
+ UNIQVAR(res) = dArrayPtr(&(name)->list, (nodePtr)->prev);\
+ }\
+ UNIQVAR(res);\
+ })
+
+
+
+
+
+
+
+/** loop on indexes from last to head, to access the element use isingleListElem */
+#define isingleListForEachDown(name, index)\
+ for(var index = isingleListLastIdx(name); index != (name)->null ; index = isingleListPrevIdx(name, index))
+
+/** loop node pointers from last to head, to access the elment use isingleListNodePtrElem(node) or (node)->elem */
+#define isingleListForEachNodeDown(name, node)\
+ for(var node = isingleListLastPtr(name); node != NULL ; node = isingleListPrevPtr(name, node))
+
+/** loop element from last to head (the element data is copied) */
+#define isingleListForEachElemDown(name, element)\
+ var UNIQVAR(idx) = isingleListLastIdx(name);\
+ for(var element = isingleListLast(name); UNIQVAR(idx) != (name)->null ; UNIQVAR(idx) = isingleListPrevIdx(name, UNIQVAR(idx)), element = (UNIQVAR(idx) != (name)->null) ? isingleListElem(name, UNIQVAR(idx)) : element)
+
+/** loop element pointers from last to head, use *elemPtr to access the element data */
+#define isingleListForEachElemPDown(name, elemPtr)\
+ var UNIQVAR(idx) = isingleListLastIdx(name);\
+ for(var elemPtr = &isingleListLast(name); UNIQVAR(idx) != (name)->null ; UNIQVAR(idx) = isingleListPrevIdx(name, UNIQVAR(idx)), elemPtr = (UNIQVAR(idx) != (name)->null) ? &isingleListElem(name, UNIQVAR(idx)) : elemPtr)
+
+/** loop on indexes from startIndex to head, to access the element use isingleListElem */
+#define isingleListForEachFromDown(name, index, startIndex)\
+ for(typeof((name)->null) index = startIndex; index != (name)->null ; index = isingleListPrevIdx(name, index))
+
+/** loop node pointers from startNode to head, to access the elment use isingleListNodePtrElem(node) or (node)->elem */
+#define isingleListForEachNodeFromDown(name, node, startNode)\
+ for(isingleListNodeType(name) node = startNode; node != NULL ; node = isingleListPrevPtr(name, node))
+
+/** loop element from startIndex to head (the element data is copied) */
+#define isingleListForEachElemFromDown(name, element, startIndex)\
+ typeof((name)->null) UNIQVAR(idx) = startIndex;\
+ for(var element = isingleListLast(name); UNIQVAR(idx) != (name)->null ; UNIQVAR(idx) = isingleListPrevIdx(name, UNIQVAR(idx)), element = (UNIQVAR(idx) != (name)->null) ? isingleListElem(name, UNIQVAR(idx)) : element)
+
+/** loop element pointers from startIndex to head, use *elemPtr to access the element data */
+#define isingleListForEachElemPFromDown(name, elemPtr, startIndex)\
+ typeof((name)->null) UNIQVAR(idx) = startIndex;\
+ for(var elemPtr = &isingleListLast(name); UNIQVAR(idx) != (name)->null ; UNIQVAR(idx) = isingleListPrevIdx(name, UNIQVAR(idx)), elemPtr = (UNIQVAR(idx) != (name)->null) ? &isingleListElem(name, UNIQVAR(idx)) : elemPtr)
+
+
+
+
+
+
+/**
+ * insert nodeToInsert index before referenceNode index
+ */
+#define isingleListInsertBefore(name, referenceNodeIndex, nodeToInsertIndex) do{\
+ typeof((name)->null) UNIQVAR(referenceNodeIdx) = referenceNodeIndex;\
+ typeof((name)->null) UNIQVAR(nodeToInsertIdx) = nodeToInsertIndex;\
+ /* save previous node index */\
+ var UNIQVAR(tmp) = isingleListPrevIdx(name, UNIQVAR(referenceNodeIdx));\
+ /* previous node in now nodeToInsert */\
+ isingleListPrevIdx(name, UNIQVAR(referenceNodeIdx)) = UNIQVAR(nodeToInsertIdx);\
+ /* connect rest of the list to nodeToInsert */\
+ isingleListPrevIdx(name, UNIQVAR(nodeToInsertIdx)) = UNIQVAR(tmp);\
+ if (UNIQVAR(tmp) == (name)->null) /* referenceNode was head node */ (name)->head = UNIQVAR(nodeToInsertIdx);\
+ (name)->count++;\
+ } while(0)
+
+#define isingleListInsertPrev isingleListInsertBefore
+
+/**
+ * insert nodeToInsert index last
+ */
+#define isingleListInsertLast(name, nodeToInsertIndex) do{\
+ typeof((name)->null) UNIQVAR(nodeToInsertIdx) = nodeToInsertIndex;\
+ if (isingleListIsEmpty(name)) {\
+ /* list is empty, previous node is null and set both head and last */\
+ isingleListPrevIdx(name, UNIQVAR(nodeToInsertIdx)) = (name)->null;\
+ (name)->head = (name)->last = UNIQVAR(nodeToInsertIdx);\
+ }\
+ else {\
+ /* last node is previous node for nodeToInsert */\
+ isingleListPrevIdx(name, UNIQVAR(nodeToInsertIdx)) = (name)->last;\
+ /* now last is nodeToInsert */\
+ (name)->last = UNIQVAR(nodeToInsertIdx);\
+ }\
+ (name)->count++;\
+ } while(0)
+
+// // NO - cant insert before and after last
+// #define isingleListInsert(name, referenceNodeIndex, nodeToInsertIndex) do{\
+// typeof((name)->null) UNIQVAR(refNodeIdx) = referenceNodeIndex;\
+// if (UNIQVAR(refNodeIdx) != (name)->last) isingleListInsertBefore(name, UNIQVAR(refNodeIdx), nodeToInsertIndex);\
+// else isingleListInsertLast(name, nodeToInsertIndex);\
+// } while(0)
+
+
+// Internal
+// allocate a node
+#define isingleListAddNode(name) ({\
+ typeof((name)->null) UNIQVAR(res) = (name)->null;\
+ if (dArrayIsEmpty(&(name)->freeList)) {\
+ /* create new node */\
+ dArrayPush(&(name)->list);\
+ UNIQVAR(res) = dArrayLastIndex(&(name)->list);\
+ }\
+ else {\
+ /* reuse a free node */\
+ UNIQVAR(res) = dArrayLast(&(name)->freeList);\
+ dArrayDelLast(&(name)->freeList);\
+ }\
+ UNIQVAR(res);\
+ })
+
+/**
+ * add new node before referenceNode index
+ *
+ * \return
+ * resultNode index: access element in node with isingleListElem(name, resultNode)
+ */
+#define isingleListAddBefore(name, referenceNodeIndex) ({\
+ typeof((name)->null) UNIQVAR(res) = isingleListAddNode(name);\
+ isingleListInsertBefore(name, referenceNodeIndex, UNIQVAR(res));\
+ UNIQVAR(res);\
+ })
+
+#define isingleListAddPrev isingleListAddBefore
+
+/** add new node index after last
+ *
+ * \return
+ * resultNode new node index after last (new last node)
+ */
+#define isingleListAddLast(name) ({\
+ typeof((name)->null) UNIQVAR(res) = isingleListAddNode(name);\
+ isingleListInsertLast(name, UNIQVAR(res));\
+ UNIQVAR(res);\
+ })
+
+// // NO - cant insert before and after last
+// #define isingleListAdd(name, referenceNodeIndex) ({\
+// typeof((name)->null) UNIQVAR(res) = isingleListAddNode(name);\
+// isingleListInsert(name, referenceNodeIndex, UNIQVAR(res));\
+// UNIQVAR(res);\
+// })
+
+
+
+
+
+/**
+ * write the isingleList content to filename file
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * filename file name string
+ */
+#define isingleListWriteFilename(name, filename) do {\
+ FILE *UNIQVAR(f) = fopen(filename, "w");\
+ if (UNIQVAR(f)) {\
+ isingleListForEachDown(name, UNIQVAR(i)) {\
+ fwrite(&isingleListElem(name, UNIQVAR(i)), 1, sizeof(isingleListElem(name, 0)), UNIQVAR(f));\
+ }\
+ fclose(UNIQVAR(f));\
+ }\
+ } while(0)
+
+/**
+ * write the isingleList content to disk
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * file already opened file
+ */
+#define isingleListWrite(name, file) do {\
+ isingleListForEachDown(name, UNIQVAR(i)) {\
+ fwrite(&isingleListElem(name, UNIQVAR(i)), 1, sizeof(isingleListElem(name, 0)), file);\
+ }\
+ } while(0)
+
+/**
+ * read a isingleList from filename file
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * filename file name string
+ */
+#define isingleListReadFilename(name, filename) do {\
+ if (fileExists(filename)) {\
+ size_t UNIQVAR(sz) = fileSize(filename);\
+ const size_t UNIQVAR(elemSz) = sizeof(isingleListElem(name, 0));\
+ if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
+ UNIQVAR(sz) /= UNIQVAR(elemSz);\
+ if (!UNIQVAR(sz)) /* there is no element to load*/ break;\
+ FILE *UNIQVAR(f) = fopen(filename, "r");\
+ if (UNIQVAR(f)) {\
+ isingleListPush(name);\
+ fread(&isingleListLast(name), 1, UNIQVAR(elemSz), UNIQVAR(f));\
+ typeof((name)->null) UNIQVAR(insertBefore) = (name)->last;\
+ range(UNIQVAR(i), UNIQVAR(sz)-1) {\
+ UNIQVAR(insertBefore) = isingleListAddBefore(name, UNIQVAR(insertBefore));\
+ fread(&isingleListElem(name, UNIQVAR(insertBefore)), 1, UNIQVAR(elemSz), UNIQVAR(f));\
+ }\
+ fclose(UNIQVAR(f));\
+ }\
+ }\
+ } while(0)
+
+/**
+ * read a isingleList from disk
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * file already opened file
+ */
+#define isingleListRead(name, file) do {\
+ fseek(file, 0 , SEEK_END);\
+ size_t UNIQVAR(sz) = ftell(file);\
+ fseek(file, 0 , SEEK_SET);\
+ const size_t UNIQVAR(elemSz) = sizeof(isingleListElem(name, 0));\
+ if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
+ UNIQVAR(sz) /= UNIQVAR(elemSz);\
+ if (!UNIQVAR(sz)) /* there is no element to load*/ break;\
+ isingleListPush(name);\
+ fread(&isingleListLast(name), 1, UNIQVAR(elemSz), file);\
+ typeof((name)->null) UNIQVAR(insertBefore) = (name)->last;\
+ range(UNIQVAR(i), UNIQVAR(sz)-1) {\
+ UNIQVAR(insertBefore) = isingleListAddBefore(name, UNIQVAR(insertBefore));\
+ fread(&isingleListElem(name, UNIQVAR(insertBefore)), 1, UNIQVAR(elemSz), file);\
+ }\
+ } while(0)
+
+// vim: set expandtab ts=2 sw=2:
diff --git a/main.c b/main.c
@@ -0,0 +1,382 @@
+#! /usr/bin/env sheepy
+/* or direct path to sheepy: #! /usr/local/bin/sheepy */
+
+/* Libsheepy documentation: http://spartatek.se/libsheepy/ */
+#include "libsheepyObject.h"
+#include "isingleList.h"
+#include "singleList.h"
+#include "singleListe.h"
+
+int argc; char **argv;
+
+/* enable/disable logging */
+/* #undef pLog */
+/* #define pLog(...) */
+
+
+int main(int ARGC, char** ARGV) {
+
+ argc = ARGC; argv = ARGV;
+
+ initLibsheepy(ARGV[0]);
+ setLogMode(LOG_FUNC);
+
+ // define list:
+ isingleListT(slt, u8, char*);
+
+ // declare list:
+ slt sl;
+
+ logVarG(sizeof sl);
+
+ // initialize:
+ isingleListInit(&sl, -1);
+
+ logVarG(isingleListHeadIdx(&sl));
+ logVarG(isingleListLastIdx(&sl));
+
+ isingleListNodeType(&sl) sE;
+
+ logI("isEmpty %b", isingleListIsEmpty(&sl));
+ logI("count %zu", isingleListCount(&sl));
+ logI("push %b", isingleListPush(&sl));
+ logI("count %zu", isingleListCount(&sl));
+ logVarG(sl.last);
+ isingleListFirst(&sl) = "qwe";
+ logVarG(isingleListLast(&sl));
+ isingleListLastNode(&sl).elem = "QWER";
+ logVarG(isingleListElem(&sl, 0));
+ logVarG(isingleListNode(&sl, 0).elem);
+ logVarG(isingleListPrevIdx(&sl, 0));
+ logI("push %b", isingleListPush(&sl));
+ logI("count %zu", isingleListCount(&sl));
+ logVarG(sl.last);
+ isingleListLast(&sl) = "22 qwe";
+ logVarG(isingleListLastPrevIdx(&sl));
+ logVarG(isingleListPrevAt(&sl, isingleListLastIdx(&sl)).elem);
+ logVarG(isingleListPrev(&sl, isingleListLastNode(&sl)).elem);
+ logI("push %b", isingleListPush(&sl));
+ logI("count %zu", isingleListCount(&sl));
+ logVarG(sl.last);
+ isingleListLast(&sl) = "qwe33333";
+ isingleListForEachDown(&sl, i) {
+ logI("elem: %s", isingleListElem(&sl, i));
+ }
+ isingleListForEachNodeDown(&sl, node) {
+ logI("elem: %s", node->elem);
+ }
+ isingleListForEachElemDown(&sl, i) {
+ logI("elem: %s", i);
+ }
+ isingleListForEachElemPDown(&sl, i) {
+ logI("elem: %s", *i);
+ }
+ logI("count %zu", isingleListCount(&sl));
+ var u = isingleListUnlinkPrev(&sl, sl.last);
+ //var u = isingleListUnlinkLast(&sl);
+ logI("count %zu", isingleListCount(&sl));
+ AT;
+ //isingleListInsertBefore(&sl, sl.head, u);
+ isingleListInsertLast(&sl, u);
+ var add = isingleListAddBefore(&sl, sl.head);
+ isingleListFirst(&sl) = "4444 add qwe";
+ isingleListForEachElemPDown(&sl, i) {
+ logI("elem: %s", *i);
+ }
+ isingleListPrevPtr(&sl, isingleListLastPtr(&sl))->elem = "zxcxc";
+ logI("count %zu", isingleListCount(&sl));
+ var idx = isingleListDelPrev(&sl, 2);
+ logVarG(idx);
+ logI("count %zu", isingleListCount(&sl));
+ logVarG(sl.last);
+ logI("pop %b", isingleListPop(&sl));
+ logI("count %zu", isingleListCount(&sl));
+ logVarG(sl.last);
+ logI("pop %b", isingleListPop(&sl));
+ logI("count %zu", isingleListCount(&sl));
+ logVarG(sl.last);
+ logI("pop %b", isingleListPop(&sl));
+ logI("count %zu", isingleListCount(&sl));
+ logVarG(sl.last);
+ isingleListFree(&sl);
+
+ // read/write list
+ // define list:
+ isingleListT(sllt, u8, u8);
+
+ // declare list:
+ sllt sll;
+
+ // initialize:
+ isingleListInit(&sll, -1);
+
+ isingleListPush(&sll);
+ //isingleListFirst(&sll) = 1;
+ isingleListLast(&sll) = 1;
+
+ //isingleListAddBefore(&sll, sll.head);
+ isingleListPush(&sll);
+ //isingleListFirst(&sll) = 2;
+ isingleListLast(&sll) = 2;
+ //isingleListAddBefore(&sll, sll.head);
+ isingleListPush(&sll);
+ //isingleListFirst(&sll) = 3;
+ isingleListLast(&sll) = 3;
+ isingleListForEachDown(&sll, i) {
+ logI("uint elem: %d", isingleListElem(&sll, i));
+ }
+ put;
+ isingleListWriteFilename(&sll, "slist.dat");
+
+ isingleListPush(&sll);
+ isingleListLast(&sll) = 222;
+ isingleListPush(&sll);
+ isingleListLast(&sll) = 33;
+ isingleListFirst(&sll) = 0;
+
+ isingleListReadFilename(&sll, "slist.dat");
+
+ isingleListForEachDown(&sll, i) {
+ logI("uint elem: %d", isingleListElem(&sll, i));
+ }
+
+ isingleListFree(&sll);
+
+
+ void s(void) {
+
+ // define list:
+ singleListT(slt, char*);
+
+ // declare list:
+ slt sl;
+
+ logVarG(sizeof sl);
+
+ // initialize:
+ singleListInit(&sl);
+
+ singleListNodeType(&sl) sE;
+
+ logI("isEmpty %b", singleListIsEmpty(&sl));
+ logI("count %zu", singleListCount(&sl));
+ logI("push %b", singleListPush(&sl));
+ logI("count %zu", singleListCount(&sl));
+ singleListFirst(&sl) = "qwe";
+ logVarG(singleListLast(&sl));
+ singleListLastNode(&sl)->elem = "QWER";
+ logVarG(singleListElem(sl.head));
+ logVarG(sl.head->prev);
+ logI("push %b", singleListPush(&sl));
+ logI("count %zu", singleListCount(&sl));
+ singleListLast(&sl) = "22 qwe";
+ logVarG(sl.last->elem);
+ logVarG(sl.last->prev->elem);
+ logI("push %b", singleListPush(&sl));
+ logI("count %zu", singleListCount(&sl));
+ singleListLast(&sl) = "qwe33333";
+ singleListForEachDown(&sl, node) {
+ logI("elem: %s", node->elem);
+ }
+ singleListForEachElemDown(&sl, i) {
+ logI("elem: %s", i);
+ }
+ singleListForEachElemPDown(&sl, i) {
+ logI("elem: %s", *i);
+ }
+ logI("count %zu", singleListCount(&sl));
+ var u = singleListUnlinkPrev(&sl, sl.last);
+ //var u = singleListUnlinkLast(&sl);
+ logI("count %zu", singleListCount(&sl));
+ AT;
+ //singleListInsertBefore(&sl, sl.head, u);
+ singleListInsertLast(&sl, u);
+ var add = singleListAddBefore(&sl, sl.head);
+ singleListFirst(&sl) = "4444 add qwe";
+ singleListForEachElemPDown(&sl, i) {
+ logI("elem: %s", *i);
+ }
+ logI("count %zu", singleListCount(&sl));
+ var idx = singleListDelPrev(&sl, sl.last);
+ logI("count %zu", singleListCount(&sl));
+ logI("pop %b", singleListPop(&sl));
+ logI("count %zu", singleListCount(&sl));
+ logI("pop %b", singleListPop(&sl));
+ logI("count %zu", singleListCount(&sl));
+ logI("pop %b", singleListPop(&sl));
+ logI("count %zu", singleListCount(&sl));
+ singleListFree(&sl);
+
+ // read/write list
+ // define list:
+ singleListT(sllt, u8);
+
+ // declare list:
+ sllt sll;
+
+ // initialize:
+ singleListInit(&sll);
+
+ singleListPush(&sll);
+ //singleListFirst(&sll) = 1;
+ singleListLast(&sll) = 1;
+
+ //singleListAddBefore(&sll, sll.head);
+ singleListPush(&sll);
+ //singleListFirst(&sll) = 2;
+ singleListLast(&sll) = 2;
+ //singleListAddBefore(&sll, sll.head);
+ singleListPush(&sll);
+ //singleListFirst(&sll) = 3;
+ singleListLast(&sll) = 3;
+ singleListForEachDown(&sll, i) {
+ logI("uint elem: %d", singleListElem(i));
+ }
+ put;
+ singleListWriteFilename(&sll, "slist.dat");
+
+ singleListPush(&sll);
+ singleListLast(&sll) = 222;
+ singleListPush(&sll);
+ singleListLast(&sll) = 33;
+ singleListFirst(&sll) = 0;
+
+ singleListReadFilename(&sll, "slist.dat");
+
+ singleListForEachDown(&sll, i) {
+ logI("uint elem: %d", singleListElem(i));
+ }
+
+ singleListFree(&sll);
+ }
+
+ s();
+
+
+ void se(void) {
+
+ // define list:
+ singleListeT(slt, char*);
+
+ // declare list:
+ slt sl;
+
+ singleListeNodesT(&sl) da;
+ singleListeFreeNodesT(&sl) fre;
+
+ singleListeStoreInit(&da, &fre);
+
+ logVarG(sizeof sl);
+
+ // initialize:
+ singleListeInit(&sl, &da, &fre);
+
+ singleListeNodeType(&sl) sE;
+
+ logI("isEmpty %b", singleListeIsEmpty(&sl));
+ logI("count %zu", singleListeCount(&sl));
+ logI("push %b", singleListePush(&sl));
+ logI("count %zu", singleListeCount(&sl));
+ singleListeFirst(&sl) = "qwe";
+ logVarG(singleListeLast(&sl));
+ singleListeLastNode(&sl)->elem = "QWER";
+ logVarG(singleListeElem(sl.head));
+ logVarG(sl.head->prev);
+ logI("push %b", singleListePush(&sl));
+ logI("count %zu", singleListeCount(&sl));
+ singleListeLast(&sl) = "22 qwe";
+ logVarG(sl.last->elem);
+ logVarG(sl.last->prev->elem);
+ logI("push %b", singleListePush(&sl));
+ logI("count %zu", singleListeCount(&sl));
+ singleListeLast(&sl) = "qwe33333";
+ singleListeForEachDown(&sl, node) {
+ logI("elem: %s", node->elem);
+ }
+ singleListeForEachElemDown(&sl, i) {
+ logI("elem: %s", i);
+ }
+ singleListeForEachElemPDown(&sl, i) {
+ logI("elem: %s", *i);
+ }
+ logI("count %zu", singleListeCount(&sl));
+ var u = singleListeUnlinkPrev(&sl, sl.last);
+ //var u = singleListeUnlinkLast(&sl);
+ logI("count %zu", singleListeCount(&sl));
+ AT;
+ //singleListeInsertBefore(&sl, sl.head, u);
+ singleListeInsertLast(&sl, u);
+ var add = singleListeAddBefore(&sl, sl.head);
+ singleListeFirst(&sl) = "4444 add qwe";
+ singleListeForEachElemPDown(&sl, i) {
+ logI("elem: %s", *i);
+ }
+ logI("count %zu", singleListeCount(&sl));
+ var idx = singleListeDelPrev(&sl, sl.last);
+ logI("count %zu", singleListeCount(&sl));
+ logI("pop %b", singleListePop(&sl));
+ logI("count %zu", singleListeCount(&sl));
+ logI("pop %b", singleListePop(&sl));
+ logI("count %zu", singleListeCount(&sl));
+ logI("pop %b", singleListePop(&sl));
+ logI("count %zu", singleListeCount(&sl));
+ singleListeFree(&sl);
+
+ singleListeStoreFree(&da, &fre);
+
+ // read/write list
+ // define list:
+ singleListeT(sllt, u8);
+
+ // declare list:
+ sllt sll;
+
+ singleListeNodesPtrT(&sll) da8;
+ singleListeFreeNodesPtrT(&sll) fre8;
+
+ da8 = malloc(sizeof(singleListeNodesT(&sll)));
+ fre8 = malloc(sizeof(singleListeFreeNodesT(&sll)));
+
+ singleListeStoreInit(da8, fre8);
+
+ // initialize:
+ singleListeInit(&sll, da8, fre8);
+
+ singleListePush(&sll);
+ //singleListeFirst(&sll) = 1;
+ singleListeLast(&sll) = 1;
+
+ //singleListeAddBefore(&sll, sll.head);
+ singleListePush(&sll);
+ //singleListeFirst(&sll) = 2;
+ singleListeLast(&sll) = 2;
+ //singleListeAddBefore(&sll, sll.head);
+ singleListePush(&sll);
+ //singleListeFirst(&sll) = 3;
+ singleListeLast(&sll) = 3;
+ singleListeForEachDown(&sll, i) {
+ logI("uint elem: %d", singleListeElem(i));
+ }
+ put;
+ singleListeWriteFilename(&sll, "slist.dat");
+
+ singleListePush(&sll);
+ singleListeLast(&sll) = 222;
+ singleListePush(&sll);
+ singleListeLast(&sll) = 33;
+ singleListeFirst(&sll) = 0;
+
+ singleListeReadFilename(&sll, "slist.dat");
+
+ singleListeForEachDown(&sll, i) {
+ logI("uint elem: %d", singleListeElem(i));
+ }
+
+ singleListeFree(&sll);
+
+ singleListeStoreFree(da8, fre8);
+ }
+
+ se();
+}
+// vim: set expandtab ts=2 sw=2:
diff --git a/package.yml b/package.yml
@@ -0,0 +1,32 @@
+---
+ name: singleList
+ version: 0.0.1
+ description: "single linked lists"
+ bin: ./singleList.h
+ #cflags: -DA -ggdb -std=gnu11 -fPIC -pipe
+ #lflags: -lpcre
+ repository:
+ type: git
+ url: git+https://github.com/RemyNoulin/singleList.git
+ keywords:
+ - data structure
+ # - command
+ author: Remy Noulin
+ license: MIT
+ bugs:
+ url: https://github.com/RemyNoulin/singleList/issues
+ homepage: https://github.com/RemyNoulin/singleList#readme
+ #compileHelp: # text displayed when there is a compilation error
+ #dependencies:
+ # md4c:
+ # Test configuration:
+ #testBin: ./testSingleList.c
+ #testCflags: -ggdb -std=gnu11 -fPIC -pipe -fprofile-arcs -ftest-coverage -Wall -Wextra
+ #testLflags: -lcheck_pic -lrt -lm -lsubunit -fprofile-arcs -ftest-coverage -rdynamic
+ # Memcheck configuration:
+ #memcheckBin: ./memcheckSingleList.c
+ #memcheckCmd: valgrind --leak-check=full --show-leak-kinds=all
+ #memcheckCflags: -ggdb -std=gnu11 -fPIC -pipe
+ #memcheckLflags: -rdynamic
+ #documentationCmd: # command for generating the documentation with spm doc
+ private: false # true for private package
diff --git a/singleList.h b/singleList.h
@@ -0,0 +1,544 @@
+
+
+/**
+ * \file
+ *
+ * Single linked list: singleList
+ *
+ * head 1 <- 2 <- 3 last
+ *
+ * The single linked list can be used as a stack and is not efficient when used as a queue.
+ *
+ * The nodes in singleList are linked with pointers and dynamically allocated in segments
+ *
+ * NOTE: The macros in this file are for creating list functions wrapping the macros.
+ *
+ * The element type handled by the list is defined with singleListT
+ *
+ * The nodes have 2 members: .elem and .prev, .elem is the element data and .prev is the index of the previous node
+ *
+ * use push and pop to stack nodes
+ *
+ * The forEach macros loop on nodes or elements from last node to head node
+ *
+ * use unlinkPrev or unlinkBefore and unlinkLast to unlink nodes anywhere in the list
+ *
+ * use insertBefore, addBefore to insert anywhere in the list, before head and push, insertLast, addLast to insert after last
+ *
+ * use freeUnlinked to free unlinked nodes
+ *
+ * use singleListDelPrev or singleListDelBefore, singleListDelLast or singleListPop to delete nodes anywhere in the list
+ *
+ * To create a list in reverse order, add the first node with push and then add the nodes with addBefore head
+ *
+ * Example:
+ *
+ * // define list:
+ * singleListT(slt, u32);
+ *
+ * // declare list:
+ * slt sl;
+ *
+ * // initialize:
+ * singleListInit(&sl);
+ *
+ * // push element:
+ * singleListPush(&sl);
+ * singleListLast(&sl) = 1;
+ * sl.last->elem = 1;
+ *
+ * singleListPush(&sl);
+ * singleListLast(&sl) = 2;
+ *
+ * // head element
+ * singleListHead(&sl) = 0;
+ * sl.head->elem = 0;
+ *
+ * // previous node for last node
+ * var prev = sl.last->prev;
+ * prev->elem = 4;
+ *
+ * // pointer to node
+ * singleListNodeType(&sl) pointer = singleListHeadNode(&sl);
+ *
+ * // Pop/delLast element:
+ * singleListPop(&sl);
+ *
+ * // free list
+ * singleListFree(&sl);
+ */
+
+#include "libsheepyObject.h"
+
+/**
+ * list and node definition
+ */
+#define singleListT(typeName, elementType)\
+ /* node type */\
+ typ struct UNIQVAR(nodet) UNIQVAR(nodet);\
+ struct UNIQVAR(nodet) {\
+ elementType elem;\
+ UNIQVAR(nodet) *prev;\
+ };\
+ /* dArray storing the nodes */\
+ dArrayT(UNIQVAR(aNodet), UNIQVAR(nodet));\
+ /* free node list */\
+ dArrayT(UNIQVAR(freeaNodet), UNIQVAR(nodet)*);\
+ typ struct {\
+ UNIQVAR(nodet) *head; /* first node */\
+ UNIQVAR(nodet) *last; /* last node */\
+ UNIQVAR(aNodet) list; /* node dArray */\
+ UNIQVAR(freeaNodet) freeList; /* free node dArray */\
+ size_t count; /* node count */\
+ } typeName
+
+/**
+ * initialize list
+ *
+ * \return
+ * true success, false failed
+ */
+#define singleListInit(name) ({\
+ (name)->head = NULL;\
+ (name)->last = NULL;\
+ dArrayInit(&(name)->list);\
+ dArrayInit(&(name)->freeList);\
+ (name)->count = 0;\
+ true;\
+ })
+
+/**
+ * free list
+ * free and reset internal structures
+ */
+#define singleListFree(name) do{\
+ dArrayFree(&(name)->list);\
+ dArrayFree(&(name)->freeList);\
+ (name)->head = NULL;\
+ (name)->last = NULL;\
+ (name)->count = 0;\
+ } while(0)
+
+/**
+ * node type for declaring pointers to nodes
+ * */
+#define singleListNodeType(name) typeof((name)->head)
+
+/**
+ * is list empty
+ */
+#define singleListIsEmpty(name) (!(name)->count)
+
+/**
+ * element count in list
+ */
+#define singleListCount(name) (name)->count
+
+/**
+ * push element to list (only allocates node)
+ * use singleListLast to access the element
+ *
+ * \return
+ * true success, false failed
+ */
+#define singleListPush(name) ({\
+ /* steps:
+ * check if free node is empty
+ * free list is empty, add a new node
+ * create first node
+ * or link to previous node
+ * reuse a free node
+ * create first node
+ * or link to previous node
+ */\
+ if (dArrayIsEmpty(&(name)->freeList)) {\
+ /* free list is empty, add a new node */\
+ dArrayPush(&(name)->list);\
+ if (singleListIsEmpty(name)) {\
+ /* first node */\
+ dArrayLast(&(name)->list).prev = NULL;\
+ (name)->head = (name)->last = dArrayLastPtr(&(name)->list);\
+ }\
+ else {\
+ /* link to previous node */\
+ dArrayLast(&(name)->list).prev = (name)->last;\
+ (name)->last = dArrayLastPtr(&(name)->list);\
+ }\
+ }\
+ else {\
+ /* reuse a free node */\
+ if (singleListIsEmpty(name)) {\
+ /* first node */\
+ dArrayLast(&(name)->freeList)->prev = NULL;\
+ (name)->head = (name)->last = dArrayLast(&(name)->freeList);\
+ }\
+ else {\
+ /* link to previous node */\
+ dArrayLast(&(name)->freeList)->prev = (name)->last;\
+ (name)->last = dArrayLast(&(name)->freeList);\
+ }\
+ dArrayDelLast(&(name)->freeList);\
+ }\
+ (name)->count++;\
+ true;\
+ })
+
+/**
+ * pop element from list (only free node)
+ *
+ * \return
+ * true success, false failed: the list is empty
+ */
+#define singleListPop(name) ({\
+ bool UNIQVAR(res) = true;\
+ if (singleListIsEmpty(name)) {\
+ /* the list is empty */\
+ UNIQVAR(res) = false;\
+ goto UNIQVAR(ret);\
+ }\
+ /* free last node */\
+ dArrayAppend(&(name)->freeList, (name)->last);\
+ /* previous node becomes last node */\
+ (name)->last = (name)->last->prev;\
+ if ((name)->count == 1) /* the list is empty, head is gone */ (name)->head = NULL;\
+ (name)->count--;\
+ UNIQVAR(ret):\
+ UNIQVAR(res);\
+ })
+
+#define singleListDelLast singleListPop
+
+/**
+ * unlink previous node (use pop or unlinkLast to unlink the last node)
+ *
+ * node must be of type singleListNodeType(name)
+ *
+ * the node can be freed with singleListFreeUnlinked or
+ * inserted in the list with singleListInsertBefore or singleListInsertLast
+ *
+ * \return
+ * unlinked node index
+ * null index when the list is empty or when node is head
+ */
+#define singleListUnlinkPrev(name, node) ({\
+ singleListNodeType(name) UNIQVAR(nde) = node;\
+ singleListNodeType(name) UNIQVAR(res) = NULL;\
+ if (singleListIsEmpty(name)) /* list is empty*/ goto UNIQVAR(ret);\
+ if (UNIQVAR(nde) == (name)->head) {\
+ /* node is head, there is no previous node */\
+ goto UNIQVAR(ret);\
+ }\
+ /* the unlinked node is prev */\
+ UNIQVAR(res) = UNIQVAR(nde)->prev;\
+ if (UNIQVAR(res) == (name)->head) {\
+ /* prev node is head, so node is now head and update head */\
+ (name)->head = UNIQVAR(nde);\
+ UNIQVAR(nde)->prev = NULL;\
+ }\
+ else {\
+ /* link previous previous node to node */\
+ UNIQVAR(nde)->prev = UNIQVAR(res)->prev;\
+ }\
+ (name)->count--;\
+ UNIQVAR(ret):\
+ UNIQVAR(res);\
+ })
+
+#define singleListUnlinkBefore singleListUnlinkPrev
+
+/**
+ * unlink last node
+ *
+ * the node can be freed with singleListFreeUnlinked or
+ * inserted in the list with singleListInsertBefore or singleListInsertLast
+ *
+ * \return
+ * unlinked node
+ * null index when the list is empty
+ */
+#define singleListUnlinkLast(name) ({\
+ var UNIQVAR(res) = NULL;\
+ if (singleListIsEmpty(name)) /* list is empty*/ goto UNIQVAR(ret);\
+ /* last is unlinked */\
+ UNIQVAR(res) = (name)->last;\
+ /* previous node is now last */\
+ (name)->last = (name)->last->prev;\
+ (name)->count--;\
+ /* if the list is empty set head to null */\
+ if (singleListIsEmpty(name)) (name)->head = NULL;\
+ UNIQVAR(ret):\
+ UNIQVAR(res);\
+ })
+
+/**
+ * free unlinked node
+ *
+ * node must be of type singleListNodeType(name)
+ */
+#define singleListFreeUnlinked(name, node) dArrayAppend(&(name)->freeList, node)
+
+/**
+ * delete node
+ *
+ * node must be of type singleListNodeType(name)
+ *
+ * unlink and free node
+ */
+#define singleListDelPrev(name, node) ({\
+ var UNIQVAR(prev) = singleListUnlinkPrev(name, node);\
+ singleListFreeUnlinked(name, UNIQVAR(prev));\
+ true;\
+ })
+
+#define singleListDelBefore singleListDelPrev
+
+
+
+
+
+/** first element */
+#define singleListFirst(name) (name)->head->elem
+#define singleListHead singleListFirst
+
+/** first previous node index (always null) */
+#define singleListFirstPrevIdx(name) (name)->head->prev
+#define singleListHeadPrev singleListFirstPrev
+
+/** first node */
+#define singleListFirstNode(name) (name)->head
+#define singleListHeadNode singleListFirstNode
+
+/** last element */
+#define singleListLast(name) (name)->last->elem
+
+/** last previous node index */
+#define singleListLastPrev(name) (name)->last->prev
+
+/** last node */
+#define singleListLastNode(name) (name)->last
+
+/** node element (or use node->elem) */
+#define singleListElem(node) (node)->elem
+
+/** previous index in node */
+#define singleListPrev(node) (node)->prev
+
+
+
+
+
+
+
+
+/** loop node pointers from last to head, to access the elment use singleListNodePtrElem(node) or (node)->elem */
+#define singleListForEachDown(name, node) lForEachDown(node, (name)->last)
+
+/** loop element from last to head (the element data is copied) */
+#define singleListForEachElemDown(name, element)\
+ var UNIQVAR(node) = (name)->last;\
+ for(var element = singleListLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, element = UNIQVAR(node) ? UNIQVAR(node)->elem : element)
+
+/** loop element pointers from last to head, use *elemPtr to access the element data */
+#define singleListForEachElemPDown(name, elemPtr)\
+ var UNIQVAR(node) = (name)->last;\
+ for(var elemPtr = &singleListLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, elemPtr = UNIQVAR(node) ? &UNIQVAR(node)->elem : elemPtr)
+
+/** loop node pointers from startNode to head, to access the elment use singleListNodePtrElem(node) or (node)->elem */
+#define singleListForEachNodeFromDown(name, node, startNode) lForEachDown(node, startNode)
+
+/** loop element from startNode to head (the element data is copied) */
+#define singleListForEachElemFromDown(name, element, startNode)\
+ var UNIQVAR(node) = startNode;\
+ for(var element = singleListLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, element = UNIQVAR(node) ? UNIQVAR(node)->elem : element)
+
+/** loop element pointers from startNode to head, use *elemPtr to access the element data */
+#define singleListForEachElemPFromDown(name, elemPtr, startNode)\
+ var UNIQVAR(node) = startNode;\
+ for(var elemPtr = &singleListLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, elemPtr = UNIQVAR(node) ? &UNIQVAR(node)->elem : elemPtr)
+
+
+
+
+
+
+/**
+ * insert nodeToInsert before referenceNode
+ */
+#define singleListInsertBefore(name, referenceNode, nodeToInsert) do{\
+ singleListNodeType(name) UNIQVAR(refNode) = referenceNode;\
+ singleListNodeType(name) UNIQVAR(nodeToInsert) = nodeToInsert;\
+ /* save previous node index */\
+ var UNIQVAR(tmp) = UNIQVAR(refNode)->prev;\
+ /* previous node in now nodeToInsert */\
+ UNIQVAR(refNode)->prev = UNIQVAR(nodeToInsert);\
+ /* connect rest of the list to nodeToInsert */\
+ UNIQVAR(nodeToInsert)->prev = UNIQVAR(tmp);\
+ if (!UNIQVAR(tmp)) /* referenceNode was head node */ (name)->head = UNIQVAR(nodeToInsert);\
+ (name)->count++;\
+ } while(0)
+
+#define singleListInsertPrev singleListInsertBefore
+
+/**
+ * insert nodeToInsert last
+ */
+#define singleListInsertLast(name, nodeToInsert) do{\
+ singleListNodeType(name) UNIQVAR(nodeToInsert) = nodeToInsert;\
+ if (singleListIsEmpty(name)) {\
+ /* list is empty, previous node is null and set both head and last */\
+ UNIQVAR(nodeToInsert)->prev = NULL;\
+ (name)->head = (name)->last = UNIQVAR(nodeToInsert);\
+ }\
+ else {\
+ /* last node is previous node for nodeToInsert */\
+ UNIQVAR(nodeToInsert)->prev = (name)->last;\
+ /* now last is nodeToInsert */\
+ (name)->last = UNIQVAR(nodeToInsert);\
+ }\
+ (name)->count++;\
+ } while(0)
+
+// // NO - cant insert before and after last
+// #define singleListInsert(name, referenceNodeIndex, nodeToInsertIndex) do{\
+// typeof((name)->null) UNIQVAR(refNodeIdx) = referenceNodeIndex;\
+// if (UNIQVAR(refNodeIdx) != (name)->last) singleListInsertBefore(name, UNIQVAR(refNodeIdx), nodeToInsertIndex);\
+// else singleListInsertLast(name, nodeToInsertIndex);\
+// } while(0)
+
+
+// Internal
+// allocate a node
+#define singleListAddNode(name) ({\
+ singleListNodeType(name) UNIQVAR(res) = NULL;\
+ if (dArrayIsEmpty(&(name)->freeList)) {\
+ /* create new node */\
+ dArrayPush(&(name)->list);\
+ UNIQVAR(res) = dArrayLastPtr(&(name)->list);\
+ }\
+ else {\
+ /* reuse a free node */\
+ UNIQVAR(res) = dArrayLast(&(name)->freeList);\
+ dArrayDelLast(&(name)->freeList);\
+ }\
+ UNIQVAR(res);\
+ })
+
+/**
+ * add new node before referenceNode
+ *
+ * \return
+ * resultNode new node inserted before referenceNode
+ */
+#define singleListAddBefore(name, referenceNode) ({\
+ var UNIQVAR(res) = singleListAddNode(name);\
+ singleListInsertBefore(name, referenceNode, UNIQVAR(res));\
+ UNIQVAR(res);\
+ })
+
+#define singleListAddPrev singleListAddBefore
+
+/** add new node after last
+ *
+ * \return
+ * resultNode new node after last (new last node)
+ */
+#define singleListAddLast(name) ({\
+ var UNIQVAR(res) = singleListAddNode(name);\
+ singleListInsertLast(name, UNIQVAR(res));\
+ UNIQVAR(res);\
+ })
+
+// // NO - cant insert before and after last
+// #define singleListAdd(name, referenceNodeIndex) ({\
+// typeof((name)->null) UNIQVAR(res) = singleListAddNode(name);\
+// singleListInsert(name, referenceNodeIndex, UNIQVAR(res));\
+// UNIQVAR(res);\
+// })
+
+
+
+
+
+/**
+ * write the singleList content to filename file
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * filename file name string
+ */
+#define singleListWriteFilename(name, filename) do {\
+ FILE *UNIQVAR(f) = fopen(filename, "w");\
+ if (UNIQVAR(f)) {\
+ singleListForEachDown(name, UNIQVAR(node)) {\
+ fwrite(&singleListElem(UNIQVAR(node)), 1, sizeof(singleListElem((name)->head)), UNIQVAR(f));\
+ }\
+ fclose(UNIQVAR(f));\
+ }\
+ } while(0)
+
+/**
+ * write the singleList content to disk
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * file already opened file
+ */
+#define singleListWrite(name, file) do {\
+ singleListForEachDown(name, UNIQVAR(node)) {\
+ fwrite(&singleListElem(UNIQVAR(node)), 1, sizeof(singleListElem((name)->head)), file);\
+ }\
+ } while(0)
+
+/**
+ * read a singleList from filename file
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * filename file name string
+ */
+#define singleListReadFilename(name, filename) do {\
+ if (fileExists(filename)) {\
+ size_t UNIQVAR(sz) = fileSize(filename);\
+ const size_t UNIQVAR(elemSz) = sizeof(singleListElem((name)->head));\
+ if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
+ UNIQVAR(sz) /= UNIQVAR(elemSz);\
+ if (!UNIQVAR(sz)) /* there is no element to load*/ break;\
+ FILE *UNIQVAR(f) = fopen(filename, "r");\
+ if (UNIQVAR(f)) {\
+ singleListPush(name);\
+ fread(&singleListLast(name), 1, UNIQVAR(elemSz), UNIQVAR(f));\
+ var UNIQVAR(insertBefore) = (name)->last;\
+ range(UNIQVAR(i), UNIQVAR(sz)-1) {\
+ UNIQVAR(insertBefore) = singleListAddBefore(name, UNIQVAR(insertBefore));\
+ fread(&singleListElem(UNIQVAR(insertBefore)), 1, UNIQVAR(elemSz), UNIQVAR(f));\
+ }\
+ fclose(UNIQVAR(f));\
+ }\
+ }\
+ } while(0)
+
+/**
+ * read a singleList from disk
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * file already opened file
+ */
+#define singleListRead(name, file) do {\
+ fseek(file, 0 , SEEK_END);\
+ size_t UNIQVAR(sz) = ftell(file);\
+ fseek(file, 0 , SEEK_SET);\
+ const size_t UNIQVAR(elemSz) = sizeof(singleListElem((name)->head));\
+ if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
+ UNIQVAR(sz) /= UNIQVAR(elemSz);\
+ if (!UNIQVAR(sz)) /* there is no element to load*/ break;\
+ singleListPush(name);\
+ fread(&singleListLast(name), 1, UNIQVAR(elemSz), file);\
+ var UNIQVAR(insertBefore) = (name)->last;\
+ range(UNIQVAR(i), UNIQVAR(sz)-1) {\
+ UNIQVAR(insertBefore) = singleListAddBefore(name, UNIQVAR(insertBefore));\
+ fread(&singleListElem(UNIQVAR(insertBefore)), 1, UNIQVAR(elemSz), file);\
+ }\
+ } while(0)
+
+// vim: set expandtab ts=2 sw=2:
diff --git a/singleListe.h b/singleListe.h
@@ -0,0 +1,599 @@
+
+
+/**
+ * \file
+ *
+ * Single linked list with external dArray: singleListe
+ *
+ * head 1 <- 2 <- 3 last
+ *
+ * The single linked list can be used as a stack and is not efficient when used as a queue.
+ *
+ * The nodes in singleListe are linked with pointers and dynamically allocated in segments and an extrernal dArray
+ * so multiple lists can be stored in single dArray making free node reuse more efficient.
+ *
+ * NOTE: The macros in this file are for creating list functions wrapping the macros.
+ *
+ * The element type handled by the list is defined with singleListeT
+ *
+ * The external node and free node storage must be allocated after declaring the first list and before running singleListeStoreIinit
+ *
+ * The nodes have 2 members: .elem and .prev, .elem is the element data and .prev is the index of the previous node
+ *
+ * use push and pop to stack nodes
+ *
+ * The forEach macros loop on nodes or elements from last node to head node
+ *
+ * use unlinkPrev or unlinkBefore and unlinkLast to unlink nodes anywhere in the list
+ *
+ * use insertBefore, addBefore to insert anywhere in the list, before head and push, insertLast, addLast to insert after last
+ *
+ * use freeUnlinked to free unlinked nodes
+ *
+ * use singleListeDelPrev or singleListeDelBefore, singleListeDelLast or singleListePop to delete nodes anywhere in the list
+ *
+ * To create a list in reverse order, add the first node with push and then add the nodes with addBefore head
+ *
+ * Example:
+ *
+ * // define list:
+ * singleListeT(slt, u32);
+ *
+ * // declare list:
+ * slt sl;
+ *
+ * // initialize node storage
+ * // local
+ * singleListeNodesT(&sl) nodeStore;
+ * singleListeFreeNodesT(&sl) freeNodeStore;
+ * singleListeStoreInit(&nodeStore, &freeNodeStore);
+ *
+ * // or on heap
+ * singleListeNodesPtrT(&sl) nodeStore;
+ * singleListeFreeNodesPtrT(&sl) freeNodeStore;
+ * nodeStore = malloc(sizeof(singleListeNodesT(&sl)));
+ * freeNodeStore = malloc(sizeof(singleListeFreeNodesT(&sl)));
+ *
+ * // initialize:
+ * singleListeInit(&sl, &nodeStore, &freeNodeStore);
+ *
+ * // or on heap
+ * singleListeInit(&sl, nodeStore, freeNodeStore);
+ *
+ * // push element:
+ * singleListePush(&sl);
+ * singleListeLast(&sl) = 1;
+ * sl.last->elem = 1;
+ *
+ * singleListePush(&sl);
+ * singleListeLast(&sl) = 2;
+ *
+ * // head element
+ * singleListeHead(&sl) = 0;
+ * sl.head->elem = 0;
+ *
+ * // previous node for last node
+ * var prev = sl.last->prev;
+ * prev->elem = 4;
+ *
+ * // pointer to node
+ * singleListeNodeType(&sl) pointer = singleListeHeadNode(&sl);
+ *
+ * // Pop/delLast element:
+ * singleListePop(&sl);
+ *
+ * // free list
+ * singleListeFree(&sl);
+ *
+ * // free node storage, after this all lists using this storage are invalid
+ * singleListeStoreFree(&nodeStore, &freeNodeStore);
+ */
+
+#include "libsheepyObject.h"
+
+/**
+ * list and node definition
+ */
+#define singleListeT(typeName, elementType)\
+ /* node type */\
+ typ struct UNIQVAR(nodet) UNIQVAR(nodet);\
+ struct UNIQVAR(nodet) {\
+ elementType elem;\
+ UNIQVAR(nodet) *prev;\
+ };\
+ /* dArray storing the nodes */\
+ dArrayT(UNIQVAR(aNodet), UNIQVAR(nodet));\
+ /* free node list */\
+ dArrayT(UNIQVAR(freeaNodet), UNIQVAR(nodet)*);\
+ typ struct {\
+ UNIQVAR(nodet) *head; /* first node */\
+ UNIQVAR(nodet) *last; /* last node */\
+ UNIQVAR(aNodet) *list; /* node dArray */\
+ UNIQVAR(freeaNodet) *freeList; /* free node dArray */\
+ size_t count; /* node count */\
+ } typeName
+
+/** dArray type for storing the nodes */
+#define singleListeNodesT(name) typeof(*(name)->list)
+
+/** pointer type to dArray storing the nodes */
+#define singleListeNodesPtrT(name) typeof((name)->list)
+
+/** dArray type for storing the free nodes */
+#define singleListeFreeNodesT(name) typeof(*(name)->freeList)
+
+/** pointer type to dArray storing the free nodes */
+#define singleListeFreeNodesPtrT(name) typeof((name)->freeList)
+
+/**
+ * initialize the dArrays storing the nodes for all the lists
+ */
+#define singleListeStoreInit(nodes, freeNodes) do{\
+ dArrayInit(nodes);\
+ dArrayInit(freeNodes);\
+ } while(0)
+
+/**
+ * free node store for all lists
+ * after this, all the nodes in lists are freed
+ */
+#define singleListeStoreFree(nodes, freeNodes) do{\
+ dArrayFree(nodes);\
+ dArrayFree(freeNodes);\
+ } while(0)
+
+/**
+ * initialize list
+ *
+ * nodes and freeNodes must be initialized once before calling singleListeInit
+ *
+ * \return
+ * true success, false failed
+ */
+#define singleListeInit(name, nodes, freeNodes) ({\
+ (name)->head = NULL;\
+ (name)->last = NULL;\
+ (name)->list = nodes;\
+ (name)->freeList = freeNodes;\
+ (name)->count = 0;\
+ true;\
+ })
+
+/**
+ * free list nodes
+ * free and reset internal structures
+ *
+ * the dArrays storing the nodes are kept, use singleListeStoreFree to free them
+ */
+#define singleListeFree(name) do{\
+ singleListeForEachDown(name, UNIQVAR(node)) {\
+ dArrayAppend((name)->freeList, UNIQVAR(node));\
+ }\
+ (name)->head = NULL;\
+ (name)->last = NULL;\
+ (name)->count = 0;\
+ } while(0)
+
+/**
+ * node type for declaring pointers to nodes
+ * */
+#define singleListeNodeType(name) typeof((name)->head)
+
+/**
+ * is list empty
+ */
+#define singleListeIsEmpty(name) (!(name)->count)
+
+/**
+ * element count in list
+ */
+#define singleListeCount(name) (name)->count
+
+/**
+ * push element to list (only allocates node)
+ * use singleListeLast to access the element
+ *
+ * \return
+ * true success, false failed
+ */
+#define singleListePush(name) ({\
+ /* steps:
+ * check if free node is empty
+ * free list is empty, add a new node
+ * create first node
+ * or link to previous node
+ * reuse a free node
+ * create first node
+ * or link to previous node
+ */\
+ if (dArrayIsEmpty((name)->freeList)) {\
+ /* free list is empty, add a new node */\
+ dArrayPush((name)->list);\
+ if (singleListeIsEmpty(name)) {\
+ /* first node */\
+ dArrayLast((name)->list).prev = NULL;\
+ (name)->head = (name)->last = dArrayLastPtr((name)->list);\
+ }\
+ else {\
+ /* link to previous node */\
+ dArrayLast((name)->list).prev = (name)->last;\
+ (name)->last = dArrayLastPtr((name)->list);\
+ }\
+ }\
+ else {\
+ /* reuse a free node */\
+ if (singleListeIsEmpty(name)) {\
+ /* first node */\
+ dArrayLast((name)->freeList)->prev = NULL;\
+ (name)->head = (name)->last = dArrayLast((name)->freeList);\
+ }\
+ else {\
+ /* link to previous node */\
+ dArrayLast((name)->freeList)->prev = (name)->last;\
+ (name)->last = dArrayLast((name)->freeList);\
+ }\
+ dArrayDelLast((name)->freeList);\
+ }\
+ (name)->count++;\
+ true;\
+ })
+
+/**
+ * pop element from list (only free node)
+ *
+ * \return
+ * true success, false failed: the list is empty
+ */
+#define singleListePop(name) ({\
+ bool UNIQVAR(res) = true;\
+ if (singleListeIsEmpty(name)) {\
+ /* the list is empty */\
+ UNIQVAR(res) = false;\
+ goto UNIQVAR(ret);\
+ }\
+ /* free last node */\
+ dArrayAppend((name)->freeList, (name)->last);\
+ /* previous node becomes last node */\
+ (name)->last = (name)->last->prev;\
+ if ((name)->count == 1) /* the list is empty, head is gone */ (name)->head = NULL;\
+ (name)->count--;\
+ UNIQVAR(ret):\
+ UNIQVAR(res);\
+ })
+
+#define singleListeDelLast singleListePop
+
+/**
+ * unlink previous node (use pop or unlinkLast to unlink the last node)
+ *
+ * node must be of type singleListeNodeType(name)
+ *
+ * the node can be freed with singleListeFreeUnlinked or
+ * inserted in the list with singleListeInsertBefore or singleListeInsertLast
+ *
+ * \return
+ * unlinked node index
+ * null index when the list is empty or when node is head
+ */
+#define singleListeUnlinkPrev(name, node) ({\
+ singleListeNodeType(name) UNIQVAR(nde) = node;\
+ singleListeNodeType(name) UNIQVAR(res) = NULL;\
+ if (singleListeIsEmpty(name)) /* list is empty*/ goto UNIQVAR(ret);\
+ if (UNIQVAR(nde) == (name)->head) {\
+ /* node is head, there is no previous node */\
+ goto UNIQVAR(ret);\
+ }\
+ /* the unlinked node is prev */\
+ UNIQVAR(res) = UNIQVAR(nde)->prev;\
+ if (UNIQVAR(res) == (name)->head) {\
+ /* prev node is head, so node is now head and update head */\
+ (name)->head = UNIQVAR(nde);\
+ UNIQVAR(nde)->prev = NULL;\
+ }\
+ else {\
+ /* link previous previous node to node */\
+ UNIQVAR(nde)->prev = UNIQVAR(res)->prev;\
+ }\
+ (name)->count--;\
+ UNIQVAR(ret):\
+ UNIQVAR(res);\
+ })
+
+#define singleListeUnlinkBefore singleListeUnlinkPrev
+
+/**
+ * unlink last node
+ *
+ * the node can be freed with singleListeFreeUnlinked or
+ * inserted in the list with singleListeInsertBefore or singleListeInsertLast
+ *
+ * \return
+ * unlinked node
+ * null index when the list is empty
+ */
+#define singleListeUnlinkLast(name) ({\
+ var UNIQVAR(res) = NULL;\
+ if (singleListeIsEmpty(name)) /* list is empty*/ goto UNIQVAR(ret);\
+ /* last is unlinked */\
+ UNIQVAR(res) = (name)->last;\
+ /* previous node is now last */\
+ (name)->last = (name)->last->prev;\
+ (name)->count--;\
+ /* if the list is empty set head to null */\
+ if (singleListeIsEmpty(name)) (name)->head = NULL;\
+ UNIQVAR(ret):\
+ UNIQVAR(res);\
+ })
+
+/**
+ * free unlinked node
+ *
+ * node must be of type singleListeNodeType(name)
+ */
+#define singleListeFreeUnlinked(name, node) dArrayAppend((name)->freeList, node)
+
+/**
+ * delete node
+ *
+ * node must be of type singleListeNodeType(name)
+ *
+ * unlink and free node
+ */
+#define singleListeDelPrev(name, node) ({\
+ var UNIQVAR(prev) = singleListeUnlinkPrev(name, node);\
+ singleListeFreeUnlinked(name, UNIQVAR(prev));\
+ true;\
+ })
+
+#define singleListeDelBefore singleListeDelPrev
+
+
+
+
+
+/** first element */
+#define singleListeFirst(name) (name)->head->elem
+#define singleListeHead singleListeFirst
+
+/** first previous node index (always null) */
+#define singleListeFirstPrevIdx(name) (name)->head->prev
+#define singleListeHeadPrev singleListeFirstPrev
+
+/** first node */
+#define singleListeFirstNode(name) (name)->head
+#define singleListeHeadNode singleListeFirstNode
+
+/** last element */
+#define singleListeLast(name) (name)->last->elem
+
+/** last previous node index */
+#define singleListeLastPrev(name) (name)->last->prev
+
+/** last node */
+#define singleListeLastNode(name) (name)->last
+
+/** node element (or use node->elem) */
+#define singleListeElem(node) (node)->elem
+
+/** previous index in node */
+#define singleListePrev(node) (node)->prev
+
+
+
+
+
+
+
+
+/** loop node pointers from last to head, to access the elment use singleListeNodePtrElem(node) or (node)->elem */
+#define singleListeForEachDown(name, node) lForEachDown(node, (name)->last)
+
+/** loop element from last to head (the element data is copied) */
+#define singleListeForEachElemDown(name, element)\
+ var UNIQVAR(node) = (name)->last;\
+ for(var element = singleListeLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, element = UNIQVAR(node) ? UNIQVAR(node)->elem : element)
+
+/** loop element pointers from last to head, use *elemPtr to access the element data */
+#define singleListeForEachElemPDown(name, elemPtr)\
+ var UNIQVAR(node) = (name)->last;\
+ for(var elemPtr = &singleListeLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, elemPtr = UNIQVAR(node) ? &UNIQVAR(node)->elem : elemPtr)
+
+/** loop node pointers from startNode to head, to access the elment use singleListeNodePtrElem(node) or (node)->elem */
+#define singleListeForEachNodeFromDown(name, node, startNode) lForEachDown(node, startNode)
+
+/** loop element from startNode to head (the element data is copied) */
+#define singleListeForEachElemFromDown(name, element, startNode)\
+ var UNIQVAR(node) = startNode;\
+ for(var element = singleListeLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, element = UNIQVAR(node) ? UNIQVAR(node)->elem : element)
+
+/** loop element pointers from startNode to head, use *elemPtr to access the element data */
+#define singleListeForEachElemPFromDown(name, elemPtr, startNode)\
+ var UNIQVAR(node) = startNode;\
+ for(var elemPtr = &singleListeLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, elemPtr = UNIQVAR(node) ? &UNIQVAR(node)->elem : elemPtr)
+
+
+
+
+
+
+/**
+ * insert nodeToInsert before referenceNode
+ */
+#define singleListeInsertBefore(name, referenceNode, nodeToInsert) do{\
+ singleListeNodeType(name) UNIQVAR(refNode) = referenceNode;\
+ singleListeNodeType(name) UNIQVAR(nodeToInsert) = nodeToInsert;\
+ /* save previous node index */\
+ var UNIQVAR(tmp) = UNIQVAR(refNode)->prev;\
+ /* previous node in now nodeToInsert */\
+ UNIQVAR(refNode)->prev = UNIQVAR(nodeToInsert);\
+ /* connect rest of the list to nodeToInsert */\
+ UNIQVAR(nodeToInsert)->prev = UNIQVAR(tmp);\
+ if (!UNIQVAR(tmp)) /* referenceNode was head node */ (name)->head = UNIQVAR(nodeToInsert);\
+ (name)->count++;\
+ } while(0)
+
+#define singleListeInsertPrev singleListeInsertBefore
+
+/**
+ * insert nodeToInsert last
+ */
+#define singleListeInsertLast(name, nodeToInsert) do{\
+ singleListeNodeType(name) UNIQVAR(nodeToInsert) = nodeToInsert;\
+ if (singleListeIsEmpty(name)) {\
+ /* list is empty, previous node is null and set both head and last */\
+ UNIQVAR(nodeToInsert)->prev = NULL;\
+ (name)->head = (name)->last = UNIQVAR(nodeToInsert);\
+ }\
+ else {\
+ /* last node is previous node for nodeToInsert */\
+ UNIQVAR(nodeToInsert)->prev = (name)->last;\
+ /* now last is nodeToInsert */\
+ (name)->last = UNIQVAR(nodeToInsert);\
+ }\
+ (name)->count++;\
+ } while(0)
+
+// // NO - cant insert before and after last
+// #define singleListeInsert(name, referenceNodeIndex, nodeToInsertIndex) do{\
+// typeof((name)->null) UNIQVAR(refNodeIdx) = referenceNodeIndex;\
+// if (UNIQVAR(refNodeIdx) != (name)->last) singleListeInsertBefore(name, UNIQVAR(refNodeIdx), nodeToInsertIndex);\
+// else singleListeInsertLast(name, nodeToInsertIndex);\
+// } while(0)
+
+
+// Internal
+// allocate a node
+#define singleListeAddNode(name) ({\
+ singleListeNodeType(name) UNIQVAR(res) = NULL;\
+ if (dArrayIsEmpty((name)->freeList)) {\
+ /* create new node */\
+ dArrayPush((name)->list);\
+ UNIQVAR(res) = dArrayLastPtr((name)->list);\
+ }\
+ else {\
+ /* reuse a free node */\
+ UNIQVAR(res) = dArrayLast((name)->freeList);\
+ dArrayDelLast((name)->freeList);\
+ }\
+ UNIQVAR(res);\
+ })
+
+/**
+ * add new node before referenceNode
+ *
+ * \return
+ * resultNode new node inserted before referenceNode
+ */
+#define singleListeAddBefore(name, referenceNode) ({\
+ var UNIQVAR(res) = singleListeAddNode(name);\
+ singleListeInsertBefore(name, referenceNode, UNIQVAR(res));\
+ UNIQVAR(res);\
+ })
+
+#define singleListeAddPrev singleListeAddBefore
+
+/** add new node after last
+ *
+ * \return
+ * resultNode new node after last (new last node)
+ */
+#define singleListeAddLast(name) ({\
+ var UNIQVAR(res) = singleListeAddNode(name);\
+ singleListeInsertLast(name, UNIQVAR(res));\
+ UNIQVAR(res);\
+ })
+
+// // NO - cant insert before and after last
+// #define singleListeAdd(name, referenceNodeIndex) ({\
+// typeof((name)->null) UNIQVAR(res) = singleListeAddNode(name);\
+// singleListeInsert(name, referenceNodeIndex, UNIQVAR(res));\
+// UNIQVAR(res);\
+// })
+
+
+
+
+
+/**
+ * write the singleListe content to filename file
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * filename file name string
+ */
+#define singleListeWriteFilename(name, filename) do {\
+ FILE *UNIQVAR(f) = fopen(filename, "w");\
+ if (UNIQVAR(f)) {\
+ singleListeForEachDown(name, UNIQVAR(node)) {\
+ fwrite(&singleListeElem(UNIQVAR(node)), 1, sizeof(singleListeElem((name)->head)), UNIQVAR(f));\
+ }\
+ fclose(UNIQVAR(f));\
+ }\
+ } while(0)
+
+/**
+ * write the singleListe content to disk
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * file already opened file
+ */
+#define singleListeWrite(name, file) do {\
+ singleListeForEachDown(name, UNIQVAR(node)) {\
+ fwrite(&singleListeElem(UNIQVAR(node)), 1, sizeof(singleListeElem((name)->head)), file);\
+ }\
+ } while(0)
+
+/**
+ * read a singleListe from filename file
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * filename file name string
+ */
+#define singleListeReadFilename(name, filename) do {\
+ if (fileExists(filename)) {\
+ size_t UNIQVAR(sz) = fileSize(filename);\
+ const size_t UNIQVAR(elemSz) = sizeof(singleListeElem((name)->head));\
+ if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
+ UNIQVAR(sz) /= UNIQVAR(elemSz);\
+ if (!UNIQVAR(sz)) /* there is no element to load*/ break;\
+ FILE *UNIQVAR(f) = fopen(filename, "r");\
+ if (UNIQVAR(f)) {\
+ singleListePush(name);\
+ fread(&singleListeLast(name), 1, UNIQVAR(elemSz), UNIQVAR(f));\
+ var UNIQVAR(insertBefore) = (name)->last;\
+ range(UNIQVAR(i), UNIQVAR(sz)-1) {\
+ UNIQVAR(insertBefore) = singleListeAddBefore(name, UNIQVAR(insertBefore));\
+ fread(&singleListeElem(UNIQVAR(insertBefore)), 1, UNIQVAR(elemSz), UNIQVAR(f));\
+ }\
+ fclose(UNIQVAR(f));\
+ }\
+ }\
+ } while(0)
+
+/**
+ * read a singleListe from disk
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * file already opened file
+ */
+#define singleListeRead(name, file) do {\
+ fseek(file, 0 , SEEK_END);\
+ size_t UNIQVAR(sz) = ftell(file);\
+ fseek(file, 0 , SEEK_SET);\
+ const size_t UNIQVAR(elemSz) = sizeof(singleListeElem((name)->head));\
+ if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
+ UNIQVAR(sz) /= UNIQVAR(elemSz);\
+ if (!UNIQVAR(sz)) /* there is no element to load*/ break;\
+ singleListePush(name);\
+ fread(&singleListeLast(name), 1, UNIQVAR(elemSz), file);\
+ var UNIQVAR(insertBefore) = (name)->last;\
+ range(UNIQVAR(i), UNIQVAR(sz)-1) {\
+ UNIQVAR(insertBefore) = singleListeAddBefore(name, UNIQVAR(insertBefore));\
+ fread(&singleListeElem(UNIQVAR(insertBefore)), 1, UNIQVAR(elemSz), file);\
+ }\
+ } while(0)
+
+// vim: set expandtab ts=2 sw=2:
