include/xbt/swag.h

   1 /*      $Id$     */
   2
   3 /* Copyright (c) 2004 Arnaud Legrand. All rights reserved.                */
   4
   5 /* This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the license (GNU LGPL) which comes with this package. */
   7
   8 /* Warning, this module is done to be efficient and performs tons of
   9    cast and dirty things. So avoid using it unless you really know
  10    what you are doing. */
  11
  12 #ifndef _XBT_SWAG_H
  13 #define _XBT_SWAG_H
  14
  15 #include "xbt/misc.h"
  16 #include "xbt/sysdep.h"
  17
  18 /* This type should be added to a type that is to be used in such a swag */
  19 /* Whenever a new object with this struct is created, all fields have
  20    to be set to NULL */
  21
  22 /**
  23  * \addtogroup XBT_swag
  24  *
  25  *  Warning, this module is done to be efficient and performs tons of
  26  *  cast and dirty things. So avoid using it unless you really know
  27  *  what you are doing. It is basically a fifo but with restrictions so that
  28  *  it can be used as a set. Any operation (add, remove, belongs) is O(1) and
  29  *  no call to malloc/free is done.
  30  *
  31  * @{
  32  */
  33
  34 /** \name Swag types
  35
  36     Specific set.
  37
  38     These typedefs are public so that the compiler can
  39     do his job but believe me, you don't want to try to play with
  40     those structs directly. Use them as an abstract datatype.
  41 */
  42 /* @{ */
  43 typedef struct xbt_swag_hookup {
  44   void *next;
  45   void *prev;
  46 } s_xbt_swag_hookup_t;
  47 /**< This type should be added to a type that is to be used in a swag.
  48  * For example like that :
  49
  50 \code
  51 typedef struct foo {
  52   s_xbt_swag_hookup_t set1_hookup;
  53   s_xbt_swag_hookup_t set2_hookup;
  54
  55   double value;
  56 } s_foo_t, *foo_t;
  57 ...
  58 {
  59   s_foo_t elem;
  60   xbt_swag_t set1=NULL;
  61   xbt_swag_t set2=NULL;
  62
  63   set1 = xbt_swag_new(xbt_swag_offset(elem, set1_hookup));
  64   set2 = xbt_swag_new(xbt_swag_offset(elem, set2_hookup));
  65
  66 }
  67 \endcode
  68 */
  69 typedef s_xbt_swag_hookup_t  *xbt_swag_hookup_t;
  70
  71
  72 typedef struct xbt_swag {
  73   void *head;
  74   void *tail;
  75   size_t offset;
  76   int count;
  77 } s_xbt_swag_t, *xbt_swag_t;
  78 /**< A typical swag */
  79 /* @} */
  80
  81 /** \name Functions
  82  */
  83 /* @{ */
  84
  85 xbt_swag_t xbt_swag_new(size_t offset);
  86 void xbt_swag_free(xbt_swag_t swag);
  87 void xbt_swag_init(xbt_swag_t swag, size_t offset);
  88 void xbt_swag_insert(void *obj, xbt_swag_t swag);
  89 void xbt_swag_insert_at_head(void *obj, xbt_swag_t swag);
  90 void xbt_swag_insert_at_tail(void *obj, xbt_swag_t swag);
  91 void *xbt_swag_remove(void *obj, xbt_swag_t swag);
  92 void *xbt_swag_extract(xbt_swag_t swag);
  93 int xbt_swag_size(xbt_swag_t swag);
  94 int xbt_swag_belongs(void *obj, xbt_swag_t swag);
  95
  96 static _XBT_INLINE void *xbt_swag_getFirst(xbt_swag_t swag)
  97 {
  98   return (swag->head);
  99 }
 100
 101 #define xbt_swag_getNext(obj,offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->prev)
 102 #define xbt_swag_getPrev(obj,offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->next)
 103
 104 /**
 105  * \brief Offset computation
 106  * \arg var a variable of type <tt>struct</tt> something
 107  * \arg field a field of <tt>struct</tt> something
 108  * \return the offset of \a field in <tt>struct</tt> something.
 109  *
 110  * It is very similar to offsetof except that is done at runtime and that
 111  * you have to declare a variable. Why defining such a macro then ?
 112  * Because it is portable...
 113  */
 114 #define xbt_swag_offset(var,field) ((char *)&( (var).field ) - (char *)&(var))
 115 /* @} */
 116
 117 /**
 118  * \name Swag iterator
 119  *
 120  * Iterates over the whole swag.
 121  *
 122  * @{ */
 123
 124  /** @brief A simple swag iterator
 125   *  @param obj the indice of the loop
 126   *  @param swag what to iterate over
 127   *  @warning you cannot modify the \a swag while using this loop
 128   *  @hideinitializer */
 129 #define xbt_swag_foreach(obj,swag)                            \
 130    for((obj)=xbt_swag_getFirst((swag));                       \
 131        (obj)!=NULL;                                           \
 132        (obj)=xbt_swag_getNext((obj),(swag)->offset))
 133
 134 /**
 135  * @brief A safe swag iterator
 136  * @param obj the indice of the loop
 137  * @param obj_next the object that is right after (if any) \a obj in the swag
 138  * @param swag what to iterate over
 139  * @hideinitializer
 140
 141     You can safely modify the \a swag while using this loop.
 142     Well, safely... Err. You can remove \a obj without having any
 143     trouble at least.  */
 144
 145 #define xbt_swag_foreach_safe(obj,obj_next,swag)                  \
 146    for((obj)=xbt_swag_getFirst((swag)),                           \
 147        ((obj)?(obj_next=xbt_swag_getNext((obj),(swag)->offset)):  \
 148                  (obj_next=NULL));                                \
 149        (obj)!=NULL;                                               \
 150        (obj)=obj_next,                                            \
 151        ((obj)?(obj_next=xbt_swag_getNext((obj),(swag)->offset)):  \
 152                  (obj_next=NULL))     )
 153 /* @} */
 154 /* @} */
 155
 156 #endif    /* _XBT_SWAG_H */