3 /* Copyright (c) 2004 Arnaud Legrand. All rights reserved. */
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. */
8 #include "xbt/sysdep.h"
10 #include "fifo_private.h"
12 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(fifo,xbt,"FIFO");
17 xbt_fifo_t xbt_fifo_new(void)
20 fifo = xbt_new0(struct xbt_fifo,1);
25 * \param l poor victim
27 * Free the fifo structure. None of the objects that was in the fifo is however modified.
29 void xbt_fifo_free(xbt_fifo_t l)
31 xbt_fifo_item_t b, tmp;
33 for (b = xbt_fifo_get_first_item(l); b;
34 tmp = b, b = b->next, xbt_fifo_free_item(tmp));
42 * \return the bucket that was just added
44 * Add an object at the tail of the list
46 xbt_fifo_item_t xbt_fifo_push(xbt_fifo_t l, void *t)
50 new = xbt_fifo_new_item();
53 xbt_fifo_push_item(l,new);
59 * \returns the object stored at the tail of the list.
61 * Removes and returns the object stored at the tail of the list.
62 * Returns NULL if the list is empty.
64 void *xbt_fifo_pop(xbt_fifo_t l)
69 if(l==NULL) return NULL;
70 if(!(item = xbt_fifo_pop_item(l))) return NULL;
72 content = item->content;
73 xbt_fifo_free_item(item);
80 * \return the bucket that was just added
82 * Add an object at the head of the list
84 xbt_fifo_item_t xbt_fifo_unshift(xbt_fifo_t l, void *t)
88 new = xbt_fifo_new_item();
90 xbt_fifo_unshift_item(l,new);
96 * \returns the object stored at the head of the list.
98 * Removes and returns the object stored at the head of the list.
99 * Returns NULL if the list is empty.
101 void *xbt_fifo_shift(xbt_fifo_t l)
103 xbt_fifo_item_t item;
106 if(l==NULL) return NULL;
107 if(!(item = xbt_fifo_shift_item(l))) return NULL;
109 content = item->content;
110 xbt_fifo_free_item(item);
118 * Hook up this bucket at the tail of the list
120 void xbt_fifo_push_item(xbt_fifo_t l, xbt_fifo_item_t new)
122 xbt_assert0((new->next == NULL)&&(new->prev == NULL),"Invalid item!");
124 if (l->head == NULL) {
130 new->prev->next = new;
136 * \returns the bucket that was at the tail of the list.
138 * Returns NULL if the list was empty.
140 xbt_fifo_item_t xbt_fifo_pop_item(xbt_fifo_t l)
142 xbt_fifo_item_t item;
149 l->tail = item->prev;
153 l->tail->next = NULL;
166 * Hook up this bucket at the head of the list
168 void xbt_fifo_unshift_item(xbt_fifo_t l, xbt_fifo_item_t new)
170 xbt_assert0((new->next == NULL)&&(new->prev == NULL),"Invalid item!");
172 if (l->head == NULL) {
178 new->next->prev = new;
185 * \returns the bucket that was at the head of the list.
187 * Returns NULL if the list was empty.
189 xbt_fifo_item_t xbt_fifo_shift_item(xbt_fifo_t l)
191 xbt_fifo_item_t item;
198 l->head = item->next;
202 l->head->prev = NULL;
215 * removes the first occurence of \a t from \a l.
216 * \warning it will not remove duplicates
218 void xbt_fifo_remove(xbt_fifo_t l, void *t)
220 xbt_fifo_item_t current, current_next;
223 for (current = l->head; current; current = current_next) {
224 current_next = current->next;
225 if (current->content != t)
227 /* remove the item */
228 xbt_fifo_remove_item(l, current);
229 xbt_fifo_free_item(current);
230 /* WILL NOT REMOVE DUPLICATES */
238 * \param current a bucket
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...
243 void xbt_fifo_remove_item(xbt_fifo_t l, xbt_fifo_item_t current)
245 if (l->head == l->tail) { /* special case */
246 xbt_assert0((current==l->head),"This item is not in the list!");
250 current->prev = current->next = NULL;
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;
265 current->prev = current->next = NULL;
270 * \param content an object
271 * \return 1 if \a content is in \a f.
273 int xbt_fifo_is_in(xbt_fifo_t f, void *content)
275 xbt_fifo_item_t item = xbt_fifo_get_first_item(f);
277 if (item->content == content)
286 * \return a table with the objects stored in \a f.
288 void **xbt_fifo_to_array(xbt_fifo_t f)
297 array = xbt_new0(void *, f->count);
299 for (i = 0, b = xbt_fifo_get_first_item(f); b; i++, b = b->next) {
300 array[i] = b->content;
307 * \return a copy of \a f.
309 xbt_fifo_t xbt_fifo_copy(xbt_fifo_t f)
311 xbt_fifo_t copy = NULL;
314 copy = xbt_fifo_new();
316 for (b = xbt_fifo_get_first_item(f); b; b = b->next) {
317 xbt_fifo_push(copy, b->content);
323 * \return a new bucket
325 xbt_fifo_item_t xbt_fifo_new_item(void)
327 return xbt_new0(struct xbt_fifo_item,1);
330 /** \deprecated Use #xbt_fifo_new_item instead.
332 xbt_fifo_item_t xbt_fifo_newitem(void)
334 WARN0("This function is deprecated. Use xbt_fifo_new_item.");
335 return xbt_fifo_new_item();
342 * stores \a v in \a i.
344 void xbt_fifo_set_item_content(xbt_fifo_item_t i , void *v)
346 xbt_fifo_setItemcontent(i,v);
351 * \return the object stored \a i.
353 void *xbt_fifo_get_item_content(xbt_fifo_item_t i)
355 return xbt_fifo_getItemcontent(i);
359 * \param b poor victim
361 * Free the bucket but does not modifies the object (if any) that was stored in it.
363 void xbt_fifo_free_item(xbt_fifo_item_t b)
370 * \deprecated Use #xbt_fifo_free_item instead.
372 void xbt_fifo_freeitem(xbt_fifo_item_t b)
374 WARN0("This function is deprecated. Use xbt_fifo_free_item.");
381 * \return the number of buckets in \a f.
383 int xbt_fifo_size(xbt_fifo_t f)
390 * \return the head of \a l.
392 xbt_fifo_item_t xbt_fifo_get_first_item(xbt_fifo_t l)
397 /** \deprecated Use #xbt_fifo_get_first_item instead.
399 xbt_fifo_item_t xbt_fifo_getFirstItem(xbt_fifo_t l)
401 WARN0("This function is deprecated. Use xbt_fifo_get_first_item.");
402 return xbt_fifo_get_first_item(l);
407 * \return the bucket that comes next
409 xbt_fifo_item_t xbt_fifo_get_next_item(xbt_fifo_item_t i)
411 if(i) return i->next;
415 /** \deprecated Use #xbt_fifo_get_next_item instead.
417 xbt_fifo_item_t xbt_fifo_getNextItem(xbt_fifo_item_t i)
419 WARN0("This function is deprecated. Use xbt_fifo_get_next_item.");
420 return xbt_fifo_get_next_item(i);
425 * \return the bucket that is just before \a i.
427 xbt_fifo_item_t xbt_fifo_get_prev_item(xbt_fifo_item_t i)
429 if(i) return i->prev;
433 /** \deprecated Use #xbt_fifo_get_prev_item instead.
435 xbt_fifo_item_t xbt_fifo_getPrevItem(xbt_fifo_item_t i)
437 WARN0("This function is deprecated. Use xbt_fifo_get_prev_item.");
438 return xbt_fifo_get_prev_item(i);