From 10d9f983f15fe67eb5465eabb05390c23ea3ac14 Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 11 Jun 2009 18:13:20 +0000 Subject: [PATCH] Need a double-ended queue for work-stealing algorithm, extended Runtime//Queue to have the functionality. Found some bugs in Queue with pointers that were never exposed when using Queue as singly-linked list, added fixes and my test files --- Robust/src/Runtime/Queue.c | 136 ++++++++++++++++++++++++++++++ Robust/src/Runtime/Queue.h | 15 ++++ Robust/src/Tests/Queue/makefile | 18 ++++ Robust/src/Tests/Queue/testMain.c | 73 ++++++++++++++++ 4 files changed, 242 insertions(+) create mode 100644 Robust/src/Tests/Queue/makefile create mode 100644 Robust/src/Tests/Queue/testMain.c diff --git a/Robust/src/Runtime/Queue.c b/Robust/src/Runtime/Queue.c index 726483b4..a058d3f1 100644 --- a/Robust/src/Runtime/Queue.c +++ b/Robust/src/Runtime/Queue.c @@ -1,5 +1,10 @@ +#ifdef DEBUG_QUEUE +#include +#endif + #include "mem.h" #include "Queue.h" + #ifdef DMALLOC #include "dmalloc.h" #endif @@ -22,14 +27,35 @@ struct QueueItem * addNewItem(struct Queue * queue, void * ptr) { if (queue->head==NULL) { queue->head=item; queue->tail=item; + item->next=NULL; + item->prev=NULL; } else { item->next=queue->head; + item->prev=NULL; queue->head->prev=item; queue->head=item; } return item; } +struct QueueItem * addNewItemBack(struct Queue * queue, void * ptr) { + struct QueueItem * item=RUNMALLOC(sizeof(struct QueueItem)); + item->objectptr=ptr; + item->queue=queue; + if (queue->tail==NULL) { + queue->head=item; + queue->tail=item; + item->next=NULL; + item->prev=NULL; + } else { + item->prev=queue->tail; + item->next=NULL; + queue->tail->next=item; + queue->tail=item; + } + return item; +} + #ifdef MULTICORE struct QueueItem * addNewItem_I(struct Queue * queue, void * ptr) { struct QueueItem * item=RUNMALLOC_I(sizeof(struct QueueItem)); @@ -82,7 +108,117 @@ struct QueueItem * getNextQueueItem(struct QueueItem * qi) { void * getItem(struct Queue * queue) { struct QueueItem * q=queue->head; void * ptr=q->objectptr; + if(queue->tail==queue->head) { + queue->tail=NULL; + } else { + q->next->prev=NULL; + } queue->head=q->next; RUNFREE(q); return ptr; } + +void * getItemBack(struct Queue * queue) { + struct QueueItem * q=queue->tail; + void * ptr=q->objectptr; + if(queue->head==queue->tail) { + queue->head=NULL; + } else { + q->prev->next=NULL; + } + queue->tail=q->prev; + RUNFREE(q); + return ptr; +} + +#ifdef DEBUG_QUEUE +int assertQueue(struct Queue * queue) { + + struct QueueItem* i = queue->head; + + if( i == NULL && queue->tail != NULL ) { + return 0; + } + + while( i != NULL ) { + + if( queue->head == i && i->prev != NULL ) { + return 0; + } + + if( i->prev == NULL ) { + if( queue->head != i ) { + return 0; + } + + // i->prev != NULL + } else { + if( i->prev->next == NULL ) { + return 0; + } else if( i->prev->next != i ) { + return 0; + } + } + + if( i->next == NULL ) { + if( queue->tail != i ) { + return 0; + } + + // i->next != NULL + } else { + if( i->next->prev == NULL ) { + return 0; + } else if( i->next->prev != i ) { + return 0; + } + } + + if( queue->tail == i && i->next != NULL ) { + return 0; + } + + i = getNextQueueItem(i); + } + + return 1; +} + +void printQueue(struct Queue * queue) { + struct QueueItem* i; + + printf("Queue empty? %d\n", isEmpty(queue)); + + printf("head "); + i = queue->head; + while( i != NULL ) { + printf("item "); + i = getNextQueueItem(i); + } + printf("tail\n"); + + printf("[%08x] ", (int)queue->head); + i = queue->head; + while( i != NULL ) { + printf("[%08x] ", (int)i); + i = getNextQueueItem(i); + } + printf("[%08x]\n", (int)queue->tail); + + printf(" (next) "); + i = queue->head; + while( i != NULL ) { + printf("[%08x] ", (int)(i->next)); + i = getNextQueueItem(i); + } + printf("\n"); + + printf(" (prev) "); + i = queue->head; + while( i != NULL ) { + printf("[%08x] ", (int)(i->prev)); + i = getNextQueueItem(i); + } + printf("\n"); +} +#endif diff --git a/Robust/src/Runtime/Queue.h b/Robust/src/Runtime/Queue.h index 425d5573..27aaa0ee 100644 --- a/Robust/src/Runtime/Queue.h +++ b/Robust/src/Runtime/Queue.h @@ -27,4 +27,19 @@ void removeItem(struct Queue * queue, struct QueueItem * item); struct QueueItem * getTail(struct Queue * queue); struct QueueItem * getNextQueueItem(struct QueueItem * qi); +// to implement a double-ended queue +void * getItemBack(struct Queue * queue); +struct QueueItem * addNewItemBack(struct Queue * queue, void * ptr); + + +// for debugging, only included if macro is defined +#ifdef DEBUG_QUEUE + +// returns 1 if queue's pointers are valid, 0 otherwise +int assertQueue(struct Queue * queue); + +// use this to print head, tail and next, prev of each item +void printQueue(struct Queue * queue); +#endif + #endif diff --git a/Robust/src/Tests/Queue/makefile b/Robust/src/Tests/Queue/makefile new file mode 100644 index 00000000..3506110d --- /dev/null +++ b/Robust/src/Tests/Queue/makefile @@ -0,0 +1,18 @@ +QDIR=../../Runtime +DEFS= -D "RUNMALLOC=malloc" -D "RUNFREE=free" -D "DEBUG_QUEUE=" + +all: a.out + +a.out: testMain.o queue.o + gcc testMain.o queue.o + +queue.o: $(QDIR)/Queue.h $(QDIR)/Queue.c + gcc -c -I$(QDIR) $(DEFS) $(QDIR)/Queue.c -o queue.o + +testMain.o: testMain.c $(QDIR)/Queue.h + gcc -c -I$(QDIR) $(DEFS) testMain.c -o testMain.o + +clean: + rm -f a.out + rm -f *.o + rm -f *~ diff --git a/Robust/src/Tests/Queue/testMain.c b/Robust/src/Tests/Queue/testMain.c new file mode 100644 index 00000000..3c08358b --- /dev/null +++ b/Robust/src/Tests/Queue/testMain.c @@ -0,0 +1,73 @@ +#include +#include + +#include "Queue.h" + + +void check( struct Queue* q ) { + if( assertQueue( q ) ) { + printf( "Queue valid\n" ); + } else { + printf( "QUEUE INVALID\n" ); + } +} + + +int main() { + + struct Queue* q = createQueue(); + + struct QueueItem* i1; + struct QueueItem* i2; + struct QueueItem* i3; + + char m1[] = "1"; + char m2[] = "2"; + char m3[] = "3"; + char m4[] = "4"; + char* mo; + + addNewItem( q, (void*)m1 ); + check( q ); + + addNewItem( q, (void*)m2 ); + check( q ); + + addNewItemBack( q, (void*)m3 ); + check( q ); + + mo = (char*) getItem( q ); + check( q ); + + addNewItemBack( q, (void*)m4 ); + check( q ); + + mo = (char*) getItemBack( q ); + check( q ); + + mo = (char*) getItem( q ); + check( q ); + + mo = (char*) getItemBack( q ); + check( q ); + + i1 = addNewItemBack( q, (void*)m3 ); + check( q ); + + i2 = addNewItem( q, (void*)m1 ); + check( q ); + + i3 = addNewItem( q, (void*)m2 ); + check( q ); + + removeItem( q, i2 ); + check( q ); + + removeItem( q, i3 ); + check( q ); + + removeItem( q, i1 ); + check( q ); + + return 0; +} -- 2.34.1