Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
splint'able
[simgrid.git] / src / xbt / fifo.c
1 /*      $Id$     */
2
3 /* Copyright (c) 2004 Arnaud Legrand. All rights reserved.                  */
4
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. */
7
8 #include "xbt/sysdep.h"
9 #include "xbt/error.h"
10 #include "fifo_private.h"
11
12 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(fifo,xbt,"FIFO");
13
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.
18   */
19
20 /** \name Functions 
21  *  \ingroup XBT_fifo
22  */
23 /* @{ */
24
25 /** Constructor
26  * \return a new fifo
27  */
28 xbt_fifo_t xbt_fifo_new(void)
29 {
30   xbt_fifo_t fifo;
31   fifo = xbt_new0(struct xbt_fifo,1);
32   return fifo;
33 }
34
35 /** Destructor
36  * \param l poor victim
37  *
38  * Free the fifo structure. None of the objects that was in the fifo is however modified.
39  */
40 void xbt_fifo_free(xbt_fifo_t l)
41 {
42   xbt_fifo_item_t b, tmp;
43
44   for (b = xbt_fifo_getFirstitem(l); b;
45        tmp = b, b = b->next, xbt_fifo_freeitem(tmp));
46   free(l);
47   return;
48 }
49
50 /* Push
51  * \param l list
52  * \param t element
53  * \return the bucket that was just added
54  *
55  * Add an object at the tail of the list
56  */
57 xbt_fifo_item_t xbt_fifo_push(xbt_fifo_t l, void *t)
58 {
59   xbt_fifo_item_t new;
60
61   new = xbt_fifo_newitem();
62   new->content = t;
63
64   xbt_fifo_push_item(l,new);
65   return new;
66 }
67
68 /** Pop
69  * \param l list
70  * \returns the object stored at the tail of the list.
71  *
72  * Removes and returns the object stored at the tail of the list. 
73  * Returns NULL if the list is empty.
74  */
75 void *xbt_fifo_pop(xbt_fifo_t l)
76 {
77   xbt_fifo_item_t item;
78   void *content;
79
80   if(l==NULL) return NULL;
81   if(!(item = xbt_fifo_pop_item(l))) return NULL;
82
83   content = item->content;
84   xbt_fifo_freeitem(item);
85   return content;
86 }
87
88 /**
89  * \param l list
90  * \param t element
91  * \return the bucket that was just added
92  *
93  * Add an object at the head of the list
94  */
95 xbt_fifo_item_t xbt_fifo_unshift(xbt_fifo_t l, void *t)
96 {
97   xbt_fifo_item_t new;
98
99   new = xbt_fifo_newitem();
100   new->content = t;
101   xbt_fifo_unshift_item(l,new);
102   return new;
103 }
104
105 /** Shift
106  * \param l list
107  * \returns the object stored at the head of the list.
108  *
109  * Removes and returns the object stored at the head of the list. 
110  * Returns NULL if the list is empty.
111  */
112 void *xbt_fifo_shift(xbt_fifo_t l)
113 {
114   xbt_fifo_item_t item;
115   void *content;
116
117   if(l==NULL) return NULL;
118   if(!(item = xbt_fifo_shift_item(l))) return NULL;
119   
120   content = item->content;
121   xbt_fifo_freeitem(item);
122   return content;
123 }
124
125 /** Push a bucket
126  * \param l list
127  * \param new bucket
128  *
129  * Hook up this bucket at the tail of the list
130  */
131 void xbt_fifo_push_item(xbt_fifo_t l, xbt_fifo_item_t new)
132 {
133   (l->count)++;
134   if (l->head == NULL) {
135     l->head = new;
136     l->tail = new;
137     return;
138   }
139   new->prev = l->tail;
140   new->prev->next = new;
141   l->tail = new;
142 }
143
144 /** Pop bucket
145  * \param l
146  * \returns the bucket that was at the tail of the list.
147  *
148  * Returns NULL if the list was empty.
149  */
150 xbt_fifo_item_t xbt_fifo_pop_item(xbt_fifo_t l)
151 {
152   xbt_fifo_item_t item;
153
154   if (l->tail == NULL)
155     return NULL;
156
157   item = l->tail;
158
159   l->tail = item->prev;
160   if (l->tail == NULL)
161     l->head = NULL;
162   else
163     l->tail->next = NULL;
164
165   (l->count)--;
166   return item;
167 }
168
169 /** Push a bucket
170  * \param l list
171  * \param new bucket
172  *
173  * Hook up this bucket at the head of the list
174  */
175 void xbt_fifo_unshift_item(xbt_fifo_t l, xbt_fifo_item_t new)
176 {
177   (l->count)++;
178   if (l->head == NULL) {
179     l->head = new;
180     l->tail = new;
181     return;
182   }
183   new->next = l->head;
184   new->next->prev = new;
185   l->head = new;
186   return;
187 }
188
189 /** Shift bucket
190  * \param l
191  * \returns the bucket that was at the head of the list.
192  *
193  * Returns NULL if the list was empty.
194  */
195 xbt_fifo_item_t xbt_fifo_shift_item(xbt_fifo_t l)
196 {
197   xbt_fifo_item_t item;
198
199   if (l->head == NULL)
200     return NULL;
201
202   item = l->head;
203
204   l->head = item->next;
205   if (l->head == NULL)
206     l->tail = NULL;
207   else
208     l->head->prev = NULL;
209
210   (l->count)--;
211   return item;
212 }
213
214 /**
215  * \param l 
216  * \param t an objet
217  *
218  * removes the first occurence of \a t from \a l. 
219  * \warning it will not remove duplicates
220  */
221 void xbt_fifo_remove(xbt_fifo_t l, void *t)
222 {
223   xbt_fifo_item_t current, current_next;
224
225
226   for (current = l->head; current; current = current_next) {
227     current_next = current->next;
228     if (current->content != t)
229       continue;
230     /* remove the item */
231     xbt_fifo_remove_item(l, current);
232     xbt_fifo_freeitem(current);
233     /* WILL NOT REMOVE DUPLICATES */
234     break;
235   }
236   return;
237 }
238
239 /**
240  * \param l a list
241  * \param current a bucket
242  *
243  * removes a the bucket \a current from the list \a l
244  */
245 void xbt_fifo_remove_item(xbt_fifo_t l, xbt_fifo_item_t current)
246 {
247   if (l->head == l->tail) {     /* special case */
248       l->head = NULL;
249       l->tail = NULL;
250       (l->count)--;
251       return;
252     }
253
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;
263     }
264     (l->count)--;
265 }
266
267 /**
268  * \param f a list
269  * \param content an object
270  * \return 1 if \a content is in \a f.
271  */
272 int xbt_fifo_is_in(xbt_fifo_t f, void *content)
273 {
274   xbt_fifo_item_t item = xbt_fifo_getFirstitem(f);
275   while (item) {
276     if (item->content == content)
277       return 1;
278     item = item->next;
279   }
280   return 0;
281 }
282
283 /**
284  * \param f a list
285  * \return a table with the objects stored in \a f.
286  */
287 void **xbt_fifo_to_array(xbt_fifo_t f)
288 {
289   void **array;
290   xbt_fifo_item_t b;
291   int i;
292
293   if (f->count == 0)
294     return NULL;
295   else
296     array = xbt_new0(void *, f->count);
297
298   for (i = 0, b = xbt_fifo_getFirstitem(f); b; i++, b = b->next) {
299     array[i] = b->content;
300   }
301   return array;
302 }
303
304 /**
305  * \param f a list
306  * \return a copy of \a f.
307  */
308 xbt_fifo_t xbt_fifo_copy(xbt_fifo_t f)
309 {
310   xbt_fifo_t copy = NULL;
311   xbt_fifo_item_t b;
312
313   copy = xbt_fifo_new();
314
315   for (b = xbt_fifo_getFirstitem(f); b; b = b->next) {
316     xbt_fifo_push(copy, b->content);
317   }
318   return copy;
319 }
320
321 /** Constructor
322  * \return a new bucket
323  */
324 xbt_fifo_item_t xbt_fifo_newitem(void)
325 {
326   return xbt_new0(struct xbt_fifo_item,1);
327 }
328
329 /**
330  * \param i a bucket
331  * \param v an object
332  *
333  * stores \a v in \a i.
334  */
335 void xbt_fifo_set_item_content(xbt_fifo_item_t i , void *v)
336 {
337   xbt_fifo_setItemcontent(i,v);
338 }
339
340 /**
341  * \param i a bucket
342  * \return the object stored \a i.
343  */
344 void *xbt_fifo_get_item_content(xbt_fifo_item_t i)
345 {
346   return xbt_fifo_getItemcontent(i);
347 }
348
349 /** Destructor
350  * \param b poor victim
351  *
352  * Free the bucket but does not modifies the object (if any) that was stored in it.
353  */
354 void xbt_fifo_freeitem(xbt_fifo_item_t b)
355 {
356   free(b);
357   return;
358 }
359
360 /**
361  * \param f a list
362  * \return the number of buckets in \a f.
363  */
364 int xbt_fifo_size(xbt_fifo_t f)
365 {
366   return f->count;
367 }
368
369 /**
370  * \param l a list
371  * \return the head of \a l.
372  */
373 xbt_fifo_item_t xbt_fifo_getFirstItem(xbt_fifo_t l)
374 {
375   return l->head;
376 }
377
378 /**
379  * \param i a bucket
380  * \return the bucket that comes next
381  */
382 xbt_fifo_item_t xbt_fifo_getNextItem(xbt_fifo_item_t i)
383 {
384   if(i) return i->next;
385   return NULL;
386 }
387
388 /**
389  * \param i a bucket
390  * \return the bucket that is just before \a i.
391  */
392 xbt_fifo_item_t xbt_fifo_getPrevItem(xbt_fifo_item_t i)
393 {
394   if(i) return i->prev;
395   return NULL;
396 }
397 /* @} */
398
399