GList - double linked abstract list implementation
authorteodor <teodor>
Thu, 19 Oct 2006 11:33:31 +0000 (11:33 +0000)
committerteodor <teodor>
Thu, 19 Oct 2006 11:33:31 +0000 (11:33 +0000)
Makefile
expected/glist [new file with mode: 0644]
expected/glisttest [new file with mode: 0644]
glist.c [new file with mode: 0644]
glist.h [new file with mode: 0644]
glisttest.c [new file with mode: 0644]
tests/glist [new file with mode: 0644]

index df63daf..6fc788f 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -10,8 +10,9 @@ LIB=-g -L. -ltedtools -lm
 
 OBJS=tlog.o tmalloc.o tools.o prs_hmap.o sfxstr.o \
        regis.o prs_inf.o shmem.o tcp.o udp.o connpool.o \
 
 OBJS=tlog.o tmalloc.o tools.o prs_hmap.o sfxstr.o \
        regis.o prs_inf.o shmem.o tcp.o udp.o connpool.o \
-       psort.o flatdb.o tbtree.o
-PROGS=sfxtest hextest inftest kilter psortex flatdbtest tbtreetest gendata memtest
+       psort.o flatdb.o tbtree.o glist.o
+PROGS=sfxtest hextest inftest kilter psortex flatdbtest \
+       tbtreetest gendata memtest glisttest
 
 .SUFFIXES: .o.c
 
 
 .SUFFIXES: .o.c
 
@@ -34,7 +35,7 @@ test: all
        @[ -d results ] || mkdir results  
        @[ -d diffs ] || mkdir diffs  
        @[ -d temp ] || mkdir temp  
        @[ -d results ] || mkdir results  
        @[ -d diffs ] || mkdir diffs  
        @[ -d temp ] || mkdir temp  
-       @for FILE in btree flatdb hex inf mem psort sfxmem ; do \
+       @for FILE in btree flatdb hex inf mem psort sfxmem glist ; do \
                echo -n $$FILE "        ........ " ; \
                if sh tests/$$FILE > results/$$FILE 2>results/$$FILE.errout && diff -c expected/$$FILE results/$$FILE > diffs/$$FILE ; then \
                        echo ok ; \
                echo -n $$FILE "        ........ " ; \
                if sh tests/$$FILE > results/$$FILE 2>results/$$FILE.errout && diff -c expected/$$FILE results/$$FILE > diffs/$$FILE ; then \
                        echo ok ; \
