1 /* Copyright (c) 2004, 2005, 2006, 2007, 2008, 2009, 2010. The SimGrid Team.
2 * All rights reserved. */
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. */
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
15 #include "xbt/sysdep.h" /* size_t */
20 * @addtogroup XBT_swag
21 * @brief a O(1) set based on linked lists
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.
30 /** @defgroup XBT_swag_type Swag types
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.
41 typedef struct xbt_swag_hookup {
44 } s_xbt_swag_hookup_t;
45 /**< This type should be added to a type that is to be used in a swag.
47 * Whenever a new object with this struct is created, all fields have
50 * Here is an example like that :
54 s_xbt_swag_hookup_t set1_hookup;
55 s_xbt_swag_hookup_t set2_hookup;
65 set1 = xbt_swag_new(xbt_swag_offset(elem, set1_hookup));
66 set2 = xbt_swag_new(xbt_swag_offset(elem, set2_hookup));
71 typedef s_xbt_swag_hookup_t *xbt_swag_hookup_t;
74 typedef struct xbt_swag {
79 } s_xbt_swag_t, *xbt_swag_t;
80 /**< A typical swag */
83 /** @defgroup XBT_swag_func SWAG functions
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 XBT_PUBLIC(void) xbt_swag_insert(void *obj, xbt_swag_t swag);
93 XBT_PUBLIC(void) xbt_swag_insert_at_head(void *obj, xbt_swag_t swag);
94 XBT_PUBLIC(void) xbt_swag_insert_at_tail(void *obj, xbt_swag_t swag);
95 XBT_PUBLIC(void *) xbt_swag_remove(void *obj, xbt_swag_t swag);
96 XBT_PUBLIC(void *) xbt_swag_extract(xbt_swag_t swag);
97 XBT_PUBLIC(int) xbt_swag_size(xbt_swag_t swag);
99 #define xbt_swag_getNext(obj,offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->prev)
100 #define xbt_swag_getPrev(obj,offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->next)
102 static XBT_INLINE int xbt_swag_belongs(void *obj, xbt_swag_t swag)
104 return ((xbt_swag_getNext(obj, swag->offset))
105 || (xbt_swag_getPrev(obj, swag->offset))
106 || (swag->head == obj));
109 static XBT_INLINE void *xbt_swag_getFirst(xbt_swag_t swag)
116 * \brief Offset computation
117 * \arg var a variable of type <tt>struct</tt> something
118 * \arg field a field of <tt>struct</tt> something
119 * \return the offset of \a field in <tt>struct</tt> something.
122 * It is very similar to offsetof except that is done at runtime and that
123 * you have to declare a variable. Why defining such a macro then ?
124 * Because it is portable...
126 #define xbt_swag_offset(var,field) ((char *)&( (var).field ) - (char *)&(var))
130 * \defgroup XBT_swag_curs Swag cursor
133 * Iterates over the whole swag.
137 /** @brief A simple swag iterator
138 * @param obj the indice of the loop
139 * @param swag what to iterate over
140 * @warning you cannot modify the \a swag while using this loop
141 * @hideinitializer */
142 #define xbt_swag_foreach(obj,swag) \
143 for((obj)=xbt_swag_getFirst((swag)); \
145 (obj)=xbt_swag_getNext((obj),(swag)->offset))
148 * @brief A safe swag iterator
149 * @param obj the indice of the loop
150 * @param obj_next the object that is right after (if any) \a obj in the swag
151 * @param swag what to iterate over
154 You can safely modify the \a swag while using this loop.
155 Well, safely... Err. You can remove \a obj without having any
158 #define xbt_swag_foreach_safe(obj,obj_next,swag) \
159 for((obj)=xbt_swag_getFirst((swag)), \
160 ((obj)?(obj_next=xbt_swag_getNext((obj),(swag)->offset)): \
164 ((obj)?(obj_next=xbt_swag_getNext((obj),(swag)->offset)): \
169 #endif /* _XBT_SWAG_H */