From 3b51faf93e40891551c55207817ae43c930b4fde Mon Sep 17 00:00:00 2001 From: teodor Date: Thu, 19 Oct 2006 11:33:31 +0000 Subject: [PATCH] GList - double linked abstract list implementation --- Makefile | 7 +- expected/glist | 184 +++++++++++++++++++++ expected/glisttest | 0 glist.c | 386 +++++++++++++++++++++++++++++++++++++++++++++ glist.h | 93 +++++++++++ glisttest.c | 125 +++++++++++++++ tests/glist | 1 + 7 files changed, 793 insertions(+), 3 deletions(-) create mode 100644 expected/glist create mode 100644 expected/glisttest create mode 100644 glist.c create mode 100644 glist.h create mode 100644 glisttest.c create mode 100644 tests/glist diff --git a/Makefile b/Makefile index df63daf..6fc788f 100644 --- 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 \ - 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 @@ -34,7 +35,7 @@ test: all @[ -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 ; \ diff --git a/expected/glist b/expected/glist new file mode 100644 index 0000000..433a3e5 --- /dev/null +++ b/expected/glist @@ -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 index 0000000..e69de29 diff --git a/glist.c b/glist.c new file mode 100644 index 0000000..59213ac --- /dev/null +++ b/glist.c @@ -0,0 +1,386 @@ +/* + * Copyright (c) 2006 Teodor Sigaev + * 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 +#include +#include +#include + +#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 index 0000000..3221fe0 --- /dev/null +++ b/glist.h @@ -0,0 +1,93 @@ +/* + * Copyright (c) 2006 Teodor Sigaev + * 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 index 0000000..6defab0 --- /dev/null +++ b/glisttest.c @@ -0,0 +1,125 @@ +/* + * Copyright (c) 2006 Teodor Sigaev + * 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 +#include +#include +#include + + +#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 index 0000000..d716b20 --- /dev/null +++ b/tests/glist @@ -0,0 +1 @@ +./glisttest -- 2.37.3