diff --git a/expected/glist b/expected/glist
new file mode 100644 (file)
index 0000000..433a3e5
--- /dev/null
@@ -0,0 +1,184 @@
+Forward: GLIST_LENGTH(16)
+       0       :0:
+       1       :1:
+       2       :2:
+       3       :3:
+       4       :4:
+       5       :5:
+       6       :6:
+       7       :7:
+       8       :8:
+       9       :9:
+       10      :10:
+       11      :11:
+       12      :12:
+       13      :13:
+       14      :14:
+       15      :15:
+Backward: GLIST_LENGTH(10)
+       0       :18:
+       1       :16:
+       2       :14:
+       3       :12:
+       4       :10:
+       5       :8:
+       6       :6:
+       7       :4:
+       8       :2:
+       9       :0:
+Truncate: GLIST_LENGTH(3)
+       0       :0:
+       1       :1:
+       2       :2:
+Concat: GLIST_LENGTH(26)
+       0       :0:
+       1       :1:
+       2       :2:
+       3       :3:
+       4       :4:
+       5       :5:
+       6       :6:
+       7       :7:
+       8       :8:
+       9       :9:
+       10      :10:
+       11      :11:
+       12      :12:
+       13      :13:
+       14      :14:
+       15      :15:
+       16      :18:
+       17      :16:
+       18      :14:
+       19      :12:
+       20      :10:
+       21      :8:
+       22      :6:
+       23      :4:
+       24      :2:
+       25      :0:
+Difference: GLIST_LENGTH(8)
+       0       :1:
+       1       :3:
+       2       :5:
+       3       :7:
+       4       :9:
+       5       :11:
+       6       :13:
+       7       :15:
+Union: GLIST_LENGTH(18)
+       0       :0:
+       1       :1:
+       2       :2:
+       3       :3:
+       4       :4:
+       5       :5:
+       6       :6:
+       7       :7:
+       8       :8:
+       9       :9:
+       10      :10:
+       11      :11:
+       12      :12:
+       13      :13:
+       14      :14:
+       15      :15:
+       16      :18:
+       17      :16:
+Intersect: GLIST_LENGTH(8)
+       0       :0:
+       1       :2:
+       2       :4:
+       3       :6:
+       4       :8:
+       5       :10:
+       6       :12:
+       7       :14:
+Sort: GLIST_LENGTH(10)
+       0       :0:
+       1       :10:
+       2       :12:
+       3       :14:
+       4       :16:
+       5       :18:
+       6       :2:
+       7       :4:
+       8       :6:
+       9       :8:
+Sort + Uniq + Concat: GLIST_LENGTH(18)
+       0       :0:
+       1       :10:
+       2       :11:
+       3       :12:
+       4       :13:
+       5       :14:
+       6       :15:
+       7       :16:
+       8       :18:
+       9       :1:
+       10      :2:
+       11      :3:
+       12      :4:
+       13      :5:
+       14      :6:
+       15      :7:
+       16      :8:
+       17      :9:
+Find: :10:
+Insert: GLIST_LENGTH(11)
+       0       :18:
+       1       :16:
+       2       :14:
+       3       :12:
+       4       :10:
+       5       |11|
+       6       :8:
+       7       :6:
+       8       :4:
+       9       :2:
+       10      :0:
+Delete :10:: GLIST_LENGTH(10)
+       0       :18:
+       1       :16:
+       2       :14:
+       3       :12:
+       4       |11|
+       5       :8:
+       6       :6:
+       7       :4:
+       8       :2:
+       9       :0:
+Get #5: :8:
+Backward scan:
+       :0:
+       :2:
+       :4:
+       :6:
+       :8:
+       |11|
+       :12:
+       :14:
+       :16:
+       :18:
+Shift:
+       :18:
+       :16:
+       :14:
+       :12:
+       |11|
+       :8:
+       :6:
+       :4:
+       :2:
+       :0:
+Pop:
+       :0:
+       :2:
+       :4:
+       :6:
+       :8:
+       :10:
+       :12:
+       :14:
+       :16:
+       :18:
diff --git a/expected/glisttest b/expected/glisttest
new file mode 100644 (file)
index 0000000..e69de29
diff --git a/glist.c b/glist.c
new file mode 100644 (file)
index 0000000..59213ac
--- /dev/null
+++ b/glist.c
@@ -0,0 +1,386 @@
+/*
+ * Copyright (c) 2006 Teodor Sigaev <teodor@sigaev.ru>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *        notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *        notice, this list of conditions and the following disclaimer in the
+ *        documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the author nor the names of any co-contributors
+ *        may be used to endorse or promote products derived from this software
+ *        without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS
+ * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
+ * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
+ * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
+ * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
+ * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <sys/types.h>
+
+#include "tlog.h"
+#include "tmalloc.h"
+
+#include "glist.h"
+
+static GList*
+checkGList(GList *l) {
+       if ( l==NULL ) 
+               l = t0malloc(sizeof(GList));
+
+       tassert( GLIST_LENGTH(l) >= 0 );
+       tassert( 
+               ( GLIST_LENGTH(l) == 0 && GLIST_HEAD(l) == NULL && GLIST_TAIL(l) == NULL ) ||
+               ( GLIST_LENGTH(l) > 0  && GLIST_HEAD(l) != NULL && GLIST_TAIL(l) != NULL )
+       );
+
+       return l;
+}
+
+static GListCell*
+makeCell(void *ptr) {
+       GListCell       *cell = tmalloc(sizeof(GListCell));
+       cell->data = ptr;
+       return cell;
+}
+
+static GList*
+insertCell(GList *l, GListCell *prev, GListCell *cell) {
+       l = checkGList(l);
+
+       if ( prev == NULL ) {
+               /* insert into head */
+               if ( GLIST_LENGTH(l) == 0 ) {
+                               l->head = l->tail = cell;
+                               cell->next = cell->prev = NULL;
+               } else {
+                       cell->next = l->head;
+                       cell->prev = NULL;
+                       l->head->prev = cell;
+                       l->head = cell;
+               }
+       } else if ( prev == l->tail ) {
+               /* insert into tail */
+
+               tassert( GLIST_LENGTH(l) > 0 );
+               cell->next = NULL;
+               cell->prev = l->tail;
+               l->tail->next = cell;
+               l->tail = cell;
+       } else {
+               tassert( GLIST_LENGTH(l) > 0 );
+               cell->next = prev->next;
+               cell->next->prev = cell;
+               cell->prev = prev;
+               prev->next = cell;
+       }
+
+       l->length++;    
+
+       return l;
+}
+
+GList*
+GListInsert(GList *l, GListCell *prev, void *ptr) {
+       return insertCell(l, prev, makeCell(ptr));
+}
+
+GList*
+GListPush(GList *l, void *ptr) {
+       return insertCell(l, GLIST_TAIL(l), makeCell(ptr));
+}
+
+GList*
+GListUnshift(GList *l, void *ptr) {
+       return insertCell(l, NULL, makeCell(ptr));
+}
+
+GList*
+GListDelete(GList *l, GListCell *c) {
+       if (GLIST_LENGTH(l) <= 0)
+               return l;
+
+       if ( l->head == c ) {
+               tassert( c->prev == NULL );
+               l->head = c->next;
+               if ( l->head ) 
+                       l->head->prev = NULL;
+       } else if ( l->tail == c ) {
+               tassert( c->next == NULL );
+               l->tail = c->prev;
+               if ( l->tail )
+                       l->tail->next = NULL;
+       } else {
+               c->prev->next = c->next;
+               c->next->prev = c->prev;
+       }
+
+       c->prev = c->next = NULL;
+
+       l->length--;
+
+       return l;
+}
+
+GListCell*
+GListPop(GList *l) {
+       GListCell       *c = NULL;
+
+       if (GLIST_LENGTH(l) > 0) {
+               c = l->tail;
+               GListDelete(l, c);
+       }
+
+       return c;
+}
+
+GListCell*
+GListShift(GList *l) {
+       GListCell       *c = NULL;
+
+       if (GLIST_LENGTH(l) > 0) {
+               c = l->head;
+               GListDelete(l, c);
+       }
+
+       return c;
+}
+
+GListCell*
+GListGet(GList *l, int n) {
+       GListCell       *c;
+
+       GListForeach(c, l) {
+               if ( n-- == 0 )
+                       return c;
+       }
+
+       return NULL;
+}
+
+GListCell*
+GListFind(GList *l, void *ptr) {
+       GListCell    *c;
+
+       if ( l && l->cmpFunc ) {
+               GListForeach(c, l) {
+                       if ( l->cmpFunc(ptr, c->data) == 0 )
+                               return c;
+               }
+       } else {
+               GListForeach(c, l) {
+                       if ( ptr == c->data )
+                               return c;
+               }
+       }
+
+       return NULL;
+}
+
+static GListCellComparator curComparator;
+
+static int
+compareData( const void *a, const void *b ) {
+       if ( *(void**)a == *(void**)b )
+               return 0;
+       return curComparator( *(void**)a, *(void**)b );
+}
+
+GList*
+GListSort(GList *l) {
+       GListCell       *c;
+       void    **arrptr, **array;
+
+       if (GLIST_LENGTH(l) <= 1)
+               return l;
+               
+       tassert(l->cmpFunc != NULL);
+
+       arrptr = array = (void**)tmalloc(sizeof(void*)*GLIST_LENGTH(l));;
+       GListForeach(c, l) 
+               *arrptr++ = c->data;
+
+       tassert( arrptr - array == GLIST_LENGTH(l) );
+
+       curComparator = l->cmpFunc;
+       qsort(array, GLIST_LENGTH(l), sizeof(void*), compareData); 
+
+       arrptr = array;
+       GListForeach(c, l)
+               c->data = *arrptr++;
+
+       tfree(array);
+
+       return l;
+}
+
+GList*
+GListUniq(GList *l) {
+       GListCell   *c;
+
+       GListForeach(c, l) {
+               for(;;) {
+                       GListCell       *next = c->next;
+
+                       if ( next == NULL )
+                               break;
+
+                       if ( c->data == next->data || ( l->cmpFunc && l->cmpFunc(c->data, next->data)==0 ) ) {
+                               GListDelete( l, next );
+                               GListFreeCell( l, next );
+                       } else
+                               break;
+               }
+               
+       }
+
+       return l;
+}
+
+void
+GListFree(GList *l) {
+       GListCell   *c = GLIST_HEAD(l), *tmp;
+
+       while( c != NULL ) {
+               tmp = c->next;
+               GListFreeCell(l, c);
+               c = tmp;
+       }
+
+       if (l)
+               tfree(l);
+}
+
+void
+GListFreeCell(GList *l, GListCell* c) {
+       if (l && l->freeFunc) 
+               l->freeFunc(c->data);
+
+       tfree(c);
+}
+
+GList*
+GListTruncate(GList *l, int n) {
+       while( GLIST_LENGTH(l) > n ) {
+               GListCell       *c = l->tail;
+
+               GListDelete(l, c);
+               GListFreeCell(l, c);
+       }
+
+       return l;
+}
+
+GList*
+GListCopy(GList *l) {
+       GList   *n = NULL;
+       GListCell       *c;
+
+       GListForeach(c,l) 
+               n = GListPush(n, c->data);      
+
+       if ( n && l) {
+               n->cmpFunc = l->cmpFunc;
+               n->freeFunc = l->freeFunc;
+       }
+
+       return n;
+}
+
+GList*
+GListConcat(GList *l1, GList *l2) {
+
+       if ( l1 == l2 )
+               tlog(TL_CRIT|TL_EXIT,"Can't concat list itself");
+       if ( GLIST_LENGTH(l1) == 0 )
+               return l2;
+       if ( GLIST_LENGTH(l2) == 0 ) {
+               GListFree(l2);
+               return l1;
+       }
+
+       l1->tail->next = l2->head;
+       l2->head->prev = l1->tail;
+       l1->tail = l2->tail;
+       l1->length += l2->length;
+
+       l2->head = l2->tail = NULL;
+       l2->length=0;
+       GListFree(l2);
+
+       return l1;
+}
+
+GList*
+GListDifference(GList *l1, GList *l2) {
+       GList   *l = NULL;
+       GListCell       *c;
+
+       if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
+               tlog(TL_CRIT|TL_EXIT,"GListDifference: comparators aren't the same");
+
+       if (GLIST_LENGTH(l2) == 0 )
+               return GListCopy(l1);
+
+       GListForeach(c,l1) {
+               if ( GListFind(l2, c->data) == NULL )
+                       l = GListPush(l, c->data);
+       }
+
+       return l;
+}
+
+GList*
+GListUnion(GList *l1, GList *l2) {
+       GList   *l = GListCopy(l1);
+       GListCell       *c;
+
+       if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
+               tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
+
+       if (GLIST_LENGTH(l2) == 0 )
+               return l;
+       
+       GListForeach(c,l2) {
+               if ( GListFind(l1, c->data) == NULL )
+                       l = GListPush(l, c->data);
+       }
+
+       return l;
+}
+
+GList*
+GListIntersect(GList *l1, GList *l2) {
+       GList   *l = checkGList(NULL);
+       GListCell   *c;
+
+       if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
+               tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
+
+       if ( GLIST_LENGTH(l1) == 0 || GLIST_LENGTH(l2) == 0 )
+               return l;
+
+       GListForeach(c,l1) {
+               if ( GListFind(l2, c->data) != NULL )
+                       l = GListPush(l, c->data);
+       }
+
+       return l;
+}
+
+
+
+
diff --git a/glist.h b/glist.h
new file mode 100644 (file)
index 0000000..3221fe0
--- /dev/null
+++ b/glist.h
@@ -0,0 +1,93 @@
+/*
+ * Copyright (c) 2006 Teodor Sigaev <teodor@sigaev.ru>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *        notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *        notice, this list of conditions and the following disclaimer in the
+ *        documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the author nor the names of any co-contributors
+ *        may be used to endorse or promote products derived from this software
+ *        without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS
+ * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
+ * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
+ * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
+ * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
+ * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+#ifndef __GLIST_H__
+#define __GLIST_H__
+
+typedef struct GListCell {
+       void                            *data;
+       struct GListCell        *next;
+       struct GListCell        *prev;
+} GListCell;
+
+#define GLCELL_DATA(c) ((c)->data)
+#define GLCELL_NEXT(c) ((c)->next)
+#define GLCELL_PREV(c) ((c)->prev)
+
+typedef  int (*GListCellComparator)(const void *, const void *);
+typedef  int (*GListDataFreeFunc)(const void *);
+
+typedef struct GList {
+       GListCell       *head;
+       GListCell       *tail;
+       int     length;
+       GListCellComparator     cmpFunc;
+       GListDataFreeFunc       freeFunc;
+} GList;
+
+#define        GLIST_HEAD(l)   ((l) ? (l)->head : NULL)
+#define        GLIST_TAIL(l)   ((l) ? (l)->tail : NULL)
+#define        GLIST_LENGTH(l) ((l) ? (l)->length : 0)
+
+
+
+GListCell*     GListPop(GList *l);
+GList* GListPush(GList *l, void *ptr);
+GListCell*     GListShift(GList *l);
+GList* GListUnshift(GList *l, void *ptr);
+GList* GListInsert(GList *l, GListCell *prev, void *ptr);
+GList* GListDelete(GList *l, GListCell *c);
+GListCell* GListGet(GList *l, int n);
+
+GListCell* GListFind(GList *l, void *ptr);
+GList* GListSort(GList *l);
+GList* GListUniq(GList *l);
+
+void   GListFree(GList *l);
+void   GListFreeCell(GList *l, GListCell* c);
+
+GList* GListTruncate(GList *l, int n);
+GList* GListCopy(GList *l);
+GList* GListConcat(GList *l1, GList *l2);
+GList* GListDifference(GList *l1, GList *l2);
+GList* GListUnion(GList *l1, GList *l2);
+GList* GListIntersect(GList *l1, GList *l2);
+
+#define        GListForeach(cell, l) \
+       for ((cell) = GLIST_HEAD(l); (cell) != NULL; (cell) = GLCELL_NEXT(cell))
+
+#define        GListForeachBack(cell, l) \
+       for ((cell) = GLIST_TAIL(l); (cell) != NULL; (cell) = GLCELL_PREV(cell))
+
+#define        GListForeachCell(cell, initcell) \
+       for ((cell) = (initcell); (cell) != NULL; (cell) = GLCELL_NEXT(cell))
+
+#define        GListForeachCellBack(cell, initcell) \
+       for ((cell) = (initcell); (cell) != NULL; (cell) = GLCELL_PREV(cell))
+
+#endif
diff --git a/glisttest.c b/glisttest.c
new file mode 100644 (file)
index 0000000..6defab0
--- /dev/null
@@ -0,0 +1,125 @@
+/*
+ * Copyright (c) 2006 Teodor Sigaev <teodor@sigaev.ru>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *      notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *      notice, this list of conditions and the following disclaimer in the
+ *      documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the author nor the names of any co-contributors
+ *      may be used to endorse or promote products derived from this software
+ *      without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS
+ * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
+ * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
+ * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
+ * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
+ * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+
+#include "tmalloc.h"
+
+#include "glist.h"
+
+static void
+dumpGList(GList *l, char *str) {
+       int i=0;
+       GListCell *c;
+
+       printf("%s: GLIST_LENGTH(%d)\n", str, GLIST_LENGTH(l));
+       GListForeach(c,l)
+               printf("\t%d\t%s\n", i++, (char*)GLCELL_DATA(c));
+}
+
+static GList*
+fillF() {
+       int i;
+       char    buf[1024];
+       GList   *l = NULL;
+
+       for(i=0;i<16;i++) {
+               sprintf(buf,":%d:",i);
+               l = GListPush(l, tstrdup(buf));
+       }
+
+       l->cmpFunc = (GListCellComparator)strcmp;
+       l->freeFunc = (GListDataFreeFunc)tfree;
+       return l;
+}
+
+static GList*
+fillB() {
+       int i;
+       char    buf[1024];
+       GList   *l = NULL;
+
+       for(i=0;i<20;i+=2) {
+               sprintf(buf,":%d:",i);
+               l = GListUnshift(l, tstrdup(buf));
+       }
+
+       l->cmpFunc = (GListCellComparator)strcmp;
+       l->freeFunc = (GListDataFreeFunc)tfree;
+       return l;
+}
+
+
+int
+main(int argn, char *argv[]) {
+       GList   *l;
+       GListCell       *c;
+
+       dumpGList(fillF(), "Forward");
+       dumpGList(fillB(), "Backward");
+               
+       dumpGList(GListTruncate(fillF(), 3), "Truncate");
+       dumpGList(GListConcat(fillF(), fillB()), "Concat");
+       dumpGList(GListDifference(fillF(), fillB()), "Difference");
+       dumpGList(GListUnion(fillF(), fillB()), "Union");
+       dumpGList(GListIntersect(fillF(), fillB()), "Intersect");
+
+       dumpGList(GListSort(fillB()), "Sort");
+       dumpGList(GListUniq(GListSort(GListConcat(fillF(), fillB()))), "Sort + Uniq + Concat");
+
+       l = fillB();
+       c = GListFind(l,":10:");
+       printf("Find: %s\n", (char*)GLCELL_DATA(c));
+       dumpGList(GListInsert(l,c,"|11|"),"Insert");
+       dumpGList(GListDelete(l,c),"Delete :10:");
+       printf("Get #5: %s\n", (char*)GLCELL_DATA(GListGet(l,5)));
+       printf("Backward scan:\n");
+       GListForeachBack(c,l)
+               printf("\t%s\n", (char*)GLCELL_DATA(c));
+
+
+       printf("Shift:\n");
+       while( (c=GListShift(l))!=NULL )
+               printf("\t%s\n", (char*)GLCELL_DATA(c));
+
+       l = fillB();
+       printf("Pop:\n");
+       while( (c=GListPop(l))!=NULL )
+               printf("\t%s\n", (char*)GLCELL_DATA(c));
+
+       GListFree(fillF());
+
+       return 0;
+}
+
+
diff --git a/tests/glist b/tests/glist
new file mode 100644 (file)
index 0000000..d716b20
--- /dev/null
@@ -0,0 +1 @@
+./glisttest