src/xbt/swag.c

   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 /* This type should be added to a type that is to be used in such a swag */
  13
  14 #include "xbt/sysdep.h"
  15 #include "xbt/error.h"
  16 #include "xbt/swag.h"
  17
  18 /** \defgroup XBT_swag A O(1) set datatype
  19  *  \brief a O(1) set based on linked lists
  20  *
  21  *  Warning, this module is done to be efficient and performs tons of
  22  *  cast and dirty things. So avoid using it unless you really know
  23  *  what you are doing. It is basically a fifo but with restrictions so that
  24  *  it can be used as a set. Any operation (add, remove, belongs) is O(1) and
  25  *  no call to malloc/free is done.
  26  */
  27
  28 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(swag,xbt,"Swag : O(1) set library");
  29
  30 #define PREV(obj,offset) xbt_swag_getPrev(obj,offset)
  31 #define NEXT(obj,offset) xbt_swag_getNext(obj,offset)
  32
  33 /** \name Functions
  34  *  \ingroup XBT_swag
  35  */
  36 /* @{ */
  37
  38 /** Creates a new swag.
  39  * \param offset where the hookup is located in the structure
  40  * \see xbt_swag_offset
  41  *
  42  * Usage : xbt_swag_new(&obj.setA-&obj);
  43  */
  44 xbt_swag_t xbt_swag_new(size_t offset)
  45 {
  46   xbt_swag_t swag = xbt_new0(s_xbt_swag_t, 1);
  47
  48   swag->offset = offset;
  49
  50   return swag;
  51 }
  52
  53 /**
  54  * \param swag poor victim
  55  *
  56  * kilkil a swag but not it's content. If you do not understand why
  57  * xbt_swag_free should not free its content, don't use swags.
  58  */
  59 void xbt_swag_free(xbt_swag_t swag)
  60 {
  61   free(swag);
  62 }
  63
  64 /** Creates a new swag.
  65  * \param swag the swag to initialize
  66  * \param offset where the hookup is located in the structure
  67  * \see xbt_swag_offset
  68  *
  69  * Usage : xbt_swag_init(swag,&obj.setA-&obj);
  70  */
  71 void xbt_swag_init(xbt_swag_t swag, size_t offset)
  72 {
  73   swag->offset = offset;
  74 }
  75
  76
  77 /**
  78  * \param obj the objet to insert in the swag
  79  * \param swag a swag
  80  *
  81  * insert \a obj in \a swag
  82  */
  83 void xbt_swag_insert(void *obj, xbt_swag_t swag)
  84 {
  85
  86   if (xbt_swag_belongs(obj, swag))
  87     return;
  88
  89   (swag->count)++;
  90   if (swag->head == NULL) {
  91     xbt_assert0(!(swag->tail), "Inconsistent swag.");
  92     swag->head = obj;
  93     swag->tail = obj;
  94     return;
  95   }
  96
  97   PREV(obj, swag->offset) = swag->tail;
  98   NEXT(PREV(obj, swag->offset), swag->offset) = obj;
  99
 100   swag->tail = obj;
 101 }
 102
 103 /**
 104  * \param obj the objet to insert in the swag
 105  * \param swag a swag
 106  *
 107  * insert (at the head... you probably had a very good reason to do
 108  * that, I hope you know what you're doing) \a obj in \a swag
 109  */
 110 void xbt_swag_insert_at_head(void *obj, xbt_swag_t swag)
 111 {
 112
 113   if (xbt_swag_belongs(obj, swag))
 114     return;
 115
 116   (swag->count)++;
 117   if (swag->head == NULL) {
 118     xbt_assert0(!(swag->tail), "Inconsistent swag.");
 119     swag->head = obj;
 120     swag->tail = obj;
 121     return;
 122   }
 123
 124   NEXT(obj, swag->offset) = swag->head;
 125   PREV(NEXT(obj, swag->offset), swag->offset) = obj;
 126
 127   swag->head = obj;
 128 }
 129
 130 /**
 131  * \param obj the objet to insert in the swag
 132  * \param swag a swag
 133  *
 134  * insert (at the tail... you probably had a very good reason to do
 135  * that, I hope you know what you're doing) \a obj in \a swag
 136  */
 137 void xbt_swag_insert_at_tail(void *obj, xbt_swag_t swag)
 138 {
 139
 140   if (xbt_swag_belongs(obj, swag))
 141     return;
 142
 143   (swag->count)++;
 144   if (swag->head == NULL) {
 145     xbt_assert0(!(swag->tail), "Inconsistent swag.");
 146     swag->head = obj;
 147     swag->tail = obj;
 148     return;
 149   }
 150
 151   PREV(obj, swag->offset) = swag->tail;
 152   NEXT(PREV(obj, swag->offset), swag->offset) = obj;
 153
 154   swag->tail = obj;
 155 }
 156
 157 /**
 158  * \param obj the objet to remove from the swag
 159  * \param swag a swag
 160  * \return \a obj if it was in the \a swag and NULL otherwise
 161  *
 162  * removes \a obj from \a swag
 163  */
 164 void *xbt_swag_remove(void *obj, xbt_swag_t swag)
 165 {
 166   size_t offset = swag->offset;
 167
 168   if ((!obj) || (!swag))
 169     return NULL;
 170   if(!xbt_swag_belongs(obj, swag)) /* Trying to remove an object that
 171                                       was not in this swag */
 172       return NULL;
 173
 174   if (swag->head == swag->tail) {       /* special case */
 175     if (swag->head != obj)      /* Trying to remove an object that was not in this swag */
 176       return NULL;
 177     swag->head = NULL;
 178     swag->tail = NULL;
 179     NEXT(obj, offset) = PREV(obj, offset) = NULL;
 180   } else if (obj == swag->head) {       /* It's the head */
 181     swag->head = NEXT(obj, offset);
 182     PREV(swag->head, offset) = NULL;
 183     NEXT(obj, offset) = NULL;
 184   } else if (obj == swag->tail) {       /* It's the tail */
 185     swag->tail = PREV(obj, offset);
 186     NEXT(swag->tail, offset) = NULL;
 187     PREV(obj, offset) = NULL;
 188   } else {                      /* It's in the middle */
 189     NEXT(PREV(obj, offset), offset) = NEXT(obj, offset);
 190     PREV(NEXT(obj, offset), offset) = PREV(obj, offset);
 191     PREV(obj, offset) = NEXT(obj, offset) = NULL;
 192   }
 193   (swag->count)--;
 194   return obj;
 195 }
 196
 197 /**
 198  * \param swag a swag
 199  * \return an object from the \a swag
 200  */
 201 void *xbt_swag_extract(xbt_swag_t swag)
 202 {
 203   size_t offset = swag->offset;
 204   void *obj = NULL;
 205
 206   if ((!swag) || (!(swag->head)))
 207     return NULL;
 208
 209   obj = swag->head;
 210
 211   if (swag->head == swag->tail) {       /* special case */
 212     swag->head = swag->tail = NULL;
 213     PREV(obj, offset) = NEXT(obj, offset) = NULL;
 214   } else {
 215     swag->head = NEXT(obj, offset);
 216     PREV(swag->head, offset) = NULL;
 217     NEXT(obj, offset) = NULL;
 218   }
 219   (swag->count)--;
 220
 221   return obj;
 222 }
 223 /**
 224  * \param swag a swag
 225  * \return the number of objects in \a swag
 226  */
 227 int xbt_swag_size(xbt_swag_t swag)
 228 {
 229   return (swag->count);
 230 }
 231
 232 /**
 233  * \param obj an object
 234  * \param swag a swag
 235  * \return 1 if \a obj is in the \a swag and 0 otherwise
 236  */
 237 int xbt_swag_belongs(void *obj, xbt_swag_t swag)
 238 {
 239   return ((NEXT(obj, swag->offset)) || (PREV(obj, swag->offset))
 240           || (swag->head == obj));
 241 }
 242 /* @} */