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