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