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