include/xbt/swag.h

   1 /* Copyright (c) 2004-2017. The SimGrid Team. All rights reserved.          */
   2
   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. */
   5
   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. */
   8
   9 #ifndef XBT_SWAG_H
  10 #define XBT_SWAG_H
  11
  12 #include "xbt/misc.h"
  13 #include "xbt/sysdep.h"         /* size_t */
  14
  15 SG_BEGIN_DECL()
  16
  17 /**
  18  * @addtogroup XBT_swag
  19  * @brief a O(1) set based on linked lists
  20  *
  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.
  25  *
  26  *  @deprecated If you are using C++, you might want to use
  27  *  `boost::intrusive::set` instead.
  28  */
  29 /** @defgroup XBT_swag_type Swag types
  30     @ingroup XBT_swag
  31
  32     Specific set.
  33
  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.
  36 */
  37 /* @{ */
  38 typedef struct xbt_swag_hookup {
  39   void *next;
  40   void *prev;
  41 } s_xbt_swag_hookup_t;
  42 /**< This type should be added to a type that is to be used in a swag.
  43  *
  44  *  Whenever a new object with this struct is created, all fields have to be set to NULL
  45  *
  46  * Here is an example like that :
  47
  48 \code
  49 typedef struct foo {
  50   s_xbt_swag_hookup_t set1_hookup;
  51   s_xbt_swag_hookup_t set2_hookup;
  52
  53   double value;
  54 } s_foo_t, *foo_t;
  55 ...
  56 {
  57   s_foo_t elem;
  58   xbt_swag_t set1=NULL;
  59   xbt_swag_t set2=NULL;
  60
  61   set1 = xbt_swag_new(xbt_swag_offset(elem, set1_hookup));
  62   set2 = xbt_swag_new(xbt_swag_offset(elem, set2_hookup));
  63
  64 }
  65 \endcode
  66 */
  67 typedef s_xbt_swag_hookup_t *xbt_swag_hookup_t;
  68
  69 struct xbt_swag {
  70   void *head;
  71   void *tail;
  72   size_t offset;
  73   int count;
  74 };
  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;
  78
  79 /**< A typical swag */
  80 /* @} */
  81
  82 /** @defgroup XBT_swag_func SWAG functions
  83  *  @ingroup XBT_swag
  84
  85  *  @{
  86  */
  87
  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);
  91
  92 /**
  93  * \brief Makes a swag empty.
  94  * \param swag a swag
  95  * @hideinitializer
  96  */
  97 #define xbt_swag_reset(swag) do {} while(xbt_swag_extract(swag))
  98
  99 /**
 100  * \param obj the objet to insert in the swag
 101  * \param swag a swag
 102  * @hideinitializer
 103  *
 104  * insert \a obj in \a swag
 105  */
 106 #define xbt_swag_insert(obj, swag) xbt_swag_insert_at_tail(obj, swag)
 107
 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);
 113
 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))
 117
 118 static inline void *xbt_swag_getFirst(const_xbt_swag_t swag)
 119 {
 120   return (swag->head);
 121 }
 122
 123 /**
 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.
 128  * @hideinitializer
 129  *
 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...
 132  */
 133 #define xbt_swag_offset(var,field) ((char *)&( (var).field ) - (char *)&(var))
 134 /* @} */
 135
 136 /**
 137  * \defgroup XBT_swag_curs Swag cursor
 138  * @ingroup XBT_swag
 139
 140  * Iterates over the whole swag.
 141  *
 142  * @{ */
 143
 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 */
 149 #ifndef __cplusplus
 150 #define xbt_swag_foreach(obj,swag)                            \
 151    for((obj)=xbt_swag_getFirst((swag));                       \
 152        (obj)!=NULL;                                           \
 153        (obj)=xbt_swag_getNext((obj),(swag)->offset))
 154 #else
 155 #define xbt_swag_foreach(obj,swag)                            \
 156    for((obj)=(decltype(obj)) xbt_swag_getFirst((swag));         \
 157        (obj)!=NULL;                                           \
 158        (obj)=(decltype(obj)) xbt_swag_getNext((obj),(swag)->offset))
 159 #endif
 160 /**
 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
 165  * @hideinitializer
 166
 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.  */
 169
 170 #ifndef __cplusplus
 171
 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)):  \
 175            (obj_next=NULL));                                      \
 176        (obj)!=NULL;                                               \
 177        (obj)=obj_next,                                            \
 178        ((obj)?(obj_next=xbt_swag_getNext((obj),(swag)->offset)):  \
 179                  (obj_next=NULL))     )
 180
 181 #else
 182
 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)):  \
 186            (obj_next=NULL));                                      \
 187        (obj) != NULL;                                             \
 188        (obj) = obj_next,                           \
 189        ((obj)?(obj_next = (decltype(obj)) xbt_swag_getNext((obj),(swag)->offset)):  \
 190                  (obj_next=NULL))     )
 191
 192 #endif
 193
 194 /* @} */
 195
 196 SG_END_DECL()
 197
 198 #endif /* XBT_SWAG_H */