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