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 /** \name Functions
  15  *  \ingroup XBT_fifo
  16  */
  17 /*@{*/
  18
  19 /** Constructor
  20  * \return a new fifo
  21  */
  22 xbt_fifo_t xbt_fifo_new(void)
  23 {
  24   xbt_fifo_t fifo;
  25   fifo = xbt_new0(struct xbt_fifo,1);
  26   return fifo;
  27 }
  28
  29 /** Destructor
  30  * \param l poor victim
  31  *
  32  * Free the fifo structure. None of the objects that was in the fifo is however modified.
  33  */
  34 void xbt_fifo_free(xbt_fifo_t l)
  35 {
  36   xbt_fifo_item_t b, tmp;
  37
  38   for (b = xbt_fifo_getFirstitem(l); b;
  39        tmp = b, b = b->next, xbt_fifo_freeitem(tmp));
  40   free(l);
  41   return;
  42 }
  43
  44 /* Push
  45  * \param l list
  46  * \param t element
  47  * \return the bucket that was just added
  48  *
  49  * Add an object at the tail of the list
  50  */
  51 xbt_fifo_item_t xbt_fifo_push(xbt_fifo_t l, void *t)
  52 {
  53   xbt_fifo_item_t new;
  54
  55   new = xbt_fifo_newitem();
  56   new->content = t;
  57
  58   xbt_fifo_push_item(l,new);
  59   return new;
  60 }
  61
  62 /** Pop
  63  * \param l list
  64  * \returns the object stored at the tail of the list.
  65  *
  66  * Removes and returns the object stored at the tail of the list.
  67  * Returns NULL if the list is empty.
  68  */
  69 void *xbt_fifo_pop(xbt_fifo_t l)
  70 {
  71   xbt_fifo_item_t item;
  72   void *content;
  73
  74   if(l==NULL) return NULL;
  75   if(!(item = xbt_fifo_pop_item(l))) return NULL;
  76
  77   content = item->content;
  78   xbt_fifo_freeitem(item);
  79   return content;
  80 }
  81
  82 /**
  83  * \param l list
  84  * \param t element
  85  * \return the bucket that was just added
  86  *
  87  * Add an object at the head of the list
  88  */
  89 xbt_fifo_item_t xbt_fifo_unshift(xbt_fifo_t l, void *t)
  90 {
  91   xbt_fifo_item_t new;
  92
  93   new = xbt_fifo_newitem();
  94   new->content = t;
  95   xbt_fifo_unshift_item(l,new);
  96   return new;
  97 }
  98
  99 /** Shift
 100  * \param l list
 101  * \returns the object stored at the head of the list.
 102  *
 103  * Removes and returns the object stored at the head of the list.
 104  * Returns NULL if the list is empty.
 105  */
 106 void *xbt_fifo_shift(xbt_fifo_t l)
 107 {
 108   xbt_fifo_item_t item;
 109   void *content;
 110
 111   if(l==NULL) return NULL;
 112   if(!(item = xbt_fifo_shift_item(l))) return NULL;
 113
 114   content = item->content;
 115   xbt_fifo_freeitem(item);
 116   return content;
 117 }
 118
 119 /** Push a bucket
 120  * \param l list
 121  * \param new bucket
 122  *
 123  * Hook up this bucket at the tail of the list
 124  */
 125 void xbt_fifo_push_item(xbt_fifo_t l, xbt_fifo_item_t new)
 126 {
 127   (l->count)++;
 128   if (l->head == NULL) {
 129     l->head = new;
 130     l->tail = new;
 131     return;
 132   }
 133   new->prev = l->tail;
 134   new->prev->next = new;
 135   l->tail = new;
 136 }
 137
 138 /** Pop bucket
 139  * \param l
 140  * \returns the bucket that was at the tail of the list.
 141  *
 142  * Returns NULL if the list was empty.
 143  */
 144 xbt_fifo_item_t xbt_fifo_pop_item(xbt_fifo_t l)
 145 {
 146   xbt_fifo_item_t item;
 147
 148   if (l->tail == NULL)
 149     return NULL;
 150
 151   item = l->tail;
 152
 153   l->tail = item->prev;
 154   if (l->tail == NULL)
 155     l->head = NULL;
 156   else
 157     l->tail->next = NULL;
 158
 159   (l->count)--;
 160   return item;
 161 }
 162
 163 /** Push a bucket
 164  * \param l list
 165  * \param new bucket
 166  *
 167  * Hook up this bucket at the head of the list
 168  */
 169 void xbt_fifo_unshift_item(xbt_fifo_t l, xbt_fifo_item_t new)
 170 {
 171   (l->count)++;
 172   if (l->head == NULL) {
 173     l->head = new;
 174     l->tail = new;
 175     return;
 176   }
 177   new->next = l->head;
 178   new->next->prev = new;
 179   l->head = new;
 180   return;
 181 }
 182
 183 /** Shift bucket
 184  * \param l
 185  * \returns the bucket that was at the head of the list.
 186  *
 187  * Returns NULL if the list was empty.
 188  */
 189 xbt_fifo_item_t xbt_fifo_shift_item(xbt_fifo_t l)
 190 {
 191   xbt_fifo_item_t item;
 192
 193   if (l->head == NULL)
 194     return NULL;
 195
 196   item = l->head;
 197
 198   l->head = item->next;
 199   if (l->head == NULL)
 200     l->tail = NULL;
 201   else
 202     l->head->prev = NULL;
 203
 204   (l->count)--;
 205   return item;
 206 }
 207
 208 /**
 209  * \param l
 210  * \param t an objet
 211  *
 212  * removes the first occurence of \a t from \a l.
 213  * \warning it will not remove duplicates
 214  */
 215 void xbt_fifo_remove(xbt_fifo_t l, void *t)
 216 {
 217   xbt_fifo_item_t current, current_next;
 218
 219
 220   for (current = l->head; current; current = current_next) {
 221     current_next = current->next;
 222     if (current->content != t)
 223       continue;
 224     /* remove the item */
 225     xbt_fifo_remove_item(l, current);
 226     xbt_fifo_freeitem(current);
 227     /* WILL NOT REMOVE DUPLICATES */
 228     break;
 229   }
 230   return;
 231 }
 232
 233 /**
 234  * \param l a list
 235  * \param current a bucket
 236  *
 237  * removes a the bucket \a current from the list \a l
 238  */
 239 void xbt_fifo_remove_item(xbt_fifo_t l, xbt_fifo_item_t current)
 240 {
 241   if (l->head == l->tail) {     /* special case */
 242       l->head = NULL;
 243       l->tail = NULL;
 244       (l->count)--;
 245       return;
 246     }
 247
 248     if (current == l->head) {   /* It's the head */
 249       l->head = current->next;
 250       l->head->prev = NULL;
 251     } else if (current == l->tail) {    /* It's the tail */
 252       l->tail = current->prev;
 253       l->tail->next = NULL;
 254     } else {                    /* It's in the middle */
 255       current->prev->next = current->next;
 256       current->next->prev = current->prev;
 257     }
 258     (l->count)--;
 259 }
 260
 261 /**
 262  * \param f a list
 263  * \param content an object
 264  * \return 1 if \a content is in \a f.
 265  */
 266 int xbt_fifo_is_in(xbt_fifo_t f, void *content)
 267 {
 268   xbt_fifo_item_t item = xbt_fifo_getFirstitem(f);
 269   while (item) {
 270     if (item->content == content)
 271       return 1;
 272     item = item->next;
 273   }
 274   return 0;
 275 }
 276
 277 /**
 278  * \param f a list
 279  * \return a table with the objects stored in \a f.
 280  */
 281 void **xbt_fifo_to_array(xbt_fifo_t f)
 282 {
 283   void **array;
 284   xbt_fifo_item_t b;
 285   int i;
 286
 287   if (f->count == 0)
 288     return NULL;
 289   else
 290     array = xbt_new0(void *, f->count);
 291
 292   for (i = 0, b = xbt_fifo_getFirstitem(f); b; i++, b = b->next) {
 293     array[i] = b->content;
 294   }
 295   return array;
 296 }
 297
 298 /**
 299  * \param f a list
 300  * \return a copy of \a f.
 301  */
 302 xbt_fifo_t xbt_fifo_copy(xbt_fifo_t f)
 303 {
 304   xbt_fifo_t copy = NULL;
 305   xbt_fifo_item_t b;
 306
 307   copy = xbt_fifo_new();
 308
 309   for (b = xbt_fifo_getFirstitem(f); b; b = b->next) {
 310     xbt_fifo_push(copy, b->content);
 311   }
 312   return copy;
 313 }
 314
 315 /** Constructor
 316  * \return a new bucket
 317  */
 318 xbt_fifo_item_t xbt_fifo_newitem(void)
 319 {
 320   return xbt_new0(struct xbt_fifo_item,1);
 321 }
 322
 323 /**
 324  * \param i a bucket
 325  * \param v an object
 326  *
 327  * stores \a v in \a i.
 328  */
 329 void xbt_fifo_set_item_content(xbt_fifo_item_t i , void *v)
 330 {
 331   xbt_fifo_setItemcontent(i,v);
 332 }
 333
 334 /**
 335  * \param i a bucket
 336  * \return the object stored \a i.
 337  */
 338 void *xbt_fifo_get_item_content(xbt_fifo_item_t i)
 339 {
 340   return xbt_fifo_getItemcontent(i);
 341 }
 342
 343 /** Destructor
 344  * \param b poor victim
 345  *
 346  * Free the bucket but does not modifies the object (if any) that was stored in it.
 347  */
 348 void xbt_fifo_freeitem(xbt_fifo_item_t b)
 349 {
 350   free(b);
 351   return;
 352 }
 353
 354 /**
 355  * \param f a list
 356  * \return the number of buckets in \a f.
 357  */
 358 int xbt_fifo_size(xbt_fifo_t f)
 359 {
 360   return f->count;
 361 }
 362
 363 /**
 364  * \param l a list
 365  * \return the head of \a l.
 366  */
 367 xbt_fifo_item_t xbt_fifo_getFirstItem(xbt_fifo_t l)
 368 {
 369   return l->head;
 370 }
 371
 372 /**
 373  * \param i a bucket
 374  * \return the bucket that comes next
 375  */
 376 xbt_fifo_item_t xbt_fifo_getNextItem(xbt_fifo_item_t i)
 377 {
 378   if(i) return i->next;
 379   return NULL;
 380 }
 381
 382 /**
 383  * \param i a bucket
 384  * \return the bucket that is just before \a i.
 385  */
 386 xbt_fifo_item_t xbt_fifo_getPrevItem(xbt_fifo_item_t i)
 387 {
 388   if(i) return i->prev;
 389   return NULL;
 390 }
 391 /*@}*/
 392
 393