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"
9 #include "fifo_private.h"
11 /*XBT_LOG_NEW_DEFAULT_SUBCATEGORY(fifo,xbt,"FIFO"); UNUSED SO FAR */
13 /** \defgroup XBT_fifo A generic workqueue
14 * \brief This section describes the API to generic workqueue. These functions
15 * provide the same kind of functionnality as dynamic arrays but in time O(1).
16 * However these functions use malloc/free a way too much often.
27 xbt_fifo_t xbt_fifo_new(void)
30 fifo = xbt_new0(struct xbt_fifo,1);
35 * \param l poor victim
37 * Free the fifo structure. None of the objects that was in the fifo is however modified.
39 void xbt_fifo_free(xbt_fifo_t l)
41 xbt_fifo_item_t b, tmp;
43 for (b = xbt_fifo_getFirstitem(l); b;
44 tmp = b, b = b->next, xbt_fifo_freeitem(tmp));
52 * \return the bucket that was just added
54 * Add an object at the tail of the list
56 xbt_fifo_item_t xbt_fifo_push(xbt_fifo_t l, void *t)
60 new = xbt_fifo_newitem();
63 xbt_fifo_push_item(l,new);
69 * \returns the object stored at the tail of the list.
71 * Removes and returns the object stored at the tail of the list.
72 * Returns NULL if the list is empty.
74 void *xbt_fifo_pop(xbt_fifo_t l)
79 if(l==NULL) return NULL;
80 if(!(item = xbt_fifo_pop_item(l))) return NULL;
82 content = item->content;
83 xbt_fifo_freeitem(item);
90 * \return the bucket that was just added
92 * Add an object at the head of the list
94 xbt_fifo_item_t xbt_fifo_unshift(xbt_fifo_t l, void *t)
98 new = xbt_fifo_newitem();
100 xbt_fifo_unshift_item(l,new);
106 * \returns the object stored at the head of the list.
108 * Removes and returns the object stored at the head of the list.
109 * Returns NULL if the list is empty.
111 void *xbt_fifo_shift(xbt_fifo_t l)
113 xbt_fifo_item_t item;
116 if(l==NULL) return NULL;
117 if(!(item = xbt_fifo_shift_item(l))) return NULL;
119 content = item->content;
120 xbt_fifo_freeitem(item);
128 * Hook up this bucket at the tail of the list
130 void xbt_fifo_push_item(xbt_fifo_t l, xbt_fifo_item_t new)
133 if (l->head == NULL) {
139 new->prev->next = new;
145 * \returns the bucket that was at the tail of the list.
147 * Returns NULL if the list was empty.
149 xbt_fifo_item_t xbt_fifo_pop_item(xbt_fifo_t l)
151 xbt_fifo_item_t item;
158 l->tail = item->prev;
162 l->tail->next = NULL;
172 * Hook up this bucket at the head of the list
174 void xbt_fifo_unshift_item(xbt_fifo_t l, xbt_fifo_item_t new)
177 if (l->head == NULL) {
183 new->next->prev = new;
190 * \returns the bucket that was at the head of the list.
192 * Returns NULL if the list was empty.
194 xbt_fifo_item_t xbt_fifo_shift_item(xbt_fifo_t l)
196 xbt_fifo_item_t item;
203 l->head = item->next;
207 l->head->prev = NULL;
217 * removes the first occurence of \a t from \a l.
218 * \warning it will not remove duplicates
220 void xbt_fifo_remove(xbt_fifo_t l, void *t)
222 xbt_fifo_item_t current, current_next;
225 for (current = l->head; current; current = current_next) {
226 current_next = current->next;
227 if (current->content != t)
229 /* remove the item */
230 xbt_fifo_remove_item(l, current);
231 xbt_fifo_freeitem(current);
232 /* WILL NOT REMOVE DUPLICATES */
240 * \param current a bucket
242 * removes a the bucket \a current from the list \a l
244 void xbt_fifo_remove_item(xbt_fifo_t l, xbt_fifo_item_t current)
246 if (l->head == l->tail) { /* special case */
253 if (current == l->head) { /* It's the head */
254 l->head = current->next;
255 l->head->prev = NULL;
256 } else if (current == l->tail) { /* It's the tail */
257 l->tail = current->prev;
258 l->tail->next = NULL;
259 } else { /* It's in the middle */
260 current->prev->next = current->next;
261 current->next->prev = current->prev;
268 * \param content an object
269 * \return 1 if \a content is in \a f.
271 int xbt_fifo_is_in(xbt_fifo_t f, void *content)
273 xbt_fifo_item_t item = xbt_fifo_getFirstitem(f);
275 if (item->content == content)
284 * \return a table with the objects stored in \a f.
286 void **xbt_fifo_to_array(xbt_fifo_t f)
295 array = xbt_new0(void *, f->count);
297 for (i = 0, b = xbt_fifo_getFirstitem(f); b; i++, b = b->next) {
298 array[i] = b->content;
305 * \return a copy of \a f.
307 xbt_fifo_t xbt_fifo_copy(xbt_fifo_t f)
309 xbt_fifo_t copy = NULL;
312 copy = xbt_fifo_new();
314 for (b = xbt_fifo_getFirstitem(f); b; b = b->next) {
315 xbt_fifo_push(copy, b->content);
321 * \return a new bucket
323 xbt_fifo_item_t xbt_fifo_newitem(void)
325 return xbt_new0(struct xbt_fifo_item,1);
332 * stores \a v in \a i.
334 void xbt_fifo_set_item_content(xbt_fifo_item_t i , void *v)
336 xbt_fifo_setItemcontent(i,v);
341 * \return the object stored \a i.
343 void *xbt_fifo_get_item_content(xbt_fifo_item_t i)
345 return xbt_fifo_getItemcontent(i);
349 * \param b poor victim
351 * Free the bucket but does not modifies the object (if any) that was stored in it.
353 void xbt_fifo_freeitem(xbt_fifo_item_t b)
361 * \return the number of buckets in \a f.
363 int xbt_fifo_size(xbt_fifo_t f)
370 * \return the head of \a l.
372 xbt_fifo_item_t xbt_fifo_getFirstItem(xbt_fifo_t l)
379 * \return the bucket that comes next
381 xbt_fifo_item_t xbt_fifo_getNextItem(xbt_fifo_item_t i)
383 if(i) return i->next;
389 * \return the bucket that is just before \a i.
391 xbt_fifo_item_t xbt_fifo_getPrevItem(xbt_fifo_item_t i)
393 if(i) return i->prev;