include/xbt/swag.h

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