1 /* Copyright (c) 2004-2017. The SimGrid Team. All rights reserved. */
3 /* This program is free software; you can redistribute it and/or modify it
4 * under the terms of the license (GNU LGPL) which comes with this package. */
6 /* Warning, this module is done to be efficient and performs tons of cast and dirty things. So avoid using it unless
7 * you really know what you are doing. */
13 #include "xbt/sysdep.h" /* size_t */
18 * @addtogroup XBT_swag
19 * @brief a O(1) set based on linked lists
21 * Warning, this module is done to be efficient and performs tons of cast and dirty things. So make sure you know what
22 * you are doing while using it.
23 * It is basically a fifo but with restrictions so that it can be used as a set. Any operation (add, remove, belongs)
24 * is O(1) and no call to malloc/free is done.
26 * @deprecated If you are using C++, you might want to use
27 * `boost::intrusive::set` instead.
29 /** @defgroup XBT_swag_type Swag types
34 These typedefs are public so that the compiler can do his job but believe me, you don't want to try to play with
35 those structs directly. Use them as an abstract datatype.
38 typedef struct xbt_swag_hookup {
41 } s_xbt_swag_hookup_t;
42 /**< This type should be added to a type that is to be used in a swag.
44 * Whenever a new object with this struct is created, all fields have to be set to NULL
46 * Here is an example like that :
50 s_xbt_swag_hookup_t set1_hookup;
51 s_xbt_swag_hookup_t set2_hookup;
61 set1 = xbt_swag_new(xbt_swag_offset(elem, set1_hookup));
62 set2 = xbt_swag_new(xbt_swag_offset(elem, set2_hookup));
67 typedef s_xbt_swag_hookup_t *xbt_swag_hookup_t;
75 typedef struct xbt_swag s_xbt_swag_t;
76 typedef struct xbt_swag* xbt_swag_t;
77 typedef const struct xbt_swag* const_xbt_swag_t;
79 /**< A typical swag */
82 /** @defgroup XBT_swag_func SWAG functions
88 XBT_PUBLIC(xbt_swag_t) xbt_swag_new(size_t offset);
89 XBT_PUBLIC(void) xbt_swag_free(xbt_swag_t swag);
90 XBT_PUBLIC(void) xbt_swag_init(xbt_swag_t swag, size_t offset);
93 * \brief Makes a swag empty.
97 #define xbt_swag_reset(swag) do {} while(xbt_swag_extract(swag))
100 * \param obj the objet to insert in the swag
104 * insert \a obj in \a swag
106 #define xbt_swag_insert(obj, swag) xbt_swag_insert_at_tail(obj, swag)
108 XBT_PUBLIC(void) xbt_swag_insert_at_head(void *obj, xbt_swag_t swag);
109 XBT_PUBLIC(void) xbt_swag_insert_at_tail(void *obj, xbt_swag_t swag);
110 XBT_PUBLIC(void *) xbt_swag_remove(void *obj, xbt_swag_t swag);
111 XBT_PUBLIC(void *) xbt_swag_extract(xbt_swag_t swag);
112 XBT_PUBLIC(int) xbt_swag_size(const_xbt_swag_t swag);
114 #define xbt_swag_getPrev(obj, offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->prev)
115 #define xbt_swag_getNext(obj, offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->next)
116 #define xbt_swag_belongs(obj, swag) (xbt_swag_getNext((obj), (swag)->offset) || (swag)->tail == (obj))
118 static inline void *xbt_swag_getFirst(const_xbt_swag_t swag)
124 * \brief Offset computation
125 * \arg var a variable of type <tt>struct</tt> something
126 * \arg field a field of <tt>struct</tt> something
127 * \return the offset of \a field in <tt>struct</tt> something.
130 * It is very similar to offsetof except that is done at runtime and that you have to declare a variable. Why defining
131 * such a macro then ? Because it is portable...
133 #define xbt_swag_offset(var,field) ((char *)&( (var).field ) - (char *)&(var))
137 * \defgroup XBT_swag_curs Swag cursor
140 * Iterates over the whole swag.
144 /** @brief A simple swag iterator
145 * @param obj the indice of the loop
146 * @param swag what to iterate over
147 * @warning you cannot modify the \a swag while using this loop
148 * @hideinitializer */
150 #define xbt_swag_foreach(obj,swag) \
151 for((obj)=xbt_swag_getFirst((swag)); \
153 (obj)=xbt_swag_getNext((obj),(swag)->offset))
155 #define xbt_swag_foreach(obj,swag) \
156 for((obj)=(decltype(obj)) xbt_swag_getFirst((swag)); \
158 (obj)=(decltype(obj)) xbt_swag_getNext((obj),(swag)->offset))
161 * @brief A safe swag iterator
162 * @param obj the indice of the loop
163 * @param obj_next the object that is right after (if any) \a obj in the swag
164 * @param swag what to iterate over
167 You can safely modify the \a swag while using this loop.
168 Well, safely... Err. You can remove \a obj without having any trouble at least. */
172 #define xbt_swag_foreach_safe(obj,obj_next,swag) \
173 for((obj)=xbt_swag_getFirst((swag)), \
174 ((obj)?(obj_next=xbt_swag_getNext((obj),(swag)->offset)): \
178 ((obj)?(obj_next=xbt_swag_getNext((obj),(swag)->offset)): \
183 #define xbt_swag_foreach_safe(obj,obj_next,swag) \
184 for((obj) = (decltype(obj)) xbt_swag_getFirst((swag)), \
185 ((obj)?(obj_next = (decltype(obj)) xbt_swag_getNext((obj),(swag)->offset)): \
189 ((obj)?(obj_next = (decltype(obj)) xbt_swag_getNext((obj),(swag)->offset)): \
198 #endif /* XBT_SWAG_H */