staticList

commit 21834cd8b2ed0b1c07a8253c7fe2385555dbbbe8
parent 3ba24c6bb59c02032f00bb5e63ece07b4b917cba
Author: Remy Noulin <loader2x@gmail.com>
Date:   Sun, 20 May 2018 10:49:27 +0200

staticList library

main.c       | 195 +++++++++++++++++++++++++
package.yml  |  17 +++
staticList.h | 465 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 677 insertions(+)

Diffstat:
A
main.c
 | 
195
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
package.yml
 | 
17
+++++++++++++++++
A
staticList.h
 | 
465
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

3 files changed, 677 insertions(+), 0 deletions(-)
diff --git a/main.c b/main.c
@@ -0,0 +1,195 @@
+#! /usr/bin/env sheepy
+/* or direct path to sheepy: #! /usr/local/bin/sheepy */
+
+#include "libsheepyObject.h"
+#include "staticList.h"
+
+int argc; char **argv;
+
+int main(int ARGC, char** ARGV) {
+
+  argc = ARGC; argv = ARGV;
+
+  initLibsheepy(argv[0]);
+  setLogMode(LOG_FUNC);
+
+  puts("C template");
+
+  staticListT(slt, u32, 3);
+  slt sl;
+
+  staticListInit(sl);
+
+  logPtr(sl.head);
+  logPtr(sl.last);
+  staticListPush(sl);
+  staticListLast(sl) = 1;
+  logPtr(sl.head);
+  logPtr(sl.last);
+  staticListPush(sl);
+  staticListLast(sl) = 10;
+  logPtr(sl.head);
+  logPtr(sl.last);
+  staticListPop(sl);
+  logPtr(sl.head);
+  logPtr(sl.last);
+  staticListPop(sl);
+  logPtr(sl.head);
+  logPtr(sl.last);
+  staticListPop(sl);
+
+
+  logPtr(sl.head);
+  logPtr(sl.last);
+  staticListPush(sl);
+  staticListLast(sl) = 1;
+  logPtr(sl.head);
+  logPtr(sl.head->next);
+  logPtr(sl.head->prev);
+  logPtr(sl.last);
+  logPtr(sl.last->next);
+  logPtr(sl.last->prev);
+  staticListPush(sl);
+  staticListLast(sl) = 10;
+  logPtr(sl.head);
+  logPtr(sl.head->next);
+  logPtr(sl.head->prev);
+  logPtr(sl.last);
+  logPtr(sl.last->next);
+  logPtr(sl.last->prev);
+  staticListPush(sl);
+  staticListLast(sl) = 100;
+  logPtr(sl.head);
+  logPtr(sl.head->next);
+  logPtr(sl.head->prev);
+  logPtr(sl.last);
+  logPtr(sl.last->next);
+  logPtr(sl.last->prev);
+  logPtr(sl.last->prev->prev);
+  logPtr(sl.last->prev->next);
+  var idx = sl.head->next;
+  staticListDelNode(sl, idx);
+  logPtr(sl.head);
+  logPtr(sl.head->next);
+  logPtr(sl.head->prev);
+  logPtr(sl.last);
+  logPtr(sl.last->next);
+  logPtr(sl.last->prev);
+  idx = sl.head;
+  staticListDelNode(sl, idx);
+  logPtr(sl.head);
+  logPtr(sl.head->next);
+  logPtr(sl.head->prev);
+  logPtr(sl.last);
+  logPtr(sl.last->next);
+  logPtr(sl.last->prev);
+  idx = sl.head;
+  staticListDelNode(sl, idx);
+  logPtr(sl.head);
+  logPtr(sl.last);
+
+
+  logPtr(sl.head);
+  logPtr(sl.last);
+  staticListPush(sl);
+  staticListLast(sl) = 1;
+  logPtr(sl.head);
+  logPtr(sl.last);
+  staticListPush(sl);
+  staticListLast(sl) = 10;
+  logPtr(sl.head);
+  logPtr(sl.last);
+  staticListPush(sl);
+  staticListLast(sl) = 100;
+  logPtr(sl.head);
+  logPtr(sl.last);
+
+  staticListForEach(sl, e) {
+    logVarG(e->elem);
+  }
+
+  logPtr(sl.head);
+  logPtr(sl.head->next);
+  logPtr(sl.head->prev);
+  logPtr(sl.last);
+  logPtr(sl.last->next);
+  logPtr(sl.last->prev);
+  logPtr(sl.last->prev->prev);
+  logPtr(sl.last->prev->next);
+  var e1 = sl.head;
+  var e2 = sl.last;
+  logI("\nswap");
+  staticListSwap(sl, e1, e2);
+  logPtr(sl.head);
+  logPtr(sl.head->next);
+  logPtr(sl.head->prev);
+  logPtr(sl.last);
+  logPtr(sl.last->next);
+  logPtr(sl.last->prev);
+  logPtr(sl.last->prev->prev);
+  logPtr(sl.last->prev->next);
+  staticListForEach(sl, e) {
+    logVarG(e->elem);
+  }
+
+  e1 = sl.head;
+  e2 = sl.head->next;
+  logI("\nswap");
+  staticListSwap(sl, e1, e2);
+  staticListForEach(sl, e) {
+    logVarG(e->elem);
+  }
+
+  e1 = sl.last;
+  e2 = sl.last->prev;
+  logI("\nswap");
+  staticListSwap(sl, e1, e2);
+  staticListForEach(sl, e) {
+    logVarG(e->elem);
+  }
+
+  staticListPop(sl);
+  logI("pop");
+  staticListForEach(sl, e) {
+    logVarG(e->elem);
+  }
+
+  e1 = sl.head;
+  e2 = sl.last;
+  logI("\nswap");
+  staticListSwap(sl, e1, e2);
+  staticListForEach(sl, e) {
+    logVarG(e->elem);
+  }
+
+  put
+  logI("unlink head");
+  staticListPush(sl);
+  staticListLast(sl) = 100;
+  put
+  staticListForEach(sl, e) {
+    logVarG(e->elem);
+  }
+  e1 = sl.head;
+  staticListUnlink(sl, e1);
+  e2 = sl.last;
+  staticListInsertAfter(sl, e2, e1);
+  put
+  staticListForEach(sl, e) {
+    logVarG(e->elem);
+  }
+
+  put
+  logI("unlink last");
+  e1 = sl.last;
+  staticListUnlink(sl, e1);
+  e2 = sl.head;
+  staticListInsertAfter(sl, e2, e1);
+  put
+  staticListForEach(sl, e) {
+    logVarG(e->elem);
+  }
+
+  /* staticListWriteFilename(sl, "linked.bin"); */
+  /* staticListReadFilename(sl, "linked.bin"); */
+}
diff --git a/package.yml b/package.yml
@@ -0,0 +1,17 @@
+---
+  name: staticList
+  version: 0.0.11
+  description: "macros of double linked list with defined maximum length supporting any type, this list doesnt use malloc"
+  bin: ./staticList.h
+  #cflags: -DA -ggdb -std=gnu11 -fPIC -pipe
+  #lflags: -rdynamic # debug
+  repository:
+    type: git
+    url: git+https://github.com/RemyNoulin/staticList.git
+  keywords:
+    - data structure
+  author: Remy
+  license: MIT
+  bugs:
+    url: https://github.com/RemyNoulin/staticList/issues
+  homepage: https://github.com/RemyNoulin/staticList#readme
diff --git a/staticList.h b/staticList.h
@@ -0,0 +1,465 @@
+
+/**
+ * \file
+ *
+ * Static double linked list
+ *
+ * NOTE: The macros in this file are for creating list functions wrapping the macros.
+ *    The parameters to these macros should be variables to avoid wrong computation
+ *    and infinite loops.
+ *    Example:
+ *    staticListDelNode(list, list.head) fails because list.head changes value during the
+ *    macro execution.
+ *
+ * The number of nodes is defined at list declaration, all the nodes are preallocated.
+ * The heap is not used, there is no malloc, realloc or free.
+ *
+ * The status of the macros is saved (list).res and is set to true when the operation is success and
+ * false when the operation is failure.
+ *
+ * The element type handled by the list is defined with staticListT
+ *
+ * Example:
+ *
+ * define list:
+ * staticListT(slt, u32, 3);
+ *
+ * declare list:
+ * slt sl;
+ *
+ * initialize:
+ * staticListInit(sl);
+ *
+ * push element:
+ * staticListPush(sl);
+ * staticListLast(sl) = 1;
+ *
+ * Pop/dellast element:
+ * staticListPop(sl);
+ */
+
+#include "libsheepyObject.h"
+
+/**
+ * list and node definition
+ *
+ * MAXCOUNT is the list capacity
+ */
+#define staticListT(typeName, elementType, MAXCOUNT)\
+  typ struct UNIQVAR(nodet) UNIQVAR(nodet);\
+  struct UNIQVAR(nodet) {\
+    elementType elem;\
+    UNIQVAR(nodet) *prev;\
+    UNIQVAR(nodet) *next;\
+  };\
+  staticArrayT(UNIQVAR(aNodet), UNIQVAR(nodet), MAXCOUNT);\
+  staticArrayT(UNIQVAR(freeaNodet), UNIQVAR(nodet)*, MAXCOUNT);\
+  typ struct {\
+    UNIQVAR(nodet)      *head;\
+    UNIQVAR(nodet)      *last;\
+    UNIQVAR(aNodet)     list;\
+    UNIQVAR(freeaNodet) freeList;\
+    bool                res;\
+  } typeName
+
+/**
+ * initialize list
+ *
+ * \return
+ *  (name).res true success, false failed
+ */
+#define staticListInit(name) do{\
+    (name).head = (name).last = NULL;\
+    staticArrayInit((name).list)\
+    staticArrayInit((name).freeList);\
+    (name).res  = true;\
+  } while(0)
+
+/**
+ * node type for declaring pointers to nodes
+ *
+ * Example:
+ * staticListNodeType(name) node;
+ * staticListUnlink(name, node);
+ * */
+#define staticListNodeType(name) typeof((name).head)
+
+/**
+ * is list empty
+ */
+#define staticListIsEmpty(name) (staticArrayIsEmpty((name).list) || staticArrayIsFull((name).freeList))
+
+/**
+ * is list full
+ */
+#define staticListIsFull(name) (staticArrayIsFull((name).list) && staticArrayIsEmpty((name).freeList))
+
+/**
+ * push element to list (only allocates node)
+ * use staticListLast to access the element
+ *
+ * \return
+ *  (name).res true success, false failed
+ */
+#define staticListPush(name) do{\
+  if (staticArrayIsEmpty((name).freeList)) {\
+    if (staticArrayIsFull((name).list)) {\
+      /* the list is full */\
+      (name).res = false;\
+      break;\
+    }\
+    staticArrayPush((name).list);\
+    if (!(name).last) {\
+      /* first node */\
+      staticArrayLast((name).list).prev = NULL;\
+      staticArrayLast((name).list).next = NULL;\
+      (name).head                = &staticArrayLast((name).list);\
+      (name).last                = &staticArrayLast((name).list);\
+    }\
+    else {\
+      /* link to previous node */\
+      staticArrayLast((name).list).prev = (name).last;\
+      (name).last->next                 = &staticArrayLast((name).list);\
+      staticArrayLast((name).list).next = NULL;\
+      (name).last                       = &staticArrayLast((name).list);\
+    }\
+  }\
+  else {\
+    /* reuse a free node */\
+    if (!(name).last) {\
+      staticArrayLast((name).freeList)->prev = NULL;\
+      staticArrayLast((name).freeList)->next = NULL;\
+      (name).head                = staticArrayLast((name).freeList);\
+      (name).last                = staticArrayLast((name).freeList);\
+    }\
+    else {\
+      staticArrayLast((name).freeList)->prev = (name).last;\
+      (name).last->next                                                  = staticArrayLast((name).freeList);\
+      staticArrayLast((name).freeList)->next = NULL;\
+      (name).last                                                        = staticArrayLast((name).freeList);\
+    }\
+    staticArrayPop((name).freeList);\
+  }\
+  (name).res = true;\
+  } while(0)
+
+/**
+ * pop element from list (only free node)
+ *
+ * \return
+ *  (name).res true success, false failed: the list is empty
+ */
+#define staticListPop(name) do{\
+  if (!(name).last) {\
+    /* the list is empty */\
+    (name).res = false;\
+    break;\
+  }\
+  staticArrayPush((name).freeList);\
+  staticArrayLast((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;\
+  (name).res = true;\
+  } while(0)
+
+#define staticListDelLast staticListPop
+
+/**
+ * unlink node
+ *
+ * node must be of type staticListNodeType(name)
+ *
+ * the node can be freed with staticListFreeUnlinked or
+ * inserted in the list with staticListInsertAfter or staticListInsertBefore
+ */
+#define staticListUnlink(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 staticListNodeType(name)
+ */
+#define staticListFreeUnlinked(name, node) do{\
+  staticArrayPush((name).freeList);\
+  staticArrayLast((name).freeList) = node;\
+  } while(0)
+
+/**
+ * delete node
+ *
+ * node must be of type staticListNodeType(name)
+ *
+ * unlink and free node
+ */
+#define staticListDelNode(name, node) do{\
+  staticListUnlink(name, node);\
+  staticListFreeUnlinked(name, node);\
+  (name).res = true;\
+  } while(0)
+
+/** first element */
+#define staticListFirst(name) (name).head->elem
+
+/** first node pointer */
+#define staticListFirstNode(name) (name).head
+#define staticListHeadNode staticListFirstNode
+
+/** last element */
+#define staticListLast(name) (name).last->elem
+
+/** last node pointer */
+#define staticListLasttNode(name) (name).last
+
+/** previous node */
+#define staticListPrev(node) (node)->prev
+
+/** next node */
+#define staticListNext(node) (node)->next
+
+/** node element (or use node->elem) */
+#define staticListGetElem(node) (node)->elem
+
+/**
+ * swap node1 with node2
+ *
+ * \return
+ *  (name).res true success, false failed
+ */
+#define staticListSwap(name, node1, node2) do{\
+  /* disable sanity checks to keep it simple - if (!node1 or !node2) {*/\
+  /*  (name).res = false;*/\
+  /*  break;*/\
+  /*}*/\
+  (name).res = true;\
+  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 staticListForEach(name, node)\
+  for(var node = (name).head; node ; node = staticListNext(node))
+
+/** loop from last to head */
+#define staticListForEachDown(name, node)\
+  for(var node = (name).last; node ; node = staticListPrev(node))
+
+/** loop from startNode to last */
+#define staticListForEachFrom(node, startNode)\
+  for(var node = startNode; node ; node = (node)->next)
+
+/** loop from startNode to head */
+#define staticListForEachFromDown(node, startNode)\
+  for(var node = startNode; node ; node = (node)->prev)
+
+/**
+ * insert nodeToInsert after referenceNode
+ *
+ * nodeToInsert and referenceNode must be of type staticListNodeType(name)
+ */
+#define staticListInsertAfter(name, referenceNode, nodeToInsert) do{\
+  var UNIQVAR(tmp)      = referenceNode->next;\
+  referenceNode->next   = nodeToInsert;\
+  (nodeToInsert)->prev  = referenceNode;\
+  (nodeToInsert)->next  = UNIQVAR(tmp);\
+  if (UNIQVAR(tmp)) {\
+    UNIQVAR(tmp)->prev = nodeToInsert;\
+  }\
+  else {\
+    /* referenceNode was last node */\
+    (name).last = nodeToInsert;\
+  }\
+  } while(0)
+
+/**
+ * insert nodeToInsert before referenceNode
+ *
+ * nodeToInsert and referenceNode must be of type staticListNodeType(name)
+ */
+#define staticListInsertBefore(name, referenceNode, nodeToInsert) do{\
+  var UNIQVAR(tmp)      = referenceNode->prev;\
+  referenceNode->prev   = nodeToInsert;\
+  (nodeToInsert)->next  = referenceNode;\
+  (nodeToInsert)->prev  = UNIQVAR(tmp);\
+  if (UNIQVAR(tmp)) {\
+    UNIQVAR(tmp)->next = nodeToInsert;\
+  }\
+  else {\
+    /* referenceNode was head node */\
+    (name).head = nodeToInsert;\
+  }\
+  } while(0)
+
+
+// Internal
+// allocate a node
+// true success, false failed: list is full
+#define staticListAddNode(name, resultNode) do{\
+  if (staticArrayIsEmpty((name).freeList)) {\
+    if (staticArrayIsFull((name).list)) {\
+      /* the list is full */\
+      (name).res = false;\
+      break;\
+    }\
+    staticArrayPush((name).list);\
+    resultNode = &staticArrayLast((name).list);\
+  }\
+  else {\
+    /* reuse a free node */\
+    resultNode = staticArrayLast((name).freeList);\
+    staticArrayPop((name).freeList);\
+  }\
+  (name).res = true;\
+  } while(0)
+
+/**
+ * add new node after referenceNode
+ *
+ * resultNode and referenceNode must be of type staticListNodeType(name)
+ *
+ * \return
+ *   resultNode access element in node with resultNode->elem or staticListGetElem(resultNode)
+ */
+#define staticListAddAfter(name, referenceNode, resultNode) do{\
+  staticListAddNode(name, resultNode);\
+  if (!(name).res) /* list is full, return false */ break;\
+  var UNIQVAR(tmp)    = referenceNode->next;\
+  referenceNode->next = resultNode;\
+  (resultNode)->prev  = referenceNode;\
+  (resultNode)->next  = UNIQVAR(tmp);\
+  if (UNIQVAR(tmp)) {\
+    UNIQVAR(tmp)->prev = resultNode;\
+  }\
+  else {\
+    /* referenceNode was last node */\
+    (name).last = resultNode;\
+  }\
+  } while(0)
+
+/**
+ * add new node before referenceNode
+ *
+ * resultNode and referenceNode must be of type staticListNodeType(name)
+ *
+ * \return
+ *   resultNode access element in node with resultNode->elem or staticListGetElem(resultNode)
+ */
+#define staticListAddBefore(name, referenceNode, resultNode) do{\
+  staticListAddNode(name, resultNode);\
+  if (!(name).res) /* list is full, return false */ break;\
+  var UNIQVAR(tmp)      = referenceNode->prev;\
+  referenceNode->prev   = resultNode;\
+  (resultNode)->next  = referenceNode;\
+  (resultNode)->prev  = UNIQVAR(tmp);\
+  if (UNIQVAR(tmp)) {\
+    UNIQVAR(tmp)->next = resultNode;\
+  }\
+  else {\
+    /* referenceNode was head node */\
+    (name).head = resultNode;\
+  }\
+  } while(0)
+
+/**
+ * write the staticList content to filename file
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ *    filename file name string
+ */
+#define staticListWriteFilename(name, filename) do {\
+  FILE *UNIQVAR(f) = fopen(filename, "w");\
+  if (UNIQVAR(f)) {\
+    staticListForEach(name, UNIQVAR(node)) {\
+      fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), UNIQVAR(f));\
+    }\
+    fclose(UNIQVAR(f));\
+  }\
+  } while(0)
+
+/**
+ * write the staticList content to disk
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ *    file already opened file
+ */
+#define staticListWrite(name, file) do {\
+  staticListForEach(name, UNIQVAR(node)) {\
+    fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), file);\
+  }\
+  } while(0)
+
+/**
+ * read a staticList from filename file
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ * filename file name string
+ */
+#define staticListReadFilename(name, filename) do {\
+  if (fileExists(filename)) {\
+    size_t UNIQVAR(sz) = fileSize(filename);\
+    const size_t UNIQVAR(elemSz) = sizeof(staticArrayLast((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)) {\
+        staticListPush(name);\
+        fread(&staticListLast(name), 1, UNIQVAR(elemSz), UNIQVAR(f));\
+      }\
+      fclose(UNIQVAR(f));\
+    }\
+  }\
+  } while(0)
+
+/**
+ * read a staticList from disk
+ * No NULL checks are done on the parameters
+ *
+ * \param
+ *    file already opened file
+ */
+#define staticListRead(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(staticArrayLast((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)) {\
+    staticListPush(name);\
+    fread(&staticListLast(name), 1, UNIQVAR(elemSz), file);\
+  }\
+  } while(0)