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 #ifdef DEBUG_QUEUE
 154 int assertQueue(struct Queue * queue) {
 155
 156   struct QueueItem* i = queue->head;
 157
 158   if( i == NULL && queue->tail != NULL ) {
 159     return 0;
 160   }
 161
 162   while( i != NULL ) {
 163
 164     if( queue->head == i && i->prev != NULL ) {
 165       return 0;
 166     }
 167
 168     if( i->prev == NULL ) {
 169       if( queue->head != i ) {
 170         return 0;
 171       }
 172
 173     // i->prev != NULL
 174     } else {
 175       if( i->prev->next == NULL ) {
 176         return 0;
 177       } else if( i->prev->next != i ) {
 178         return 0;
 179       }
 180     }
 181
 182     if( i->next == NULL ) {
 183       if( queue->tail != i ) {
 184         return 0;
 185       }
 186
 187     // i->next != NULL
 188     } else {
 189       if( i->next->prev == NULL ) {
 190         return 0;
 191       } else if( i->next->prev != i ) {
 192         return 0;
 193       }
 194     }
 195
 196     if( queue->tail == i && i->next != NULL ) {
 197       return 0;
 198     }
 199
 200     i = getNextQueueItem(i);
 201   }
 202
 203   return 1;
 204 }
 205
 206 void printQueue(struct Queue * queue) {
 207   struct QueueItem* i;
 208
 209   printf("Queue empty? %d\n", isEmpty(queue));
 210
 211   printf("head        ");
 212   i = queue->head;
 213   while( i != NULL ) {
 214     printf("item        ");
 215     i = getNextQueueItem(i);
 216   }
 217   printf("tail\n");
 218
 219   printf("[%08x]  ", (int)queue->head);
 220   i = queue->head;
 221   while( i != NULL ) {
 222     printf("[%08x]  ", (int)i);
 223     i = getNextQueueItem(i);
 224   }
 225   printf("[%08x]\n", (int)queue->tail);
 226
 227   printf("   (next)   ");
 228   i = queue->head;
 229   while( i != NULL ) {
 230     printf("[%08x]  ", (int)(i->next));
 231     i = getNextQueueItem(i);
 232   }
 233   printf("\n");
 234
 235   printf("   (prev)   ");
 236   i = queue->head;
 237   while( i != NULL ) {
 238     printf("[%08x]  ", (int)(i->prev));
 239     i = getNextQueueItem(i);
 240   }
 241   printf("\n");
 242 }
 243 #endif