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