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