Merge branch 'feature-list' into develop

3 files changed, 588 insertions, 0 deletions

diff --git a/README b/README
index 0988fc4..2519d27 100644
--- a/README
+++ b/README
@@ -112,6 +112,126 @@ Target/goal:
                      reverse order.                         
                                                         
   -list:
+     This object is a double link list.                     
+     methods:                                               
+       init(addr of the list, size per entry, list size)    
+          The list's type depends on what user want to store
+          . For example: if you want a list for int, you s- 
+          hould declare like "int* v", and call the init()  
+          like "init(&v, sizeof(int), 5)", which will creat 
+          a double link list with 5 elements.               
+                                                            
+       free(addr of the list)                               
+          Free the memory  the list use. You should call it 
+          when you don't need the container.                
+                                                            
+                                                            
+       getSize(addr of the list)                            
+          Return the number of elements.                    
+                                                            
+       getEntrySize(addr of the list)                       
+          Return the size per entry, it dependent on what   
+          type of data you store in the container.          
+                                                            
+       getFront(addr of the list)                           
+          Return a const pointer which point to the entry   
+          at the head of the list.                          
+                                                            
+       getBack(addr of the list)                            
+          Return a const pointer which point to the entry   
+          at the end of the list.                           
+                                                            
+       getBegin(addr of the list)                           
+          Return a pointer which point to the iterator at   
+          the head of the list.                             
+                                                            
+       getEnd(addr of the list)                             
+          Return a pointer which point to the iterator at   
+          the end of the list (which cannot be modified).   
+                                                            
+                                                            
+       setSize(addr of the list, new_size)                  
+          Resize the lsit to new_size at the back of the    
+          list. Note that it won't initalize the newly ele- 
+          ments when you increase the size.                 
+                                                            
+       setFront(addr of the list, data)                     
+          Let the first element be the data you given.      
+                                                            
+       setBack(addr of the list, data)                      
+          Let the last element be the data you given.       
+                                                            
+                                                            
+       addBack(addr of the list, data)                      
+          Add an element which contain data at the back of  
+          the list.                                         
+                                                            
+       delBack(addr of the list)                            
+          Remove the last element of the list.              
+                                                            
+       addFront(addr of the vector, data)                   
+          Add an element which contain data at the front of 
+          the list.                                         
+                                                            
+       delFront(addr of the list)                           
+          Remove the first element of the list.             
+                                                            
+                                                            
+       rm(addr of the list, addr of the iter1, iter2)       
+          Remove the part of iter1 ~ iter2 (include iter1   
+          but not iter2)                                    
+                                                            
+       copy(addr of the list, addr of the iter1, iter2,     
+            addr of the list2)                              
+          Create a new list which contain the part of the   
+          iter1 ~ iter2 (include iter1 but not iter2) and   
+          saved it to list2.                                
+                                                            
+       move(addr of the list, addr of the iter1, iter2,     
+            addr of the list2)                              
+          Move the part iter1 ~ iter2 to list2.             
+                                                            
+       swap(addr of the l1, addr of the iter. i1, i2,       
+            addr of the l2, addr of the iter. j1, j2)       
+          Swap the part of l1 from i1 to i2.previous and    
+          the part of l2 from j1 to j2.previous.            
+                                                            
+                                                            
+       iterGetEntry(addr of the iteator)                    
+          Return a const pointer which point to the data of 
+          the iterator.                                     
+                                                            
+       iterGetNext(addr of the iterator)                    
+          Return a pointer which point to the next iterator 
+                                                            
+       iterGetPrev(addr of the iterator)                    
+          Return a pointer which point to the previous ite- 
+          ator.                                             
+                                                            
+                                                            
+       iterSetEntry(addr of the iterator, data)             
+          Let the data which is stored in iterator be the   
+          data you given.                                   
+                                                            
+       iterGoNext(addr of the iterator)                     
+          Instead of return a pointer, it will change the   
+          pointer you given.                                
+                                                            
+       iterGoPrev(addr of the iterator)                     
+          Instead of return a pointer, it will change the   
+          pointer you given.                                
+                                                            
+                                                            
+       iterDel(addr of the iterator)                        
+          Delete the iterator you given, returning a pointer
+          to the next iterator                              
+                                                            
+       iterDelPrev(addr of the iterator)                    
+          Delete the previous of the iterator you given.    
+                                                            
+       iterDelPrev(addr of the iterator)                    
+          Delete the next of the iterator you given.        
+                                                            
   -stack:
   -queue:
   -dequeue:
