Robust/src/Runtime/Queue.c

   1 #ifdef DEBUG_QUEUE
   2 #include <stdio.h>
   3 #endif
   4
   5 #include "mem.h"
   6 #include "Queue.h"
   7
   8 #ifdef DMALLOC
   9 #include "dmalloc.h"
  10 #endif
  11
  12 struct Queue * createQueue() {
  13   struct Queue * queue = (struct Queue *)RUNMALLOC(sizeof(struct Queue));
  14   queue->head = NULL;
  15   queue->tail = NULL;
  16   return queue;
  17 }
  18
  19 void freeQueue(struct Queue * q) {
  20   RUNFREE(q);
  21 }
  22
  23 struct QueueItem * addNewItem(struct Queue * queue, void * ptr) {
  24   struct QueueItem * item=RUNMALLOC(sizeof(struct QueueItem));
  25   item->objectptr=ptr;
  26   item->queue=queue;
  27   if (queue->head==NULL) {
  28     queue->head=item;
  29     queue->tail=item;
  30     item->next=NULL;
  31     item->prev=NULL;
  32   } else {
  33     item->next=queue->head;
  34     item->prev=NULL;
  35     queue->head->prev=item;
  36     queue->head=item;
  37   }
  38   return item;
  39 }
  40
  41 struct QueueItem * addNewItemBack(struct Queue * queue, void * ptr) {
  42   struct QueueItem * item=RUNMALLOC(sizeof(struct QueueItem));
  43   item->objectptr=ptr;
  44   item->queue=queue;
  45   if (queue->tail==NULL) {
  46     queue->head=item;
  47     queue->tail=item;
  48     item->next=NULL;
  49     item->prev=NULL;
  50   } else {
  51     item->prev=queue->tail;
  52     item->next=NULL;
  53     queue->tail->next=item;
  54     queue->tail=item;
  55   }
  56   return item;
  57 }
  58
  59 #ifdef MULTICORE
  60 struct Queue * createQueue_I() {
  61   struct Queue * queue = (struct Queue *)RUNMALLOC_I(sizeof(struct Queue));
  62   queue->head = NULL;
  63   queue->tail = NULL;
  64   return queue;
  65 }
  66
  67 struct QueueItem * addNewItem_I(struct Queue * queue, void * ptr) {
  68   struct QueueItem * item=RUNMALLOC_I(sizeof(struct QueueItem));
  69   item->objectptr=ptr;
  70   item->queue=queue;
  71   if (queue->head==NULL) {
  72     queue->head=item;
  73     queue->tail=item;
  74   } else {
  75     item->next=queue->head;
  76     queue->head->prev=item;
  77     queue->head=item;
  78   }
  79   return item;
  80 }
  81 #endif
  82
  83 struct QueueItem * getTail(struct Queue * queue) {
  84   return queue->tail;
  85 }
  86
  87 struct QueueItem * getHead(struct Queue * queue) {
  88   return queue->head;
  89 }
  90
  91 struct QueueItem * getNextQueueItem(struct QueueItem * qi) {
  92   return qi->next;
  93 }
  94
  95 struct QueueItem * findItem(struct Queue * queue, void *ptr) {
  96   struct QueueItem * item=queue->head;
  97   while(item!=NULL) {
  98     if (item->objectptr==ptr)
  99       return item;
 100     item=item->next;
 101   }
 102   return NULL;
 103 }
 104
 105 void removeItem(struct Queue * queue, struct QueueItem * item) {
 106   struct QueueItem * prev=item->prev;
 107   struct QueueItem * next=item->next;
 108   if (queue->head==item)
 109     queue->head=next;
 110   else
 111     prev->next=next;
 112   if (queue->tail==item)
 113     queue->tail=prev;
 114   else
 115     next->prev=prev;
 116   RUNFREE(item);
 117 }
 118
 119 void * getItem(struct Queue * queue) {
 120   struct QueueItem * q=queue->head;
 121   void * ptr=q->objectptr;
 122   if(queue->tail==queue->head) {
 123     queue->tail=NULL;
 124   } else {
 125     q->next->prev=NULL;
 126   }
 127   queue->head=q->next;
 128   if(queue->tail == q) {
 129           queue->tail = NULL;
 130   }
 131   RUNFREE(q);
 132   return ptr;
 133 }
 134
 135 void * getItemBack(struct Queue * queue) {
 136   struct QueueItem * q=queue->tail;
 137   void * ptr=q->objectptr;
 138   if(queue->head==queue->tail) {
 139     queue->head=NULL;
 140   } else {
 141     q->prev->next=NULL;
 142   }
 143   queue->tail=q->prev;
 144   RUNFREE(q);
 145   return ptr;
 146 }
 147
 148 void * peekItem(struct Queue * queue) {
 149   struct QueueItem * q=queue->head;
 150   void * ptr=q->objectptr;
 151   return ptr;
 152 }
 153
 154 void * peekItemBack(struct Queue * queue) {
 155   struct QueueItem * q=queue->tail;
 156   void * ptr=q->objectptr;
 157   return ptr;
 158 }
 159
 160 void clearQueue(struct Queue * queue) {
 161         struct QueueItem * item=queue->head;
 162   while(item!=NULL) {
 163                 struct QueueItem * next=item->next;
 164                 RUNFREE(item);
 165     item=next;
 166   }
 167         queue->head=queue->tail=NULL;
 168   return;
 169 }
 170
 171 #ifdef DEBUG_QUEUE
 172 int assertQueue(struct Queue * queue) {
 173
 174   struct QueueItem* i = queue->head;
 175
 176   if( i == NULL && queue->tail != NULL ) {
 177     return 0;
 178   }
 179
 180   while( i != NULL ) {
 181
 182     if( queue->head == i && i->prev != NULL ) {
 183       return 0;
 184     }
 185
 186     if( i->prev == NULL ) {
 187       if( queue->head != i ) {
 188         return 0;
 189       }
 190
 191     // i->prev != NULL
 192     } else {
 193       if( i->prev->next == NULL ) {
 194         return 0;
 195       } else if( i->prev->next != i ) {
 196         return 0;
 197       }
 198     }
 199
 200     if( i->next == NULL ) {
 201       if( queue->tail != i ) {
 202         return 0;
 203       }
 204
 205     // i->next != NULL
 206     } else {
 207       if( i->next->prev == NULL ) {
 208         return 0;
 209       } else if( i->next->prev != i ) {
 210         return 0;
 211       }
 212     }
 213
 214     if( queue->tail == i && i->next != NULL ) {
 215       return 0;
 216     }
 217
 218     i = getNextQueueItem(i);
 219   }
 220
 221   return 1;
 222 }
 223
 224 void printQueue(struct Queue * queue) {
 225   struct QueueItem* i;
 226
 227   printf("Queue empty? %d\n", isEmpty(queue));
 228
 229   printf("head        ");
 230   i = queue->head;
 231   while( i != NULL ) {
 232     printf("item        ");
 233     i = getNextQueueItem(i);
 234   }
 235   printf("tail\n");
 236
 237   printf("[%08x]  ", (int)queue->head);
 238   i = queue->head;
 239   while( i != NULL ) {
 240     printf("[%08x]  ", (int)i);
 241     i = getNextQueueItem(i);
 242   }
 243   printf("[%08x]\n", (int)queue->tail);
 244
 245   printf("   (next)   ");
 246   i = queue->head;
 247   while( i != NULL ) {
 248     printf("[%08x]  ", (int)(i->next));
 249     i = getNextQueueItem(i);
 250   }
 251   printf("\n");
 252
 253   printf("   (prev)   ");
 254   i = queue->head;
 255   while( i != NULL ) {
 256     printf("[%08x]  ", (int)(i->prev));
 257     i = getNextQueueItem(i);
 258   }
 259   printf("\n");
 260 }
 261 #endif