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
  78 /**< A typical swag */
  79 /* @} */
  80
  81 /** @defgroup XBT_swag_func SWAG functions
  82  *  @ingroup XBT_swag
  83
  84  *  @{
  85  */
  86
  87 XBT_PUBLIC(xbt_swag_t) xbt_swag_new(size_t offset);
  88 XBT_PUBLIC(void) xbt_swag_free(xbt_swag_t swag);
  89 XBT_PUBLIC(void) xbt_swag_init(xbt_swag_t swag, size_t offset);
  90
  91 /**
  92  * \brief Makes a swag empty.
  93  * \param swag a swag
  94  * @hideinitializer
  95  */
  96 #define xbt_swag_reset(swag) do {} while(xbt_swag_extract(swag))
  97
  98 /**
  99  * \param obj the objet to insert in the swag
 100  * \param swag a swag
 101  * @hideinitializer
 102  *
 103  * insert \a obj in \a swag
 104  */
 105 #define xbt_swag_insert(obj, swag) xbt_swag_insert_at_tail(obj, swag)
 106
 107 XBT_PUBLIC(void) xbt_swag_insert_at_head(void *obj, xbt_swag_t swag);
 108 XBT_PUBLIC(void) xbt_swag_insert_at_tail(void *obj, xbt_swag_t swag);
 109 XBT_PUBLIC(void *) xbt_swag_remove(void *obj, xbt_swag_t swag);
 110 XBT_PUBLIC(void *) xbt_swag_extract(xbt_swag_t swag);
 111 XBT_PUBLIC(int) xbt_swag_size(xbt_swag_t swag);
 112
 113 #define xbt_swag_getPrev(obj, offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->prev)
 114 #define xbt_swag_getNext(obj, offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->next)
 115 #define xbt_swag_belongs(obj, swag) (xbt_swag_getNext((obj), (swag)->offset) || (swag)->tail == (obj))
 116
 117 static inline void *xbt_swag_getFirst(xbt_swag_t swag)
 118 {
 119   return (swag->head);
 120 }
 121
 122 /**
 123  * \brief Offset computation
 124  * \arg var a variable of type <tt>struct</tt> something
 125  * \arg field a field of <tt>struct</tt> something
 126  * \return the offset of \a field in <tt>struct</tt> something.
 127  * @hideinitializer
 128  *
 129  * It is very similar to offsetof except that is done at runtime and that you have to declare a variable. Why defining
 130  * such a macro then ? Because it is portable...
 131  */
 132 #define xbt_swag_offset(var,field) ((char *)&( (var).field ) - (char *)&(var))
 133 /* @} */
 134
 135 /**
 136  * \defgroup XBT_swag_curs Swag cursor
 137  * @ingroup XBT_swag
 138
 139  * Iterates over the whole swag.
 140  *
 141  * @{ */
 142
 143  /** @brief A simple swag iterator
 144   *  @param obj the indice of the loop
 145   *  @param swag what to iterate over
 146   *  @warning you cannot modify the \a swag while using this loop
 147   *  @hideinitializer */
 148 #ifndef __cplusplus
 149 #define xbt_swag_foreach(obj,swag)                            \
 150    for((obj)=xbt_swag_getFirst((swag));                       \
 151        (obj)!=NULL;                                           \
 152        (obj)=xbt_swag_getNext((obj),(swag)->offset))
 153 #else
 154 #define xbt_swag_foreach(obj,swag)                            \
 155    for((obj)=(decltype(obj)) xbt_swag_getFirst((swag));         \
 156        (obj)!=NULL;                                           \
 157        (obj)=(decltype(obj)) xbt_swag_getNext((obj),(swag)->offset))
 158 #endif
 159 /**
 160  * @brief A safe swag iterator
 161  * @param obj the indice of the loop
 162  * @param obj_next the object that is right after (if any) \a obj in the swag
 163  * @param swag what to iterate over
 164  * @hideinitializer
 165
 166     You can safely modify the \a swag while using this loop.
 167     Well, safely... Err. You can remove \a obj without having any trouble at least.  */
 168
 169 #ifndef __cplusplus
 170
 171 #define xbt_swag_foreach_safe(obj,obj_next,swag)                  \
 172    for((obj)=xbt_swag_getFirst((swag)),                           \
 173        ((obj)?(obj_next=xbt_swag_getNext((obj),(swag)->offset)):  \
 174            (obj_next=NULL));                                      \
 175        (obj)!=NULL;                                               \
 176        (obj)=obj_next,                                            \
 177        ((obj)?(obj_next=xbt_swag_getNext((obj),(swag)->offset)):  \
 178                  (obj_next=NULL))     )
 179
 180 #else
 181
 182 #define xbt_swag_foreach_safe(obj,obj_next,swag)                  \
 183    for((obj) = (decltype(obj)) xbt_swag_getFirst((swag)),         \
 184        ((obj)?(obj_next = (decltype(obj)) xbt_swag_getNext((obj),(swag)->offset)):  \
 185            (obj_next=NULL));                                      \
 186        (obj) != NULL;                                             \
 187        (obj) = obj_next,                           \
 188        ((obj)?(obj_next = (decltype(obj)) xbt_swag_getNext((obj),(swag)->offset)):  \
 189                  (obj_next=NULL))     )
 190
 191 #endif
 192
 193 /* @} */
 194
 195 SG_END_DECL()
 196
 197 #endif /* XBT_SWAG_H */