Logo AND Algorithmique Numérique Distribuée

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