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");
14 /** \defgroup XBT_fifo A generic workqueue
15 * \brief This section describes the API to generic workqueue. These functions
16 * provide the same kind of functionnality as dynamic arrays but in time O(1).
17 * However these functions use malloc/free a way too much often.
28 xbt_fifo_t xbt_fifo_new(void)
31 fifo = xbt_new0(struct xbt_fifo,1);
36 * \param l poor victim
38 * Free the fifo structure. None of the objects that was in the fifo is however modified.
40 void xbt_fifo_free(xbt_fifo_t l)
42 xbt_fifo_item_t b, tmp;
44 for (b = xbt_fifo_getFirstitem(l); b;
45 tmp = b, b = b->next, xbt_fifo_freeitem(tmp));
53 * \return the bucket that was just added
55 * Add an object at the tail of the list
57 xbt_fifo_item_t xbt_fifo_push(xbt_fifo_t l, void *t)
61 new = xbt_fifo_newitem();
64 xbt_fifo_push_item(l,new);
70 * \returns the object stored at the tail of the list.
72 * Removes and returns the object stored at the tail of the list.
73 * Returns NULL if the list is empty.
75 void *xbt_fifo_pop(xbt_fifo_t l)
80 if(l==NULL) return NULL;
81 if(!(item = xbt_fifo_pop_item(l))) return NULL;
83 content = item->content;
84 xbt_fifo_freeitem(item);
91 * \return the bucket that was just added
93 * Add an object at the head of the list
95 xbt_fifo_item_t xbt_fifo_unshift(xbt_fifo_t l, void *t)
99 new = xbt_fifo_newitem();
101 xbt_fifo_unshift_item(l,new);
107 * \returns the object stored at the head of the list.
109 * Removes and returns the object stored at the head of the list.
110 * Returns NULL if the list is empty.
112 void *xbt_fifo_shift(xbt_fifo_t l)
114 xbt_fifo_item_t item;
117 if(l==NULL) return NULL;
118 if(!(item = xbt_fifo_shift_item(l))) return NULL;
120 content = item->content;
121 xbt_fifo_freeitem(item);
129 * Hook up this bucket at the tail of the list
131 void xbt_fifo_push_item(xbt_fifo_t l, xbt_fifo_item_t new)
134 if (l->head == NULL) {
140 new->prev->next = new;
146 * \returns the bucket that was at the tail of the list.
148 * Returns NULL if the list was empty.
150 xbt_fifo_item_t xbt_fifo_pop_item(xbt_fifo_t l)
152 xbt_fifo_item_t item;
159 l->tail = item->prev;
163 l->tail->next = NULL;
173 * Hook up this bucket at the head of the list
175 void xbt_fifo_unshift_item(xbt_fifo_t l, xbt_fifo_item_t new)
178 if (l->head == NULL) {
184 new->next->prev = new;
191 * \returns the bucket that was at the head of the list.
193 * Returns NULL if the list was empty.
195 xbt_fifo_item_t xbt_fifo_shift_item(xbt_fifo_t l)
197 xbt_fifo_item_t item;
204 l->head = item->next;
208 l->head->prev = NULL;
218 * removes the first occurence of \a t from \a l.
219 * \warning it will not remove duplicates
221 void xbt_fifo_remove(xbt_fifo_t l, void *t)
223 xbt_fifo_item_t current, current_next;
226 for (current = l->head; current; current = current_next) {
227 current_next = current->next;
228 if (current->content != t)
230 /* remove the item */
231 xbt_fifo_remove_item(l, current);
232 xbt_fifo_freeitem(current);
233 /* WILL NOT REMOVE DUPLICATES */
241 * \param current a bucket
243 * removes a the bucket \a current from the list \a l
245 void xbt_fifo_remove_item(xbt_fifo_t l, xbt_fifo_item_t current)
247 if (l->head == l->tail) { /* special case */
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;
269 * \param content an object
270 * \return 1 if \a content is in \a f.
272 int xbt_fifo_is_in(xbt_fifo_t f, void *content)
274 xbt_fifo_item_t item = xbt_fifo_getFirstitem(f);
276 if (item->content == content)
285 * \return a table with the objects stored in \a f.
287 void **xbt_fifo_to_array(xbt_fifo_t f)
296 array = xbt_new0(void *, f->count);
298 for (i = 0, b = xbt_fifo_getFirstitem(f); b; i++, b = b->next) {
299 array[i] = b->content;
306 * \return a copy of \a f.
308 xbt_fifo_t xbt_fifo_copy(xbt_fifo_t f)
310 xbt_fifo_t copy = NULL;
313 copy = xbt_fifo_new();
315 for (b = xbt_fifo_getFirstitem(f); b; b = b->next) {
316 xbt_fifo_push(copy, b->content);
322 * \return a new bucket
324 xbt_fifo_item_t xbt_fifo_newitem(void)
326 return xbt_new0(struct xbt_fifo_item,1);
333 * stores \a v in \a i.
335 void xbt_fifo_set_item_content(xbt_fifo_item_t i , void *v)
337 xbt_fifo_setItemcontent(i,v);
342 * \return the object stored \a i.
344 void *xbt_fifo_get_item_content(xbt_fifo_item_t i)
346 return xbt_fifo_getItemcontent(i);
350 * \param b poor victim
352 * Free the bucket but does not modifies the object (if any) that was stored in it.
354 void xbt_fifo_freeitem(xbt_fifo_item_t b)
362 * \return the number of buckets in \a f.
364 int xbt_fifo_size(xbt_fifo_t f)
371 * \return the head of \a l.
373 xbt_fifo_item_t xbt_fifo_getFirstItem(xbt_fifo_t l)
380 * \return the bucket that comes next
382 xbt_fifo_item_t xbt_fifo_getNextItem(xbt_fifo_item_t i)
384 if(i) return i->next;
390 * \return the bucket that is just before \a i.
392 xbt_fifo_item_t xbt_fifo_getPrevItem(xbt_fifo_item_t i)
394 if(i) return i->prev;