src/xbt/fifo.c

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