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