commit 1bf0d006195fcb9dc0dcb4f22222d48a0d30dc16
parent c2977d13051faf15b978b3d647e2141f2d5a5444
Author: Remy Noulin <loader2x@gmail.com>
Date: Tue, 25 Dec 2018 14:55:43 +0100
add llist and lliste (external store) linked lists
.gitignore | 11 ++
README.md | 19 ++-
linkedList.h | 440 +++++++++++++++++++++++++++++++++++++++++++++++++
linkedListe.h | 515 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
main.c | 84 ++++++++++
package.yml | 31 ++++
6 files changed, 1099 insertions(+), 1 deletion(-)
Diffstat:
| M | .gitignore | | | 11 | +++++++++++ |
| M | README.md | | | 19 | ++++++++++++++++++- |
| A | linkedList.h | | | 440 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | linkedListe.h | | | 515 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | main.c | | | 84 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | package.yml | | | 31 | +++++++++++++++++++++++++++++++ |
6 files changed, 1099 insertions(+), 1 deletion(-)
diff --git a/.gitignore b/.gitignore
@@ -1,3 +1,14 @@
+# Vim
+*.sw*
+
+# Debug
+.gdb_history
+
+# Coverage
+*.gcov
+*.gcda
+*.gcno
+
# Prerequisites
*.d
diff --git a/README.md b/README.md
@@ -1,2 +1,19 @@
-# linkedList
+# Sheepy
+This is a sheepy package for [sheepy](https://github.com/RemyNoulin/sheepy) and using [libsheepy](https://github.com/RemyNoulin/libsheepy)
+
+# Linked list
type-safe double linked lists
+
+The nodes in the list are stored in segments for efficiency.
+
+The data can be stored in the list directly nodes to reduce the frequency of memory allocations.
+
+# Usage
+
+Install with spm: `spm install linkedList`
+
+Include header file:
+- `#include "shpPackages/linkedList/linkedList.h"`
+
+Usage examples are on the top of the headers and in `main.c`.
+
diff --git a/linkedList.h b/linkedList.h
@@ -0,0 +1,440 @@
+
+/**
+ * \file
+ *
+ * double linked list: llist
+ *
+ * The nodes in llist are linked with pointers and dynamically allocated in segments
+ *
+ * The element type handled by the list is defined with llistT
+ *
+ *
+ * Example:
+ *
+ * // define list:
+ * llistT(llt, u32);
+ *
+ * // declare list:
+ * llt ll;
+ *
+ * // initialize:
+ * llistInit(&ll);
+ *
+ * // push element:
+ * llistPush(&ll);
+ * llistLast(&ll) = 1;
+ *
+ * // Pop/dellast element:
+ * llistPop(&ll);
+ *
+ * // Free
+ * llistFree(&ll);
+ *
+ * TODO add node count like singlelist
+ * TODO create linkedList without head and last
+ */
+
+#include "libsheepyObject.h"
+
+/**
+ * list and node definition
+ */
+#define llistT(typeName, elementType)\
+ typ struct UNIQVAR(nodet) UNIQVAR(nodet);\
+ struct UNIQVAR(nodet) {\
+ elementType elem;\
+ UNIQVAR(nodet) *prev;\
+ UNIQVAR(nodet) *next;\
+ };\
+ dArrayT(UNIQVAR(aNodet), UNIQVAR(nodet));\
+ dArrayT(UNIQVAR(freeaNodet), UNIQVAR(nodet)*);\
+ typ struct {\
+ UNIQVAR(nodet) *head;\
+ UNIQVAR(nodet) *last;\
+ UNIQVAR(aNodet) list;\
+ UNIQVAR(freeaNodet) freeList;\
+ } typeName
+
+/**
+ * initialize list
+ */
+#define llistInit(name) do{\
+ (name)->head = (name)->last = NULL;\
+ dArrayInit(&(name)->list);\
+ dArrayInit(&(name)->freeList);\
+ } while(0)
+
+/**
+ * free list
+ */
+#define llistFree(name) do{\
+ dArrayFree(&(name)->list);\
+ dArrayFree(&(name)->freeList);\
+ (name)->head = (name)->last = NULL;\
+ } while(0)
+
+/**
+ * node type for declaring pointers to nodes
+ *
+ * Example:
+ * llistNodeType(name) node;
+ * llistUnlink(name, node);
+ * */
+#define llistNodeType(name) typeof((name)->head)
+
+// /** TODO
+// * element count in list
+// */
+// #define llistCount(name) (name)->count
+
+
+/**
+ * is list empty
+ */
+#define llistIsEmpty(name) dArrayIsEmpty(&(name)->list)
+
+/**
+ * push element to list (only allocates node)
+ * use llistLast to access the element
+ */
+#define llistPush(name) do{\
+ if (dArrayIsEmpty(&(name)->freeList)) {\
+ dArrayPush(&(name)->list);\
+ if (!(name)->last) {\
+ /* first node */\
+ dArrayLast(&(name)->list).prev = NULL;\
+ dArrayLast(&(name)->list).next = NULL;\
+ (name)->head = &dArrayLast(&(name)->list);\
+ (name)->last = &dArrayLast(&(name)->list);\
+ }\
+ else {\
+ /* link to previous node */\
+ dArrayLast(&(name)->list).prev = (name)->last;\
+ (name)->last->next = &dArrayLast(&(name)->list);\
+ dArrayLast(&(name)->list).next = NULL;\
+ (name)->last = &dArrayLast(&(name)->list);\
+ }\
+ }\
+ else {\
+ /* reuse a free node */\
+ if (!(name)->last) {\
+ dArrayLast(&(name)->freeList)->prev = NULL;\
+ dArrayLast(&(name)->freeList)->next = NULL;\
+ (name)->head = dArrayLast(&(name)->freeList);\
+ (name)->last = dArrayLast(&(name)->freeList);\
+ }\
+ else {\
+ dArrayLast(&(name)->freeList)->prev = (name)->last;\
+ (name)->last->next = dArrayLast(&(name)->freeList);\
+ dArrayLast(&(name)->freeList)->next = NULL;\
+ (name)->last = dArrayLast(&(name)->freeList);\
+ }\
+ dArrayPop(&(name)->freeList);\
+ }\
+ } while(0)
+
+/**
+ * pop element from list (only free node)
+ *
+ * \return
+ * true success, false failed: the list is empty
+ */
+#define llistPop(name) ({\
+ bool UNIQVAR(r) = true;\
+ if (!(name)->last) {\
+ /* the list is empty */\
+ UNIQVAR(r) = false;\
+ goto UNIQVAR(end);\
+ }\
+ dArrayPush(&(name)->freeList);\
+ dArrayLast(&(name)->freeList) = (name)->last;\
+ (name)->last = (name)->last->prev;\
+ if ((name)->last) (name)->last->next = NULL;\
+ if (!(name)->last) /* the list is empty */ (name)->head = NULL;\
+ UNIQVAR(end):\
+ UNIQVAR(r);\
+ })
+
+#define llistDelLast llistPop
+
+/**
+ * unlink node
+ *
+ * node must be of type llistNodeType(name)
+ *
+ * the node can be freed with llistFreeUnlinked or
+ * inserted in the list with llistInsertAfter or llistInsertBefore
+ */
+#define llistUnlink(name, node) do{\
+ if (!(node)->prev) {\
+ /* node is head */\
+ (name)->head = (node)->next;\
+ }\
+ else {\
+ (node)->prev->next = (node)->next;\
+ }\
+ if (!(node)->next) {\
+ /* node is last */\
+ (name)->last = (node)->prev;\
+ }\
+ else {\
+ (node)->next->prev = (node)->prev;\
+ }\
+ } while(0)
+
+/**
+ * free unlinked node
+ *
+ * node must be of type llistNodeType(name)
+ */
+#define llistFreeUnlinked(name, node) do{\
+ dArrayPush(&(name)->freeList);\
+ dArrayLast(&(name)->freeList) = node;\
+ } while(0)
+
+/**
+ * delete node
+ *
+ * node must be of type llistNodeType(name)
+ *
+ * unlink and free node
+ */
+#define llistDelNode(name, node) do{\
+ llistUnlink(name, node);\
+ llistFreeUnlinked(name, node);\
+ } while(0)
+
+/** first element */
+#define llistFirst(name) (name)->head->elem
+
+/** first node pointer */
+#define llistFirstNode(name) (name)->head
+#define llistHeadNode llistFirstNode
+
+/** last element */
+#define llistLast(name) (name)->last->elem
+
+/** last node pointer */
+#define llistLasttNode(name) (name)->last
+
+/** previous node */
+#define llistPrev(node) (node)->prev
+
+/** next node */
+#define llistNext(node) (node)->next
+
+/** node element (or use node->elem) */
+#define llistGetElem(node) (node)->elem
+
+/**
+ * swap node1 with node2
+ */
+#define llistSwap(name, node1, node2) do{\
+ /* disable sanity checks to keep it simple - if (!node1 or !node2) {*/\
+ /* return value instead --- (name)->res = false;*/\
+ /* break;*/\
+ /*}*/\
+ if (node1 == node2) /* node1 and node2 are the same node, nothing to do */ break;\
+ var UNIQVAR(tmp) = (node1)->next;\
+ (node1)->next = (node2)->next;\
+ (node2)->next = UNIQVAR(tmp);\
+ if (!(node1)->next) (name)->last = node1;\
+ else (node1)->next->prev = node1;\
+ if (!(node2)->next) (name)->last = node2;\
+ else (node2)->next->prev = node2;\
+ UNIQVAR(tmp) = (node1)->prev;\
+ (node1)->prev = (node2)->prev;\
+ (node2)->prev = UNIQVAR(tmp);\
+ if (!(node1)->prev) (name)->head = node1;\
+ else (node1)->prev->next = node1;\
+ if (!(node2)->prev) (name)->head = node2;\
+ else (node2)->prev->next = node2;\
+ } while(0)
+
+/** loop from head to last */
+#define llistForEach(name, node)\
+ for(var node = (name)->head; node ; node = llistNext(node))
+
+/** loop from last to head */
+#define llistForEachDown(name, node)\
+ for(var node = (name)->last; node ; node = llistPrev(node))
+
+/** loop from startNode to last */
+#define llistForEachFrom(node, startNode)\
+ for(var node = startNode; node ; node = (node)->next)
+
+/** loop from startNode to head */
+#define llistForEachFromDown(node, startNode)\
+ for(var node = startNode; node ; node = (node)->prev)
+
+/**
+ * insert nodeToInsert after referenceNode
+ *
+ * nodeToInsert and referenceNode must be of type llistNodeType(name)
+ */
+#define llistInsertAfter(name, referenceNode, nodeToInsert) do{\
+ (nodeToInsert)->next = referenceNode->next;\
+ referenceNode->next = nodeToInsert;\
+ (nodeToInsert)->prev = referenceNode;\
+ if ((nodeToInsert)->next) {\
+ (nodeToInsert)->next->prev = nodeToInsert;\
+ }\
+ else {\
+ /* referenceNode was last node */\
+ (name)->last = nodeToInsert;\
+ }\
+ } while(0)
+
+/**
+ * insert nodeToInsert before referenceNode
+ *
+ * nodeToInsert and referenceNode must be of type llistNodeType(name)
+ */
+#define llistInsertBefore(name, referenceNode, nodeToInsert) do{\
+ (nodeToInsert)->prev = referenceNode->prev;\
+ referenceNode->prev = nodeToInsert;\
+ (nodeToInsert)->next = referenceNode;\
+ if ((nodeToInsert)->prev) {\
+ (nodeToInsert)->prev->next = nodeToInsert;\
+ }\
+ else {\
+ /* referenceNode was head node */\
+ (name)->head = nodeToInsert;\
+ }\
+ } while(0)
+
+
+// Internal
+// allocate a node
+#define llistAddNode(name, resultNode) do{\
+ if (dArrayIsEmpty(&(name)->freeList)) {\
+ dArrayPush(&(name)->list);\
+ resultNode = &dArrayLast(&(name)->list);\
+ }\
+ else {\
+ /* reuse a free node */\
+ resultNode = dArrayLast(&(name)->freeList);\
+ dArrayPop(&(name)->freeList);\
+ }\
+ } while(0)
+
+/**
+ * add new node after referenceNode
+ *
+ * resultNode and referenceNode must be of type llistNodeType(name)
+ *
+ * \return
+ * resultNode access element in node with resultNode->elem or llistGetElem(resultNode)
+ */
+#define llistAddAfter(name, referenceNode, resultNode) do{\
+ llistAddNode(name, resultNode);\
+ (resultNode)->next = referenceNode->next;\
+ referenceNode->next = resultNode;\
+ (resultNode)->prev = referenceNode;\
+ if ((resultNode)->next) {\
+ (resultNode)->next->prev = resultNode;\
+ }\
+ else {\
+ /* referenceNode was last node */\
+ (name)->last = resultNode;\
+ }\
+ } while(0)
+
+/**
+ * add new node before referenceNode
+ *
+ * resultNode and referenceNode must be of type llistNodeType(name)
+ *
+ * \return
+ * resultNode access element in node with resultNode->elem or llistGetElem(resultNode)
+ */
+#define llistAddBefore(name, referenceNode, resultNode) do{\
+ llistAddNode(name, resultNode);\
+ (resultNode)->prev = referenceNode->prev;\
+ referenceNode->prev = resultNode;\
+ (resultNode)->next = referenceNode;\
+ if ((resultNode)->prev) {\
+ (resultNode)->prev->next = resultNode;\
+ }\
+ else {\
+ /* referenceNode was head node */\
+ (name)->head = resultNode;\
+ }\
+ } while(0)
+
+/**
+ * write the llist content to filename file
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * filename file name string
+ */
+#define llistWriteFilename(name, filename) do {\
+ FILE *UNIQVAR(f) = fopen(filename, "w");\
+ if (UNIQVAR(f)) {\
+ llistForEach(name, UNIQVAR(node)) {\
+ fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), UNIQVAR(f));\
+ }\
+ fclose(UNIQVAR(f));\
+ }\
+ } while(0)
+
+/**
+ * write the llist content to disk
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * file already opened file
+ */
+#define llistWrite(name, file) do {\
+ llistForEach(name, UNIQVAR(node)) {\
+ fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), file);\
+ }\
+ } while(0)
+
+/**
+ * read a llist from filename file
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * filename file name string
+ */
+#define llistReadFilename(name, filename) do {\
+ if (fileExists(filename)) {\
+ size_t UNIQVAR(sz) = fileSize(filename);\
+ const size_t UNIQVAR(elemSz) = sizeof(dArrayLast(&(name)->list).elem);\
+ if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
+ UNIQVAR(sz) /= UNIQVAR(elemSz);\
+ if (UNIQVAR(sz) > (size_t)(name)->list.maxCount) /* file size exceeds capacity */ break;\
+ FILE *UNIQVAR(f) = fopen(filename, "r");\
+ if (UNIQVAR(f)) {\
+ range(UNIQVAR(i), UNIQVAR(sz)) {\
+ llistPush(name);\
+ fread(&llistLast(name), 1, UNIQVAR(elemSz), UNIQVAR(f));\
+ }\
+ fclose(UNIQVAR(f));\
+ }\
+ }\
+ } while(0)
+
+/**
+ * read a llist from disk
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * file already opened file
+ */
+#define llistRead(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(dArrayLast(&(name)->list).elem);\
+ if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
+ UNIQVAR(sz) /= UNIQVAR(elemSz);\
+ if (UNIQVAR(sz) > (size_t)(name)->list.maxCount) /* file size exceeds capacity */ break;\
+ range(UNIQVAR(i), UNIQVAR(sz)) {\
+ llistPush(name);\
+ fread(&llistLast(name), 1, UNIQVAR(elemSz), file);\
+ }\
+ } while(0)
+
diff --git a/linkedListe.h b/linkedListe.h
@@ -0,0 +1,515 @@
+
+/**
+ * \file
+ *
+ * double linked list with external dArray: lliste
+ *
+ * the nodes in lliste are linked with pointers and dynamically allocated in segments in a shared dArray,
+ * so multiple lists can be stored in single dArray making free node reuse more efficient
+ *
+ * the element type handled by the list is defined with llisteT
+ *
+ * the external node and free node storage must be allocated after declaring the first list and before running llisteStoreIinit
+ *
+ * Example:
+ *
+ * // define list:
+ * llisteT(llt, u32);
+ *
+ * // declare list:
+ * llt ll;
+ *
+ * // initialize:
+ * llisteInit(&ll);
+ *
+ * // push element:
+ * llistePush(&ll);
+ * llisteLast(&ll) = 1;
+ *
+ * // Pop/dellast element:
+ * llistePop(&ll);
+ *
+ * // Free
+ * llisteFree(&ll);
+ *
+ * // define list:
+ * llisteT(llet, u32);
+ *
+ * // declare list:
+ * llet lle;
+ *
+ * // initialize node storage
+ * // local
+ * llisteNodesT(&lle) nodeStore;
+ * llisteFreeNodesT(&lle) freeNodeStore;
+ * llisteStoreInit(&nodeStore, &freeNodeStore);
+ *
+ * // or on heap
+ * llisteNodesPtrT(&lle) nodeStore;
+ * llisteFreeNodesPtrT(&lle) freeNodeStore;
+ * nodeStore = malloc(sizeof(llisteNodesT(&lle)));
+ * freeNodeStore = malloc(sizeof(llisteFreeNodesT(&lle)));
+ *
+ * // initialize:
+ * llisteInit(&lle, &nodeStore, &freeNodeStore);
+ *
+ * // push element:
+ * llistePush(&lle);
+ * llisteLast(&lle) = 1;
+ *
+ * // Pop/delleast element:
+ * llistePop(&lle);
+ *
+ * // Free
+ * llisteFree(&lle);
+ *
+ * // free node storage, after this all lists using this storage are invalid
+ * llisteStoreFree(&nodeStore, &freeNodeStore);
+ *
+ *
+ * TODO add node count like singlelist
+ * TODO create linkedList without head and last
+ * TODO create a free macro that takes a free function in parameter
+ */
+
+#include "libsheepyObject.h"
+
+/**
+ * list and node definition
+ */
+#define llisteT(typeName, elementType)\
+ typ struct UNIQVAR(nodet) UNIQVAR(nodet);\
+ struct UNIQVAR(nodet) {\
+ elementType elem;\
+ UNIQVAR(nodet) *prev;\
+ UNIQVAR(nodet) *next;\
+ };\
+ dArrayT(UNIQVAR(aNodet), UNIQVAR(nodet));\
+ dArrayT(UNIQVAR(freeaNodet), UNIQVAR(nodet)*);\
+ typ struct {\
+ UNIQVAR(nodet) *head;\
+ UNIQVAR(nodet) *last;\
+ UNIQVAR(aNodet) *list;\
+ UNIQVAR(freeaNodet) *freeList;\
+ } typeName
+
+/** dArray type for storing the nodes */
+#define llisteNodesT(name) typeof(*(name)->list)
+
+/** pointer type to dArray storing the nodes */
+#define llisteNodesPtrT(name) typeof((name)->list)
+
+/** dArray type for storing the free nodes */
+#define llisteFreeNodesT(name) typeof(*(name)->freeList)
+
+/** pointer type to dArray storing the free nodes */
+#define llisteFreeNodesPtrT(name) typeof((name)->freeList)
+
+/**
+ * initialize the dArrays storing the nodes for all the lists
+ */
+#define llisteStoreInit(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 llisteStoreFree(nodes, freeNodes) do{\
+ dArrayFree(nodes);\
+ dArrayFree(freeNodes);\
+ } while(0)
+
+/**
+ * initialize list
+ *
+ * nodes and freeNodes must be initialized once before calling llisteInit
+ *
+ */
+#define llisteInit(name, nodes, freeNodes) do{\
+ (name)->head = (name)->last = NULL;\
+ (name)->list = nodes;\
+ (name)->freeList = freeNodes;\
+ } while(0)
+
+/**
+ * free list nodes
+ * free and reset internal structures
+ *
+ * the dArrays storing the nodes are kept, use llisteStoreFree to free them
+ */
+#define llisteFree(name) do{\
+ llisteForEachDown(name, UNIQVAR(node)) {\
+ dArrayAppend((name)->freeList, UNIQVAR(node));\
+ }\
+ (name)->head = NULL;\
+ (name)->last = NULL;\
+ } while(0)
+
+/**
+ * node type for declaring pointers to nodes
+ *
+ * Example:
+ * llisteNodeType(name) node;
+ * llisteUnlink(name, node);
+ * */
+#define llisteNodeType(name) typeof((name)->head)
+
+// /** TODO
+// * element count in list
+// */
+// #define llisteCount(name) (name)->count
+
+
+/**
+ * is list empty
+ */
+#define llisteIsEmpty(name) dArrayIsEmpty((name)->list)
+
+/**
+ * push element to list (only allocates node)
+ * use llisteLast to access the element
+ */
+#define llistePush(name) do{\
+ if (dArrayIsEmpty((name)->freeList)) {\
+ dArrayPush((name)->list);\
+ if (!(name)->last) {\
+ /* first node */\
+ dArrayLast((name)->list).prev = NULL;\
+ dArrayLast((name)->list).next = NULL;\
+ (name)->head = &dArrayLast((name)->list);\
+ (name)->last = &dArrayLast((name)->list);\
+ }\
+ else {\
+ /* link to previous node */\
+ dArrayLast((name)->list).prev = (name)->last;\
+ (name)->last->next = &dArrayLast((name)->list);\
+ dArrayLast((name)->list).next = NULL;\
+ (name)->last = &dArrayLast((name)->list);\
+ }\
+ }\
+ else {\
+ /* reuse a free node */\
+ if (!(name)->last) {\
+ dArrayLast((name)->freeList)->prev = NULL;\
+ dArrayLast((name)->freeList)->next = NULL;\
+ (name)->head = dArrayLast((name)->freeList);\
+ (name)->last = dArrayLast((name)->freeList);\
+ }\
+ else {\
+ dArrayLast((name)->freeList)->prev = (name)->last;\
+ (name)->last->next = dArrayLast((name)->freeList);\
+ dArrayLast((name)->freeList)->next = NULL;\
+ (name)->last = dArrayLast((name)->freeList);\
+ }\
+ dArrayPop((name)->freeList);\
+ }\
+ } while(0)
+
+/**
+ * pop element from list (only free node)
+ *
+ * \return
+ * true success, false failed: the list is empty
+ */
+#define llistePop(name) ({\
+ bool UNIQVAR(r) = true;\
+ if (!(name)->last) {\
+ /* the list is empty */\
+ UNIQVAR(r) = false;\
+ goto UNIQVAR(end);\
+ }\
+ dArrayPush((name)->freeList);\
+ dArrayLast((name)->freeList) = (name)->last;\
+ (name)->last = (name)->last->prev;\
+ if ((name)->last) (name)->last->next = NULL;\
+ if (!(name)->last) /* the list is empty */ (name)->head = NULL;\
+ UNIQVAR(end):\
+ UNIQVAR(r);\
+ })
+
+#define llisteDelLast llistePop
+
+/**
+ * unlink node
+ *
+ * node must be of type llisteNodeType(name)
+ *
+ * the node can be freed with llisteFreeUnlinked or
+ * inserted in the list with llisteInsertAfter or llisteInsertBefore
+ */
+#define llisteUnlink(name, node) do{\
+ if (!(node)->prev) {\
+ /* node is head */\
+ (name)->head = (node)->next;\
+ }\
+ else {\
+ (node)->prev->next = (node)->next;\
+ }\
+ if (!(node)->next) {\
+ /* node is last */\
+ (name)->last = (node)->prev;\
+ }\
+ else {\
+ (node)->next->prev = (node)->prev;\
+ }\
+ } while(0)
+
+/**
+ * free unlinked node
+ *
+ * node must be of type llisteNodeType(name)
+ */
+#define llisteFreeUnlinked(name, node) do{\
+ dArrayPush((name)->freeList);\
+ dArrayLast((name)->freeList) = node;\
+ } while(0)
+
+/**
+ * delete node
+ *
+ * node must be of type llisteNodeType(name)
+ *
+ * unlink and free node
+ */
+#define llisteDelNode(name, node) do{\
+ llisteUnlink(name, node);\
+ llisteFreeUnlinked(name, node);\
+ } while(0)
+
+/** first element */
+#define llisteFirst(name) (name)->head->elem
+
+/** first node pointer */
+#define llisteFirstNode(name) (name)->head
+#define llisteHeadNode llisteFirstNode
+
+/** last element */
+#define llisteLast(name) (name)->last->elem
+
+/** last node pointer */
+#define llisteLasttNode(name) (name)->last
+
+/** previous node */
+#define llistePrev(node) (node)->prev
+
+/** next node */
+#define llisteNext(node) (node)->next
+
+/** node element (or use node->elem) */
+#define llisteGetElem(node) (node)->elem
+
+/**
+ * swap node1 with node2
+ */
+#define llisteSwap(name, node1, node2) do{\
+ /* disable sanity checks to keep it simple - if (!node1 or !node2) {*/\
+ /* return value instead --- (name)->res = false;*/\
+ /* break;*/\
+ /*}*/\
+ if (node1 == node2) /* node1 and node2 are the same node, nothing to do */ break;\
+ var UNIQVAR(tmp) = (node1)->next;\
+ (node1)->next = (node2)->next;\
+ (node2)->next = UNIQVAR(tmp);\
+ if (!(node1)->next) (name)->last = node1;\
+ else (node1)->next->prev = node1;\
+ if (!(node2)->next) (name)->last = node2;\
+ else (node2)->next->prev = node2;\
+ UNIQVAR(tmp) = (node1)->prev;\
+ (node1)->prev = (node2)->prev;\
+ (node2)->prev = UNIQVAR(tmp);\
+ if (!(node1)->prev) (name)->head = node1;\
+ else (node1)->prev->next = node1;\
+ if (!(node2)->prev) (name)->head = node2;\
+ else (node2)->prev->next = node2;\
+ } while(0)
+
+/** loop from head to last */
+#define llisteForEach(name, node)\
+ for(var node = (name)->head; node ; node = llisteNext(node))
+
+/** loop from last to head */
+#define llisteForEachDown(name, node)\
+ for(var node = (name)->last; node ; node = llistePrev(node))
+
+/** loop from startNode to last */
+#define llisteForEachFrom(node, startNode)\
+ for(var node = startNode; node ; node = (node)->next)
+
+/** loop from startNode to head */
+#define llisteForEachFromDown(node, startNode)\
+ for(var node = startNode; node ; node = (node)->prev)
+
+/**
+ * insert nodeToInsert after referenceNode
+ *
+ * nodeToInsert and referenceNode must be of type llisteNodeType(name)
+ */
+#define llisteInsertAfter(name, referenceNode, nodeToInsert) do{\
+ (nodeToInsert)->next = referenceNode->next;\
+ referenceNode->next = nodeToInsert;\
+ (nodeToInsert)->prev = referenceNode;\
+ if ((nodeToInsert)->next) {\
+ (nodeToInsert)->next->prev = nodeToInsert;\
+ }\
+ else {\
+ /* referenceNode was last node */\
+ (name)->last = nodeToInsert;\
+ }\
+ } while(0)
+
+/**
+ * insert nodeToInsert before referenceNode
+ *
+ * nodeToInsert and referenceNode must be of type llisteNodeType(name)
+ */
+#define llisteInsertBefore(name, referenceNode, nodeToInsert) do{\
+ (nodeToInsert)->prev = referenceNode->prev;\
+ referenceNode->prev = nodeToInsert;\
+ (nodeToInsert)->next = referenceNode;\
+ if ((nodeToInsert)->prev) {\
+ (nodeToInsert)->prev->next = nodeToInsert;\
+ }\
+ else {\
+ /* referenceNode was head node */\
+ (name)->head = nodeToInsert;\
+ }\
+ } while(0)
+
+
+// Internal
+// allocate a node
+#define llisteAddNode(name, resultNode) do{\
+ if (dArrayIsEmpty((name)->freeList)) {\
+ dArrayPush((name)->list);\
+ resultNode = &dArrayLast((name)->list);\
+ }\
+ else {\
+ /* reuse a free node */\
+ resultNode = dArrayLast((name)->freeList);\
+ dArrayPop((name)->freeList);\
+ }\
+ } while(0)
+
+/**
+ * add new node after referenceNode
+ *
+ * resultNode and referenceNode must be of type llisteNodeType(name)
+ *
+ * \return
+ * resultNode access element in node with resultNode->elem or llisteGetElem(resultNode)
+ */
+#define llisteAddAfter(name, referenceNode, resultNode) do{\
+ llisteAddNode(name, resultNode);\
+ (resultNode)->next = referenceNode->next;\
+ referenceNode->next = resultNode;\
+ (resultNode)->prev = referenceNode;\
+ if ((resultNode)->next) {\
+ (resultNode)->next->prev = resultNode;\
+ }\
+ else {\
+ /* referenceNode was last node */\
+ (name)->last = resultNode;\
+ }\
+ } while(0)
+
+/**
+ * add new node before referenceNode
+ *
+ * resultNode and referenceNode must be of type llisteNodeType(name)
+ *
+ * \return
+ * resultNode access element in node with resultNode->elem or llisteGetElem(resultNode)
+ */
+#define llisteAddBefore(name, referenceNode, resultNode) do{\
+ llisteAddNode(name, resultNode);\
+ (resultNode)->prev = referenceNode->prev;\
+ referenceNode->prev = resultNode;\
+ (resultNode)->next = referenceNode;\
+ if ((resultNode)->prev) {\
+ (resultNode)->prev->next = resultNode;\
+ }\
+ else {\
+ /* referenceNode was head node */\
+ (name)->head = resultNode;\
+ }\
+ } while(0)
+
+/**
+ * write the lliste content to filename file
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * filename file name string
+ */
+#define llisteWriteFilename(name, filename) do {\
+ FILE *UNIQVAR(f) = fopen(filename, "w");\
+ if (UNIQVAR(f)) {\
+ llisteForEach(name, UNIQVAR(node)) {\
+ fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), UNIQVAR(f));\
+ }\
+ fclose(UNIQVAR(f));\
+ }\
+ } while(0)
+
+/**
+ * write the lliste content to disk
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * file already opened file
+ */
+#define llisteWrite(name, file) do {\
+ llisteForEach(name, UNIQVAR(node)) {\
+ fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), file);\
+ }\
+ } while(0)
+
+/**
+ * read a lliste from filename file
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * filename file name string
+ */
+#define llisteReadFilename(name, filename) do {\
+ if (fileExists(filename)) {\
+ size_t UNIQVAR(sz) = fileSize(filename);\
+ const size_t UNIQVAR(elemSz) = sizeof(dArrayLast((name)->list).elem);\
+ if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
+ UNIQVAR(sz) /= UNIQVAR(elemSz);\
+ if (UNIQVAR(sz) > (size_t)(name)->list.maxCount) /* file size exceeds capacity */ break;\
+ FILE *UNIQVAR(f) = fopen(filename, "r");\
+ if (UNIQVAR(f)) {\
+ range(UNIQVAR(i), UNIQVAR(sz)) {\
+ llistePush(name);\
+ fread(&llisteLast(name), 1, UNIQVAR(elemSz), UNIQVAR(f));\
+ }\
+ fclose(UNIQVAR(f));\
+ }\
+ }\
+ } while(0)
+
+/**
+ * read a lliste from disk
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * file already opened file
+ */
+#define llisteRead(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(dArrayLast((name)->list).elem);\
+ if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
+ UNIQVAR(sz) /= UNIQVAR(elemSz);\
+ if (UNIQVAR(sz) > (size_t)(name)->list.maxCount) /* file size exceeds capacity */ break;\
+ range(UNIQVAR(i), UNIQVAR(sz)) {\
+ llistePush(name);\
+ fread(&llisteLast(name), 1, UNIQVAR(elemSz), file);\
+ }\
+ } while(0)
+
diff --git a/main.c b/main.c
@@ -0,0 +1,84 @@
+#! /usr/bin/env sheepy
+/* or direct path to sheepy: #! /usr/local/bin/sheepy */
+
+/* Libsheepy documentation: http://spartatek.se/libsheepy/ */
+#include "libsheepyObject.h"
+#include "linkedList.h"
+#include "linkedListe.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);
+
+
+ // llist linked list
+
+ // define list:
+ llistT(llt, u32);
+
+ // declare list:
+ llt ll;
+
+ // initialize:
+ llistInit(&ll);
+
+ // push element:
+ llistPush(&ll);
+ llistLast(&ll) = 1;
+
+ // Pop/dellast element:
+ llistPop(&ll);
+
+ // Free
+ llistFree(&ll);
+
+
+
+
+
+ // lliste linked list with external storage
+
+ // define list:
+ llisteT(llet, u32);
+
+ // declare list:
+ llet lle;
+
+ // initialize node storage
+ // local
+ llisteNodesT(&lle) nodeStore;
+ llisteFreeNodesT(&lle) freeNodeStore;
+ llisteStoreInit(&nodeStore, &freeNodeStore);
+
+ /* // or on heap */
+ /* llisteNodesPtrT(&lle) nodeStore; */
+ /* llisteFreeNodesPtrT(&lle) freeNodeStore; */
+ /* nodeStore = malloc(sizeof(llisteNodesT(&lle))); */
+ /* freeNodeStore = malloc(sizeof(llisteFreeNodesT(&lle))); */
+
+ // initialize:
+ llisteInit(&lle, &nodeStore, &freeNodeStore);
+
+ // push element:
+ llistePush(&lle);
+ llisteLast(&lle) = 1;
+
+ // Pop/delleast element:
+ llistePop(&lle);
+
+ // Free
+ llisteFree(&lle);
+
+ // free node storage, after this all lists using this storage are invalid
+ llisteStoreFree(&nodeStore, &freeNodeStore);
+
+}
+// vim: set expandtab ts=2 sw=2:
diff --git a/package.yml b/package.yml
@@ -0,0 +1,31 @@
+---
+ name: linkedList
+ version: 0.0.1
+ description: "double linked lists"
+ bin: ./linkedList.h
+ #cflags: -DA -ggdb -std=gnu11 -fPIC -pipe
+ #lflags: -lpcre
+ repository:
+ type: git
+ url: git+https://github.com/RemyNoulin/linkedList.git
+ keywords:
+ - data structure
+ author: Remy Noulin
+ license: MIT
+ bugs:
+ url: https://github.com/RemyNoulin/linkedList/issues
+ homepage: https://github.com/RemyNoulin/linkedList#readme
+ #compileHelp: # text displayed when there is a compilation error
+ #dependencies:
+ # md4c:
+ # Test configuration:
+ #testBin: ./testLinkedList.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: ./memcheckLinkedList.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
