src/xbt/fifo.c

   1 /* Authors: Arnaud Legrand                                                  */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4    under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include "xbt/sysdep.h"
   7 #include "xbt/error.h"
   8 #include "fifo_private.h"
   9
  10 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(fifo,xbt,"FIFO");
  11
  12 /*
  13  * xbt_fifo_new()
  14  */
  15 xbt_fifo_t xbt_fifo_new(void)
  16 {
  17   xbt_fifo_t fifo;
  18   fifo = xbt_new0(struct xbt_fifo,1);
  19   return fifo;
  20 }
  21
  22 /*
  23  * xbt_fifo_free()
  24  */
  25 void xbt_fifo_free(xbt_fifo_t l)
  26 {
  27   xbt_fifo_item_t b, tmp;
  28
  29   for (b = xbt_fifo_getFirstitem(l); b;
  30        tmp = b, b = b->next, xbt_fifo_freeitem(tmp));
  31   free(l);
  32   return;
  33 }
  34
  35 /*
  36  * xbt_fifo_push()
  37  * at the tail
  38  */
  39 xbt_fifo_item_t xbt_fifo_push(xbt_fifo_t l, void *t)
  40 {
  41   xbt_fifo_item_t new;
  42
  43   new = xbt_fifo_newitem();
  44   new->content = t;
  45
  46   xbt_fifo_push_item(l,new);
  47   return new;
  48 }
  49
  50 /*
  51  * xbt_fifo_pop()
  52  * from the tail
  53  */
  54 void *xbt_fifo_pop(xbt_fifo_t l)
  55 {
  56   xbt_fifo_item_t item;
  57   void *content;
  58
  59   item = xbt_fifo_pop_item(l);
  60   if(item==NULL) return NULL;
  61
  62   content = item->content;
  63   xbt_fifo_freeitem(item);
  64   return content;
  65 }
  66
  67 /*
  68  * xbt_fifo_unshift()
  69  * at the head
  70  */
  71 xbt_fifo_item_t xbt_fifo_unshift(xbt_fifo_t l, void *t)
  72 {
  73   xbt_fifo_item_t new;
  74
  75   new = xbt_fifo_newitem();
  76   new->content = t;
  77   xbt_fifo_unshift_item(l,new);
  78   return new;
  79 }
  80
  81 /*
  82  * xbt_fifo_shift()
  83  * from the head
  84  */
  85 void *xbt_fifo_shift(xbt_fifo_t l)
  86 {
  87   xbt_fifo_item_t item;
  88   void *content;
  89
  90   item = xbt_fifo_shift_item(l);
  91   if(l==NULL) return NULL;
  92
  93   content = item->content;
  94   xbt_fifo_freeitem(item);
  95   return content;
  96 }
  97
  98 /*
  99  * xbt_fifo_push_item()
 100  * at the tail
 101  */
 102 void xbt_fifo_push_item(xbt_fifo_t l, xbt_fifo_item_t new)
 103 {
 104   (l->count)++;
 105   if (l->head == NULL) {
 106     l->head = new;
 107     l->tail = new;
 108     return;
 109   }
 110   new->prev = l->tail;
 111   new->prev->next = new;
 112   l->tail = new;
 113 }
 114
 115 /*
 116  * xbt_fifo_pop_item()
 117  * from the tail
 118  */
 119 xbt_fifo_item_t xbt_fifo_pop_item(xbt_fifo_t l)
 120 {
 121   xbt_fifo_item_t item;
 122
 123   if (l->tail == NULL)
 124     return NULL;
 125
 126   item = l->tail;
 127
 128   l->tail = item->prev;
 129   if (l->tail == NULL)
 130     l->head = NULL;
 131   else
 132     l->tail->next = NULL;
 133
 134   (l->count)--;
 135   return item;
 136 }
 137
 138 /*
 139  * xbt_fifo_unshift_item()
 140  * at the head
 141  */
 142 void xbt_fifo_unshift_item(xbt_fifo_t l, xbt_fifo_item_t new)
 143 {
 144   (l->count)++;
 145   if (l->head == NULL) {
 146     l->head = new;
 147     l->tail = new;
 148     return;
 149   }
 150   new->next = l->head;
 151   new->next->prev = new;
 152   l->head = new;
 153   return;
 154 }
 155
 156 /*
 157  * xbt_fifo_shift_item()
 158  * from the head
 159  */
 160 xbt_fifo_item_t xbt_fifo_shift_item(xbt_fifo_t l)
 161 {
 162   xbt_fifo_item_t item;
 163
 164   if (l->head == NULL)
 165     return NULL;
 166
 167   item = l->head;
 168
 169   l->head = item->next;
 170   if (l->head == NULL)
 171     l->tail = NULL;
 172   else
 173     l->head->prev = NULL;
 174
 175   (l->count)--;
 176   return item;
 177 }
 178
 179 /*
 180  * xbt_fifo_remove()
 181  *   removes an xbt_fifo_item_t using its content from the xbt_fifo
 182  */
 183 void xbt_fifo_remove(xbt_fifo_t l, void *t)
 184 {
 185   xbt_fifo_item_t current, current_next;
 186
 187
 188   for (current = l->head; current; current = current_next) {
 189     current_next = current->next;
 190     if (current->content != t)
 191       continue;
 192     /* remove the item */
 193     xbt_fifo_remove_item(l, current);
 194     xbt_fifo_freeitem(current);
 195     /* WILL NOT REMOVE DUPLICATES */
 196     break;
 197   }
 198   return;
 199 }
 200
 201 /*
 202  * xbt_fifo_remove_item()
 203  *   removes a given xbt_fifo_item_t from the xbt_fifo
 204  */
 205 void xbt_fifo_remove_item(xbt_fifo_t l, xbt_fifo_item_t current)
 206 {
 207   if (l->head == l->tail) {     /* special case */
 208       l->head = NULL;
 209       l->tail = NULL;
 210       (l->count)--;
 211       return;
 212     }
 213
 214     if (current == l->head) {   /* It's the head */
 215       l->head = current->next;
 216       l->head->prev = NULL;
 217     } else if (current == l->tail) {    /* It's the tail */
 218       l->tail = current->prev;
 219       l->tail->next = NULL;
 220     } else {                    /* It's in the middle */
 221       current->prev->next = current->next;
 222       current->next->prev = current->prev;
 223     }
 224     (l->count)--;
 225 }
 226
 227 /*
 228  * xbt_fifo_is_in()
 229  */
 230 int xbt_fifo_is_in(xbt_fifo_t f, void *content)
 231 {
 232   xbt_fifo_item_t item = xbt_fifo_getFirstitem(f);
 233   while (item) {
 234     if (item->content == content)
 235       return 1;
 236     item = item->next;
 237   }
 238   return 0;
 239 }
 240
 241 /*
 242  * xbt_fifo_to_array()
 243  */
 244 void **xbt_fifo_to_array(xbt_fifo_t f)
 245 {
 246   void **array;
 247   xbt_fifo_item_t b;
 248   int i;
 249
 250   if (f->count == 0)
 251     return NULL;
 252   else
 253     array = xbt_new0(void *, f->count);
 254
 255   for (i = 0, b = xbt_fifo_getFirstitem(f); b; i++, b = b->next) {
 256     array[i] = b->content;
 257   }
 258   return array;
 259 }
 260
 261 /*
 262  * xbt_fifo_Copy()
 263  */
 264 xbt_fifo_t xbt_fifo_copy(xbt_fifo_t f)
 265 {
 266   xbt_fifo_t copy = NULL;
 267   xbt_fifo_item_t b;
 268
 269   copy = xbt_fifo_new();
 270
 271   for (b = xbt_fifo_getFirstitem(f); b; b = b->next) {
 272     xbt_fifo_push(copy, b->content);
 273   }
 274   return copy;
 275 }
 276
 277 /*
 278  * xbt_fifo_newitem()
 279  */
 280 xbt_fifo_item_t xbt_fifo_newitem(void)
 281 {
 282   return xbt_new0(struct xbt_fifo_item,1);
 283 }
 284
 285 void xbt_fifo_set_item_content(xbt_fifo_item_t i , void *v)
 286 {
 287   xbt_fifo_setItemcontent(i,v);
 288 }
 289
 290 void *xbt_fifo_get_item_content(xbt_fifo_item_t i)
 291 {
 292   return xbt_fifo_getItemcontent(i);
 293 }
 294
 295 /*
 296  * xbt_fifo_freeitem()
 297  */
 298 void xbt_fifo_freeitem(xbt_fifo_item_t b)
 299 {
 300   free(b);
 301   return;
 302 }
 303
 304 int xbt_fifo_size(xbt_fifo_t f)
 305 {
 306   return f->count;
 307 }
 308
 309