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   return fifo;
  30 }
  31
  32
  33 /** Destructor
  34  * \param l poor victim
  35  *
  36  * Free the fifo structure. None of the objects that was in the fifo is however modified.
  37  */
  38 void xbt_fifo_free(xbt_fifo_t l)
  39 {
  40   xbt_fifo_item_t b, tmp;
  41
  42   for (b = xbt_fifo_get_first_item(l); b;
  43        tmp = b, b = b->next, xbt_fifo_free_item(tmp));
  44   xbt_free(l);
  45   return;
  46 }
  47
  48 /** Push
  49  * \param l list
  50  * \param t element
  51  * \return the bucket that was just added
  52  *
  53  * Add an object at the tail of the list
  54  */
  55 xbt_fifo_item_t xbt_fifo_push(xbt_fifo_t l, void *t)
  56 {
  57   xbt_fifo_item_t new;
  58
  59   new = xbt_fifo_new_item();
  60   new->content = t;
  61
  62   xbt_fifo_push_item(l, new);
  63   return new;
  64 }
  65
  66 /** Pop
  67  * \param l list
  68  * \returns the object stored at the tail of the list.
  69  *
  70  * Removes and returns the object stored at the tail of the list.
  71  * Returns NULL if the list is empty.
  72  */
  73 void *xbt_fifo_pop(xbt_fifo_t l)
  74 {
  75   xbt_fifo_item_t item;
  76   void *content;
  77
  78   if (l == NULL)
  79     return NULL;
  80   if (!(item = xbt_fifo_pop_item(l)))
  81     return NULL;
  82
  83   content = item->content;
  84   xbt_fifo_free_item(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_new_item();
 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)
 118     return NULL;
 119   if (!(item = xbt_fifo_shift_item(l)))
 120     return NULL;
 121
 122   content = item->content;
 123   xbt_fifo_free_item(item);
 124   return content;
 125 }
 126
 127 /** Push a bucket
 128  * \param l list
 129  * \param new bucket
 130  *
 131  * Hook up this bucket at the tail of the list
 132  */
 133 void xbt_fifo_push_item(xbt_fifo_t l, xbt_fifo_item_t new)
 134 {
 135   xbt_assert0((new->next == NULL) && (new->prev == NULL), "Invalid item!");
 136   (l->count)++;
 137   if (l->head == NULL) {
 138     l->head = new;
 139     l->tail = new;
 140     return;
 141   }
 142   new->prev = l->tail;
 143   new->prev->next = new;
 144   l->tail = new;
 145 }
 146
 147 /** Pop bucket
 148  * \param l
 149  * \returns the bucket that was at the tail of the list.
 150  *
 151  * Returns NULL if the list was empty.
 152  */
 153 xbt_fifo_item_t xbt_fifo_pop_item(xbt_fifo_t l)
 154 {
 155   xbt_fifo_item_t item;
 156
 157   if (l->tail == NULL)
 158     return NULL;
 159
 160   item = l->tail;
 161
 162   l->tail = item->prev;
 163   if (l->tail == NULL)
 164     l->head = NULL;
 165   else
 166     l->tail->next = NULL;
 167
 168   (l->count)--;
 169
 170   item->prev = NULL;
 171
 172   return item;
 173 }
 174
 175 /** Push a bucket
 176  * \param l list
 177  * \param new bucket
 178  *
 179  * Hook up this bucket at the head of the list
 180  */
 181 void xbt_fifo_unshift_item(xbt_fifo_t l, xbt_fifo_item_t new)
 182 {
 183   xbt_assert0((new->next == NULL) && (new->prev == NULL), "Invalid item!");
 184   (l->count)++;
 185   if (l->head == NULL) {
 186     l->head = new;
 187     l->tail = new;
 188     return;
 189   }
 190   new->next = l->head;
 191   new->next->prev = new;
 192   l->head = new;
 193   return;
 194 }
 195
 196 /** Shift bucket
 197  * \param l
 198  * \returns the bucket that was at the head of the list.
 199  *
 200  * Returns NULL if the list was empty.
 201  */
 202 xbt_fifo_item_t xbt_fifo_shift_item(xbt_fifo_t l)
 203 {
 204   xbt_fifo_item_t item;
 205
 206   if (l->head == NULL)
 207     return NULL;
 208
 209   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 occurence 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, current_next;
 235
 236
 237   for (current = l->head; current; current = current_next) {
 238     current_next = current->next;
 239     if (current->content != t)
 240       continue;
 241     /* remove the item */
 242     xbt_fifo_remove_item(l, current);
 243     xbt_fifo_free_item(current);
 244     /* WILL NOT REMOVE DUPLICATES */
 245     return 1;
 246   }
 247   return 0;
 248 }
 249
 250
 251 /**
 252  * \param l
 253  * \param t an objet
 254  *
 255  * removes all occurences of \a t from \a l.
 256  * \return 1 if an item was removed and 0 otherwise.
 257  */
 258 int xbt_fifo_remove_all(xbt_fifo_t l, void *t)
 259 {
 260   xbt_fifo_item_t current, 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       continue;
 267     /* remove the item */
 268     xbt_fifo_remove_item(l, current);
 269     xbt_fifo_free_item(current);
 270     res = 1;
 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 implicitely
 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_assert0((current == l->head), "This item is not in the list!");
 286     l->head = NULL;
 287     l->tail = NULL;
 288     (l->count)--;
 289     current->prev = current->next = NULL;
 290     return;
 291   }
 292
 293   if (current == l->head) {     /* It's the head */
 294     l->head = current->next;
 295     l->head->prev = NULL;
 296   } else if (current == l->tail) {      /* It's the tail */
 297     l->tail = current->prev;
 298     l->tail->next = NULL;
 299   } else {                      /* It's in the middle */
 300     current->prev->next = current->next;
 301     current->next->prev = current->prev;
 302   }
 303   (l->count)--;
 304   current->prev = current->next = NULL;
 305 }
 306
 307 /**
 308  * \param f a list
 309  * \param content an object
 310  * \return 1 if \a content is in \a f.
 311  */
 312 int xbt_fifo_is_in(xbt_fifo_t f, void *content)
 313 {
 314   xbt_fifo_item_t item = xbt_fifo_get_first_item(f);
 315   while (item) {
 316     if (item->content == content)
 317       return 1;
 318     item = item->next;
 319   }
 320   return 0;
 321 }
 322
 323 /**
 324  * \param f a list
 325  * \return a table with the objects stored in \a f.
 326  */
 327 void **xbt_fifo_to_array(xbt_fifo_t f)
 328 {
 329   void **array;
 330   xbt_fifo_item_t b;
 331   int i;
 332
 333   if (f->count == 0)
 334     return NULL;
 335   else
 336     array = xbt_new0(void *, f->count);
 337
 338   for (i = 0, b = xbt_fifo_get_first_item(f); b; i++, b = b->next) {
 339     array[i] = b->content;
 340   }
 341   return array;
 342 }
 343
 344 /**
 345  * \param f a list
 346  * \return a copy of \a f.
 347  */
 348 xbt_fifo_t xbt_fifo_copy(xbt_fifo_t f)
 349 {
 350   xbt_fifo_t copy = NULL;
 351   xbt_fifo_item_t b;
 352
 353   copy = xbt_fifo_new();
 354
 355   for (b = xbt_fifo_get_first_item(f); b; b = b->next) {
 356     xbt_fifo_push(copy, b->content);
 357   }
 358   return copy;
 359 }
 360
 361 /* Functions passed to the mallocator constructor */
 362 static void *fifo_item_mallocator_new_f(void)
 363 {
 364   return xbt_new(s_xbt_fifo_item_t, 1);
 365 }
 366
 367 static void fifo_item_mallocator_free_f(void *item)
 368 {
 369   xbt_free(item);
 370 }
 371
 372 static void fifo_item_mallocator_reset_f(void *item)
 373 {
 374   /* memset to zero like calloc */
 375   memset(item, 0, sizeof(s_xbt_fifo_item_t));
 376 }
 377
 378 /** Constructor
 379  * \return a new bucket
 380  */
 381 XBT_INLINE xbt_fifo_item_t xbt_fifo_new_item(void)
 382 {
 383   return xbt_mallocator_get(item_mallocator);
 384 }
 385
 386 /** \deprecated Use #xbt_fifo_new_item instead.
 387  */
 388 XBT_INLINE xbt_fifo_item_t xbt_fifo_newitem(void)
 389 {
 390   WARN0("This function is deprecated. Use xbt_fifo_new_item.");
 391   return xbt_fifo_new_item();
 392 }
 393
 394 /**
 395  * \param i a bucket
 396  * \param v an object
 397  *
 398  * stores \a v in \a i.
 399  */
 400 XBT_INLINE void xbt_fifo_set_item_content(xbt_fifo_item_t i, void *v)
 401 {
 402   xbt_fifo_setItemcontent(i, v);
 403 }
 404
 405 /**
 406  * \param i a bucket
 407  * \return the object stored \a i.
 408  */
 409 XBT_INLINE void *xbt_fifo_get_item_content(xbt_fifo_item_t i)
 410 {
 411   return xbt_fifo_getItemcontent(i);
 412 }
 413
 414 /** Destructor
 415  * \param b poor victim
 416  *
 417  * Free the bucket but does not modifies the object (if any) that was stored in it.
 418  */
 419 XBT_INLINE void xbt_fifo_free_item(xbt_fifo_item_t b)
 420 {
 421   xbt_mallocator_release(item_mallocator, b);
 422   return;
 423 }
 424
 425 /** Destructor
 426  * \deprecated Use #xbt_fifo_free_item instead.
 427  */
 428 XBT_INLINE void xbt_fifo_freeitem(xbt_fifo_item_t b)
 429 {
 430   WARN0("This function is deprecated. Use xbt_fifo_free_item.");
 431   xbt_fifo_free_item(b);
 432   return;
 433 }
 434
 435 /**
 436  * \param f a list
 437  * \return the number of buckets in \a f.
 438  */
 439 XBT_INLINE int xbt_fifo_size(xbt_fifo_t f)
 440 {
 441   return f->count;
 442 }
 443
 444 /**
 445  * \param l a list
 446  * \return the head of \a l.
 447  */
 448 XBT_INLINE xbt_fifo_item_t xbt_fifo_get_first_item(xbt_fifo_t l)
 449 {
 450   return l->head;
 451 }
 452
 453 /**
 454  * \param l a list
 455  * \return the tail of \a l.
 456  */
 457 XBT_INLINE xbt_fifo_item_t xbt_fifo_get_last_item(xbt_fifo_t l)
 458 {
 459   return l->tail;
 460 }
 461
 462 /** \deprecated Use #xbt_fifo_get_first_item instead.
 463  */
 464 XBT_INLINE xbt_fifo_item_t xbt_fifo_getFirstItem(xbt_fifo_t l)
 465 {
 466   WARN0("This function is deprecated. Use xbt_fifo_get_first_item.");
 467   return xbt_fifo_get_first_item(l);
 468 }
 469
 470 /**
 471  * \param i a bucket
 472  * \return the bucket that comes next
 473  */
 474 XBT_INLINE xbt_fifo_item_t xbt_fifo_get_next_item(xbt_fifo_item_t i)
 475 {
 476   if (i)
 477     return i->next;
 478   return NULL;
 479 }
 480
 481 /** \deprecated Use #xbt_fifo_get_next_item instead.
 482  */
 483 xbt_fifo_item_t xbt_fifo_getNextItem(xbt_fifo_item_t i)
 484 {
 485   WARN0("This function is deprecated. Use xbt_fifo_get_next_item.");
 486   return xbt_fifo_get_next_item(i);
 487 }
 488
 489 /**
 490  * \param i a bucket
 491  * \return the bucket that is just before \a i.
 492  */
 493 XBT_INLINE xbt_fifo_item_t xbt_fifo_get_prev_item(xbt_fifo_item_t i)
 494 {
 495   if (i)
 496     return i->prev;
 497   return NULL;
 498 }
 499
 500 /** \deprecated Use #xbt_fifo_get_prev_item instead.
 501  */
 502 xbt_fifo_item_t xbt_fifo_getPrevItem(xbt_fifo_item_t i)
 503 {
 504   WARN0("This function is deprecated. Use xbt_fifo_get_prev_item.");
 505   return xbt_fifo_get_prev_item(i);
 506 }
 507
 508 /* Module init/exit handling the fifo item mallocator
 509  * These are internal XBT functions called by xbt_preinit/postexit().
 510  * It can be used several times to recreate the mallocator, for example when you switch to MC mode
 511  */
 512 void xbt_fifo_preinit(void)
 513 {
 514   if (item_mallocator != NULL) {
 515     /* Already created. I guess we want to switch to MC mode, so kill the previously created mallocator */
 516     xbt_mallocator_free(item_mallocator);
 517   }
 518
 519   item_mallocator = xbt_mallocator_new(256,
 520                                        fifo_item_mallocator_new_f,
 521                                        fifo_item_mallocator_free_f,
 522                                        fifo_item_mallocator_reset_f);
 523 }
 524
 525 void xbt_fifo_postexit(void)
 526 {
 527   if (item_mallocator != NULL) {
 528     xbt_mallocator_free(item_mallocator);
 529     item_mallocator = NULL;
 530   }
 531 }
 532
 533 /* @} */