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 "xbt/mallocator.h"
11 #include "fifo_private.h"
12 #include "xbt_modinter.h"
14 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_fifo, xbt, "FIFO");
16 static void *fifo_item_mallocator_new_f(void);
17 static void fifo_item_mallocator_free_f(void *item);
18 static void fifo_item_mallocator_reset_f(void *item);
20 static xbt_mallocator_t item_mallocator = NULL;
25 xbt_fifo_t xbt_fifo_new(void)
28 fifo = xbt_new0(struct xbt_fifo, 1);
30 if (item_mallocator == NULL) {
31 item_mallocator = xbt_mallocator_new(256,
32 fifo_item_mallocator_new_f,
33 fifo_item_mallocator_free_f,
34 fifo_item_mallocator_reset_f);
40 * \param l poor victim
42 * Free the fifo structure. None of the objects that was in the fifo is however modified.
44 void xbt_fifo_free(xbt_fifo_t l)
46 xbt_fifo_item_t b, tmp;
48 for (b = xbt_fifo_get_first_item(l); b;
49 tmp = b, b = b->next, xbt_fifo_free_item(tmp));
57 * \return the bucket that was just added
59 * Add an object at the tail of the list
61 xbt_fifo_item_t xbt_fifo_push(xbt_fifo_t l, void *t)
65 new = xbt_fifo_new_item();
68 xbt_fifo_push_item(l, new);
74 * \returns the object stored at the tail of the list.
76 * Removes and returns the object stored at the tail of the list.
77 * Returns NULL if the list is empty.
79 void *xbt_fifo_pop(xbt_fifo_t l)
86 if (!(item = xbt_fifo_pop_item(l)))
89 content = item->content;
90 xbt_fifo_free_item(item);
97 * \return the bucket that was just added
99 * Add an object at the head of the list
101 xbt_fifo_item_t xbt_fifo_unshift(xbt_fifo_t l, void *t)
105 new = xbt_fifo_new_item();
107 xbt_fifo_unshift_item(l, new);
113 * \returns the object stored at the head of the list.
115 * Removes and returns the object stored at the head of the list.
116 * Returns NULL if the list is empty.
118 void *xbt_fifo_shift(xbt_fifo_t l)
120 xbt_fifo_item_t item;
125 if (!(item = xbt_fifo_shift_item(l)))
128 content = item->content;
129 xbt_fifo_free_item(item);
137 * Hook up this bucket at the tail of the list
139 void xbt_fifo_push_item(xbt_fifo_t l, xbt_fifo_item_t new)
141 xbt_assert0((new->next == NULL) && (new->prev == NULL), "Invalid item!");
143 if (l->head == NULL) {
149 new->prev->next = new;
155 * \returns the bucket that was at the tail of the list.
157 * Returns NULL if the list was empty.
159 xbt_fifo_item_t xbt_fifo_pop_item(xbt_fifo_t l)
161 xbt_fifo_item_t item;
168 l->tail = item->prev;
172 l->tail->next = NULL;
185 * Hook up this bucket at the head of the list
187 void xbt_fifo_unshift_item(xbt_fifo_t l, xbt_fifo_item_t new)
189 xbt_assert0((new->next == NULL) && (new->prev == NULL), "Invalid item!");
191 if (l->head == NULL) {
197 new->next->prev = new;
204 * \returns the bucket that was at the head of the list.
206 * Returns NULL if the list was empty.
208 xbt_fifo_item_t xbt_fifo_shift_item(xbt_fifo_t l)
210 xbt_fifo_item_t item;
217 l->head = item->next;
221 l->head->prev = NULL;
234 * removes the first occurence of \a t from \a l.
235 * \warning it will not remove duplicates
236 * \return 1 if an item was removed and 0 otherwise.
238 int xbt_fifo_remove(xbt_fifo_t l, void *t)
240 xbt_fifo_item_t current, current_next;
243 for (current = l->head; current; current = current_next) {
244 current_next = current->next;
245 if (current->content != t)
247 /* remove the item */
248 xbt_fifo_remove_item(l, current);
249 xbt_fifo_free_item(current);
250 /* WILL NOT REMOVE DUPLICATES */
261 * removes all occurences of \a t from \a l.
262 * \return 1 if an item was removed and 0 otherwise.
264 int xbt_fifo_remove_all(xbt_fifo_t l, void *t)
266 xbt_fifo_item_t current, current_next;
269 for (current = l->head; current; current = current_next) {
270 current_next = current->next;
271 if (current->content != t)
273 /* remove the item */
274 xbt_fifo_remove_item(l, current);
275 xbt_fifo_free_item(current);
283 * \param current a bucket
285 * removes a bucket \a current from the list \a l. This function implicitely
286 * assumes (and doesn't check!) that this item belongs to this list...
288 void xbt_fifo_remove_item(xbt_fifo_t l, xbt_fifo_item_t current)
290 if (l->head == l->tail) { /* special case */
291 xbt_assert0((current == l->head), "This item is not in the list!");
295 current->prev = current->next = NULL;
299 if (current == l->head) { /* It's the head */
300 l->head = current->next;
301 l->head->prev = NULL;
302 } else if (current == l->tail) { /* It's the tail */
303 l->tail = current->prev;
304 l->tail->next = NULL;
305 } else { /* It's in the middle */
306 current->prev->next = current->next;
307 current->next->prev = current->prev;
310 current->prev = current->next = NULL;
315 * \param content an object
316 * \return 1 if \a content is in \a f.
318 int xbt_fifo_is_in(xbt_fifo_t f, void *content)
320 xbt_fifo_item_t item = xbt_fifo_get_first_item(f);
322 if (item->content == content)
331 * \return a table with the objects stored in \a f.
333 void **xbt_fifo_to_array(xbt_fifo_t f)
342 array = xbt_new0(void *, f->count);
344 for (i = 0, b = xbt_fifo_get_first_item(f); b; i++, b = b->next) {
345 array[i] = b->content;
352 * \return a copy of \a f.
354 xbt_fifo_t xbt_fifo_copy(xbt_fifo_t f)
356 xbt_fifo_t copy = NULL;
359 copy = xbt_fifo_new();
361 for (b = xbt_fifo_get_first_item(f); b; b = b->next) {
362 xbt_fifo_push(copy, b->content);
367 /* Functions passed to the mallocator constructor */
368 static void *fifo_item_mallocator_new_f(void)
370 return xbt_new(s_xbt_fifo_item_t, 1);
373 static void fifo_item_mallocator_free_f(void *item)
378 static void fifo_item_mallocator_reset_f(void *item)
380 /* memset to zero like calloc */
381 memset(item, 0, sizeof(s_xbt_fifo_item_t));
385 * \return a new bucket
387 xbt_fifo_item_t xbt_fifo_new_item(void)
389 return xbt_mallocator_get(item_mallocator);
392 /** \deprecated Use #xbt_fifo_new_item instead.
394 xbt_fifo_item_t xbt_fifo_newitem(void)
396 WARN0("This function is deprecated. Use xbt_fifo_new_item.");
397 return xbt_fifo_new_item();
404 * stores \a v in \a i.
406 void xbt_fifo_set_item_content(xbt_fifo_item_t i, void *v)
408 xbt_fifo_setItemcontent(i, v);
413 * \return the object stored \a i.
415 void *xbt_fifo_get_item_content(xbt_fifo_item_t i)
417 return xbt_fifo_getItemcontent(i);
421 * \param b poor victim
423 * Free the bucket but does not modifies the object (if any) that was stored in it.
425 void xbt_fifo_free_item(xbt_fifo_item_t b)
427 xbt_mallocator_release(item_mallocator, b);
432 * \deprecated Use #xbt_fifo_free_item instead.
434 void xbt_fifo_freeitem(xbt_fifo_item_t b)
436 WARN0("This function is deprecated. Use xbt_fifo_free_item.");
437 xbt_fifo_free_item(b);
443 * \return the number of buckets in \a f.
445 int xbt_fifo_size(xbt_fifo_t f)
452 * \return the head of \a l.
454 xbt_fifo_item_t xbt_fifo_get_first_item(xbt_fifo_t l)
459 /** \deprecated Use #xbt_fifo_get_first_item instead.
461 xbt_fifo_item_t xbt_fifo_getFirstItem(xbt_fifo_t l)
463 WARN0("This function is deprecated. Use xbt_fifo_get_first_item.");
464 return xbt_fifo_get_first_item(l);
469 * \return the bucket that comes next
471 xbt_fifo_item_t xbt_fifo_get_next_item(xbt_fifo_item_t i)
478 /** \deprecated Use #xbt_fifo_get_next_item instead.
480 xbt_fifo_item_t xbt_fifo_getNextItem(xbt_fifo_item_t i)
482 WARN0("This function is deprecated. Use xbt_fifo_get_next_item.");
483 return xbt_fifo_get_next_item(i);
488 * \return the bucket that is just before \a i.
490 xbt_fifo_item_t xbt_fifo_get_prev_item(xbt_fifo_item_t i)
497 /** \deprecated Use #xbt_fifo_get_prev_item instead.
499 xbt_fifo_item_t xbt_fifo_getPrevItem(xbt_fifo_item_t i)
501 WARN0("This function is deprecated. Use xbt_fifo_get_prev_item.");
502 return xbt_fifo_get_prev_item(i);
506 * Destroy the fifo item mallocator.
507 * This is an internal XBT function called by xbt_exit().
509 void xbt_fifo_exit(void)
511 if (item_mallocator != NULL) {
512 xbt_mallocator_free(item_mallocator);
513 item_mallocator = NULL;