Logo AND Algorithmique Numérique Distribuée

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