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");
22 xbt_fifo_t xbt_fifo_new(void)
25 fifo = xbt_new0(struct xbt_fifo,1);
30 * \param l poor victim
32 * Free the fifo structure. None of the objects that was in the fifo is however modified.
34 void xbt_fifo_free(xbt_fifo_t l)
36 xbt_fifo_item_t b, tmp;
38 for (b = xbt_fifo_getFirstitem(l); b;
39 tmp = b, b = b->next, xbt_fifo_freeitem(tmp));
47 * \return the bucket that was just added
49 * Add an object at the tail of the list
51 xbt_fifo_item_t xbt_fifo_push(xbt_fifo_t l, void *t)
55 new = xbt_fifo_newitem();
58 xbt_fifo_push_item(l,new);
64 * \returns the object stored at the tail of the list.
66 * Removes and returns the object stored at the tail of the list.
67 * Returns NULL if the list is empty.
69 void *xbt_fifo_pop(xbt_fifo_t l)
74 if(l==NULL) return NULL;
75 if(!(item = xbt_fifo_pop_item(l))) return NULL;
77 content = item->content;
78 xbt_fifo_freeitem(item);
85 * \return the bucket that was just added
87 * Add an object at the head of the list
89 xbt_fifo_item_t xbt_fifo_unshift(xbt_fifo_t l, void *t)
93 new = xbt_fifo_newitem();
95 xbt_fifo_unshift_item(l,new);
101 * \returns the object stored at the head of the list.
103 * Removes and returns the object stored at the head of the list.
104 * Returns NULL if the list is empty.
106 void *xbt_fifo_shift(xbt_fifo_t l)
108 xbt_fifo_item_t item;
111 if(l==NULL) return NULL;
112 if(!(item = xbt_fifo_shift_item(l))) return NULL;
114 content = item->content;
115 xbt_fifo_freeitem(item);
123 * Hook up this bucket at the tail of the list
125 void xbt_fifo_push_item(xbt_fifo_t l, xbt_fifo_item_t new)
128 if (l->head == NULL) {
134 new->prev->next = new;
140 * \returns the bucket that was at the tail of the list.
142 * Returns NULL if the list was empty.
144 xbt_fifo_item_t xbt_fifo_pop_item(xbt_fifo_t l)
146 xbt_fifo_item_t item;
153 l->tail = item->prev;
157 l->tail->next = NULL;
167 * Hook up this bucket at the head of the list
169 void xbt_fifo_unshift_item(xbt_fifo_t l, xbt_fifo_item_t new)
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;
212 * removes the first occurence of \a t from \a l.
213 * \warning it will not remove duplicates
215 void xbt_fifo_remove(xbt_fifo_t l, void *t)
217 xbt_fifo_item_t current, current_next;
220 for (current = l->head; current; current = current_next) {
221 current_next = current->next;
222 if (current->content != t)
224 /* remove the item */
225 xbt_fifo_remove_item(l, current);
226 xbt_fifo_freeitem(current);
227 /* WILL NOT REMOVE DUPLICATES */
235 * \param current a bucket
237 * removes a the bucket \a current from the list \a l
239 void xbt_fifo_remove_item(xbt_fifo_t l, xbt_fifo_item_t current)
241 if (l->head == l->tail) { /* special case */
248 if (current == l->head) { /* It's the head */
249 l->head = current->next;
250 l->head->prev = NULL;
251 } else if (current == l->tail) { /* It's the tail */
252 l->tail = current->prev;
253 l->tail->next = NULL;
254 } else { /* It's in the middle */
255 current->prev->next = current->next;
256 current->next->prev = current->prev;
263 * \param content an object
264 * \return 1 if \a content is in \a f.
266 int xbt_fifo_is_in(xbt_fifo_t f, void *content)
268 xbt_fifo_item_t item = xbt_fifo_getFirstitem(f);
270 if (item->content == content)
279 * \return a table with the objects stored in \a f.
281 void **xbt_fifo_to_array(xbt_fifo_t f)
290 array = xbt_new0(void *, f->count);
292 for (i = 0, b = xbt_fifo_getFirstitem(f); b; i++, b = b->next) {
293 array[i] = b->content;
300 * \return a copy of \a f.
302 xbt_fifo_t xbt_fifo_copy(xbt_fifo_t f)
304 xbt_fifo_t copy = NULL;
307 copy = xbt_fifo_new();
309 for (b = xbt_fifo_getFirstitem(f); b; b = b->next) {
310 xbt_fifo_push(copy, b->content);
316 * \return a new bucket
318 xbt_fifo_item_t xbt_fifo_newitem(void)
320 return xbt_new0(struct xbt_fifo_item,1);
327 * stores \a v in \a i.
329 void xbt_fifo_set_item_content(xbt_fifo_item_t i , void *v)
331 xbt_fifo_setItemcontent(i,v);
336 * \return the object stored \a i.
338 void *xbt_fifo_get_item_content(xbt_fifo_item_t i)
340 return xbt_fifo_getItemcontent(i);
344 * \param b poor victim
346 * Free the bucket but does not modifies the object (if any) that was stored in it.
348 void xbt_fifo_freeitem(xbt_fifo_item_t b)
356 * \return the number of buckets in \a f.
358 int xbt_fifo_size(xbt_fifo_t f)
365 * \return the head of \a l.
367 xbt_fifo_item_t xbt_fifo_getFirstItem(xbt_fifo_t l)
374 * \return the bucket that comes next
376 xbt_fifo_item_t xbt_fifo_getNextItem(xbt_fifo_item_t i)
378 if(i) return i->next;
384 * \return the bucket that is just before \a i.
386 xbt_fifo_item_t xbt_fifo_getPrevItem(xbt_fifo_item_t i)
388 if(i) return i->prev;