Logo AND Algorithmique Numérique Distribuée

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