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/log.h"
  16 #include "xbt/swag.h"
  17
  18 #define PREV(obj,offset) xbt_swag_getPrev(obj,offset)
  19 #define NEXT(obj,offset) xbt_swag_getNext(obj,offset)
  20
  21
  22 /** Creates a new swag.
  23  * \param offset where the hookup is located in the structure
  24  * \see xbt_swag_offset
  25  *
  26  * Usage : xbt_swag_new(&obj.setA-&obj);
  27  */
  28 xbt_swag_t xbt_swag_new(size_t offset)
  29 {
  30   xbt_swag_t swag = xbt_new0(s_xbt_swag_t, 1);
  31
  32   swag->tail = NULL;
  33   swag->head = NULL;
  34   swag->offset = offset;
  35   swag->count = 0;
  36
  37   return swag;
  38 }
  39
  40 /**
  41  * \param swag poor victim
  42  *
  43  * kilkil a swag but not it's content. If you do not understand why
  44  * xbt_swag_free should not free its content, don't use swags.
  45  */
  46 void xbt_swag_free(xbt_swag_t swag)
  47 {
  48   free(swag);
  49 }
  50
  51 /** Creates a new swag.
  52  * \param swag the swag to initialize
  53  * \param offset where the hookup is located in the structure
  54  * \see xbt_swag_offset
  55  *
  56  * Usage : xbt_swag_init(swag,&obj.setA-&obj);
  57  */
  58 void xbt_swag_init(xbt_swag_t swag, size_t offset)
  59 {
  60   swag->tail = NULL;
  61   swag->head = NULL;
  62   swag->offset = offset;
  63   swag->count = 0;
  64 }
  65
  66
  67 /**
  68  * \param obj the objet to insert in the swag
  69  * \param swag a swag
  70  *
  71  * insert \a obj in \a swag
  72  */
  73 void xbt_swag_insert(void *obj, xbt_swag_t swag)
  74 {
  75
  76   if (xbt_swag_belongs(obj, swag))
  77     return;
  78
  79   (swag->count)++;
  80   if (swag->head == NULL) {
  81     xbt_assert0(!(swag->tail), "Inconsistent swag.");
  82     swag->head = obj;
  83     swag->tail = obj;
  84     return;
  85   }
  86
  87   PREV(obj, swag->offset) = swag->tail;
  88   NEXT(PREV(obj, swag->offset), swag->offset) = obj;
  89
  90   swag->tail = obj;
  91 }
  92
  93 /**
  94  * \param obj the objet to insert in the swag
  95  * \param swag a swag
  96  *
  97  * insert (at the head... you probably had a very good reason to do
  98  * that, I hope you know what you're doing) \a obj in \a swag
  99  */
 100 void xbt_swag_insert_at_head(void *obj, xbt_swag_t swag)
 101 {
 102
 103   if (xbt_swag_belongs(obj, swag))
 104     return;
 105
 106   (swag->count)++;
 107   if (swag->head == NULL) {
 108     xbt_assert0(!(swag->tail), "Inconsistent swag.");
 109     swag->head = obj;
 110     swag->tail = obj;
 111     return;
 112   }
 113
 114   NEXT(obj, swag->offset) = swag->head;
 115   PREV(NEXT(obj, swag->offset), swag->offset) = obj;
 116
 117   swag->head = obj;
 118 }
 119
 120 /**
 121  * \param obj the objet to insert in the swag
 122  * \param swag a swag
 123  *
 124  * insert (at the tail... you probably had a very good reason to do
 125  * that, I hope you know what you're doing) \a obj in \a swag
 126  */
 127 void xbt_swag_insert_at_tail(void *obj, xbt_swag_t swag)
 128 {
 129
 130   if (xbt_swag_belongs(obj, swag))
 131     return;
 132
 133   (swag->count)++;
 134   if (swag->head == NULL) {
 135     xbt_assert0(!(swag->tail), "Inconsistent swag.");
 136     swag->head = obj;
 137     swag->tail = obj;
 138     return;
 139   }
 140
 141   PREV(obj, swag->offset) = swag->tail;
 142   NEXT(PREV(obj, swag->offset), swag->offset) = obj;
 143
 144   swag->tail = obj;
 145 }
 146
 147 /**
 148  * \param obj the objet to remove from the swag
 149  * \param swag a swag
 150  * \return \a obj if it was in the \a swag and NULL otherwise
 151  *
 152  * removes \a obj from \a swag
 153  */
 154 void *xbt_swag_remove(void *obj, xbt_swag_t swag)
 155 {
 156   size_t offset = swag->offset;
 157
 158   if ((!obj) || (!swag))
 159     return NULL;
 160   if(!xbt_swag_belongs(obj, swag)) /* Trying to remove an object that
 161                                       was not in this swag */
 162       return NULL;
 163
 164   if (swag->head == swag->tail) {       /* special case */
 165     if (swag->head != obj)      /* Trying to remove an object that was not in this swag */
 166       return NULL;
 167     swag->head = NULL;
 168     swag->tail = NULL;
 169     NEXT(obj, offset) = PREV(obj, offset) = NULL;
 170   } else if (obj == swag->head) {       /* It's the head */
 171     swag->head = NEXT(obj, offset);
 172     PREV(swag->head, offset) = NULL;
 173     NEXT(obj, offset) = NULL;
 174   } else if (obj == swag->tail) {       /* It's the tail */
 175     swag->tail = PREV(obj, offset);
 176     NEXT(swag->tail, offset) = NULL;
 177     PREV(obj, offset) = NULL;
 178   } else {                      /* It's in the middle */
 179     NEXT(PREV(obj, offset), offset) = NEXT(obj, offset);
 180     PREV(NEXT(obj, offset), offset) = PREV(obj, offset);
 181     PREV(obj, offset) = NEXT(obj, offset) = NULL;
 182   }
 183   (swag->count)--;
 184   return obj;
 185 }
 186
 187 /**
 188  * \param swag a swag
 189  * \return an object from the \a swag
 190  */
 191 void *xbt_swag_extract(xbt_swag_t swag)
 192 {
 193   size_t offset = swag->offset;
 194   void *obj = NULL;
 195
 196   if ((!swag) || (!(swag->head)))
 197     return NULL;
 198
 199   obj = swag->head;
 200
 201   if (swag->head == swag->tail) {       /* special case */
 202     swag->head = swag->tail = NULL;
 203     PREV(obj, offset) = NEXT(obj, offset) = NULL;
 204   } else {
 205     swag->head = NEXT(obj, offset);
 206     PREV(swag->head, offset) = NULL;
 207     NEXT(obj, offset) = NULL;
 208   }
 209   (swag->count)--;
 210
 211   return obj;
 212 }
 213 /**
 214  * \param swag a swag
 215  * \return the number of objects in \a swag
 216  */
 217 int xbt_swag_size(xbt_swag_t swag)
 218 {
 219   return (swag->count);
 220 }
 221
 222 /**
 223  * \param obj an object
 224  * \param swag a swag
 225  * \return 1 if \a obj is in the \a swag and 0 otherwise
 226  */
 227 int xbt_swag_belongs(void *obj, xbt_swag_t swag)
 228 {
 229   return ((NEXT(obj, swag->offset)) || (PREV(obj, swag->offset))
 230           || (swag->head == obj));
 231 }
 232
 233
 234 #ifdef SIMGRID_TEST
 235
 236 XBT_TEST_SUITE("swag","Swag data container");
 237
 238 typedef struct {
 239   s_xbt_swag_hookup_t setA;
 240   s_xbt_swag_hookup_t setB;
 241   const char *name;
 242 } shmurtz, s_shmurtz_t, *shmurtz_t;
 243
 244
 245 XBT_TEST_UNIT("basic",test_swag_basic,"Basic usage") {
 246   shmurtz_t obj1, obj2, obj;
 247   xbt_swag_t setA,setB;
 248
 249   obj1 = calloc(1,sizeof(s_shmurtz_t));
 250   obj2 = calloc(1,sizeof(s_shmurtz_t));
 251
 252   obj1->name="Obj 1";
 253   obj2->name="Obj 2";
 254
 255   xbt_test_add0("Basic usage");
 256   xbt_test_log3("%p %p %ld\n",obj1,&(obj1->setB),
 257                 (long)((char *)&(obj1->setB) - (char *)obj1));
 258
 259   setA = xbt_swag_new(xbt_swag_offset(*obj1,setA));
 260   setB = xbt_swag_new(xbt_swag_offset(*obj1,setB));
 261
 262   xbt_swag_insert(obj1, setA);
 263   xbt_swag_insert(obj1, setB);
 264   xbt_swag_insert(obj2, setA);
 265   xbt_swag_insert(obj2, setB);
 266
 267   xbt_swag_remove(obj1, setB);
 268   /*  xbt_swag_remove(obj2, setB);*/
 269
 270   xbt_test_add0("Traverse set A");
 271   xbt_swag_foreach(obj,setA) {
 272     xbt_test_log1("Saw: %s",obj->name);
 273   }
 274
 275   xbt_test_add0("Traverse set B");
 276   xbt_swag_foreach(obj,setB) {
 277     xbt_test_log1("Saw: %s",obj->name);
 278   }
 279
 280   xbt_test_add0("Ensure set content and length");
 281   xbt_test_assert(  xbt_swag_belongs(obj1,setA));
 282   xbt_test_assert(  xbt_swag_belongs(obj2,setA));
 283
 284   xbt_test_assert(! xbt_swag_belongs(obj1,setB));
 285   xbt_test_assert(  xbt_swag_belongs(obj2,setB));
 286
 287   xbt_test_assert(xbt_swag_size(setA) == 2);
 288   xbt_test_assert(xbt_swag_size(setB) == 1);
 289
 290   xbt_swag_free(setA);
 291   xbt_swag_free(setB);
 292 }
 293
 294 #endif /* SIMGRID_TEST */