src/xbt/fifo.c

   1 /* Copyright (c) 2004-2014. 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 "src/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 #define fifo_item_mallocator_free_f xbt_free_f
  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 = xbt_new0(struct xbt_fifo, 1);
  27
  28   return fifo;
  29 }
  30
  31 /** Destructor
  32  * \param l poor victim
  33  *
  34  * Free the fifo structure. None of the objects that was in the fifo is however modified.
  35  */
  36 void xbt_fifo_free(xbt_fifo_t l)
  37 {
  38   xbt_fifo_reset(l);
  39   xbt_free(l);
  40 }
  41
  42 /**
  43  * \brief Makes a fifo empty.
  44  * \param l a fifo
  45  *
  46  * None of the objects that was in the fifo is however modified.
  47  */
  48 void xbt_fifo_reset(xbt_fifo_t l)
  49 {
  50   xbt_fifo_item_t b = xbt_fifo_get_first_item(l);
  51
  52   while (b) {
  53     xbt_fifo_item_t tmp = b;
  54     b = b->next;
  55     xbt_fifo_free_item(tmp);
  56   }
  57   l->head = NULL;
  58   l->tail = NULL;
  59 }
  60
  61 /** Push
  62  * \param l list
  63  * \param t element
  64  * \return the bucket that was just added
  65  *
  66  * Add an object at the tail of the list
  67  */
  68 xbt_fifo_item_t xbt_fifo_push(xbt_fifo_t l, void *t)
  69 {
  70   xbt_fifo_item_t new = xbt_fifo_new_item();
  71   new->content = t;
  72
  73   xbt_fifo_push_item(l, new);
  74   return new;
  75 }
  76
  77 /** Pop
  78  * \param l list
  79  * \returns the object stored at the tail of the list.
  80  *
  81  * Removes and returns the object stored at the tail of the list.
  82  * Returns NULL if the list is empty.
  83  */
  84 void *xbt_fifo_pop(xbt_fifo_t l)
  85 {
  86   if (l == NULL)
  87     return NULL;
  88   xbt_fifo_item_t item = xbt_fifo_pop_item(l);
  89   if (!item)
  90     return NULL;
  91
  92   void *content = item->content;
  93   xbt_fifo_free_item(item);
  94   return content;
  95 }
  96
  97 /**
  98  * \param l list
  99  * \param t element
 100  * \return the bucket that was just added
 101  *
 102  * Add an object at the head of the list
 103  */
 104 xbt_fifo_item_t xbt_fifo_unshift(xbt_fifo_t l, void *t)
 105 {
 106   xbt_fifo_item_t new = xbt_fifo_new_item();
 107   new->content = t;
 108   xbt_fifo_unshift_item(l, new);
 109   return new;
 110 }
 111
 112 /** Shift
 113  * \param l list
 114  * \returns the object stored at the head of the list.
 115  *
 116  * Removes and returns the object stored at the head of the list.
 117  * Returns NULL if the list is empty.
 118  */
 119 void *xbt_fifo_shift(xbt_fifo_t l)
 120 {
 121   if (l == NULL)
 122     return NULL;
 123   xbt_fifo_item_t item = xbt_fifo_shift_item(l);
 124   if (!item)
 125     return NULL;
 126
 127   void *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_assert((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   if (l->tail == NULL)
 161     return NULL;
 162
 163   xbt_fifo_item_t item = l->tail;
 164
 165   l->tail = item->prev;
 166   if (l->tail == NULL)
 167     l->head = NULL;
 168   else
 169     l->tail->next = NULL;
 170
 171   (l->count)--;
 172
 173   item->prev = NULL;
 174
 175   return item;
 176 }
 177
 178 /** Push a bucket
 179  * \param l list
 180  * \param new bucket
 181  *
 182  * Hook up this bucket at the head of the list
 183  */
 184 void xbt_fifo_unshift_item(xbt_fifo_t l, xbt_fifo_item_t new)
 185 {
 186   xbt_assert((new->next == NULL) && (new->prev == NULL), "Invalid item!");
 187   (l->count)++;
 188   if (l->head == NULL) {
 189     l->head = new;
 190     l->tail = new;
 191     return;
 192   }
 193   new->next = l->head;
 194   new->next->prev = new;
 195   l->head = new;
 196 }
 197
 198 /** Shift bucket
 199  * \param l
 200  * \returns the bucket that was at the head of the list.
 201  *
 202  * Returns NULL if the list was empty.
 203  */
 204 xbt_fifo_item_t xbt_fifo_shift_item(xbt_fifo_t l)
 205 {
 206   if (l->head == NULL)
 207     return NULL;
 208
 209   xbt_fifo_item_t item = l->head;
 210
 211   l->head = item->next;
 212   if (l->head == NULL)
 213     l->tail = NULL;
 214   else
 215     l->head->prev = NULL;
 216
 217   (l->count)--;
 218
 219   item->next = NULL;
 220
 221   return item;
 222 }
 223
 224 /**
 225  * \param l
 226  * \param t an objet
 227  *
 228  * removes the first occurrence of \a t from \a l.
 229  * \warning it will not remove duplicates
 230  * \return 1 if an item was removed and 0 otherwise.
 231  */
 232 int xbt_fifo_remove(xbt_fifo_t l, void *t)
 233 {
 234   xbt_fifo_item_t current;
 235   xbt_fifo_item_t current_next;
 236
 237   for (current = l->head; current; current = current_next) {
 238     current_next = current->next;
 239     if (current->content == t) {
 240       /* remove the item */
 241       xbt_fifo_remove_item(l, current);
 242       xbt_fifo_free_item(current);
 243       /* WILL NOT REMOVE DUPLICATES */
 244       return 1;
 245     }
 246   }
 247   return 0;
 248 }
 249
 250 /**
 251  * \param l
 252  * \param t an objet
 253  *
 254  * removes all occurrences of \a t from \a l.
 255  * \return 1 if an item was removed and 0 otherwise.
 256  */
 257 int xbt_fifo_remove_all(xbt_fifo_t l, void *t)
 258 {
 259   xbt_fifo_item_t current;
 260   xbt_fifo_item_t current_next;
 261   int res = 0;
 262
 263   for (current = l->head; current; current = current_next) {
 264     current_next = current->next;
 265     if (current->content == t){
 266       /* remove the item */
 267       xbt_fifo_remove_item(l, current);
 268       xbt_fifo_free_item(current);
 269       res = 1;
 270     }
 271   }
 272   return res;
 273 }
 274
 275 /**
 276  * \param l a list
 277  * \param current a bucket
 278  *
 279  * removes a bucket \a current from the list \a l. This function implicitly
 280  * assumes (and doesn't check!) that this item belongs to this list...
 281  */
 282 void xbt_fifo_remove_item(xbt_fifo_t l, xbt_fifo_item_t current)
 283 {
 284   if (l->head == l->tail) {     /* special case */
 285     xbt_assert((current == l->head), "This item is not in the list!");
 286     l->head = NULL;
 287     l->tail = NULL;
 288     (l->count)--;
 289     current->prev = NULL;
 290     current->next = NULL;
 291     return;
 292   }
 293
 294   if (current == l->head) {     /* It's the head */
 295     l->head = current->next;
 296     l->head->prev = NULL;
 297   } else if (current == l->tail) {      /* It's the tail */
 298     l->tail = current->prev;
 299     l->tail->next = NULL;
 300   } else {                      /* It's in the middle */
 301     current->prev->next = current->next;
 302     current->next->prev = current->prev;
 303   }
 304   (l->count)--;
 305   current->prev = NULL;
 306   current->next = NULL;
 307 }
 308
 309 /**
 310  * \param f a list
 311  * \param content an object
 312  * \return 1 if \a content is in \a f.
 313  */
 314 int xbt_fifo_is_in(xbt_fifo_t f, void *content)
 315 {
 316   xbt_fifo_item_t item = xbt_fifo_get_first_item(f);
 317   while (item) {
 318     if (item->content == content)
 319       return 1;
 320     item = item->next;
 321   }
 322   return 0;
 323 }
 324
 325 /**
 326  * @brief Search the given element in the fifo using a comparison function
 327  *
 328  * This function allows to search an item with a user provided function instead
 329  * of the pointer comparison used elsewhere in this module. Assume for example that you have a fifo of
 330  * strings. You cannot use xbt_fifo_remove() to remove, say, "TOTO" from it because internally, xbt_fifo_remove()
 331  * will do something like "if (item->content == "toto"), then remove it". And the pointer to the item content and the
 332  * pointer to "toto" will never match. As a solution, the current function provides a way to search elements that are
 333  * semantically equivalent instead of only syntactically. So, removing "Toto" from a fifo can be achieved this way:
 334  *
 335  *  @verbatim
 336 int my_comparison_function(void *searched, void *seen) {
 337   return !strcmp(searched, seen);
 338 }
 339
 340   xbt_fifo_remove_item(fifo, xbt_fifo_search_item(fifo, my_comparison_function, "Toto"));
 341 @endverbatim
 342  *
 343  * \param f a fifo list
 344  * \param cmp_fun the comparison function. Prototype: void *a,void *b -> int. Semantic: returns true iff a=b
 345  * @param closure the element to search. It will be provided as first argument to each call of cmp_fun
 346  * \return the first item matching the comparison function, or NULL if no such item exists
 347  */
 348 xbt_fifo_item_t xbt_fifo_search_item(xbt_fifo_t f, int_f_pvoid_pvoid_t cmp_fun, void *closure) {
 349   xbt_fifo_item_t item = xbt_fifo_get_first_item(f);
 350   while (item) {
 351     if (cmp_fun(closure, item->content))
 352       return item;
 353     item = item->next;
 354   }
 355   return NULL;
 356 }
 357
 358 /**
 359  * \param f a list
 360  * \return a table with the objects stored in \a f.
 361  */
 362 void **xbt_fifo_to_array(xbt_fifo_t f)
 363 {
 364   void **array;
 365   xbt_fifo_item_t b;
 366   int i;
 367
 368   if (f->count == 0)
 369     return NULL;
 370   else
 371     array = xbt_new0(void *, f->count);
 372
 373   for (i = 0, b = xbt_fifo_get_first_item(f); b; i++, b = b->next) {
 374     array[i] = b->content;
 375   }
 376   return array;
 377 }
 378
 379 /**
 380  * \param f a list
 381  * \return a copy of \a f.
 382  */
 383 xbt_fifo_t xbt_fifo_copy(xbt_fifo_t f)
 384 {
 385   xbt_fifo_t copy = xbt_fifo_new();
 386   xbt_fifo_item_t b;
 387
 388   for (b = xbt_fifo_get_first_item(f); b; b = b->next) {
 389     xbt_fifo_push(copy, b->content);
 390   }
 391   return copy;
 392 }
 393
 394 /* Functions passed to the mallocator constructor */
 395 static void *fifo_item_mallocator_new_f(void)
 396 {
 397   return xbt_new(s_xbt_fifo_item_t, 1);
 398 }
 399
 400 static void fifo_item_mallocator_reset_f(void *item)
 401 {
 402   /* memset to zero like calloc */
 403   memset(item, 0, sizeof(s_xbt_fifo_item_t));
 404 }
 405
 406 /** Constructor
 407  * \return a new bucket
 408  */
 409 inline xbt_fifo_item_t xbt_fifo_new_item(void)
 410 {
 411   return xbt_mallocator_get(item_mallocator);
 412 }
 413
 414 /** \deprecated Use #xbt_fifo_new_item instead.
 415  */
 416 inline xbt_fifo_item_t xbt_fifo_newitem(void)
 417 {
 418   XBT_CWARN(xbt_fifo, "This function is deprecated. Use xbt_fifo_new_item.");
 419   return xbt_fifo_new_item();
 420 }
 421
 422 /**
 423  * \param i a bucket
 424  * \param v an object
 425  *
 426  * stores \a v in \a i.
 427  */
 428 inline void xbt_fifo_set_item_content(xbt_fifo_item_t i, void *v)
 429 {
 430   xbt_fifo_setItemcontent(i, v);
 431 }
 432
 433 /**
 434  * \param i a bucket
 435  * \return the object stored \a i.
 436  */
 437 inline void *xbt_fifo_get_item_content(xbt_fifo_item_t i)
 438 {
 439   return xbt_fifo_getItemcontent(i);
 440 }
 441
 442 /** Destructor
 443  * \param b poor victim
 444  *
 445  * Free the bucket but does not modifies the object (if any) that was stored in it.
 446  */
 447 inline void xbt_fifo_free_item(xbt_fifo_item_t b)
 448 {
 449   xbt_mallocator_release(item_mallocator, b);
 450 }
 451
 452 /** Destructor
 453  * \deprecated Use #xbt_fifo_free_item instead.
 454  */
 455 inline void xbt_fifo_freeitem(xbt_fifo_item_t b)
 456 {
 457   XBT_CWARN(xbt_fifo, "This function is deprecated. Use xbt_fifo_free_item.");
 458   xbt_fifo_free_item(b);
 459 }
 460
 461 /**
 462  * \param f a list
 463  * \return the number of buckets in \a f.
 464  */
 465 inline int xbt_fifo_size(xbt_fifo_t f)
 466 {
 467   return f->count;
 468 }
 469
 470 /**
 471  * \param l a list
 472  * \return the head of \a l.
 473  *
 474  * Returns NULL if the list is empty.
 475  */
 476 inline xbt_fifo_item_t xbt_fifo_get_first_item(xbt_fifo_t l)
 477 {
 478   return l->head;
 479 }
 480
 481 /**
 482  * \param l a list
 483  * \return the tail of \a l.
 484  *
 485  * Returns NULL if the list is empty.
 486  */
 487 inline xbt_fifo_item_t xbt_fifo_get_last_item(xbt_fifo_t l)
 488 {
 489   return l->tail;
 490 }
 491
 492 /** \deprecated Use #xbt_fifo_get_first_item instead.
 493  */
 494 inline xbt_fifo_item_t xbt_fifo_getFirstItem(xbt_fifo_t l)
 495 {
 496   XBT_CWARN(xbt_fifo, "This function is deprecated. Use xbt_fifo_get_first_item.");
 497   return xbt_fifo_get_first_item(l);
 498 }
 499
 500 /**
 501  * \param i a bucket
 502  * \return the bucket that comes next
 503  *
 504  * Returns NULL if \a i is the tail of the list.
 505  */
 506 inline xbt_fifo_item_t xbt_fifo_get_next_item(xbt_fifo_item_t i)
 507 {
 508   if (i)
 509     return i->next;
 510   return NULL;
 511 }
 512
 513 /** \deprecated Use #xbt_fifo_get_next_item instead.
 514  */
 515 xbt_fifo_item_t xbt_fifo_getNextItem(xbt_fifo_item_t i)
 516 {
 517   XBT_CWARN(xbt_fifo, "This function is deprecated. Use xbt_fifo_get_next_item.");
 518   return xbt_fifo_get_next_item(i);
 519 }
 520
 521 /**
 522  * \param i a bucket
 523  * \return the bucket that is just before \a i.
 524  *
 525  * Returns NULL if \a i is the head of the list.
 526  */
 527 inline xbt_fifo_item_t xbt_fifo_get_prev_item(xbt_fifo_item_t i)
 528 {
 529   if (i)
 530     return i->prev;
 531   return NULL;
 532 }
 533
 534 /** \deprecated Use #xbt_fifo_get_prev_item instead.
 535  */
 536 xbt_fifo_item_t xbt_fifo_getPrevItem(xbt_fifo_item_t i)
 537 {
 538   XBT_WARN("This function is deprecated. Use xbt_fifo_get_prev_item.");
 539   return xbt_fifo_get_prev_item(i);
 540 }
 541
 542 /* Module init/exit handling the fifo item mallocator
 543  * These are internal XBT functions called by xbt_preinit/postexit().
 544  * It can be used several times to recreate the mallocator, for example when you switch to MC mode
 545  */
 546 void xbt_fifo_preinit()
 547 {
 548   item_mallocator = xbt_mallocator_new(65536, fifo_item_mallocator_new_f,
 549                                        fifo_item_mallocator_free_f, fifo_item_mallocator_reset_f);
 550 }
 551
 552 void xbt_fifo_postexit()
 553 {
 554   if (item_mallocator != NULL) {
 555     xbt_mallocator_free(item_mallocator);
 556     item_mallocator = NULL;
 557   }
 558 }
 559 /* @} */