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   (l->count)++;
 123   if (l->head == NULL) {
 124     l->head = new;
 125     l->tail = new;
 126     return;
 127   }
 128   new->prev = l->tail;
 129   new->prev->next = new;
 130   l->tail = new;
 131 }
 132
 133 /** Pop bucket
 134  * \param l
 135  * \returns the bucket that was at the tail of the list.
 136  *
 137  * Returns NULL if the list was empty.
 138  */
 139 xbt_fifo_item_t xbt_fifo_pop_item(xbt_fifo_t l)
 140 {
 141   xbt_fifo_item_t item;
 142
 143   if (l->tail == NULL)
 144     return NULL;
 145
 146   item = l->tail;
 147
 148   l->tail = item->prev;
 149   if (l->tail == NULL)
 150     l->head = NULL;
 151   else
 152     l->tail->next = NULL;
 153
 154   (l->count)--;
 155   return item;
 156 }
 157
 158 /** Push a bucket
 159  * \param l list
 160  * \param new bucket
 161  *
 162  * Hook up this bucket at the head of the list
 163  */
 164 void xbt_fifo_unshift_item(xbt_fifo_t l, xbt_fifo_item_t new)
 165 {
 166   (l->count)++;
 167   if (l->head == NULL) {
 168     l->head = new;
 169     l->tail = new;
 170     return;
 171   }
 172   new->next = l->head;
 173   new->next->prev = new;
 174   l->head = new;
 175   return;
 176 }
 177
 178 /** Shift bucket
 179  * \param l
 180  * \returns the bucket that was at the head of the list.
 181  *
 182  * Returns NULL if the list was empty.
 183  */
 184 xbt_fifo_item_t xbt_fifo_shift_item(xbt_fifo_t l)
 185 {
 186   xbt_fifo_item_t item;
 187
 188   if (l->head == NULL)
 189     return NULL;
 190
 191   item = l->head;
 192
 193   l->head = item->next;
 194   if (l->head == NULL)
 195     l->tail = NULL;
 196   else
 197     l->head->prev = NULL;
 198
 199   (l->count)--;
 200   return item;
 201 }
 202
 203 /**
 204  * \param l
 205  * \param t an objet
 206  *
 207  * removes the first occurence of \a t from \a l.
 208  * \warning it will not remove duplicates
 209  */
 210 void xbt_fifo_remove(xbt_fifo_t l, void *t)
 211 {
 212   xbt_fifo_item_t current, current_next;
 213
 214
 215   for (current = l->head; current; current = current_next) {
 216     current_next = current->next;
 217     if (current->content != t)
 218       continue;
 219     /* remove the item */
 220     xbt_fifo_remove_item(l, current);
 221     xbt_fifo_free_item(current);
 222     /* WILL NOT REMOVE DUPLICATES */
 223     break;
 224   }
 225   return;
 226 }
 227
 228 /**
 229  * \param l a list
 230  * \param current a bucket
 231  *
 232  * removes a the bucket \a current from the list \a l
 233  */
 234 void xbt_fifo_remove_item(xbt_fifo_t l, xbt_fifo_item_t current)
 235 {
 236   if (l->head == l->tail) {     /* special case */
 237       l->head = NULL;
 238       l->tail = NULL;
 239       (l->count)--;
 240       return;
 241     }
 242
 243     if (current == l->head) {   /* It's the head */
 244       l->head = current->next;
 245       l->head->prev = NULL;
 246     } else if (current == l->tail) {    /* It's the tail */
 247       l->tail = current->prev;
 248       l->tail->next = NULL;
 249     } else {                    /* It's in the middle */
 250       current->prev->next = current->next;
 251       current->next->prev = current->prev;
 252     }
 253     (l->count)--;
 254 }
 255
 256 /**
 257  * \param f a list
 258  * \param content an object
 259  * \return 1 if \a content is in \a f.
 260  */
 261 int xbt_fifo_is_in(xbt_fifo_t f, void *content)
 262 {
 263   xbt_fifo_item_t item = xbt_fifo_get_first_item(f);
 264   while (item) {
 265     if (item->content == content)
 266       return 1;
 267     item = item->next;
 268   }
 269   return 0;
 270 }
 271
 272 /**
 273  * \param f a list
 274  * \return a table with the objects stored in \a f.
 275  */
 276 void **xbt_fifo_to_array(xbt_fifo_t f)
 277 {
 278   void **array;
 279   xbt_fifo_item_t b;
 280   int i;
 281
 282   if (f->count == 0)
 283     return NULL;
 284   else
 285     array = xbt_new0(void *, f->count);
 286
 287   for (i = 0, b = xbt_fifo_get_first_item(f); b; i++, b = b->next) {
 288     array[i] = b->content;
 289   }
 290   return array;
 291 }
 292
 293 /**
 294  * \param f a list
 295  * \return a copy of \a f.
 296  */
 297 xbt_fifo_t xbt_fifo_copy(xbt_fifo_t f)
 298 {
 299   xbt_fifo_t copy = NULL;
 300   xbt_fifo_item_t b;
 301
 302   copy = xbt_fifo_new();
 303
 304   for (b = xbt_fifo_get_first_item(f); b; b = b->next) {
 305     xbt_fifo_push(copy, b->content);
 306   }
 307   return copy;
 308 }
 309
 310 /** Constructor
 311  * \return a new bucket
 312  */
 313 xbt_fifo_item_t xbt_fifo_new_item(void)
 314 {
 315   return xbt_new0(struct xbt_fifo_item,1);
 316 }
 317
 318 /** \deprecated Use #xbt_fifo_new_item instead.
 319  */
 320 xbt_fifo_item_t xbt_fifo_newitem(void)
 321 {
 322   WARN0("This function is deprecated. Use xbt_fifo_new_item.");
 323   return xbt_fifo_new_item();
 324 }
 325
 326 /**
 327  * \param i a bucket
 328  * \param v an object
 329  *
 330  * stores \a v in \a i.
 331  */
 332 void xbt_fifo_set_item_content(xbt_fifo_item_t i , void *v)
 333 {
 334   xbt_fifo_setItemcontent(i,v);
 335 }
 336
 337 /**
 338  * \param i a bucket
 339  * \return the object stored \a i.
 340  */
 341 void *xbt_fifo_get_item_content(xbt_fifo_item_t i)
 342 {
 343   return xbt_fifo_getItemcontent(i);
 344 }
 345
 346 /** Destructor
 347  * \param b poor victim
 348  *
 349  * Free the bucket but does not modifies the object (if any) that was stored in it.
 350  */
 351 void xbt_fifo_free_item(xbt_fifo_item_t b)
 352 {
 353   free(b);
 354   return;
 355 }
 356
 357 /** Destructor
 358  * \deprecated Use #xbt_fifo_free_item instead.
 359  */
 360 void xbt_fifo_freeitem(xbt_fifo_item_t b)
 361 {
 362   WARN0("This function is deprecated. Use xbt_fifo_free_item.");
 363   free(b);
 364   return;
 365 }
 366
 367 /**
 368  * \param f a list
 369  * \return the number of buckets in \a f.
 370  */
 371 int xbt_fifo_size(xbt_fifo_t f)
 372 {
 373   return f->count;
 374 }
 375
 376 /**
 377  * \param l a list
 378  * \return the head of \a l.
 379  */
 380 xbt_fifo_item_t xbt_fifo_get_first_item(xbt_fifo_t l)
 381 {
 382   return l->head;
 383 }
 384
 385 /** \deprecated Use #xbt_fifo_get_first_item instead.
 386  */
 387 xbt_fifo_item_t xbt_fifo_getFirstItem(xbt_fifo_t l)
 388 {
 389   WARN0("This function is deprecated. Use xbt_fifo_get_first_item.");
 390   return xbt_fifo_get_first_item(l);
 391 }
 392
 393 /**
 394  * \param i a bucket
 395  * \return the bucket that comes next
 396  */
 397 xbt_fifo_item_t xbt_fifo_get_next_item(xbt_fifo_item_t i)
 398 {
 399   if(i) return i->next;
 400   return NULL;
 401 }
 402
 403 /** \deprecated Use #xbt_fifo_get_next_item instead.
 404  */
 405 xbt_fifo_item_t xbt_fifo_getNextItem(xbt_fifo_item_t i)
 406 {
 407   WARN0("This function is deprecated. Use xbt_fifo_get_next_item.");
 408   return xbt_fifo_get_next_item(i);
 409 }
 410
 411 /**
 412  * \param i a bucket
 413  * \return the bucket that is just before \a i.
 414  */
 415 xbt_fifo_item_t xbt_fifo_get_prev_item(xbt_fifo_item_t i)
 416 {
 417   if(i) return i->prev;
 418   return NULL;
 419 }
 420
 421 /** \deprecated Use #xbt_fifo_get_prev_item instead.
 422  */
 423 xbt_fifo_item_t xbt_fifo_getPrevItem(xbt_fifo_item_t i)
 424 {
 425   WARN0("This function is deprecated. Use xbt_fifo_get_prev_item.");
 426   return xbt_fifo_get_prev_item(i);
 427 }
 428
 429 /* @} */
 430
 431