src/xbt/fifo.c

   1 /* Copyright (c) 2004, 2005, 2006, 2007, 2008, 2009, 2010. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 #include "xbt/sysdep.h"
   8 #include "xbt/log.h"
   9 #include "xbt/mallocator.h"
  10 #include "fifo_private.h"
  11 #include "xbt_modinter.h"
  12
  13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_fifo, xbt, "FIFO");
  14
  15 static void *fifo_item_mallocator_new_f(void);
  16 static void fifo_item_mallocator_free_f(void *item);
  17 static void fifo_item_mallocator_reset_f(void *item);
  18
  19 static xbt_mallocator_t item_mallocator = NULL;
  20
  21 /** Constructor
  22  * \return a new fifo
  23  */
  24 xbt_fifo_t xbt_fifo_new(void)
  25 {
  26   xbt_fifo_t fifo;
  27   fifo = xbt_new0(struct xbt_fifo, 1);
  28
  29   if (item_mallocator == NULL) {
  30     item_mallocator = xbt_mallocator_new(256,
  31                                          fifo_item_mallocator_new_f,
  32                                          fifo_item_mallocator_free_f,
  33                                          fifo_item_mallocator_reset_f);
  34   }
  35   return fifo;
  36 }
  37
  38 /** Destructor
  39  * \param l poor victim
  40  *
  41  * Free the fifo structure. None of the objects that was in the fifo is however modified.
  42  */
  43 void xbt_fifo_free(xbt_fifo_t l)
  44 {
  45   xbt_fifo_item_t b, tmp;
  46
  47   for (b = xbt_fifo_get_first_item(l); b;
  48        tmp = b, b = b->next, xbt_fifo_free_item(tmp));
  49   xbt_free(l);
  50   return;
  51 }
  52
  53 /** Push
  54  * \param l list
  55  * \param t element
  56  * \return the bucket that was just added
  57  *
  58  * Add an object at the tail of the list
  59  */
  60 xbt_fifo_item_t xbt_fifo_push(xbt_fifo_t l, void *t)
  61 {
  62   xbt_fifo_item_t new;
  63
  64   new = xbt_fifo_new_item();
  65   new->content = t;
  66
  67   xbt_fifo_push_item(l, new);
  68   return new;
  69 }
  70
  71 /** Pop
  72  * \param l list
  73  * \returns the object stored at the tail of the list.
  74  *
  75  * Removes and returns the object stored at the tail of the list.
  76  * Returns NULL if the list is empty.
  77  */
  78 void *xbt_fifo_pop(xbt_fifo_t l)
  79 {
  80   xbt_fifo_item_t item;
  81   void *content;
  82
  83   if (l == NULL)
  84     return NULL;
  85   if (!(item = xbt_fifo_pop_item(l)))
  86     return NULL;
  87
  88   content = item->content;
  89   xbt_fifo_free_item(item);
  90   return content;
  91 }
  92
  93 /**
  94  * \param l list
  95  * \param t element
  96  * \return the bucket that was just added
  97  *
  98  * Add an object at the head of the list
  99  */
 100 xbt_fifo_item_t xbt_fifo_unshift(xbt_fifo_t l, void *t)
 101 {
 102   xbt_fifo_item_t new;
 103
 104   new = xbt_fifo_new_item();
 105   new->content = t;
 106   xbt_fifo_unshift_item(l, new);
 107   return new;
 108 }
 109
 110 /** Shift
 111  * \param l list
 112  * \returns the object stored at the head of the list.
 113  *
 114  * Removes and returns the object stored at the head of the list.
 115  * Returns NULL if the list is empty.
 116  */
 117 void *xbt_fifo_shift(xbt_fifo_t l)
 118 {
 119   xbt_fifo_item_t item;
 120   void *content;
 121
 122   if (l == NULL)
 123     return NULL;
 124   if (!(item = xbt_fifo_shift_item(l)))
 125     return NULL;
 126
 127   content = item->content;
 128   xbt_fifo_free_item(item);
 129   return content;
 130 }
 131
 132 /** Push a bucket
 133  * \param l list
 134  * \param new bucket
 135  *
 136  * Hook up this bucket at the tail of the list
 137  */
 138 void xbt_fifo_push_item(xbt_fifo_t l, xbt_fifo_item_t new)
 139 {
 140   xbt_assert0((new->next == NULL) && (new->prev == NULL), "Invalid item!");
 141   (l->count)++;
 142   if (l->head == NULL) {
 143     l->head = new;
 144     l->tail = new;
 145     return;
 146   }
 147   new->prev = l->tail;
 148   new->prev->next = new;
 149   l->tail = new;
 150 }
 151
 152 /** Pop bucket
 153  * \param l
 154  * \returns the bucket that was at the tail of the list.
 155  *
 156  * Returns NULL if the list was empty.
 157  */
 158 xbt_fifo_item_t xbt_fifo_pop_item(xbt_fifo_t l)
 159 {
 160   xbt_fifo_item_t item;
 161
 162   if (l->tail == NULL)
 163     return NULL;
 164
 165   item = l->tail;
 166
 167   l->tail = item->prev;
 168   if (l->tail == NULL)
 169     l->head = NULL;
 170   else
 171     l->tail->next = NULL;
 172
 173   (l->count)--;
 174
 175   item->prev = NULL;
 176
 177   return item;
 178 }
 179
 180 /** Push a bucket
 181  * \param l list
 182  * \param new bucket
 183  *
 184  * Hook up this bucket at the head of the list
 185  */
 186 void xbt_fifo_unshift_item(xbt_fifo_t l, xbt_fifo_item_t new)
 187 {
 188   xbt_assert0((new->next == NULL) && (new->prev == NULL), "Invalid item!");
 189   (l->count)++;
 190   if (l->head == NULL) {
 191     l->head = new;
 192     l->tail = new;
 193     return;
 194   }
 195   new->next = l->head;
 196   new->next->prev = new;
 197   l->head = new;
 198   return;
 199 }
 200
 201 /** Shift bucket
 202  * \param l
 203  * \returns the bucket that was at the head of the list.
 204  *
 205  * Returns NULL if the list was empty.
 206  */
 207 xbt_fifo_item_t xbt_fifo_shift_item(xbt_fifo_t l)
 208 {
 209   xbt_fifo_item_t item;
 210
 211   if (l->head == NULL)
 212     return NULL;
 213
 214   item = l->head;
 215
 216   l->head = item->next;
 217   if (l->head == NULL)
 218     l->tail = NULL;
 219   else
 220     l->head->prev = NULL;
 221
 222   (l->count)--;
 223
 224   item->next = NULL;
 225
 226   return item;
 227 }
 228
 229 /**
 230  * \param l
 231  * \param t an objet
 232  *
 233  * removes the first occurence of \a t from \a l.
 234  * \warning it will not remove duplicates
 235  * \return 1 if an item was removed and 0 otherwise.
 236  */
 237 int xbt_fifo_remove(xbt_fifo_t l, void *t)
 238 {
 239   xbt_fifo_item_t current, current_next;
 240
 241
 242   for (current = l->head; current; current = current_next) {
 243     current_next = current->next;
 244     if (current->content != t)
 245       continue;
 246     /* remove the item */
 247     xbt_fifo_remove_item(l, current);
 248     xbt_fifo_free_item(current);
 249     /* WILL NOT REMOVE DUPLICATES */
 250     return 1;
 251   }
 252   return 0;
 253 }
 254
 255
 256 /**
 257  * \param l
 258  * \param t an objet
 259  *
 260  * removes all occurences of \a t from \a l.
 261  * \return 1 if an item was removed and 0 otherwise.
 262  */
 263 int xbt_fifo_remove_all(xbt_fifo_t l, void *t)
 264 {
 265   xbt_fifo_item_t current, current_next;
 266   int res = 0;
 267
 268   for (current = l->head; current; current = current_next) {
 269     current_next = current->next;
 270     if (current->content != t)
 271       continue;
 272     /* remove the item */
 273     xbt_fifo_remove_item(l, current);
 274     xbt_fifo_free_item(current);
 275     res = 1;
 276   }
 277   return res;
 278 }
 279
 280 /**
 281  * \param l a list
 282  * \param current a bucket
 283  *
 284  * removes a bucket \a current from the list \a l. This function implicitely
 285  * assumes (and doesn't check!) that this item belongs to this list...
 286  */
 287 void xbt_fifo_remove_item(xbt_fifo_t l, xbt_fifo_item_t current)
 288 {
 289   if (l->head == l->tail) {     /* special case */
 290     xbt_assert0((current == l->head), "This item is not in the list!");
 291     l->head = NULL;
 292     l->tail = NULL;
 293     (l->count)--;
 294     current->prev = current->next = NULL;
 295     return;
 296   }
 297
 298   if (current == l->head) {     /* It's the head */
 299     l->head = current->next;
 300     l->head->prev = NULL;
 301   } else if (current == l->tail) {      /* It's the tail */
 302     l->tail = current->prev;
 303     l->tail->next = NULL;
 304   } else {                      /* It's in the middle */
 305     current->prev->next = current->next;
 306     current->next->prev = current->prev;
 307   }
 308   (l->count)--;
 309   current->prev = current->next = NULL;
 310 }
 311
 312 /**
 313  * \param f a list
 314  * \param content an object
 315  * \return 1 if \a content is in \a f.
 316  */
 317 int xbt_fifo_is_in(xbt_fifo_t f, void *content)
 318 {
 319   xbt_fifo_item_t item = xbt_fifo_get_first_item(f);
 320   while (item) {
 321     if (item->content == content)
 322       return 1;
 323     item = item->next;
 324   }
 325   return 0;
 326 }
 327
 328 /**
 329  * \param f a list
 330  * \return a table with the objects stored in \a f.
 331  */
 332 void **xbt_fifo_to_array(xbt_fifo_t f)
 333 {
 334   void **array;
 335   xbt_fifo_item_t b;
 336   int i;
 337
 338   if (f->count == 0)
 339     return NULL;
 340   else
 341     array = xbt_new0(void *, f->count);
 342
 343   for (i = 0, b = xbt_fifo_get_first_item(f); b; i++, b = b->next) {
 344     array[i] = b->content;
 345   }
 346   return array;
 347 }
 348
 349 /**
 350  * \param f a list
 351  * \return a copy of \a f.
 352  */
 353 xbt_fifo_t xbt_fifo_copy(xbt_fifo_t f)
 354 {
 355   xbt_fifo_t copy = NULL;
 356   xbt_fifo_item_t b;
 357
 358   copy = xbt_fifo_new();
 359
 360   for (b = xbt_fifo_get_first_item(f); b; b = b->next) {
 361     xbt_fifo_push(copy, b->content);
 362   }
 363   return copy;
 364 }
 365
 366 /* Functions passed to the mallocator constructor */
 367 static void *fifo_item_mallocator_new_f(void)
 368 {
 369   return xbt_new(s_xbt_fifo_item_t, 1);
 370 }
 371
 372 static void fifo_item_mallocator_free_f(void *item)
 373 {
 374   xbt_free(item);
 375 }
 376
 377 static void fifo_item_mallocator_reset_f(void *item)
 378 {
 379   /* memset to zero like calloc */
 380   memset(item, 0, sizeof(s_xbt_fifo_item_t));
 381 }
 382
 383 /** Constructor
 384  * \return a new bucket
 385  */
 386 XBT_INLINE xbt_fifo_item_t xbt_fifo_new_item(void)
 387 {
 388   return xbt_mallocator_get(item_mallocator);
 389 }
 390
 391 /** \deprecated Use #xbt_fifo_new_item instead.
 392  */
 393 XBT_INLINE xbt_fifo_item_t xbt_fifo_newitem(void)
 394 {
 395   WARN0("This function is deprecated. Use xbt_fifo_new_item.");
 396   return xbt_fifo_new_item();
 397 }
 398
 399 /**
 400  * \param i a bucket
 401  * \param v an object
 402  *
 403  * stores \a v in \a i.
 404  */
 405 XBT_INLINE void xbt_fifo_set_item_content(xbt_fifo_item_t i, void *v)
 406 {
 407   xbt_fifo_setItemcontent(i, v);
 408 }
 409
 410 /**
 411  * \param i a bucket
 412  * \return the object stored \a i.
 413  */
 414 XBT_INLINE void *xbt_fifo_get_item_content(xbt_fifo_item_t i)
 415 {
 416   return xbt_fifo_getItemcontent(i);
 417 }
 418
 419 /** Destructor
 420  * \param b poor victim
 421  *
 422  * Free the bucket but does not modifies the object (if any) that was stored in it.
 423  */
 424 XBT_INLINE void xbt_fifo_free_item(xbt_fifo_item_t b)
 425 {
 426   xbt_mallocator_release(item_mallocator, b);
 427   return;
 428 }
 429
 430 /** Destructor
 431  * \deprecated Use #xbt_fifo_free_item instead.
 432  */
 433 XBT_INLINE void xbt_fifo_freeitem(xbt_fifo_item_t b)
 434 {
 435   WARN0("This function is deprecated. Use xbt_fifo_free_item.");
 436   xbt_fifo_free_item(b);
 437   return;
 438 }
 439
 440 /**
 441  * \param f a list
 442  * \return the number of buckets in \a f.
 443  */
 444 XBT_INLINE int xbt_fifo_size(xbt_fifo_t f)
 445 {
 446   return f->count;
 447 }
 448
 449 /**
 450  * \param l a list
 451  * \return the head of \a l.
 452  */
 453 XBT_INLINE xbt_fifo_item_t xbt_fifo_get_first_item(xbt_fifo_t l)
 454 {
 455   return l->head;
 456 }
 457
 458 /** \deprecated Use #xbt_fifo_get_first_item instead.
 459  */
 460 XBT_INLINE xbt_fifo_item_t xbt_fifo_getFirstItem(xbt_fifo_t l)
 461 {
 462   WARN0("This function is deprecated. Use xbt_fifo_get_first_item.");
 463   return xbt_fifo_get_first_item(l);
 464 }
 465
 466 /**
 467  * \param i a bucket
 468  * \return the bucket that comes next
 469  */
 470 XBT_INLINE xbt_fifo_item_t xbt_fifo_get_next_item(xbt_fifo_item_t i)
 471 {
 472   if (i)
 473     return i->next;
 474   return NULL;
 475 }
 476
 477 /** \deprecated Use #xbt_fifo_get_next_item instead.
 478  */
 479 xbt_fifo_item_t xbt_fifo_getNextItem(xbt_fifo_item_t i)
 480 {
 481   WARN0("This function is deprecated. Use xbt_fifo_get_next_item.");
 482   return xbt_fifo_get_next_item(i);
 483 }
 484
 485 /**
 486  * \param i a bucket
 487  * \return the bucket that is just before \a i.
 488  */
 489 XBT_INLINE xbt_fifo_item_t xbt_fifo_get_prev_item(xbt_fifo_item_t i)
 490 {
 491   if (i)
 492     return i->prev;
 493   return NULL;
 494 }
 495
 496 /** \deprecated Use #xbt_fifo_get_prev_item instead.
 497  */
 498 xbt_fifo_item_t xbt_fifo_getPrevItem(xbt_fifo_item_t i)
 499 {
 500   WARN0("This function is deprecated. Use xbt_fifo_get_prev_item.");
 501   return xbt_fifo_get_prev_item(i);
 502 }
 503
 504 /**
 505  * Destroy the fifo item mallocator.
 506  * This is an internal XBT function called by xbt_exit().
 507  */
 508 void xbt_fifo_exit(void)
 509 {
 510   if (item_mallocator != NULL) {
 511     xbt_mallocator_free(item_mallocator);
 512     item_mallocator = NULL;
 513   }
 514 }
 515
 516 /* @} */