diff --git a/include/list.h b/include/list.h
new file mode 100644
index 0000000..902a39c
--- /dev/null
+++ b/include/list.h
@@ -0,0 +1,200 @@
+#ifndef    __list_h__
+#define    __list_h__
+
+#include "utility.h"
+
+/**********************************************************/
+/* This object is a double link list.                     */
+/* methods:                                               */
+/*   init(addr of the list, size per entry, list size)    */
+/*      The list's type depends on what user want to store*/
+/*      . For example: if you want a list for int, you s- */
+/*      hould declare like "int* v", and call the init()  */
+/*      like "init(&v, sizeof(int), 5)", which will creat */
+/*      a double link list with 5 elements.               */
+/*                                                        */
+/*   free(addr of the list)                               */
+/*      Free the memory  the list use. You should call it */
+/*      when you don't need the container.                */
+/*                                                        */
+/*                                                        */
+/*   getSize(addr of the list)                            */
+/*      Return the number of elements.                    */
+/*                                                        */
+/*   getEntrySize(addr of the list)                       */
+/*      Return the size per entry, it dependent on what   */
+/*      type of data you store in the container.          */
+/*                                                        */
+/*   getFront(addr of the list)                           */
+/*      Return a const pointer which point to the entry   */
+/*      at the head of the list.                          */
+/*                                                        */
+/*   getBack(addr of the list)                            */
+/*      Return a const pointer which point to the entry   */
+/*      at the end of the list.                           */
+/*                                                        */
+/*   getBegin(addr of the list)                           */
+/*      Return a pointer which point to the iterator at   */
+/*      the head of the list.                             */
+/*                                                        */
+/*   getEnd(addr of the list)                             */
+/*      Return a pointer which point to the iterator at   */
+/*      the end of the list (which cannot be modified).   */
+/*                                                        */
+/*                                                        */
+/*   setSize(addr of the list, new_size)                  */
+/*      Resize the lsit to new_size at the back of the    */
+/*      list. Note that it won't initalize the newly ele- */
+/*      ments when you increase the size.                 */
+/*                                                        */
+/*   setFront(addr of the list, data)                     */
+/*      Let the first element be the data you given.      */
+/*                                                        */
+/*   setBack(addr of the list, data)                      */
+/*      Let the last element be the data you given.       */
+/*                                                        */
+/*                                                        */
+/*   addBack(addr of the list, data)                      */
+/*      Add an element which contain data at the back of  */
+/*      the list.                                         */
+/*                                                        */
+/*   delBack(addr of the list)                            */
+/*      Remove the last element of the list.              */
+/*                                                        */
+/*   addFront(addr of the vector, data)                   */
+/*      Add an element which contain data at the front of */
+/*      the list.                                         */
+/*                                                        */
+/*   delFront(addr of the list)                           */
+/*      Remove the first element of the list.             */
+/*                                                        */
+/*                                                        */
+/*   rm(addr of the list, addr of the iter1, iter2)       */
+/*      Remove the part of iter1 ~ iter2 (include iter1   */
+/*      but not iter2)                                    */
+/*                                                        */
+/*   copy(addr of the list, addr of the iter1, iter2,     */
+/*        addr of the list2)                              */
+/*      Create a new list which contain the part of the   */
+/*      iter1 ~ iter2 (include iter1 but not iter2) and   */
+/*      saved it to list2.                                */
+/*                                                        */
+/*   move(addr of the list, addr of the iter1, iter2,     */
+/*        addr of the list2)                              */
+/*      Move the part iter1 ~ iter2 to list2.             */
+/*                                                        */
+/*   swap(addr of the l1, addr of the iter. i1, i2,       */
+/*        addr of the l2, addr of the iter. j1, j2)       */
+/*      Swap the part of l1 from i1 to i2.previous and    */
+/*      the part of l2 from j1 to j2.previous.            */
+/*                                                        */
+/*                                                        */
+/*   iterGetEntry(addr of the iteator)                    */
+/*      Return a const pointer which point to the data of */
+/*      the iterator.                                     */
+/*                                                        */
+/*   iterGetNext(addr of the iterator)                    */
+/*      Return a pointer which point to the next iterator */
+/*                                                        */
+/*   iterGetPrev(addr of the iterator)                    */
+/*      Return a pointer which point to the previous ite- */
+/*      ator.                                             */
+/*                                                        */
+/*                                                        */
+/*   iterSetEntry(addr of the iterator, data)             */
+/*      Let the data which is stored in iterator be the   */
+/*      data you given.                                   */
+/*                                                        */
+/*   iterGoNext(addr of the iterator)                     */
+/*      Instead of return a pointer, it will change the   */
+/*      pointer you given.                                */
+/*                                                        */
+/*   iterGoPrev(addr of the iterator)                     */
+/*      Instead of return a pointer, it will change the   */
+/*      pointer you given.                                */
+/*                                                        */
+/*                                                        */
+/*   iterDel(addr of the iterator)                        */
+/*      Delete the iterator you given, returning a pointer*/
+/*      to the next iterator                              */
+/*                                                        */
+/*   iterDelPrev(addr of the iterator)                    */
+/*      Delete the previous of the iterator you given.    */
+/*                                                        */
+/*   iterDelPrev(addr of the iterator)                    */
+/*      Delete the next of the iterator you given.        */
+/*                                                        */
+/*                                                        */
+/**********************************************************/
+
+pvoid ctl_list_initX(ppvoid l, size_t size, uint count);
+pvoid ctl_list_freeX(ppvoid l);
+
+int    ctl_list_getSizeX     (ppcvoid l);
+int    ctl_list_getEntrySizeX(ppcvoid l);
+pcvoid ctl_list_getFrontX    (ppcvoid l);
+pcvoid ctl_list_getBackX     (ppcvoid l);
+pvoid  ctl_list_getBeginX    (ppcvoid l);
+pcvoid ctl_list_getEndX     (ppcvoid l);
+
+int   ctl_list_setSizeX (ppvoid l, uint count);
+pvoid ctl_list_setFrontX(ppvoid l, pcvoid data);
+pvoid ctl_list_setBackX (ppvoid l, pcvoid data);
+
+int ctl_list_addFrontX(ppvoid l, pcvoid data);
+int ctl_list_delFrontX(ppvoid l);
+int ctl_list_addBackX (ppvoid l, pcvoid data);
+int ctl_list_delBackX (ppvoid l);
+
+int   ctl_list_rmX  (ppvoid li, pvoid i1, pvoid i2);
+pvoid ctl_list_copyX(ppvoid li, pvoid i1, pvoid i2, ppvoid out);
+pvoid ctl_list_moveX(ppvoid li, pvoid i1, pvoid i2, ppvoid out);
+int   ctl_list_swapX(ppvoid li, pvoid i1, pvoid i2,
+                     ppvoid lj, pvoid j1, pvoid j2);
+
+pcvoid ctl_list_iterGetEntryX(pcvoid i);
+pvoid  ctl_list_iterGetNextX (pcvoid i);
+pvoid  ctl_list_iterGetPrevX (pcvoid i);
+
+pvoid  ctl_list_iterSetEntryX(pvoid  i, pcvoid data);
+
+pvoid  ctl_list_iterDelX    (pvoid i);
+pvoid  ctl_list_iterDelPrevX(pvoid i);
+pvoid  ctl_list_iterDelNextX(pvoid i);
+
+#define ctl_list_init(X,Y,Z) ctl_list_initX(ppVoid(X),Y,Z)
+#define ctl_list_free(X)     ctl_list_freeX(ppVoid(X))
+
+#define ctl_list_getSize(X)      ctl_list_getSizeX     (ppcVoid(X))
+#define ctl_list_getEntrySize(X) ctl_list_getEntrySizeX(ppcVoid(X))
+#define ctl_list_getFront(X)     ctl_list_getFrontX    (ppcVoid(X))
+#define ctl_list_getBack(X)      ctl_list_getBackX     (ppcVoid(X))
+#define ctl_list_getBegin(X)     ctl_list_getBeginX    (ppcVoid(X))
+#define ctl_list_getEnd(X)       ctl_list_getEndX      (ppcVoid(X))
+
+#define ctl_list_setSize(X,Y)  ctl_list_setSizeX (ppVoid(X),Y)
+#define ctl_list_setFront(X,Y) ctl_list_setFrontX(ppVoid(X),pcVoid(Y))
+#define ctl_list_setBack(X,Y)  ctl_list_setBackX (ppVoid(X),pcVoid(Y))
+
+#define ctl_list_addFront(X,Y) ctl_list_addFrontX(ppVoid(X),pcVoid(Y))
+#define ctl_list_delFront(X)   ctl_list_delFrontX(ppVoid(X))
+#define ctl_list_addBack(X,Y)  ctl_list_addBackX (ppVoid(X),pcVoid(Y))
+#define ctl_list_delBack(X)    ctl_list_delBackX (ppVoid(X))
+
+
+#define ctl_list_rm(X,Y,Z)         ctl_list_rmX  (ppVoid(X),pVoid(Y),pVoid(Z))
+#define ctl_list_copy(X,Y,Z,A)     ctl_list_copyX(ppVoid(X),pVoid(Y),pVoid(Z),ppVoid(A))
+#define ctl_list_move(X,Y,Z,A)     ctl_list_moveX(ppVoid(X),pVoid(Y),pVoid(Z),ppVoid(A))
+#define ctl_list_swap(X,Y,Z,A,B,C) ctl_list_swapX(ppVoid(X),pVoid(Y),pVoid(Z),ppVoid(A),pVoid(B),pVoid(C))
+
+#define ctl_list_iterGetEntry(X)  ctl_list_iterGetEntryX(pcVoid(X))
+#define ctl_list_iterGetNext(X)   ctl_list_iterGetNextX (pcVoid(X))
+#define ctl_list_iterGetPrev(X)   ctl_list_iterGetPrevX (pcVoid(X))
+
+#define ctl_list_iterSetEntry(X,Y) ctl_list_iterSetEntryX(pVoid(X),pcVoid(Y))
+
+#define ctl_list_iterDel(X)     ctl_list_iterDelX    (pVoid(X))
+#define ctl_list_iterDelPrev(X) ctl_list_iterDelPrevX(pVoid(X))
+#define ctl_list_iterDelNext(X) ctl_list_iterDelNextX(pVoid(X))
+
+#endif  /* __list_h__ */
diff --git a/src/list.c b/src/list.c
new file mode 100644
index 0000000..98d594b
--- /dev/null
+++ b/src/list.c
@@ -0,0 +1,268 @@
+#include "list.h"
+
+#include <string.h>
+
+struct ListNodeStruct;
+struct ListHeaderStruct;
+
+struct ListNodeStruct{
+    struct ListHeaderStruct *head;
+    struct ListNodeStruct   *prev;
+    struct ListNodeStruct   *next;
+    char buf[];
+};
+
+struct ListHeaderStruct{
+    size_t                size;
+    uint                  count;
+    struct ListNodeStruct data;
+};
+
+typedef struct ListNodeStruct   ListNode;
+typedef struct ListHeaderStruct ListHeader;
+
+
+#define getHeader(X)   (*(ListHeader**)(pChar(X)-offsetof(ListNode,buf)))
+#define getNode(X)     ((ListNode*)(pChar(X)-offsetof(ListNode,buf)))
+#define getNodeSize(X) ((X)->size+sizeof(ListNode))
+
+/******************** private functions *******************/
+#define nodeConnect(a,b) \
+    do{\
+        (a)->next = (b);\
+        (b)->prev = (a);\
+    }while(0)
+#define addNodeFront(lllll) \
+    do{\
+        ListNode *tzzzmp = (ListNode*)ctl_malloc(getNodeSize(lllll));\
+        tzzzmp->head = (lllll);\
+        nodeConnect(tzzzmp, (lllll)->data.next);\
+        nodeConnect(&(lllll)->data, tzzzmp);\
+        (lllll)->count++;\
+    }while(0)
+#define addNodeBack(lllll) \
+    do{\
+        ListNode *tzzzmp = (ListNode*)ctl_malloc(getNodeSize(lllll));\
+        tzzzmp->head = (lllll);\
+        nodeConnect((lllll)->data.prev, tzzzmp);\
+        nodeConnect(tzzzmp, &(lllll)->data);\
+        (lllll)->count++;\
+    }while(0)
+#define delNodeFront(lllll) \
+    do{\
+        ListNode *tzzzmp = (lllll)->data.next;\
+        tzzzmp->head = (lllll);\
+        nodeConnect(&(lllll)->data, tzzzmp->next);\
+        ctl_free(tzzzmp);\
+        (lllll)->count--;\
+    }while(0)
+#define delNodeBack(lllll) \
+    do{\
+        ListNode *tzzzmp = (lllll)->data.prev;\
+        tzzzmp->head = (lllll);\
+        nodeConnect(tzzzmp->prev, &(lllll)->data);\
+        ctl_free(tzzzmp);\
+        (lllll)->count--;\
+    }while(0)
+
+/***************** initalize & destructure ****************/
+pvoid ctl_list_initX(ppvoid l, size_t size, uint count){
+    ListHeader *tmp = (ListHeader*)ctl_malloc(sizeof(ListHeader));
+    tmp->size      = size;
+    tmp->data.head = tmp;
+    tmp->data.prev = &tmp->data;
+    tmp->data.next = &tmp->data;
+    for(tmp->count = 0; tmp->count < count; tmp->count++){
+        addNodeBack(tmp);
+    }
+    if(l != NULL){
+        *l = tmp->data.buf;
+    }
+    return tmp->data.buf;
+}
+
+pvoid ctl_list_freeX(ppvoid l){
+    ListHeader* tmp = getHeader(*l);
+    while(tmp->data.next != &tmp->data){
+        ListNode *ntmp = tmp->data.next;
+        tmp->data.next = tmp->data.next->next;
+        ctl_free(ntmp);
+    }
+    ctl_free(tmp);
+    *l = NULL;
+    return NULL;
+}
+
+/**************** about get??? methods ********************/
+int ctl_list_getSizeX(ppcvoid l){
+    return  getHeader(*l)->count;
+}
+int ctl_list_getEntrySizeX(ppcvoid l){
+    return getHeader(*l)->size;
+}
+pcvoid ctl_list_getFrontX(ppcvoid l){
+    return getHeader(*l)->data.next->buf;
+}
+pcvoid ctl_list_getBackX(ppcvoid l){
+    return getHeader(*l)->data.prev->buf;
+}
+pvoid ctl_list_getBeginX(ppcvoid l){
+    return getHeader(*l)->data.next->buf;
+}
+pcvoid ctl_list_getEndX(ppcvoid l){
+    return *l;
+}
+
+/**************** about set??? methods ********************/
+int ctl_list_setSizeX(ppvoid l, uint count){
+    ListHeader *tmp = getHeader(*l);
+    while(tmp->count > count){
+        delNodeBack(tmp);
+    }
+    while(tmp->count < count){
+        addNodeBack(tmp);
+    }
+    return tmp->count;
+}
+pvoid ctl_list_setFrontX(ppvoid l, pcvoid data){
+    ListHeader *tmp = getHeader(*l);
+    memcpy(tmp->data.next->buf, data, sizeof(tmp->size));
+    return tmp->data.next->buf;
+}
+pvoid ctl_list_setBackX(ppvoid l, pcvoid data){
+    ListHeader *tmp = getHeader(*l);
+    memcpy(tmp->data.prev->buf, data, sizeof(tmp->size));
+    return tmp->data.prev->buf;
+}
+
+/**************** about add/del front/back ****************/
+int ctl_list_addFrontX(ppvoid l, pcvoid data){
+    ListHeader* tmp = getHeader(*l);
+    addNodeFront(tmp);
+    ctl_list_setFrontX(l, data);
+    return tmp->count;
+}
+int ctl_list_delFrontX(ppvoid l){
+    ListHeader *tmp = getHeader(*l);
+    delNodeFront(tmp);
+    return tmp->count;
+}
+int ctl_list_addBackX(ppvoid l, pcvoid data){
+    ListHeader* tmp = getHeader(*l);
+    addNodeBack(tmp);
+    ctl_list_setBackX(l, data);
+    return tmp->count;
+}
+int ctl_list_delBackX(ppvoid l){
+    ListHeader *tmp = getHeader(*l);
+    delNodeBack(tmp);
+    return tmp->count;
+}
+
+/************** about list's special methods **************/
+int ctl_list_rmX(ppvoid l, pvoid i1, pvoid i2){
+    ListHeader *tmp = getHeader(*l );
+    ListNode*    n1 = getNode  (i1);
+    ListNode*    n2 = getNode  (i2);
+    nodeConnect(n1->prev, n2);
+    int ret = 0;
+    while(n1 != n2){
+        ListNode* ntmp = n1;
+        n1 = n1->next;
+        ctl_free(ntmp);
+        ret++;
+    }
+    tmp->count -= ret;
+    return ret;
+}
+pvoid ctl_list_copyX(ppvoid l, pvoid i1, pvoid i2, ppvoid out){
+    ListHeader* tmp  = getHeader(*l);
+    pvoid *p0 = ctl_list_init(NULL, tmp->size, 0);
+    ListHeader* tmp2 = getHeader(p0);
+    ListNode*     n1 = getNode(i1);
+    ListNode*     n2 = getNode(i2);
+    while(n1 != n2){
+        char *c = tmp2->data.buf;
+        ctl_list_addBack(&c, n1->buf);
+        n1 = n1->next;
+        tmp2->count++;
+    }
+    if(out != NULL){
+        *out = tmp2->data.buf;
+    }
+    return tmp2->data.buf;
+}
+pvoid ctl_list_moveX(ppvoid l, pvoid i1, pvoid i2, ppvoid out){
+    ListHeader* tmp  = getHeader(*l);
+    pvoid *p0 = ctl_list_init(NULL, tmp->size, 0);
+    ListHeader* tmp2 = getHeader(p0);
+    ListNode*     n1 = getNode(i1);
+    ListNode*     n3 = getNode(i2);
+    ListNode*     n0 = n1->prev;
+    ListNode*     n2 = n3->prev;
+    ListNode*     ni;
+    for(ni = n1; ni != n3; ni = ni->next){
+        tmp ->count--;
+        tmp2->count++;
+    }
+    nodeConnect(&tmp2->data, n1);
+    nodeConnect(n2, &tmp2->data);
+    nodeConnect(n0, n3);
+    if(out != NULL){
+        *out = tmp2->data.buf;
+    }
+    return tmp2->data.buf;
+}
+int ctl_list_swapX(ppvoid li, pvoid i1, pvoid i2,
+                   ppvoid lj, pvoid j1, pvoid j2){
+    ListHeader* hi  = getHeader(*li),* hj  = getHeader(*lj);
+    ListNode  * ni1 = getNode  ( i1),* nj1 = getNode  ( j1), *i;
+    ListNode  * ni3 = getNode  ( i2),* nj3 = getNode  ( j2), *j;
+    int count1 = 0, count2 = 0;
+    for(i = ni1; i != ni3; i = i->next){
+        count1++;
+    }
+    for(j = nj1; j != nj3; j = j->next){
+        count2++;
+    }
+    ListNode* ni0 = ni1->prev,* ni2 = ni3->prev;
+    ListNode* nj0 = nj1->prev,* nj2 = nj3->prev;
+    nodeConnect(ni0, nj1);
+    nodeConnect(nj0, ni1);
+    nodeConnect(ni2, nj3);
+    nodeConnect(nj2, ni3);
+    hi->size += (count2 - count1);
+    hj->size += (count1 - count2);
+    return count1;
+}
+
+/******************** about iterator **********************/
+pcvoid ctl_list_iterGetEntryX(pcvoid i){
+    return i;
+}
+pvoid ctl_list_iterGetNextX(pcvoid i){
+    return getNode(i)->next->buf;
+}
+pvoid ctl_list_iterGetPrevX(pcvoid i){
+    return getNode(i)->prev->buf;
+}
+
+pvoid ctl_list_iterSetEntryX(pvoid i, pcvoid data){
+    memcpy(i, data, getNode(i)->head->size);
+    return i;
+}
+
+pvoid ctl_list_iterDelX(pvoid i){
+    ListNode* n = getNode(i);
+    nodeConnect(n->prev, n->next);
+    n->head->count--;
+    return n->next->buf;
+}
+pvoid ctl_list_iterDelPrevX(pvoid i){
+    ctl_list_iterDelX(ppVoid(getNode(i)->prev->buf));
+    return i;
+}
+pvoid ctl_list_iterDelNextX(pvoid i){
+    ctl_list_iterDelX(ppVoid(getNode(i)->next->buf));
+    return i;
+}