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