include/xbt/swag.h

   1 /* Copyright (c) 2004, 2005, 2006, 2007, 2008, 2009, 2010. 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
   8    cast and dirty things. So avoid using it unless you really know
   9    what you are doing. */
  10
  11 #ifndef _XBT_SWAG_H
  12 #define _XBT_SWAG_H
  13
  14 #include "xbt/misc.h"
  15 #include "xbt/sysdep.h"         /* size_t */
  16
  17 SG_BEGIN_DECL()
  18
  19 /**
  20  * @addtogroup XBT_swag
  21  * @brief a O(1) set based on linked lists
  22  *
  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.
  28  *
  29  */
  30 /** @defgroup XBT_swag_type Swag types
  31     @ingroup XBT_swag
  32
  33     Specific set.
  34
  35
  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.
  39 */
  40 /* @{ */
  41 typedef struct xbt_swag_hookup {
  42   void *next;
  43   void *prev;
  44 } s_xbt_swag_hookup_t;
  45 /**< This type should be added to a type that is to be used in a swag.
  46  *
  47  *  Whenever a new object with this struct is created, all fields have
  48  *  to be set to NULL
  49  *
  50  * Here is an example like that :
  51
  52 \code
  53 typedef struct foo {
  54   s_xbt_swag_hookup_t set1_hookup;
  55   s_xbt_swag_hookup_t set2_hookup;
  56
  57   double value;
  58 } s_foo_t, *foo_t;
  59 ...
  60 {
  61   s_foo_t elem;
  62   xbt_swag_t set1=NULL;
  63   xbt_swag_t set2=NULL;
  64
  65   set1 = xbt_swag_new(xbt_swag_offset(elem, set1_hookup));
  66   set2 = xbt_swag_new(xbt_swag_offset(elem, set2_hookup));
  67
  68 }
  69 \endcode
  70 */
  71 typedef s_xbt_swag_hookup_t *xbt_swag_hookup_t;
  72
  73
  74 typedef struct xbt_swag {
  75   void *head;
  76   void *tail;
  77   size_t offset;
  78   int count;
  79 } s_xbt_swag_t, *xbt_swag_t;
  80 /**< A typical swag */
  81 /* @} */
  82
  83 /** @defgroup XBT_swag_func SWAG functions
  84  *  @ingroup XBT_swag
  85
  86  *  @{
  87  */
  88
  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_PUBLIC(void) xbt_swag_init(xbt_swag_t swag, size_t offset);
  92
  93 /**
  94  * \brief Makes a swag empty.
  95  * \param swag a swag
  96  * @hideinitializer
  97  */
  98 #define xbt_swag_reset(swag) do {} while(xbt_swag_extract(swag))
  99
 100 /**
 101  * \param obj the objet to insert in the swag
 102  * \param swag a swag
 103  * @hideinitializer
 104  *
 105  * insert \a obj in \a swag
 106  */
 107 #define xbt_swag_insert(obj, swag) xbt_swag_insert_at_tail(obj, swag)
 108
 109 XBT_PUBLIC(void) xbt_swag_insert_at_head(void *obj, xbt_swag_t swag);
 110 XBT_PUBLIC(void) xbt_swag_insert_at_tail(void *obj, xbt_swag_t swag);
 111 XBT_PUBLIC(void *) xbt_swag_remove(void *obj, xbt_swag_t swag);
 112 XBT_PUBLIC(void *) xbt_swag_extract(xbt_swag_t swag);
 113 XBT_PUBLIC(int) xbt_swag_size(xbt_swag_t swag);
 114
 115 #define xbt_swag_getPrev(obj, offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->prev)
 116 #define xbt_swag_getNext(obj, offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->next)
 117 #define xbt_swag_belongs(obj, swag) (xbt_swag_getNext((obj), (swag)->offset) || (swag)->tail == (obj))
 118
 119 static XBT_INLINE void *xbt_swag_getFirst(xbt_swag_t swag)
 120 {
 121   return (swag->head);
 122 }
 123
 124
 125 /**
 126  * \brief Offset computation
 127  * \arg var a variable of type <tt>struct</tt> something
 128  * \arg field a field of <tt>struct</tt> something
 129  * \return the offset of \a field in <tt>struct</tt> something.
 130  * @hideinitializer
 131  *
 132  * It is very similar to offsetof except that is done at runtime and that
 133  * you have to declare a variable. Why defining such a macro then ?
 134  * Because it is portable...
 135  */
 136 #define xbt_swag_offset(var,field) ((char *)&( (var).field ) - (char *)&(var))
 137 /* @} */
 138
 139 /**
 140  * \defgroup XBT_swag_curs Swag cursor
 141  * @ingroup XBT_swag
 142
 143  * Iterates over the whole swag.
 144  *
 145  * @{ */
 146
 147  /** @brief A simple swag iterator
 148   *  @param obj the indice of the loop
 149   *  @param swag what to iterate over
 150   *  @warning you cannot modify the \a swag while using this loop
 151   *  @hideinitializer */
 152 #define xbt_swag_foreach(obj,swag)                            \
 153    for((obj)=xbt_swag_getFirst((swag));                       \
 154        (obj)!=NULL;                                           \
 155        (obj)=xbt_swag_getNext((obj),(swag)->offset))
 156
 157 /**
 158  * @brief A safe swag iterator
 159  * @param obj the indice of the loop
 160  * @param obj_next the object that is right after (if any) \a obj in the swag
 161  * @param swag what to iterate over
 162  * @hideinitializer
 163
 164     You can safely modify the \a swag while using this loop.
 165     Well, safely... Err. You can remove \a obj without having any
 166     trouble at least.  */
 167
 168 #define xbt_swag_foreach_safe(obj,obj_next,swag)                  \
 169    for((obj)=xbt_swag_getFirst((swag)),                           \
 170        ((obj)?(obj_next=xbt_swag_getNext((obj),(swag)->offset)):  \
 171            (obj_next=NULL));                                \
 172        (obj)!=NULL;                                               \
 173        (obj)=obj_next,                                            \
 174        ((obj)?(obj_next=xbt_swag_getNext((obj),(swag)->offset)):  \
 175                  (obj_next=NULL))     )
 176 /* @} */
 177
 178 SG_END_DECL()
 179 #endif                          /* _XBT_SWAG_H */