Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
xbt_swag: remove duplicated code.
[simgrid.git] / include / xbt / swag.h
1 /* Copyright (c) 2004, 2005, 2006, 2007, 2008, 2009, 2010. The SimGrid Team.
2  * All rights reserved.                                                     */
3
4 /* This program is free software; you can redistribute it and/or modify it
5  * under the terms of the license (GNU LGPL) which comes with this package. */
6
7 /* Warning, this module is done to be efficient and performs tons of
8    cast and dirty things. So avoid using it unless you really know
9    what you are doing. */
10
11 #ifndef _XBT_SWAG_H
12 #define _XBT_SWAG_H
13
14 #include "xbt/misc.h"
15 #include "xbt/sysdep.h"         /* size_t */
16
17 SG_BEGIN_DECL()
18
19 /** 
20  * @addtogroup XBT_swag
21  * @brief a O(1) set based on linked lists
22  * 
23  *  Warning, this module is done to be efficient and performs tons of
24  *  cast and dirty things. So make sure you know what you are doing while using it.
25  *  It is basically a fifo but with restrictions so that
26  *  it can be used as a set. Any operation (add, remove, belongs) is O(1) and
27  *  no call to malloc/free is done.
28  *
29  */
30 /** @defgroup XBT_swag_type Swag types
31     @ingroup XBT_swag
32
33     Specific set. 
34
35
36     These typedefs are public so that the compiler can
37     do his job but believe me, you don't want to try to play with 
38     those structs directly. Use them as an abstract datatype.
39 */
40 /* @{ */
41 typedef struct xbt_swag_hookup {
42   void *next;
43   void *prev;
44 } s_xbt_swag_hookup_t;
45 /**< This type should be added to a type that is to be used in a swag. 
46  *
47  *  Whenever a new object with this struct is created, all fields have
48  *  to be set to NULL 
49  *
50  * Here is an example like that :
51
52 \code
53 typedef struct foo {
54   s_xbt_swag_hookup_t set1_hookup;
55   s_xbt_swag_hookup_t set2_hookup;
56
57   double value;
58 } s_foo_t, *foo_t;
59 ...
60 {
61   s_foo_t elem;
62   xbt_swag_t set1=NULL;
63   xbt_swag_t set2=NULL;
64
65   set1 = xbt_swag_new(xbt_swag_offset(elem, set1_hookup));
66   set2 = xbt_swag_new(xbt_swag_offset(elem, set2_hookup));
67
68 }
69 \endcode
70 */
71 typedef s_xbt_swag_hookup_t *xbt_swag_hookup_t;
72
73
74 typedef struct xbt_swag {
75   void *head;
76   void *tail;
77   size_t offset;
78   int count;
79 } s_xbt_swag_t, *xbt_swag_t;
80 /**< A typical swag */
81 /* @} */
82
83 /** @defgroup XBT_swag_func SWAG functions 
84  *  @ingroup XBT_swag
85  
86  *  @{
87  */
88
89 XBT_PUBLIC(xbt_swag_t) xbt_swag_new(size_t offset);
90 XBT_PUBLIC(void) xbt_swag_free(xbt_swag_t swag);
91 XBT_INLINE XBT_PUBLIC(void) xbt_swag_init(xbt_swag_t swag, size_t offset);
92
93 /**
94  * \param obj the objet to insert in the swag
95  * \param swag a swag
96  * @hideinitializer
97  *
98  * insert \a obj in \a swag
99  */
100 #define xbt_swag_insert(obj, swag) xbt_swag_insert_at_tail(obj, swag)
101
102 XBT_PUBLIC(void) xbt_swag_insert_at_head(void *obj, xbt_swag_t swag);
103 XBT_PUBLIC(void) xbt_swag_insert_at_tail(void *obj, xbt_swag_t swag);
104 XBT_PUBLIC(void *) xbt_swag_remove(void *obj, xbt_swag_t swag);
105 XBT_PUBLIC(void *) xbt_swag_extract(xbt_swag_t swag);
106 XBT_PUBLIC(int) xbt_swag_size(xbt_swag_t swag);
107
108 #define xbt_swag_getPrev(obj,offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->prev)
109 #define xbt_swag_getNext(obj,offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->next)
110
111 static XBT_INLINE int xbt_swag_belongs(void *obj, xbt_swag_t swag)
112 {
113   return ((xbt_swag_getNext(obj, swag->offset))
114           || (xbt_swag_getPrev(obj, swag->offset))
115           || (swag->head == obj));
116 }
117
118 static XBT_INLINE void *xbt_swag_getFirst(xbt_swag_t swag)
119 {
120   return (swag->head);
121 }
122
123
124 /**
125  * \brief Offset computation
126  * \arg var a variable of type <tt>struct</tt> something
127  * \arg field a field of <tt>struct</tt> something
128  * \return the offset of \a field in <tt>struct</tt> something.
129  * @hideinitializer
130  *
131  * It is very similar to offsetof except that is done at runtime and that 
132  * you have to declare a variable. Why defining such a macro then ? 
133  * Because it is portable...
134  */
135 #define xbt_swag_offset(var,field) ((char *)&( (var).field ) - (char *)&(var))
136 /* @} */
137
138 /**
139  * \defgroup XBT_swag_curs Swag cursor
140  * @ingroup XBT_swag
141
142  * Iterates over the whole swag. 
143  *
144  * @{ */
145
146  /** @brief A simple swag iterator
147   *  @param obj the indice of the loop
148   *  @param swag what to iterate over
149   *  @warning you cannot modify the \a swag while using this loop
150   *  @hideinitializer */
151 #define xbt_swag_foreach(obj,swag)                            \
152    for((obj)=xbt_swag_getFirst((swag));                       \
153        (obj)!=NULL;                                           \
154        (obj)=xbt_swag_getNext((obj),(swag)->offset))
155
156 /**
157  * @brief A safe swag iterator 
158  * @param obj the indice of the loop
159  * @param obj_next the object that is right after (if any) \a obj in the swag
160  * @param swag what to iterate over
161  * @hideinitializer
162
163     You can safely modify the \a swag while using this loop. 
164     Well, safely... Err. You can remove \a obj without having any 
165     trouble at least.  */
166
167 #define xbt_swag_foreach_safe(obj,obj_next,swag)                  \
168    for((obj)=xbt_swag_getFirst((swag)),                           \
169        ((obj)?(obj_next=xbt_swag_getNext((obj),(swag)->offset)):  \
170                  (obj_next=NULL));                                \
171        (obj)!=NULL;                                               \
172        (obj)=obj_next,                                            \
173        ((obj)?(obj_next=xbt_swag_getNext((obj),(swag)->offset)):  \
174                  (obj_next=NULL))     )
175 /* @} */
176
177 SG_END_DECL()
178 #endif                          /* _XBT_SWAG_H */