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