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