1 |
14 |
jcastillo |
/*
|
2 |
|
|
|
3 |
|
|
This is SGLIB version 1.0.1
|
4 |
|
|
|
5 |
|
|
(C) by Marian Vittek, Bratislava, http://www.xref-tech.com/sglib, 2003,2004
|
6 |
|
|
|
7 |
|
|
License Conditions: You can use this software:
|
8 |
|
|
- freely for non-commercial purposes,
|
9 |
|
|
- or under the terms of the Open Source Software License,
|
10 |
|
|
- or under the terms of the GNU Public License.
|
11 |
|
|
If you wish to receive it under other (commercial) license conditions,
|
12 |
|
|
contact the author.
|
13 |
|
|
|
14 |
|
|
*/
|
15 |
|
|
|
16 |
|
|
|
17 |
|
|
#ifndef _SGLIB__h_
|
18 |
|
|
#define _SGLIB__h_
|
19 |
|
|
|
20 |
|
|
/* the assert is used exclusively to write unexpected error messages */
|
21 |
|
|
#include <assert.h>
|
22 |
|
|
|
23 |
|
|
|
24 |
|
|
/* ---------------------------------------------------------------------------- */
|
25 |
|
|
/* ---------------------------------------------------------------------------- */
|
26 |
|
|
/* - LEVEL - 0 INTERFACE - */
|
27 |
|
|
/* ---------------------------------------------------------------------------- */
|
28 |
|
|
/* ---------------------------------------------------------------------------- */
|
29 |
|
|
|
30 |
|
|
|
31 |
|
|
/* ---------------------------------------------------------------------------- */
|
32 |
|
|
/* ------------------------------ STATIC ARRAYS ------------------------------- */
|
33 |
|
|
/* ---------------------------------------------------------------------------- */
|
34 |
|
|
|
35 |
|
|
/*
|
36 |
|
|
|
37 |
|
|
Basic algorithms for sorting arrays. Multiple depending arrays can
|
38 |
|
|
be rearranged using user defined 'elem_exchangers'
|
39 |
|
|
|
40 |
|
|
*/
|
41 |
|
|
|
42 |
|
|
/* HEAP - SORT (level 0) */
|
43 |
|
|
|
44 |
|
|
#define SGLIB_ARRAY_SINGLE_HEAP_SORT(type, a, max, comparator) {\
|
45 |
|
|
SGLIB_ARRAY_HEAP_SORT(type, a, max, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\
|
46 |
|
|
}
|
47 |
|
|
|
48 |
|
|
#define SGLIB_ARRAY_HEAP_SORT(type, a, max, comparator, elem_exchanger) {\
|
49 |
|
|
int _k_;\
|
50 |
|
|
for(_k_=(max)/2; _k_>=0; _k_--) {\
|
51 |
|
|
SGLIB___ARRAY_HEAP_DOWN(type, a, _k_, max, comparator, elem_exchanger);\
|
52 |
|
|
}\
|
53 |
|
|
for(_k_=(max)-1; _k_>=0; _k_--) {\
|
54 |
|
|
elem_exchanger(type, a, 0, _k_);\
|
55 |
|
|
SGLIB___ARRAY_HEAP_DOWN(type, a, 0, _k_, comparator, elem_exchanger);\
|
56 |
|
|
}\
|
57 |
|
|
}
|
58 |
|
|
|
59 |
|
|
#define SGLIB___ARRAY_HEAP_DOWN(type, a, ind, max, comparator, elem_exchanger) {\
|
60 |
|
|
type _t_;\
|
61 |
|
|
int _m_, _l_, _r_, _i_;\
|
62 |
|
|
_i_ = (ind);\
|
63 |
|
|
_m_ = _i_;\
|
64 |
|
|
do {\
|
65 |
|
|
_i_ = _m_; \
|
66 |
|
|
_l_ = 2*_i_+1;\
|
67 |
|
|
_r_ = _l_+1;\
|
68 |
|
|
if (_l_ < (max)){\
|
69 |
|
|
if (comparator(((a)[_m_]), ((a)[_l_])) < 0) _m_ = _l_;\
|
70 |
|
|
if (_r_ < (max)) {\
|
71 |
|
|
if (comparator(((a)[_m_]), ((a)[_r_])) < 0) _m_ = _r_;\
|
72 |
|
|
}\
|
73 |
|
|
}\
|
74 |
|
|
if (_m_ != _i_) {\
|
75 |
|
|
elem_exchanger(type, a, _i_, _m_);\
|
76 |
|
|
}\
|
77 |
|
|
} while (_m_ != _i_);\
|
78 |
|
|
}
|
79 |
|
|
|
80 |
|
|
|
81 |
|
|
/* QUICK - SORT (level 0) */
|
82 |
|
|
|
83 |
|
|
#define SGLIB_ARRAY_SINGLE_QUICK_SORT(type, a, max, comparator) {\
|
84 |
|
|
SGLIB_ARRAY_QUICK_SORT(type, a, max, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\
|
85 |
|
|
}
|
86 |
|
|
|
87 |
|
|
#define SGLIB_ARRAY_QUICK_SORT(type, a, max, comparator, elem_exchanger) {\
|
88 |
|
|
int _i_, _j_, _p_, _stacki_, _start_, _end_;\
|
89 |
|
|
/* can sort up to 2^64 elements */\
|
90 |
|
|
int _startStack_[64]; \
|
91 |
|
|
int _endStack_[64];\
|
92 |
|
|
type _tmp_;\
|
93 |
|
|
_startStack_[0] = 0;\
|
94 |
|
|
_endStack_[0] = (max);\
|
95 |
|
|
_stacki_ = 1;\
|
96 |
|
|
while (_stacki_ > 0) {\
|
97 |
|
|
_stacki_ --;\
|
98 |
|
|
_start_ = _startStack_[_stacki_];\
|
99 |
|
|
_end_ = _endStack_[_stacki_];\
|
100 |
|
|
while (_end_ - _start_ > 2) {\
|
101 |
|
|
_p_ = _start_;\
|
102 |
|
|
_i_ = _start_ + 1;\
|
103 |
|
|
_j_ = _end_ - 1;\
|
104 |
|
|
while (_i_<_j_) {\
|
105 |
|
|
for(; _i_<=_j_ && comparator(((a)[_i_]),((a)[_p_]))<=0; _i_++) ;\
|
106 |
|
|
if (_i_ > _j_) {\
|
107 |
|
|
/* all remaining elements lesseq than pivot */\
|
108 |
|
|
elem_exchanger(type, a, _j_, _p_);\
|
109 |
|
|
_i_ = _j_;\
|
110 |
|
|
} else {\
|
111 |
|
|
for(; _i_<=_j_ && comparator(((a)[_j_]),((a)[_p_]))>=0; _j_--) ;\
|
112 |
|
|
if (_i_ > _j_) {\
|
113 |
|
|
/* all remaining elements greater than pivot */\
|
114 |
|
|
elem_exchanger(type, a, _j_, _p_);\
|
115 |
|
|
_i_ = _j_;\
|
116 |
|
|
} else if (_i_ < _j_) {\
|
117 |
|
|
elem_exchanger(type, a, _i_, _j_);\
|
118 |
|
|
if (_i_+2 < _j_) {_i_++; _j_--;}\
|
119 |
|
|
else if (_i_+1 < _j_) _i_++;\
|
120 |
|
|
}\
|
121 |
|
|
}\
|
122 |
|
|
}\
|
123 |
|
|
/* O.K. i==j and pivot is on a[i] == a[j] */\
|
124 |
|
|
/* handle recursive calls without recursion */\
|
125 |
|
|
if (_i_-_start_ > 1 && _end_-_j_ > 1) {\
|
126 |
|
|
/* two recursive calls, use array-stack */\
|
127 |
|
|
if (_i_-_start_ < _end_-_j_-1) {\
|
128 |
|
|
_startStack_[_stacki_] = _j_+1;\
|
129 |
|
|
_endStack_[_stacki_] = _end_;\
|
130 |
|
|
_stacki_ ++;\
|
131 |
|
|
_end_ = _i_;\
|
132 |
|
|
} else {\
|
133 |
|
|
_startStack_[_stacki_] = _start_;\
|
134 |
|
|
_endStack_[_stacki_] = _i_;\
|
135 |
|
|
_stacki_ ++;\
|
136 |
|
|
_start_ = _j_+1;\
|
137 |
|
|
}\
|
138 |
|
|
} else {\
|
139 |
|
|
if (_i_-_start_ > 1) {\
|
140 |
|
|
_end_ = _i_;\
|
141 |
|
|
} else {\
|
142 |
|
|
_start_ = _j_+1;\
|
143 |
|
|
}\
|
144 |
|
|
}\
|
145 |
|
|
}\
|
146 |
|
|
if (_end_ - _start_ == 2) {\
|
147 |
|
|
if (comparator(((a)[_start_]),((a)[_end_-1])) > 0) {\
|
148 |
|
|
elem_exchanger(type, a, _start_, _end_-1);\
|
149 |
|
|
}\
|
150 |
|
|
}\
|
151 |
|
|
}\
|
152 |
|
|
}
|
153 |
|
|
|
154 |
|
|
/* BINARY SEARCH (level 0) */
|
155 |
|
|
|
156 |
|
|
#define SGLIB_ARRAY_BINARY_SEARCH(type, a, start_index, end_index, key, comparator, found, result_index) {\
|
157 |
|
|
int _kk_, _cc_, _ii_, _jj_, _ff_;\
|
158 |
|
|
_ii_ = (start_index); \
|
159 |
|
|
_jj_ = (end_index);\
|
160 |
|
|
_ff_ = 0;\
|
161 |
|
|
while (_ii_ <= _jj_ && _ff_==0) {\
|
162 |
|
|
_kk_ = (_jj_+_ii_)/2;\
|
163 |
|
|
_cc_ = comparator(((a)[_kk_]), (key));\
|
164 |
|
|
if (_cc_ == 0) {\
|
165 |
|
|
(result_index) = _kk_; \
|
166 |
|
|
_ff_ = 1;\
|
167 |
|
|
} else if (_cc_ < 0) {\
|
168 |
|
|
_ii_ = _kk_+1;\
|
169 |
|
|
} else {\
|
170 |
|
|
_jj_ = _kk_-1;\
|
171 |
|
|
}\
|
172 |
|
|
}\
|
173 |
|
|
if (_ff_ == 0) {\
|
174 |
|
|
/* not found, but set its resulting place in the array */\
|
175 |
|
|
(result_index) = _jj_+1;\
|
176 |
|
|
}\
|
177 |
|
|
(found) = _ff_;\
|
178 |
|
|
}
|
179 |
|
|
|
180 |
|
|
/* -------------------------------- queue (in an array) ------------------ */
|
181 |
|
|
/* queue is a quadruple (a,i,j,dim) such that: */
|
182 |
|
|
/* a is the array storing values */
|
183 |
|
|
/* i is the index of the first used element in the array */
|
184 |
|
|
/* j is the index of the first free element in the array */
|
185 |
|
|
/* dim is the size of the array a */
|
186 |
|
|
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */
|
187 |
|
|
|
188 |
|
|
#define SGLIB_QUEUE_INIT(type, a, i, j) { i = j = 0; }
|
189 |
|
|
#define SGLIB_QUEUE_IS_EMPTY(type, a, i, j) ((i)==(j))
|
190 |
|
|
#define SGLIB_QUEUE_IS_FULL(type, a, i, j, dim) ((i)==((j)+1)%(dim))
|
191 |
|
|
#define SGLIB_QUEUE_FIRST_ELEMENT(type, a, i, j) (a[i])
|
192 |
|
|
#define SGLIB_QUEUE_ADD_NEXT(type, a, i, j, dim) {\
|
193 |
|
|
if (SGLIB_QUEUE_IS_FULL(type, a, i, j, dim)) assert(0 && "the queue is full");\
|
194 |
|
|
(j) = ((j)+1) % (dim);\
|
195 |
|
|
}
|
196 |
|
|
#define SGLIB_QUEUE_ADD(type, a, elem, i, j, dim) {\
|
197 |
|
|
a[j] = (elem);\
|
198 |
|
|
SGLIB_QUEUE_ADD_NEXT(type, a, i, j, dim);\
|
199 |
|
|
}
|
200 |
|
|
#define SGLIB_QUEUE_DELETE_FIRST(type, a, i, j, dim) {\
|
201 |
|
|
if (SGLIB_QUEUE_IS_EMPTY(type, a, i, j)) assert(0 && "the queue is empty");\
|
202 |
|
|
(i) = ((i)+1) % (dim);\
|
203 |
|
|
}
|
204 |
|
|
#define SGLIB_QUEUE_DELETE(type, a, i, j, dim) {\
|
205 |
|
|
SGLIB_QUEUE_DELETE_FIRST(type, a, i, j, dim);\
|
206 |
|
|
}
|
207 |
|
|
|
208 |
|
|
/* ----------------- priority queue (heap) (in an array) -------------------- */
|
209 |
|
|
/* heap is a triple (a,i,dim) such that: */
|
210 |
|
|
/* a is the array storing values */
|
211 |
|
|
/* i is the index of the first free element in the array */
|
212 |
|
|
/* dim is the size of the array a */
|
213 |
|
|
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */
|
214 |
|
|
|
215 |
|
|
#define SGLIB_HEAP_INIT(type, a, i) { i = 0; }
|
216 |
|
|
#define SGLIB_HEAP_IS_EMPTY(type, a, i) ((i)==0)
|
217 |
|
|
#define SGLIB_HEAP_IS_FULL(type, a, i, dim) ((i)==(dim))
|
218 |
|
|
#define SGLIB_HEAP_FIRST_ELEMENT(type, a, i) (a[0])
|
219 |
|
|
#define SGLIB_HEAP_ADD_NEXT(type, a, i, dim, comparator, elem_exchanger) {\
|
220 |
|
|
int _i_;\
|
221 |
|
|
if (SGLIB_HEAP_IS_FULL(type, a, i, dim)) assert(0 && "the heap is full");\
|
222 |
|
|
_i_ = (i)++;\
|
223 |
|
|
while (_i_ > 0 && comparator(a[_i_/2], a[_i_]) < 0) {\
|
224 |
|
|
elem_exchanger(type, a, (_i_/2), _i_);\
|
225 |
|
|
_i_ = _i_/2;\
|
226 |
|
|
}\
|
227 |
|
|
}
|
228 |
|
|
#define SGLIB_HEAP_ADD(type, a, elem, i, dim, comparator) {\
|
229 |
|
|
if (SGLIB_HEAP_IS_FULL(type, a, i, dim)) assert(0 && "the heap is full");\
|
230 |
|
|
a[i] = (elem);\
|
231 |
|
|
SGLIB_HEAP_ADD_NEXT(type, a, i, dim, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\
|
232 |
|
|
}
|
233 |
|
|
#define SGLIB_HEAP_DELETE_FIRST(type, a, i, dim, comparator, elem_exchanger) {\
|
234 |
|
|
if (SGLIB_HEAP_IS_EMPTY(type, a, i)) assert(0 && "the heap is empty");\
|
235 |
|
|
(i)--;\
|
236 |
|
|
a[0] = a[i];\
|
237 |
|
|
SGLIB___ARRAY_HEAP_DOWN(type, a, 0, i, comparator, elem_exchanger);\
|
238 |
|
|
}
|
239 |
|
|
#define SGLIB_HEAP_DELETE(type, a, i, dim, comparator) {\
|
240 |
|
|
SGLIB_HEAP_DELETE_FIRST(type, a, i, dim, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\
|
241 |
|
|
}
|
242 |
|
|
|
243 |
|
|
|
244 |
|
|
/* ----------------- hashed table of pointers (in an array) -------------------- */
|
245 |
|
|
|
246 |
|
|
/*
|
247 |
|
|
|
248 |
|
|
This hashed table is storing pointers to objects (not containers).
|
249 |
|
|
In this table there is a one-to-one mapping between 'objects' stored
|
250 |
|
|
in the table and indexes where they are placed. Each index is
|
251 |
|
|
pointing to exactly one 'object' and each 'object' stored in the
|
252 |
|
|
table occurs on exactly one index. Once an object is stored in the
|
253 |
|
|
table, it can be represented via its index.
|
254 |
|
|
|
255 |
|
|
In case of collision while adding an object the index shifted
|
256 |
|
|
by SGLIB_HASH_TAB_SHIFT_CONSTANT (constant can be redefined)
|
257 |
|
|
|
258 |
|
|
You can NOT delete an element from such hash table. The only
|
259 |
|
|
justification (I can see) for this data structure is an exchange
|
260 |
|
|
file format, having an index table at the beginning and then
|
261 |
|
|
refering objects via indexes.
|
262 |
|
|
|
263 |
|
|
!!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!!
|
264 |
|
|
|
265 |
|
|
*/
|
266 |
|
|
|
267 |
|
|
#define SGLIB_HASH_TAB_INIT(type, table, dim) {\
|
268 |
|
|
int _i_;\
|
269 |
|
|
for(_i_ = 0; _i_ < (dim); _i_++) (table)[_i_] = NULL;\
|
270 |
|
|
}
|
271 |
|
|
|
272 |
|
|
#define SGLIB_HASH_TAB_ADD_IF_NOT_MEMBER(type, table, dim, elem, hash_function, comparator, member){\
|
273 |
|
|
unsigned _pos_;\
|
274 |
|
|
type *_elem_;\
|
275 |
|
|
SGLIB_HASH_TAB_FIND_MEMBER(type, table, dim, elem, _pos_, _elem_);\
|
276 |
|
|
(member) = (table)[_pos_];\
|
277 |
|
|
if (_elem_ == NULL) {\
|
278 |
|
|
if ((table)[_pos_] != NULL) assert(0 && "the hash table is full");\
|
279 |
|
|
(table)[_pos_] = (elem);\
|
280 |
|
|
}\
|
281 |
|
|
}
|
282 |
|
|
|
283 |
|
|
#define SGLIB_HASH_TAB_FIND_MEMBER(type, table, dim, elem, hash_function, comparator, resultIndex, resultMember) {\
|
284 |
|
|
unsigned _i_;\
|
285 |
|
|
int _count_;\
|
286 |
|
|
type *_e_;\
|
287 |
|
|
_count = 0;\
|
288 |
|
|
_i_ = hash_function(elem);\
|
289 |
|
|
_i_ %= (dim);\
|
290 |
|
|
while ((_e_=(table)[_i_])!=NULL && comparator(_e_, (elem))!=0 && _count_<(dim)) {\
|
291 |
|
|
_count_ ++;\
|
292 |
|
|
_i_ = (_i_ + SGLIB_HASH_TAB_SHIFT_CONSTANT) % (dim);\
|
293 |
|
|
}\
|
294 |
|
|
(resultIndex) = _i_;\
|
295 |
|
|
if (_count_ < (dim)) (resultMember) = _e_;\
|
296 |
|
|
else (resultMember) = NULL;\
|
297 |
|
|
}
|
298 |
|
|
|
299 |
|
|
#define SGLIB_HASH_TAB_IS_MEMBER(type, table, dim, elem, hash_function, resultIndex) {\
|
300 |
|
|
unsigned _i_;\
|
301 |
|
|
int _c_;\
|
302 |
|
|
type *_e_;\
|
303 |
|
|
_count = 0;\
|
304 |
|
|
_i_ = hash_function(elem);\
|
305 |
|
|
_i_ %= (dim);\
|
306 |
|
|
while ((_e_=(table)[_i_])!=NULL && _e_!=(elem) && _c_<(dim)) {\
|
307 |
|
|
_c_ ++;\
|
308 |
|
|
_i_ = (_i_ + SGLIB_HASH_TAB_SHIFT_CONSTANT) % (dim);\
|
309 |
|
|
}\
|
310 |
|
|
if (_e_==(elem)) (resultIndex) = _i_;\
|
311 |
|
|
else (resultIndex) = -1;\
|
312 |
|
|
}
|
313 |
|
|
|
314 |
|
|
#define SGLIB_HASH_TAB_MAP_ON_ELEMENTS(type, table, dim, iteratedIndex, iteratedVariable, command) {\
|
315 |
|
|
unsigned iteratedIndex;\
|
316 |
|
|
type *iteratedVariable;\
|
317 |
|
|
for(iteratedIndex=0; iteratedIndex < (dim); iteratedIndex++) {\
|
318 |
|
|
iteratedVariable = (table)[iteratedIndex];\
|
319 |
|
|
if (iteratedVariable != NULL) {command;}\
|
320 |
|
|
}\
|
321 |
|
|
}
|
322 |
|
|
|
323 |
|
|
|
324 |
|
|
/* ---------------------------------------------------------------------------- */
|
325 |
|
|
/* ------------------------- DYNAMIC DATA STRUCTURES -------------------------- */
|
326 |
|
|
/* ---------------------------------------------------------------------------- */
|
327 |
|
|
|
328 |
|
|
/* ------------------------------------ lists (level 0) --------------------- */
|
329 |
|
|
|
330 |
|
|
#define SGLIB_LIST_ADD(type, list, elem, next) {\
|
331 |
|
|
(elem)->next = (list);\
|
332 |
|
|
(list) = (elem);\
|
333 |
|
|
}
|
334 |
|
|
|
335 |
|
|
#define SGLIB_LIST_CONCAT(type, first, second, next) {\
|
336 |
|
|
if ((first)==NULL) {\
|
337 |
|
|
(first) = (second);\
|
338 |
|
|
} else {\
|
339 |
|
|
type *_p_;\
|
340 |
|
|
for(_p_ = (first); _p_->next!=NULL; _p_=_p_->next) ;\
|
341 |
|
|
_p_->next = (second);\
|
342 |
|
|
}\
|
343 |
|
|
}
|
344 |
|
|
|
345 |
|
|
#define SGLIB_LIST_DELETE(type, list, elem, next) {\
|
346 |
|
|
type **_p_;\
|
347 |
|
|
for(_p_ = &(list); *_p_!=NULL && *_p_!=(elem); _p_= &(*_p_)->next) ;\
|
348 |
|
|
assert(*_p_!=NULL && "element is not member of the container, use DELETE_IF_MEMBER instead"!=NULL);\
|
349 |
|
|
*_p_ = (*_p_)->next;\
|
350 |
|
|
}
|
351 |
|
|
|
352 |
|
|
#define SGLIB_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, next, member) {\
|
353 |
|
|
type *_p_;\
|
354 |
|
|
for(_p_ = (list); _p_!=NULL && comparator(_p_, (elem)) != 0; _p_= _p_->next) ;\
|
355 |
|
|
(member) = _p_;\
|
356 |
|
|
if (_p_ == NULL) {\
|
357 |
|
|
SGLIB_LIST_ADD(type, list, elem, next);\
|
358 |
|
|
}\
|
359 |
|
|
}
|
360 |
|
|
|
361 |
|
|
#define SGLIB_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, next, member) {\
|
362 |
|
|
type **_p_;\
|
363 |
|
|
for(_p_ = &(list); *_p_!=NULL && comparator((*_p_), (elem)) != 0; _p_= &(*_p_)->next) ;\
|
364 |
|
|
(member) = *_p_;\
|
365 |
|
|
if (*_p_ != NULL) {\
|
366 |
|
|
*_p_ = (*_p_)->next;\
|
367 |
|
|
}\
|
368 |
|
|
}
|
369 |
|
|
|
370 |
|
|
#define SGLIB_LIST_IS_MEMBER(type, list, elem, next, result) {\
|
371 |
|
|
type *_p_;\
|
372 |
|
|
for(_p_ = (list); _p_!=NULL && _p_ != (elem); _p_= _p_->next) ;\
|
373 |
|
|
(result) = (_p_!=NULL);\
|
374 |
|
|
}
|
375 |
|
|
|
376 |
|
|
#define SGLIB_LIST_FIND_MEMBER(type, list, elem, comparator, next, member) {\
|
377 |
|
|
type *_p_;\
|
378 |
|
|
for(_p_ = (list); _p_!=NULL && comparator(_p_, (elem)) != 0; _p_= _p_->next) ;\
|
379 |
|
|
(member) = _p_;\
|
380 |
|
|
}
|
381 |
|
|
|
382 |
|
|
#define SGLIB_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, next, command) {\
|
383 |
|
|
type *_ne_;\
|
384 |
|
|
type *iteratedVariable;\
|
385 |
|
|
(iteratedVariable) = (list); \
|
386 |
|
|
while ((iteratedVariable)!=NULL) {\
|
387 |
|
|
_ne_ = (iteratedVariable)->next;\
|
388 |
|
|
{command;};\
|
389 |
|
|
(iteratedVariable) = _ne_;\
|
390 |
|
|
}\
|
391 |
|
|
}
|
392 |
|
|
|
393 |
|
|
#define SGLIB_LIST_LEN(type, list, next, result) {\
|
394 |
|
|
type *_ce_;\
|
395 |
|
|
(result) = 0;\
|
396 |
|
|
SGLIB_LIST_MAP_ON_ELEMENTS(type, list, _ce_, next, (result)++);\
|
397 |
|
|
}
|
398 |
|
|
|
399 |
|
|
#define SGLIB_LIST_REVERSE(type, list, next) {\
|
400 |
|
|
type *_list_,*_tmp_,*_res_;\
|
401 |
|
|
_list_ = (list);\
|
402 |
|
|
_res_ = NULL;\
|
403 |
|
|
while (_list_!=NULL) {\
|
404 |
|
|
_tmp_ = _list_->next; _list_->next = _res_;\
|
405 |
|
|
_res_ = _list_; _list_ = _tmp_;\
|
406 |
|
|
}\
|
407 |
|
|
(list) = _res_;\
|
408 |
|
|
}
|
409 |
|
|
|
410 |
|
|
#define SGLIB_LIST_SORT(type, list, comparator, next) {\
|
411 |
|
|
/* a non-recursive merge sort on lists */\
|
412 |
|
|
type *_r_;\
|
413 |
|
|
type *_a_, *_b_, *_todo_, *_t_, **_restail_;\
|
414 |
|
|
int _i_, _n_, _contFlag_;\
|
415 |
|
|
_r_ = (list);\
|
416 |
|
|
_contFlag_ = 1;\
|
417 |
|
|
for(_n_ = 1; _contFlag_; _n_ = _n_+_n_) {\
|
418 |
|
|
_todo_ = _r_; _r_ = NULL; _restail_ = &_r_; _contFlag_ =0;\
|
419 |
|
|
while (_todo_!=NULL) {\
|
420 |
|
|
_a_ = _todo_;\
|
421 |
|
|
for(_i_ = 1, _t_ = _a_; _i_ < _n_ && _t_!=NULL; _i_++, _t_ = _t_->next) ;\
|
422 |
|
|
if (_t_ ==NULL) {\
|
423 |
|
|
*_restail_ = _a_;\
|
424 |
|
|
break;\
|
425 |
|
|
}\
|
426 |
|
|
_b_ = _t_->next; _t_->next=NULL;\
|
427 |
|
|
for(_i_ =1, _t_ = _b_; _i_<_n_ && _t_!=NULL; _i_++, _t_ = _t_->next) ;\
|
428 |
|
|
if (_t_ ==NULL) {\
|
429 |
|
|
_todo_ =NULL;\
|
430 |
|
|
} else {\
|
431 |
|
|
_todo_ = _t_->next; _t_->next=NULL;\
|
432 |
|
|
}\
|
433 |
|
|
/* merge */\
|
434 |
|
|
while (_a_!=NULL && _b_!=NULL) {\
|
435 |
|
|
if (comparator(_a_, _b_) < 0) {\
|
436 |
|
|
*_restail_ = _a_; _restail_ = &(_a_->next); _a_ = _a_->next;\
|
437 |
|
|
} else {\
|
438 |
|
|
*_restail_ = _b_; _restail_ = &(_b_->next); _b_ = _b_->next;\
|
439 |
|
|
}\
|
440 |
|
|
}\
|
441 |
|
|
if (_a_!=NULL) *_restail_ = _a_;\
|
442 |
|
|
else *_restail_ = _b_;\
|
443 |
|
|
while (*_restail_!=NULL) _restail_ = &((*_restail_)->next);\
|
444 |
|
|
_contFlag_ =1;\
|
445 |
|
|
}\
|
446 |
|
|
}\
|
447 |
|
|
(list) = _r_;\
|
448 |
|
|
}
|
449 |
|
|
|
450 |
|
|
/* --------------------------------- sorted list (level 0) --------------------- */
|
451 |
|
|
/*
|
452 |
|
|
All operations suppose that the list is sorted and they preserve
|
453 |
|
|
this property.
|
454 |
|
|
*/
|
455 |
|
|
|
456 |
|
|
|
457 |
|
|
#define SGLIB_SORTED_LIST_ADD(type, list, elem, comparator, next) {\
|
458 |
|
|
type **_e_;\
|
459 |
|
|
int _cmpres_;\
|
460 |
|
|
SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, _cmpres_, _e_);\
|
461 |
|
|
(elem)->next = *_e_;\
|
462 |
|
|
*_e_ = (elem);\
|
463 |
|
|
}
|
464 |
|
|
|
465 |
|
|
#define SGLIB_SORTED_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, next, member) {\
|
466 |
|
|
type **_e_;\
|
467 |
|
|
int _cmp_res_;\
|
468 |
|
|
SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, _cmp_res_, _e_);\
|
469 |
|
|
if (_cmp_res_ != 0) {\
|
470 |
|
|
(elem)->next = *_e_;\
|
471 |
|
|
*_e_ = (elem);\
|
472 |
|
|
(member) = NULL;\
|
473 |
|
|
} else {\
|
474 |
|
|
(member) = *_e_;\
|
475 |
|
|
}\
|
476 |
|
|
}
|
477 |
|
|
|
478 |
|
|
#define SGLIB_SORTED_LIST_DELETE(type, list, elem, next) {\
|
479 |
|
|
SGLIB_LIST_DELETE(type, list, elem, next);\
|
480 |
|
|
}
|
481 |
|
|
|
482 |
|
|
#define SGLIB_SORTED_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, next, member) {\
|
483 |
|
|
type **_e_;\
|
484 |
|
|
int _cmp_res_;\
|
485 |
|
|
SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, _cmp_res_, _e_);\
|
486 |
|
|
if (_cmp_res_ == 0) {\
|
487 |
|
|
(member) = *_e_;\
|
488 |
|
|
*_e_ = (*_e_)->next;\
|
489 |
|
|
} else {\
|
490 |
|
|
(member) = NULL;\
|
491 |
|
|
}\
|
492 |
|
|
}
|
493 |
|
|
|
494 |
|
|
#define SGLIB_SORTED_LIST_FIND_MEMBER(type, list, elem, comparator, next, member) {\
|
495 |
|
|
type *_p_;\
|
496 |
|
|
int _cmpres_;\
|
497 |
|
|
for(_p_ = (list); _p_!=NULL && (_cmpres_=comparator(_p_, (elem))) < 0; _p_=_p_->next) ;\
|
498 |
|
|
if (_cmpres_ != 0) (member) = NULL;\
|
499 |
|
|
else (member) = _p_;\
|
500 |
|
|
}
|
501 |
|
|
|
502 |
|
|
#define SGLIB_SORTED_LIST_IS_MEMBER(type, list, elem, comparator, next, result) {\
|
503 |
|
|
type *_p_;\
|
504 |
|
|
int _cmpres_;\
|
505 |
|
|
for(_p_ = (list); _p_!=NULL && (_cmpres_=comparator(_p_, (elem))) < 0; _p_=_p_->next) ;\
|
506 |
|
|
while (_p_ != NULL && _p_ != (elem) && (_cmpres_ = comparator(_p_, (elem))) == 0) _p_=_p_->next;\
|
507 |
|
|
(result) = (_p_ == (elem));\
|
508 |
|
|
}
|
509 |
|
|
|
510 |
|
|
#define SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, comparator_result, member_ptr) {\
|
511 |
|
|
for((member_ptr) = &(list); \
|
512 |
|
|
*(member_ptr)!=NULL && ((comparator_result)=comparator((*member_ptr), (elem))) < 0; \
|
513 |
|
|
(member_ptr) = &(*(member_ptr))->next) ;\
|
514 |
|
|
if (*(member_ptr) == NULL) (comparator_result) = -1;\
|
515 |
|
|
}
|
516 |
|
|
|
517 |
|
|
#define SGLIB_SORTED_LIST_LEN(type, list, next, result) {\
|
518 |
|
|
SGLIB_LIST_LEN(type, list, next, result);\
|
519 |
|
|
}
|
520 |
|
|
|
521 |
|
|
#define SGLIB_SORTED_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, next, command) {\
|
522 |
|
|
SGLIB_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, next, command);\
|
523 |
|
|
}
|
524 |
|
|
|
525 |
|
|
|
526 |
|
|
/* ------------------------------- double linked list (level 0) ------------------------- */
|
527 |
|
|
/*
|
528 |
|
|
Lists with back pointer to previous element. Those lists implements deletion
|
529 |
|
|
of an element in a constant time.
|
530 |
|
|
*/
|
531 |
|
|
|
532 |
|
|
#define SGLIB___DL_LIST_CREATE_SINGLETON(type, list, elem, previous, next) {\
|
533 |
|
|
(list) = (elem);\
|
534 |
|
|
(list)->next = (list)->previous = NULL;\
|
535 |
|
|
}
|
536 |
|
|
|
537 |
|
|
#define SGLIB_DL_LIST_ADD_AFTER(type, place, elem, previous, next) {\
|
538 |
|
|
if ((place) == NULL) {\
|
539 |
|
|
SGLIB___DL_LIST_CREATE_SINGLETON(type, place, elem, previous, next);\
|
540 |
|
|
} else {\
|
541 |
|
|
(elem)->next = (place)->next;\
|
542 |
|
|
(elem)->previous = (place);\
|
543 |
|
|
(place)->next = (elem);\
|
544 |
|
|
if ((elem)->next != NULL) (elem)->next->previous = (elem);\
|
545 |
|
|
}\
|
546 |
|
|
}
|
547 |
|
|
|
548 |
|
|
#define SGLIB_DL_LIST_ADD_BEFORE(type, place, elem, previous, next) {\
|
549 |
|
|
if ((place) == NULL) {\
|
550 |
|
|
SGLIB___DL_LIST_CREATE_SINGLETON(type, place, elem, previous, next);\
|
551 |
|
|
} else {\
|
552 |
|
|
(elem)->next = (place);\
|
553 |
|
|
(elem)->previous = (place)->previous;\
|
554 |
|
|
(place)->previous = (elem);\
|
555 |
|
|
if ((elem)->previous != NULL) (elem)->previous->next = (elem);\
|
556 |
|
|
}\
|
557 |
|
|
}
|
558 |
|
|
|
559 |
|
|
#define SGLIB_DL_LIST_ADD(type, list, elem, previous, next) {\
|
560 |
|
|
SGLIB_DL_LIST_ADD_BEFORE(type, list, elem, previous, next)\
|
561 |
|
|
}
|
562 |
|
|
|
563 |
|
|
#define SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, the_add_operation) {\
|
564 |
|
|
type *_dlp_;\
|
565 |
|
|
for(_dlp_ = (list); _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->previous) ;\
|
566 |
|
|
if (_dlp_ == NULL && (list) != NULL) {\
|
567 |
|
|
for(_dlp_ = (list)->next; _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->next) ;\
|
568 |
|
|
}\
|
569 |
|
|
(member) = _dlp_;\
|
570 |
|
|
if (_dlp_ == NULL) {\
|
571 |
|
|
the_add_operation(type, list, elem, previous, next);\
|
572 |
|
|
}\
|
573 |
|
|
}
|
574 |
|
|
|
575 |
|
|
#define SGLIB_DL_LIST_ADD_BEFORE_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
576 |
|
|
SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, SGLIB_DL_LIST_ADD_BEFORE);\
|
577 |
|
|
}
|
578 |
|
|
|
579 |
|
|
#define SGLIB_DL_LIST_ADD_AFTER_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
580 |
|
|
SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, SGLIB_DL_LIST_ADD_AFTER);\
|
581 |
|
|
}
|
582 |
|
|
|
583 |
|
|
#define SGLIB_DL_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
584 |
|
|
SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, SGLIB_DL_LIST_ADD);\
|
585 |
|
|
}
|
586 |
|
|
|
587 |
|
|
#define SGLIB_DL_LIST_CONCAT(type, first, second, previous, next) {\
|
588 |
|
|
if ((first)==NULL) {\
|
589 |
|
|
(first) = (second);\
|
590 |
|
|
} else {\
|
591 |
|
|
type *_dlp_;\
|
592 |
|
|
for(_dlp_ = (first); _dlp_->next!=NULL; _dlp_=_dlp_->next) ;\
|
593 |
|
|
SGLIB_DL_LIST_ADD_AFTER(type, _dlp_, second, previous, next);\
|
594 |
|
|
}\
|
595 |
|
|
}
|
596 |
|
|
|
597 |
|
|
#define SGLIB_DL_LIST_DELETE(type, list, elem, previous, next) {\
|
598 |
|
|
type *_l_;\
|
599 |
|
|
_l_ = (list);\
|
600 |
|
|
if (_l_ == (elem)) {\
|
601 |
|
|
if ((elem)->previous != NULL) _l_ = (elem)->previous;\
|
602 |
|
|
else _l_ = (elem)->next;\
|
603 |
|
|
}\
|
604 |
|
|
if ((elem)->next != NULL) (elem)->next->previous = (elem)->previous;\
|
605 |
|
|
if ((elem)->previous != NULL) (elem)->previous->next = (elem)->next;\
|
606 |
|
|
(list) = _l_;\
|
607 |
|
|
}
|
608 |
|
|
|
609 |
|
|
#define SGLIB_DL_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
610 |
|
|
type *_dlp_;\
|
611 |
|
|
for(_dlp_ = (list); _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->previous) ;\
|
612 |
|
|
if (_dlp_ == NULL && (list) != NULL) {\
|
613 |
|
|
for(_dlp_ = (list)->next; _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->next) ;\
|
614 |
|
|
}\
|
615 |
|
|
(member) = _dlp_;\
|
616 |
|
|
if (_dlp_ != NULL) {\
|
617 |
|
|
SGLIB_DL_LIST_DELETE(type, list, _dlp_, previous, next);\
|
618 |
|
|
}\
|
619 |
|
|
}
|
620 |
|
|
|
621 |
|
|
#define SGLIB_DL_LIST_IS_MEMBER(type, list, elem, previous, next, result) {\
|
622 |
|
|
type *_dlp_;\
|
623 |
|
|
SGLIB_LIST_IS_MEMBER(type, list, elem, previous, result);\
|
624 |
|
|
if (result == 0 && (list) != NULL) {\
|
625 |
|
|
_dlp_ = (list)->next;\
|
626 |
|
|
SGLIB_LIST_IS_MEMBER(type, _dlp_, elem, next, result);\
|
627 |
|
|
}\
|
628 |
|
|
}
|
629 |
|
|
|
630 |
|
|
#define SGLIB_DL_LIST_FIND_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
631 |
|
|
type *_dlp_;\
|
632 |
|
|
SGLIB_LIST_FIND_MEMBER(type, list, elem, comparator, previous, member);\
|
633 |
|
|
if ((member) == NULL && (list) != NULL) {\
|
634 |
|
|
_dlp_ = (list)->next;\
|
635 |
|
|
SGLIB_LIST_FIND_MEMBER(type, _dlp_, elem, comparator, next, member);\
|
636 |
|
|
}\
|
637 |
|
|
}
|
638 |
|
|
|
639 |
|
|
#define SGLIB_DL_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, previous, next, command) {\
|
640 |
|
|
type *_dl_;\
|
641 |
|
|
type *iteratedVariable;\
|
642 |
|
|
if ((list)!=NULL) {\
|
643 |
|
|
_dl_ = (list)->next;\
|
644 |
|
|
SGLIB_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, previous, command);\
|
645 |
|
|
SGLIB_LIST_MAP_ON_ELEMENTS(type, _dl_, iteratedVariable, next, command);\
|
646 |
|
|
}\
|
647 |
|
|
}
|
648 |
|
|
|
649 |
|
|
#define SGLIB_DL_LIST_SORT(type, list, comparator, previous, next) {\
|
650 |
|
|
type *_dll_, *_dlp_, *_dlt_;\
|
651 |
|
|
_dll_ = (list);\
|
652 |
|
|
if (_dll_ != NULL) {\
|
653 |
|
|
for(; _dll_->previous!=NULL; _dll_=_dll_->previous) ;\
|
654 |
|
|
SGLIB_LIST_SORT(type, _dll_, comparator, next);\
|
655 |
|
|
SGLIB___DL_LIST_CREATE_FROM_LIST(type, _dll_, previous, next);\
|
656 |
|
|
(list) = _dll_;\
|
657 |
|
|
}\
|
658 |
|
|
}
|
659 |
|
|
|
660 |
|
|
#define SGLIB_DL_LIST_GET_FIRST(type, list, previous, next, result) {\
|
661 |
|
|
type *_dll_;\
|
662 |
|
|
_dll_ = (list);\
|
663 |
|
|
if (_dll_ != NULL) {\
|
664 |
|
|
for(; _dll_->previous!=NULL; _dll_=_dll_->previous) ;\
|
665 |
|
|
}\
|
666 |
|
|
(result) = _dll_;\
|
667 |
|
|
}
|
668 |
|
|
|
669 |
|
|
#define SGLIB_DL_LIST_GET_LAST(type, list, previous, next, result) {\
|
670 |
|
|
type *_dll_;\
|
671 |
|
|
_dll_ = (list);\
|
672 |
|
|
if (_dll_ != NULL) {\
|
673 |
|
|
for(; _dll_->next!=NULL; _dll_=_dll_->next) ;\
|
674 |
|
|
}\
|
675 |
|
|
(result) = _dll_;\
|
676 |
|
|
}
|
677 |
|
|
|
678 |
|
|
#define SGLIB_DL_LIST_LEN(type, list, previous, next, result) {\
|
679 |
|
|
type *_dl_;\
|
680 |
|
|
int _r1_, _r2_;\
|
681 |
|
|
if ((list)==NULL) {\
|
682 |
|
|
(result) = 0;\
|
683 |
|
|
} else {\
|
684 |
|
|
SGLIB_LIST_LEN(type, list, previous, _r1_);\
|
685 |
|
|
_dl_ = (list)->next;\
|
686 |
|
|
SGLIB_LIST_LEN(type, _dl_, next, _r2_);\
|
687 |
|
|
(result) = _r1_ + _r2_;\
|
688 |
|
|
}\
|
689 |
|
|
}
|
690 |
|
|
|
691 |
|
|
#define SGLIB_DL_LIST_REVERSE(type, list, previous, next) {\
|
692 |
|
|
type *_list_,*_nlist_,*_dlp_,*_dln_;\
|
693 |
|
|
_list_ = (list);\
|
694 |
|
|
if (_list_!=NULL) {\
|
695 |
|
|
_nlist_ = _list_->next;\
|
696 |
|
|
while (_list_!=NULL) {\
|
697 |
|
|
_dln_ = _list_->next; \
|
698 |
|
|
_dlp_ = _list_->previous; \
|
699 |
|
|
_list_->next = _dlp_;\
|
700 |
|
|
_list_->previous = _dln_;\
|
701 |
|
|
_list_ = _dlp_;\
|
702 |
|
|
}\
|
703 |
|
|
while (_nlist_!=NULL) {\
|
704 |
|
|
_dln_ = _nlist_->next; \
|
705 |
|
|
_dlp_ = _nlist_->previous; \
|
706 |
|
|
_nlist_->next = _dlp_;\
|
707 |
|
|
_nlist_->previous = _dln_;\
|
708 |
|
|
_nlist_ = _dln_;\
|
709 |
|
|
}\
|
710 |
|
|
}\
|
711 |
|
|
}
|
712 |
|
|
|
713 |
|
|
#define SGLIB___DL_LIST_CREATE_FROM_LIST(type, list, previous, next) {\
|
714 |
|
|
type *_dlp_, *_dlt_;\
|
715 |
|
|
_dlp_ = NULL;\
|
716 |
|
|
for(_dlt_ = (list); _dlt_!=NULL; _dlt_ = _dlt_->next) {\
|
717 |
|
|
_dlt_->previous = _dlp_;\
|
718 |
|
|
_dlp_ = _dlt_;\
|
719 |
|
|
}\
|
720 |
|
|
}
|
721 |
|
|
|
722 |
|
|
|
723 |
|
|
/* ------------------------------- binary tree traversal (level 0) -------------------- */
|
724 |
|
|
|
725 |
|
|
|
726 |
|
|
#define SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, iteratedVariable, order, left, right, command) {\
|
727 |
|
|
/* this is non-recursive implementation of tree traversal */\
|
728 |
|
|
/* it maintains the path to the current node in the array '_path_' */\
|
729 |
|
|
/* the _path_[0] contains the root of the tree; */\
|
730 |
|
|
/* the _path_[_pathi_] contains the _current_element_ */\
|
731 |
|
|
/* the macro does not use the _current_element_ after execution of command */\
|
732 |
|
|
/* command can destroy it, it can free the element for example */\
|
733 |
|
|
type *_path_[SGLIB_MAX_TREE_DEEP];\
|
734 |
|
|
type *_right_[SGLIB_MAX_TREE_DEEP];\
|
735 |
|
|
char _pass_[SGLIB_MAX_TREE_DEEP];\
|
736 |
|
|
type *_cn_;\
|
737 |
|
|
int _pathi_;\
|
738 |
|
|
type *iteratedVariable;\
|
739 |
|
|
_cn_ = (tree);\
|
740 |
|
|
_pathi_ = 0;\
|
741 |
|
|
while (_cn_!=NULL) {\
|
742 |
|
|
/* push down to leftmost innermost element */\
|
743 |
|
|
while(_cn_!=NULL) {\
|
744 |
|
|
_path_[_pathi_] = _cn_;\
|
745 |
|
|
_right_[_pathi_] = _cn_->right;\
|
746 |
|
|
_pass_[_pathi_] = 0;\
|
747 |
|
|
_cn_ = _cn_->left;\
|
748 |
|
|
if (order == 0) {\
|
749 |
|
|
iteratedVariable = _path_[_pathi_];\
|
750 |
|
|
{command;}\
|
751 |
|
|
}\
|
752 |
|
|
_pathi_ ++;\
|
753 |
|
|
if (_pathi_ >= SGLIB_MAX_TREE_DEEP) assert(0 && "the binary_tree is too deep");\
|
754 |
|
|
}\
|
755 |
|
|
do {\
|
756 |
|
|
_pathi_ --;\
|
757 |
|
|
if ((order==1 && _pass_[_pathi_] == 0)\
|
758 |
|
|
|| (order == 2 && (_pass_[_pathi_] == 1 || _right_[_pathi_]==NULL))) {\
|
759 |
|
|
iteratedVariable = _path_[_pathi_];\
|
760 |
|
|
{command;}\
|
761 |
|
|
}\
|
762 |
|
|
_pass_[_pathi_] ++;\
|
763 |
|
|
} while (_pathi_>0 && _right_[_pathi_]==NULL) ;\
|
764 |
|
|
_cn_ = _right_[_pathi_];\
|
765 |
|
|
_right_[_pathi_] = NULL;\
|
766 |
|
|
_pathi_ ++;\
|
767 |
|
|
}\
|
768 |
|
|
}
|
769 |
|
|
|
770 |
|
|
#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, left, right, command) {\
|
771 |
|
|
SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 1, left, right, command);\
|
772 |
|
|
}
|
773 |
|
|
|
774 |
|
|
#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS_PREORDER(type, tree, _current_element_, left, right, command) {\
|
775 |
|
|
SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 0, left, right, command);\
|
776 |
|
|
}
|
777 |
|
|
|
778 |
|
|
#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS_POSTORDER(type, tree, _current_element_, left, right, command) {\
|
779 |
|
|
SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 2, left, right, command);\
|
780 |
|
|
}
|
781 |
|
|
|
782 |
|
|
#define SGLIB___BIN_TREE_FIND_MEMBER(type, tree, elem, left, right, comparator, res) {\
|
783 |
|
|
type *_s_;\
|
784 |
|
|
int _c_;\
|
785 |
|
|
_s_ = (tree);\
|
786 |
|
|
while (_s_!=NULL) {\
|
787 |
|
|
_c_ = comparator((elem), _s_);\
|
788 |
|
|
if (_c_ < 0) _s_ = _s_->left;\
|
789 |
|
|
else if (_c_ > 0) _s_ = _s_->right;\
|
790 |
|
|
else break;\
|
791 |
|
|
}\
|
792 |
|
|
(res) = _s_;\
|
793 |
|
|
}
|
794 |
|
|
|
795 |
|
|
/* ---------------------------------------------------------------------------- */
|
796 |
|
|
/* ---------------------------------------------------------------------------- */
|
797 |
|
|
/* - LEVEL - 1 INTERFACE - */
|
798 |
|
|
/* ---------------------------------------------------------------------------- */
|
799 |
|
|
/* ---------------------------------------------------------------------------- */
|
800 |
|
|
|
801 |
|
|
|
802 |
|
|
|
803 |
|
|
/* ---------------------------------------------------------------------------- */
|
804 |
|
|
/* ------------------------------ STATIC ARRAYS ------------------------------- */
|
805 |
|
|
/* ---------------------------------------------------------------------------- */
|
806 |
|
|
|
807 |
|
|
/* ----------------------------- array sorting (level 1) ---------------------- */
|
808 |
|
|
|
809 |
|
|
#define SGLIB_DEFINE_ARRAY_SORTING_PROTOTYPES(type, comparator) \
|
810 |
|
|
extern void sglib_##type##_array_quick_sort(type *a, int max);\
|
811 |
|
|
extern void sglib_##type##_array_heap_sort(type *a, int max);\
|
812 |
|
|
|
813 |
|
|
|
814 |
|
|
#define SGLIB_DEFINE_ARRAY_SORTING_FUNCTIONS(type, comparator) \
|
815 |
|
|
void sglib_##type##_array_quick_sort(type *a, int max) {\
|
816 |
|
|
SGLIB_ARRAY_SINGLE_QUICK_SORT(type, a, max, comparator);\
|
817 |
|
|
}\
|
818 |
|
|
void sglib_##type##_array_heap_sort(type *a, int max) {\
|
819 |
|
|
SGLIB_ARRAY_SINGLE_HEAP_SORT(type, a, max, comparator);\
|
820 |
|
|
}\
|
821 |
|
|
|
822 |
|
|
|
823 |
|
|
/* ----------------------------- array queue (level 1) ------------------- */
|
824 |
|
|
/* sglib's queue is stored in a fixed sized array */
|
825 |
|
|
/* queue_type MUST be a structure containing fields: */
|
826 |
|
|
/* afield is the array storing elem_type */
|
827 |
|
|
/* ifield is the index of the first element in the queue */
|
828 |
|
|
/* jfield is the index of the first free element after the queue */
|
829 |
|
|
/* dim is the size of the array afield */
|
830 |
|
|
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */
|
831 |
|
|
|
832 |
|
|
|
833 |
|
|
#define SGLIB_DEFINE_QUEUE_PROTOTYPES(queue_type, elem_type, afield, ifield, jfield, dim) \
|
834 |
|
|
extern void sglib_##queue_type##_init(queue_type *q); \
|
835 |
|
|
extern int sglib_##queue_type##_is_empty(queue_type *q); \
|
836 |
|
|
extern int sglib_##queue_type##_is_full(queue_type *q); \
|
837 |
|
|
extern elem_type sglib_##queue_type##_first_element(queue_type *q); \
|
838 |
|
|
extern elem_type *sglib_##queue_type##_first_element_ptr(queue_type *q); \
|
839 |
|
|
extern void sglib_##queue_type##_add_next(queue_type *q); \
|
840 |
|
|
extern void sglib_##queue_type##_add(queue_type *q, elem_type elem); \
|
841 |
|
|
extern void sglib_##queue_type##_delete_first(queue_type *q); \
|
842 |
|
|
extern void sglib_##queue_type##_delete(queue_type *q);
|
843 |
|
|
|
844 |
|
|
|
845 |
|
|
#define SGLIB_DEFINE_QUEUE_FUNCTIONS(queue_type, elem_type, afield, ifield, jfield, dim) \
|
846 |
|
|
void sglib_##queue_type##_init(queue_type *q) {\
|
847 |
|
|
SGLIB_QUEUE_INIT(elem_type, q->afield, q->ifield, q->jfield);\
|
848 |
|
|
}\
|
849 |
|
|
int sglib_##queue_type##_is_empty(queue_type *q) {\
|
850 |
|
|
return(SGLIB_QUEUE_IS_EMPTY(elem_type, q->afield, q->ifield, q->jfield));\
|
851 |
|
|
}\
|
852 |
|
|
int sglib_##queue_type##_is_full(queue_type *q) {\
|
853 |
|
|
return(SGLIB_QUEUE_IS_FULL(elem_type, q->afield, q->ifield, q->jfield));\
|
854 |
|
|
}\
|
855 |
|
|
elem_type sglib_##queue_type##_first_element(queue_type *q) {\
|
856 |
|
|
return(SGLIB_QUEUE_FIRST_ELEMENT(elem_type, q->afield, q->ifield, q->jfield));\
|
857 |
|
|
}\
|
858 |
|
|
elem_type *sglib_##queue_type##_first_element_ptr(queue_type *q) {\
|
859 |
|
|
return(& SGLIB_QUEUE_FIRST_ELEMENT(elem_type, q->afield, q->ifield, q->jfield));\
|
860 |
|
|
}\
|
861 |
|
|
void sglib_##queue_type##_add_next(queue_type *q) {\
|
862 |
|
|
SGLIB_QUEUE_ADD_NEXT(elem_type, q->afield, q->ifield, q->jfield, dim);\
|
863 |
|
|
}\
|
864 |
|
|
void sglib_##queue_type##_add(queue_type *q, elem_type elem) {\
|
865 |
|
|
SGLIB_QUEUE_ADD(elem_type, q->afield, elem, q->ifield, q->jfield, dim);\
|
866 |
|
|
}\
|
867 |
|
|
void sglib_##queue_type##_delete_first(queue_type *q) {\
|
868 |
|
|
SGLIB_QUEUE_DELETE_FIRST(elem_type, q->afield, q->ifield, q->jfield, dim);\
|
869 |
|
|
}\
|
870 |
|
|
void sglib_##queue_type##_delete(queue_type *q) {\
|
871 |
|
|
SGLIB_QUEUE_DELETE_FIRST(elem_type, q->afield, q->ifield, q->jfield, dim);\
|
872 |
|
|
}
|
873 |
|
|
|
874 |
|
|
|
875 |
|
|
/* ------------------------ array heap (level 1) ------------------------- */
|
876 |
|
|
/* sglib's heap is a priority queue implemented in a fixed sized array */
|
877 |
|
|
/* heap_type MUST be a structure containing fields: */
|
878 |
|
|
/* afield is the array of size dim storing elem_type */
|
879 |
|
|
/* ifield is the index of the first free element after the queue */
|
880 |
|
|
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */
|
881 |
|
|
|
882 |
|
|
|
883 |
|
|
#define SGLIB_DEFINE_HEAP_PROTOTYPES(heap_type, elem_type, afield, ifield, dim, comparator, elem_exchanger) \
|
884 |
|
|
extern void sglib_##heap_type##_init(heap_type *q); \
|
885 |
|
|
extern int sglib_##heap_type##_is_empty(heap_type *q); \
|
886 |
|
|
extern int sglib_##heap_type##_is_full(heap_type *q); \
|
887 |
|
|
extern elem_type sglib_##heap_type##_first_element(heap_type *q); \
|
888 |
|
|
extern elem_type *sglib_##heap_type##_first_element_ptr(heap_type *q); \
|
889 |
|
|
extern void sglib_##heap_type##_add_next(heap_type *q); \
|
890 |
|
|
extern void sglib_##heap_type##_add(heap_type *q, elem_type elem); \
|
891 |
|
|
extern void sglib_##heap_type##_delete_first(heap_type *q); \
|
892 |
|
|
extern void sglib_##heap_type##_delete(heap_type *q)
|
893 |
|
|
|
894 |
|
|
#define SGLIB_DEFINE_HEAP_FUNCTIONS(heap_type, elem_type, afield, ifield, dim, comparator, elem_exchanger) \
|
895 |
|
|
void sglib_##heap_type##_init(heap_type *q) {\
|
896 |
|
|
SGLIB_HEAP_INIT(elem_type, q->afield, q->ifield);\
|
897 |
|
|
}\
|
898 |
|
|
int sglib_##heap_type##_is_empty(heap_type *q) {\
|
899 |
|
|
return(SGLIB_HEAP_IS_EMPTY(elem_type, q->afield, q->ifield));\
|
900 |
|
|
}\
|
901 |
|
|
int sglib_##heap_type##_is_full(heap_type *q) {\
|
902 |
|
|
return(SGLIB_HEAP_IS_FULL(elem_type, q->afield, q->ifield));\
|
903 |
|
|
}\
|
904 |
|
|
elem_type sglib_##heap_type##_first_element(heap_type *q) {\
|
905 |
|
|
return(SGLIB_HEAP_FIRST_ELEMENT(elem_type, q->afield, q->ifield));\
|
906 |
|
|
}\
|
907 |
|
|
elem_type *sglib_##heap_type##_first_element_ptr(heap_type *q) {\
|
908 |
|
|
return(& SGLIB_HEAP_FIRST_ELEMENT(elem_type, q->afield, q->ifield));\
|
909 |
|
|
}\
|
910 |
|
|
void sglib_##heap_type##_add_next(heap_type *q) {\
|
911 |
|
|
SGLIB_HEAP_ADD_NEXT(elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger);\
|
912 |
|
|
}\
|
913 |
|
|
void sglib_##heap_type##_add(heap_type *q, elem_type elem) {\
|
914 |
|
|
SGLIB_HEAP_ADD(elem_type, q->afield, elem, q->ifield, dim, comparator, elem_exchanger);\
|
915 |
|
|
}\
|
916 |
|
|
void sglib_##heap_type##_delete_first(heap_type *q) {\
|
917 |
|
|
SGLIB_HEAP_DELETE_FIRST(elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger);\
|
918 |
|
|
}\
|
919 |
|
|
void sglib_##heap_type##_delete(heap_type *q) {\
|
920 |
|
|
SGLIB_HEAP_DELETE_FIRST(elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger);\
|
921 |
|
|
}
|
922 |
|
|
|
923 |
|
|
|
924 |
|
|
/* ------------------------ hashed table (level 1) ------------------------- */
|
925 |
|
|
/*
|
926 |
|
|
|
927 |
|
|
sglib's hash table is an array storing directly pointers to objects (not containers).
|
928 |
|
|
In this table there is a one-to-one mapping between 'objects' stored
|
929 |
|
|
in the table and indexes where they are placed. Each index is
|
930 |
|
|
pointing to exactly one 'object' and each 'object' stored in the
|
931 |
|
|
table occurs on exactly one index. Once an object is stored in the
|
932 |
|
|
table, it can be represented via its index.
|
933 |
|
|
|
934 |
|
|
type - is the type of elements
|
935 |
|
|
dim - is the size of the hash array
|
936 |
|
|
hash_function - is a hashing function mapping type* to unsigned
|
937 |
|
|
comparator - is a comparator on elements
|
938 |
|
|
|
939 |
|
|
!!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!!
|
940 |
|
|
*/
|
941 |
|
|
|
942 |
|
|
#define SGLIB_DEFINE_HASHED_TABLE_PROTOTYPES(type, dim, hash_function, comparator) \
|
943 |
|
|
struct sglib_hashed_##type##_iterator {\
|
944 |
|
|
int currentIndex;\
|
945 |
|
|
int (*subcomparator)(type *, type *);\
|
946 |
|
|
type *equalto;\
|
947 |
|
|
};\
|
948 |
|
|
extern void sglib_hashed_##type##_init(type *table[dim]);\
|
949 |
|
|
extern int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member);\
|
950 |
|
|
extern int sglib_hashed_##type##_is_member(type *table[dim], type *elem);\
|
951 |
|
|
extern type * sglib_hashed_##type##_find_member(type *table[dim], type *elem);\
|
952 |
|
|
extern type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]); \
|
953 |
|
|
extern type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto); \
|
954 |
|
|
extern type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it); \
|
955 |
|
|
extern type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it);
|
956 |
|
|
|
957 |
|
|
#define SGLIB_DEFINE_HASHED_TABLE_FUNCTIONS(type, dim, hash_function, comparator) \
|
958 |
|
|
struct sglib_hashed_##type##_iterator {\
|
959 |
|
|
int currentIndex;\
|
960 |
|
|
type **table;\
|
961 |
|
|
int (*subcomparator)(type *, type *);\
|
962 |
|
|
type *equalto;\
|
963 |
|
|
};\
|
964 |
|
|
void sglib_hashed_##type##_init(type *table[dim]) {\
|
965 |
|
|
SGLIB_HASH_TAB_INIT(type, table, dim);\
|
966 |
|
|
}\
|
967 |
|
|
int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member) {\
|
968 |
|
|
SGLIB_HASH_TAB_ADD_IF_NOT_MEMBER(type, table, dim, elem, hash_function, comparator, *member);\
|
969 |
|
|
}\
|
970 |
|
|
int sglib_hashed_##type##_is_member(type *table[dim], type *elem) {\
|
971 |
|
|
int ind;\
|
972 |
|
|
SGLIB_HASH_TAB_IS_MEMBER(type, table, dim, elem, hash_function, ind);\
|
973 |
|
|
return(ind != -1);\
|
974 |
|
|
}\
|
975 |
|
|
type * sglib_hashed_##type##_find_member(type *table[dim], type *elem) {\
|
976 |
|
|
type *mmb;\
|
977 |
|
|
int ind;\
|
978 |
|
|
SGLIB_HASH_TAB_FIND_MEMBER(type, table, dim, elem, hash_function, comparator, ind, mmb);\
|
979 |
|
|
return(mmb);\
|
980 |
|
|
}\
|
981 |
|
|
type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto) {\
|
982 |
|
|
int i;\
|
983 |
|
|
it->table = table;\
|
984 |
|
|
it->subcomparator = subcomparator;\
|
985 |
|
|
it->equalto = equalto;\
|
986 |
|
|
for(i=0; i<(dim) && table[i]==NULL; i++) ;\
|
987 |
|
|
it->currentIndex = i;\
|
988 |
|
|
if (i<(dim)) return(table[i]);\
|
989 |
|
|
return(NULL);\
|
990 |
|
|
}\
|
991 |
|
|
type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]) {\
|
992 |
|
|
sglib_hashed_##type##_it_init_on_equal(it, table, NULL, NULL);\
|
993 |
|
|
}\
|
994 |
|
|
type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it) {\
|
995 |
|
|
return(table[it->currentIndex]);\
|
996 |
|
|
}\
|
997 |
|
|
type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it) {\
|
998 |
|
|
i=it->currentIndex;\
|
999 |
|
|
if (i<(dim)) {\
|
1000 |
|
|
for(i++; i<(dim) && table[i]==NULL; i++) ;\
|
1001 |
|
|
}\
|
1002 |
|
|
it->currentIndex = i;\
|
1003 |
|
|
if (i<(dim)) return(table[i]);\
|
1004 |
|
|
return(NULL);\
|
1005 |
|
|
}
|
1006 |
|
|
|
1007 |
|
|
|
1008 |
|
|
/* ------------------- hashed container (only for level 1) -------------------- */
|
1009 |
|
|
/*
|
1010 |
|
|
hashed container is a table of given fixed size containing another
|
1011 |
|
|
(dynamic) base container in each cell. Once an object should be
|
1012 |
|
|
inserted into the hashed container, a hash function is used to
|
1013 |
|
|
determine the cell where the object belongs and the object is
|
1014 |
|
|
inserted into the base container stored in this cell. Usually the
|
1015 |
|
|
base container is simply a list or a sorted list, but it can be a
|
1016 |
|
|
red-black tree as well.
|
1017 |
|
|
|
1018 |
|
|
parameters:
|
1019 |
|
|
type - the type of the container stored in each cell.
|
1020 |
|
|
dim - the size of the hashed array
|
1021 |
|
|
hash_function - the hashing function hashing 'type *' to unsigned.
|
1022 |
|
|
|
1023 |
|
|
*/
|
1024 |
|
|
|
1025 |
|
|
#define SGLIB_DEFINE_HASHED_CONTAINER_PROTOTYPES(type, dim, hash_function) \
|
1026 |
|
|
struct sglib_hashed_##type##_iterator {\
|
1027 |
|
|
struct sglib_##type##_iterator containerIt;\
|
1028 |
|
|
type **table;\
|
1029 |
|
|
int currentIndex;\
|
1030 |
|
|
int (*subcomparator)(type *, type *);\
|
1031 |
|
|
type *equalto;\
|
1032 |
|
|
};\
|
1033 |
|
|
extern void sglib_hashed_##type##_init(type *table[dim]);\
|
1034 |
|
|
extern void sglib_hashed_##type##_add(type *table[dim], type *elem);\
|
1035 |
|
|
extern int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member);\
|
1036 |
|
|
extern void sglib_hashed_##type##_delete(type *table[dim], type *elem);\
|
1037 |
|
|
extern int sglib_hashed_##type##_delete_if_member(type *table[dim], type *elem, type **memb);\
|
1038 |
|
|
extern int sglib_hashed_##type##_is_member(type *table[dim], type *elem);\
|
1039 |
|
|
extern type * sglib_hashed_##type##_find_member(type *table[dim], type *elem);\
|
1040 |
|
|
extern type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]); \
|
1041 |
|
|
extern type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto); \
|
1042 |
|
|
extern type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it); \
|
1043 |
|
|
extern type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it);
|
1044 |
|
|
|
1045 |
|
|
#define SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS(type, dim, hash_function) \
|
1046 |
|
|
/*extern unsigned hash_function(type *elem);*/\
|
1047 |
|
|
void sglib_hashed_##type##_init(type *table[dim]) {\
|
1048 |
|
|
unsigned i;\
|
1049 |
|
|
for(i=0; i<(dim); i++) table[i] = NULL;\
|
1050 |
|
|
}\
|
1051 |
|
|
void sglib_hashed_##type##_add(type *table[dim], type *elem) {\
|
1052 |
|
|
unsigned i;\
|
1053 |
|
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
1054 |
|
|
sglib_##type##_add(&(table)[i], elem);\
|
1055 |
|
|
}\
|
1056 |
|
|
int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member) {\
|
1057 |
|
|
unsigned i;\
|
1058 |
|
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
1059 |
|
|
return(sglib_##type##_add_if_not_member(&(table)[i], elem, member));\
|
1060 |
|
|
}\
|
1061 |
|
|
void sglib_hashed_##type##_delete(type *table[dim], type *elem) {\
|
1062 |
|
|
unsigned i;\
|
1063 |
|
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
1064 |
|
|
sglib_##type##_delete(&(table)[i], elem);\
|
1065 |
|
|
}\
|
1066 |
|
|
int sglib_hashed_##type##_delete_if_member(type *table[dim], type *elem, type **memb) {\
|
1067 |
|
|
unsigned i;\
|
1068 |
|
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
1069 |
|
|
return(sglib_##type##_delete_if_member(&(table)[i], elem, memb));\
|
1070 |
|
|
}\
|
1071 |
|
|
int sglib_hashed_##type##_is_member(type *table[dim], type *elem) {\
|
1072 |
|
|
unsigned i;\
|
1073 |
|
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
1074 |
|
|
return(sglib_##type##_is_member((table)[i], elem));\
|
1075 |
|
|
}\
|
1076 |
|
|
type * sglib_hashed_##type##_find_member(type *table[dim], type *elem) {\
|
1077 |
|
|
unsigned i;\
|
1078 |
|
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
1079 |
|
|
return(sglib_##type##_find_member((table)[i], elem));\
|
1080 |
|
|
}\
|
1081 |
|
|
type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto) {\
|
1082 |
|
|
type *e;\
|
1083 |
|
|
it->table = table;\
|
1084 |
|
|
it->currentIndex = 0;\
|
1085 |
|
|
it->subcomparator = subcomparator;\
|
1086 |
|
|
it->equalto = equalto;\
|
1087 |
|
|
e = sglib_##type##_it_init_on_equal(&it->containerIt, table[it->currentIndex], it->subcomparator, it->equalto);\
|
1088 |
|
|
if (e==NULL) e = sglib_hashed_##type##_it_next(it);\
|
1089 |
|
|
return(e);\
|
1090 |
|
|
}\
|
1091 |
|
|
type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]) {\
|
1092 |
|
|
return(sglib_hashed_##type##_it_init_on_equal(it, table, NULL, NULL));\
|
1093 |
|
|
}\
|
1094 |
|
|
type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it) {\
|
1095 |
|
|
return(sglib_##type##_it_current(&it->containerIt));\
|
1096 |
|
|
}\
|
1097 |
|
|
type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it) {\
|
1098 |
|
|
type *e;\
|
1099 |
|
|
e = sglib_##type##_it_next(&it->containerIt);\
|
1100 |
|
|
while (e==NULL && (++(it->currentIndex))<(dim)) {\
|
1101 |
|
|
e = sglib_##type##_it_init_on_equal(&it->containerIt, it->table[it->currentIndex], it->subcomparator, it->equalto);\
|
1102 |
|
|
}\
|
1103 |
|
|
return(e);\
|
1104 |
|
|
}
|
1105 |
|
|
|
1106 |
|
|
|
1107 |
|
|
|
1108 |
|
|
/* ---------------------------------------------------------------------------- */
|
1109 |
|
|
/* ------------------------- DYNAMIC DATA STRUCTURES -------------------------- */
|
1110 |
|
|
/* ---------------------------------------------------------------------------- */
|
1111 |
|
|
|
1112 |
|
|
|
1113 |
|
|
|
1114 |
|
|
/* ------------------------------------ list (level 1) -------------------------------- */
|
1115 |
|
|
|
1116 |
|
|
#define SGLIB_DEFINE_LIST_PROTOTYPES(type, comparator, next) \
|
1117 |
|
|
struct sglib_##type##_iterator {\
|
1118 |
|
|
type *currentelem;\
|
1119 |
|
|
type *nextelem;\
|
1120 |
|
|
int (*subcomparator)(type *, type *);\
|
1121 |
|
|
type *equalto;\
|
1122 |
|
|
};\
|
1123 |
|
|
extern void sglib_##type##_add(type **list, type *elem);\
|
1124 |
|
|
extern int sglib_##type##_add_if_not_member(type **list, type *elem, type **member);\
|
1125 |
|
|
extern void sglib_##type##_concat(type **first, type *second);\
|
1126 |
|
|
extern void sglib_##type##_delete(type **list, type *elem);\
|
1127 |
|
|
extern int sglib_##type##_delete_if_member(type **list, type *elem, type **member);\
|
1128 |
|
|
extern int sglib_##type##_is_member(type *list, type *elem);\
|
1129 |
|
|
extern type *sglib_##type##_find_member(type *list, type *elem);\
|
1130 |
|
|
extern void sglib_##type##_sort(type **list);\
|
1131 |
|
|
extern int sglib_##type##_len(type *list);\
|
1132 |
|
|
extern void sglib_##type##_reverse(type **list);\
|
1133 |
|
|
extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list); \
|
1134 |
|
|
extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto); \
|
1135 |
|
|
extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \
|
1136 |
|
|
extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it);
|
1137 |
|
|
|
1138 |
|
|
|
1139 |
|
|
#define SGLIB_DEFINE_LIST_FUNCTIONS(type, comparator, next) \
|
1140 |
|
|
int sglib_##type##_is_member(type *list, type *elem) {\
|
1141 |
|
|
int result;\
|
1142 |
|
|
SGLIB_LIST_IS_MEMBER(type, list, elem, next, result);\
|
1143 |
|
|
return(result);\
|
1144 |
|
|
}\
|
1145 |
|
|
type *sglib_##type##_find_member(type *list, type *elem) {\
|
1146 |
|
|
type *result;\
|
1147 |
|
|
SGLIB_LIST_FIND_MEMBER(type, list, elem, comparator, next, result);\
|
1148 |
|
|
return(result);\
|
1149 |
|
|
}\
|
1150 |
|
|
int sglib_##type##_add_if_not_member(type **list, type *elem, type **member) {\
|
1151 |
|
|
SGLIB_LIST_ADD_IF_NOT_MEMBER(type, *list, elem, comparator, next, *member);\
|
1152 |
|
|
return(*member==NULL);\
|
1153 |
|
|
}\
|
1154 |
|
|
void sglib_##type##_add(type **list, type *elem) {\
|
1155 |
|
|
SGLIB_LIST_ADD(type, *list, elem, next);\
|
1156 |
|
|
}\
|
1157 |
|
|
void sglib_##type##_concat(type **first, type *second) {\
|
1158 |
|
|
SGLIB_LIST_CONCAT(type, *first, second, next);\
|
1159 |
|
|
}\
|
1160 |
|
|
void sglib_##type##_delete(type **list, type *elem) {\
|
1161 |
|
|
SGLIB_LIST_DELETE(type, *list, elem, next);\
|
1162 |
|
|
}\
|
1163 |
|
|
int sglib_##type##_delete_if_member(type **list, type *elem, type **member) {\
|
1164 |
|
|
SGLIB_LIST_DELETE_IF_MEMBER(type, *list, elem, comparator, next, *member);\
|
1165 |
|
|
return(*member!=NULL);\
|
1166 |
|
|
}\
|
1167 |
|
|
void sglib_##type##_sort(type **list) { \
|
1168 |
|
|
SGLIB_LIST_SORT(type, *list, comparator, next);\
|
1169 |
|
|
}\
|
1170 |
|
|
int sglib_##type##_len(type *list) {\
|
1171 |
|
|
int res;\
|
1172 |
|
|
SGLIB_LIST_LEN(type, list, next, res);\
|
1173 |
|
|
return(res);\
|
1174 |
|
|
}\
|
1175 |
|
|
void sglib_##type##_reverse(type **list) {\
|
1176 |
|
|
SGLIB_LIST_REVERSE(type, *list, next);\
|
1177 |
|
|
}\
|
1178 |
|
|
\
|
1179 |
|
|
type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto) {\
|
1180 |
|
|
it->subcomparator = subcomparator;\
|
1181 |
|
|
it->equalto = equalto;\
|
1182 |
|
|
it->nextelem = list;\
|
1183 |
|
|
return(sglib_##type##_it_next(it));\
|
1184 |
|
|
}\
|
1185 |
|
|
type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list) {\
|
1186 |
|
|
return(sglib_##type##_it_init_on_equal(it, list, NULL, NULL));\
|
1187 |
|
|
}\
|
1188 |
|
|
type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\
|
1189 |
|
|
return(it->currentelem);\
|
1190 |
|
|
}\
|
1191 |
|
|
type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\
|
1192 |
|
|
type *ce, *eq;\
|
1193 |
|
|
int (*scp)(type *, type *);\
|
1194 |
|
|
ce = it->nextelem;\
|
1195 |
|
|
it->nextelem = NULL;\
|
1196 |
|
|
if (it->subcomparator != NULL) {\
|
1197 |
|
|
eq = it->equalto; \
|
1198 |
|
|
scp = it->subcomparator;\
|
1199 |
|
|
while (ce!=NULL && scp(ce, eq)!=0) ce = ce->next;\
|
1200 |
|
|
}\
|
1201 |
|
|
it->currentelem = ce;\
|
1202 |
|
|
if (ce != NULL) it->nextelem = ce->next;\
|
1203 |
|
|
return(ce);\
|
1204 |
|
|
}
|
1205 |
|
|
|
1206 |
|
|
/* ----------------------------- sorted list (level 1) ----------------------------------- */
|
1207 |
|
|
|
1208 |
|
|
|
1209 |
|
|
#define SGLIB_DEFINE_SORTED_LIST_PROTOTYPES(type, comparator, next) \
|
1210 |
|
|
struct sglib_##type##_iterator {\
|
1211 |
|
|
type *currentelem;\
|
1212 |
|
|
type *nextelem;\
|
1213 |
|
|
int (*subcomparator)(type *, type *);\
|
1214 |
|
|
type *equalto;\
|
1215 |
|
|
};\
|
1216 |
|
|
extern void sglib_##type##_add(type **list, type *elem);\
|
1217 |
|
|
extern int sglib_##type##_add_if_not_member(type **list, type *elem, type **member);\
|
1218 |
|
|
extern void sglib_##type##_delete(type **list, type *elem);\
|
1219 |
|
|
extern int sglib_##type##_delete_if_member(type **list, type *elem, type **member);\
|
1220 |
|
|
extern int sglib_##type##_is_member(type *list, type *elem);\
|
1221 |
|
|
extern type *sglib_##type##_find_member(type *list, type *elem);\
|
1222 |
|
|
extern int sglib_##type##_len(type *list);\
|
1223 |
|
|
extern void sglib_##type##_sort(type **list);\
|
1224 |
|
|
extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list); \
|
1225 |
|
|
extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto); \
|
1226 |
|
|
extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \
|
1227 |
|
|
extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it);
|
1228 |
|
|
|
1229 |
|
|
|
1230 |
|
|
#define SGLIB_DEFINE_SORTED_LIST_FUNCTIONS(type, comparator, next) \
|
1231 |
|
|
int sglib_##type##_is_member(type *list, type *elem) {\
|
1232 |
|
|
int result;\
|
1233 |
|
|
SGLIB_SORTED_LIST_IS_MEMBER(type, list, elem, comparator, next, result);\
|
1234 |
|
|
return(result);\
|
1235 |
|
|
}\
|
1236 |
|
|
type *sglib_##type##_find_member(type *list, type *elem) {\
|
1237 |
|
|
type *result;\
|
1238 |
|
|
SGLIB_SORTED_LIST_FIND_MEMBER(type, list, elem, comparator, next, result);\
|
1239 |
|
|
return(result);\
|
1240 |
|
|
}\
|
1241 |
|
|
int sglib_##type##_add_if_not_member(type **list, type *elem, type **member) {\
|
1242 |
|
|
SGLIB_SORTED_LIST_ADD_IF_NOT_MEMBER(type, *list, elem, comparator, next, *member);\
|
1243 |
|
|
return(*member==NULL);\
|
1244 |
|
|
}\
|
1245 |
|
|
void sglib_##type##_add(type **list, type *elem) {\
|
1246 |
|
|
SGLIB_SORTED_LIST_ADD(type, *list, elem, comparator, next);\
|
1247 |
|
|
}\
|
1248 |
|
|
void sglib_##type##_delete(type **list, type *elem) {\
|
1249 |
|
|
SGLIB_SORTED_LIST_DELETE(type, *list, elem, next);\
|
1250 |
|
|
}\
|
1251 |
|
|
int sglib_##type##_delete_if_member(type **list, type *elem, type **member) {\
|
1252 |
|
|
SGLIB_SORTED_LIST_DELETE_IF_MEMBER(type, *list, elem, comparator, next, *member);\
|
1253 |
|
|
return(*member!=NULL);\
|
1254 |
|
|
}\
|
1255 |
|
|
int sglib_##type##_len(type *list) {\
|
1256 |
|
|
int res;\
|
1257 |
|
|
SGLIB_SORTED_LIST_LEN(type, list, next, res);\
|
1258 |
|
|
return(res);\
|
1259 |
|
|
}\
|
1260 |
|
|
void sglib_##type##_sort(type **list) { \
|
1261 |
|
|
SGLIB_LIST_SORT(type, *list, comparator, next);\
|
1262 |
|
|
}\
|
1263 |
|
|
\
|
1264 |
|
|
type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto) {\
|
1265 |
|
|
it->subcomparator = subcomparator;\
|
1266 |
|
|
it->equalto = equalto;\
|
1267 |
|
|
it->nextelem = list;\
|
1268 |
|
|
return(sglib_##type##_it_next(it));\
|
1269 |
|
|
}\
|
1270 |
|
|
type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list) {\
|
1271 |
|
|
return(sglib_##type##_it_init_on_equal(it, list, NULL, NULL));\
|
1272 |
|
|
}\
|
1273 |
|
|
type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\
|
1274 |
|
|
return(it->currentelem);\
|
1275 |
|
|
}\
|
1276 |
|
|
type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\
|
1277 |
|
|
type *ce, *eq;\
|
1278 |
|
|
int (*scp)(type *, type *);\
|
1279 |
|
|
int c;\
|
1280 |
|
|
ce = it->nextelem;\
|
1281 |
|
|
it->nextelem = NULL;\
|
1282 |
|
|
if (it->subcomparator != NULL) {\
|
1283 |
|
|
eq = it->equalto; \
|
1284 |
|
|
scp = it->subcomparator;\
|
1285 |
|
|
while (ce!=NULL && (c=scp(ce, eq)) < 0) ce = ce->next;\
|
1286 |
|
|
if (ce != NULL && c > 0) ce = NULL;\
|
1287 |
|
|
}\
|
1288 |
|
|
it->currentelem = ce;\
|
1289 |
|
|
if (ce != NULL) it->nextelem = ce->next;\
|
1290 |
|
|
return(ce);\
|
1291 |
|
|
}
|
1292 |
|
|
|
1293 |
|
|
|
1294 |
|
|
/* ----------------------------- double linked list (level 1) ------------------------------ */
|
1295 |
|
|
|
1296 |
|
|
|
1297 |
|
|
#define SGLIB_DEFINE_DL_LIST_PROTOTYPES(type, comparator, previous, next) \
|
1298 |
|
|
struct sglib_##type##_iterator {\
|
1299 |
|
|
type *currentelem;\
|
1300 |
|
|
type *prevelem;\
|
1301 |
|
|
type *nextelem;\
|
1302 |
|
|
int (*subcomparator)(type *, type *);\
|
1303 |
|
|
type *equalto;\
|
1304 |
|
|
};\
|
1305 |
|
|
extern void sglib_##type##_add(type **list, type *elem);\
|
1306 |
|
|
extern void sglib_##type##_add_before(type **list, type *elem);\
|
1307 |
|
|
extern void sglib_##type##_add_after(type **list, type *elem);\
|
1308 |
|
|
extern int sglib_##type##_add_if_not_member(type **list, type *elem, type **member);\
|
1309 |
|
|
extern int sglib_##type##_add_before_if_not_member(type **list, type *elem, type **member);\
|
1310 |
|
|
extern int sglib_##type##_add_after_if_not_member(type **list, type *elem, type **member);\
|
1311 |
|
|
extern void sglib_##type##_concat(type **first, type *second);\
|
1312 |
|
|
extern void sglib_##type##_delete(type **list, type *elem);\
|
1313 |
|
|
extern int sglib_##type##_delete_if_member(type **list, type *elem, type **member);\
|
1314 |
|
|
extern int sglib_##type##_is_member(type *list, type *elem);\
|
1315 |
|
|
extern type *sglib_##type##_find_member(type *list, type *elem);\
|
1316 |
|
|
extern type *sglib_##type##_get_first(type *list);\
|
1317 |
|
|
extern type *sglib_##type##_get_last(type *list);\
|
1318 |
|
|
extern void sglib_##type##_sort(type **list);\
|
1319 |
|
|
extern int sglib_##type##_len(type *list);\
|
1320 |
|
|
extern void sglib_##type##_reverse(type **list);\
|
1321 |
|
|
extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list); \
|
1322 |
|
|
extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto); \
|
1323 |
|
|
extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \
|
1324 |
|
|
extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it);
|
1325 |
|
|
|
1326 |
|
|
|
1327 |
|
|
#define SGLIB_DEFINE_DL_LIST_FUNCTIONS(type, comparator, previous, next) \
|
1328 |
|
|
void sglib_##type##_add(type **list, type *elem) {\
|
1329 |
|
|
SGLIB_DL_LIST_ADD(type, *list, elem, previous, next);\
|
1330 |
|
|
}\
|
1331 |
|
|
void sglib_##type##_add_after(type **list, type *elem) {\
|
1332 |
|
|
SGLIB_DL_LIST_ADD_AFTER(type, *list, elem, previous, next);\
|
1333 |
|
|
}\
|
1334 |
|
|
void sglib_##type##_add_before(type **list, type *elem) {\
|
1335 |
|
|
SGLIB_DL_LIST_ADD_BEFORE(type, *list, elem, previous, next);\
|
1336 |
|
|
}\
|
1337 |
|
|
int sglib_##type##_add_if_not_member(type **list, type *elem, type **member) {\
|
1338 |
|
|
SGLIB_DL_LIST_ADD_IF_NOT_MEMBER(type, *list, elem, comparator, previous, next, *member);\
|
1339 |
|
|
return(*member==NULL);\
|
1340 |
|
|
}\
|
1341 |
|
|
int sglib_##type##_add_after_if_not_member(type **list, type *elem, type **member) {\
|
1342 |
|
|
SGLIB_DL_LIST_ADD_AFTER_IF_NOT_MEMBER(type, *list, elem, comparator, previous, next, *member);\
|
1343 |
|
|
return(*member==NULL);\
|
1344 |
|
|
}\
|
1345 |
|
|
int sglib_##type##_add_before_if_not_member(type **list, type *elem, type **member) {\
|
1346 |
|
|
SGLIB_DL_LIST_ADD_BEFORE_IF_NOT_MEMBER(type, *list, elem, comparator, previous, next, *member);\
|
1347 |
|
|
return(*member==NULL);\
|
1348 |
|
|
}\
|
1349 |
|
|
void sglib_##type##_concat(type **first, type *second) {\
|
1350 |
|
|
SGLIB_DL_LIST_CONCAT(type, *first, second, previous, next);\
|
1351 |
|
|
}\
|
1352 |
|
|
void sglib_##type##_delete(type **list, type *elem) {\
|
1353 |
|
|
SGLIB_DL_LIST_DELETE(type, *list, elem, previous, next);\
|
1354 |
|
|
}\
|
1355 |
|
|
int sglib_##type##_delete_if_member(type **list, type *elem, type **member) {\
|
1356 |
|
|
SGLIB_DL_LIST_DELETE_IF_MEMBER(type, *list, elem, comparator, previous, next, *member);\
|
1357 |
|
|
return(*member!=NULL);\
|
1358 |
|
|
}\
|
1359 |
|
|
int sglib_##type##_is_member(type *list, type *elem) {\
|
1360 |
|
|
int result;\
|
1361 |
|
|
SGLIB_DL_LIST_IS_MEMBER(type, list, elem, previous, next, result);\
|
1362 |
|
|
return(result);\
|
1363 |
|
|
}\
|
1364 |
|
|
type *sglib_##type##_find_member(type *list, type *elem) {\
|
1365 |
|
|
type *result;\
|
1366 |
|
|
SGLIB_DL_LIST_FIND_MEMBER(type, list, elem, comparator, previous, next, result);\
|
1367 |
|
|
return(result);\
|
1368 |
|
|
}\
|
1369 |
|
|
type *sglib_##type##_get_first(type *list) {\
|
1370 |
|
|
type *result;\
|
1371 |
|
|
SGLIB_DL_LIST_GET_FIRST(type, list, previous, next, result);\
|
1372 |
|
|
return(result);\
|
1373 |
|
|
}\
|
1374 |
|
|
type *sglib_##type##_get_last(type *list) {\
|
1375 |
|
|
type *result;\
|
1376 |
|
|
SGLIB_DL_LIST_GET_LAST(type, list, previous, next, result);\
|
1377 |
|
|
return(result);\
|
1378 |
|
|
}\
|
1379 |
|
|
void sglib_##type##_sort(type **list) {\
|
1380 |
|
|
SGLIB_DL_LIST_SORT(type, *list, comparator, previous, next);\
|
1381 |
|
|
}\
|
1382 |
|
|
int sglib_##type##_len(type *list) {\
|
1383 |
|
|
int res;\
|
1384 |
|
|
SGLIB_DL_LIST_LEN(type, list, previous, next, res);\
|
1385 |
|
|
return(res);\
|
1386 |
|
|
}\
|
1387 |
|
|
void sglib_##type##_reverse(type **list) {\
|
1388 |
|
|
SGLIB_DL_LIST_REVERSE(type, *list, previous, next);\
|
1389 |
|
|
}\
|
1390 |
|
|
\
|
1391 |
|
|
type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto) {\
|
1392 |
|
|
it->subcomparator = subcomparator;\
|
1393 |
|
|
it->equalto = equalto;\
|
1394 |
|
|
it->prevelem = list;\
|
1395 |
|
|
it->nextelem = list;\
|
1396 |
|
|
if (list != NULL) it->nextelem = list->next;\
|
1397 |
|
|
return(sglib_##type##_it_next(it));\
|
1398 |
|
|
}\
|
1399 |
|
|
type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list) {\
|
1400 |
|
|
return(sglib_##type##_it_init_on_equal(it, list, NULL, NULL));\
|
1401 |
|
|
}\
|
1402 |
|
|
type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\
|
1403 |
|
|
return(it->currentelem);\
|
1404 |
|
|
}\
|
1405 |
|
|
type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\
|
1406 |
|
|
type *ce, *eq;\
|
1407 |
|
|
int (*scp)(type *, type *);\
|
1408 |
|
|
ce = it->prevelem;\
|
1409 |
|
|
it->prevelem = NULL;\
|
1410 |
|
|
if (it->subcomparator != NULL) {\
|
1411 |
|
|
eq = it->equalto; \
|
1412 |
|
|
scp = it->subcomparator;\
|
1413 |
|
|
while (ce!=NULL && scp(eq, ce)!=0) ce = ce->previous;\
|
1414 |
|
|
}\
|
1415 |
|
|
if (ce != NULL) {\
|
1416 |
|
|
it->prevelem = ce->previous;\
|
1417 |
|
|
} else {\
|
1418 |
|
|
ce = it->nextelem;\
|
1419 |
|
|
it->nextelem = NULL;\
|
1420 |
|
|
if (it->subcomparator != NULL) {\
|
1421 |
|
|
eq = it->equalto; \
|
1422 |
|
|
scp = it->subcomparator;\
|
1423 |
|
|
while (ce!=NULL && scp(ce, eq)!=0) ce = ce->next;\
|
1424 |
|
|
}\
|
1425 |
|
|
if (ce != NULL) it->nextelem = ce->next;\
|
1426 |
|
|
}\
|
1427 |
|
|
it->currentelem = ce;\
|
1428 |
|
|
return(ce);\
|
1429 |
|
|
}
|
1430 |
|
|
|
1431 |
|
|
|
1432 |
|
|
/* --------------------------------- red-black trees (level 1) -------------------------------- */
|
1433 |
|
|
|
1434 |
|
|
/*
|
1435 |
|
|
|
1436 |
|
|
This implementation requires pointers to left and right sons (no
|
1437 |
|
|
parent pointer is needed) and one bit of additional information
|
1438 |
|
|
storing the color of the node. The implementation follows discrepancy
|
1439 |
|
|
fixing rules from:
|
1440 |
|
|
http://www.cis.ohio-state.edu/~gurari/course/cis680/cis680Ch11.html
|
1441 |
|
|
|
1442 |
|
|
*/
|
1443 |
|
|
|
1444 |
|
|
#define SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, leftt, rightt, bits, RED, BLACK) {\
|
1445 |
|
|
type *t, *tl, *a, *b, *c, *ar, *bl, *br, *cl, *cr;\
|
1446 |
|
|
t = *tree;\
|
1447 |
|
|
tl = t->leftt;\
|
1448 |
|
|
if (t->rightt!=NULL && SGLIB___GET_VALUE(t->rightt->bits)==RED) {\
|
1449 |
|
|
if (SGLIB___GET_VALUE(tl->bits)==RED) {\
|
1450 |
|
|
if ((tl->leftt!=NULL && SGLIB___GET_VALUE(tl->leftt->bits)==RED) \
|
1451 |
|
|
|| (tl->rightt!=NULL && SGLIB___GET_VALUE(tl->rightt->bits)==RED)) {\
|
1452 |
|
|
SGLIB___SET_VALUE(t->leftt->bits,BLACK);\
|
1453 |
|
|
SGLIB___SET_VALUE(t->rightt->bits,BLACK);\
|
1454 |
|
|
SGLIB___SET_VALUE(t->bits,RED);\
|
1455 |
|
|
}\
|
1456 |
|
|
}\
|
1457 |
|
|
} else {\
|
1458 |
|
|
if (SGLIB___GET_VALUE(tl->bits)==RED) {\
|
1459 |
|
|
if (tl->leftt!=NULL && SGLIB___GET_VALUE(tl->leftt->bits)==RED) {\
|
1460 |
|
|
a = t; b = tl; c = tl->leftt;\
|
1461 |
|
|
br = b->rightt;\
|
1462 |
|
|
a->leftt = br;\
|
1463 |
|
|
b->leftt = c; b->rightt = a;\
|
1464 |
|
|
SGLIB___SET_VALUE(a->bits,RED);\
|
1465 |
|
|
SGLIB___SET_VALUE(b->bits,BLACK);\
|
1466 |
|
|
*tree = b;\
|
1467 |
|
|
} else if (tl->rightt!=NULL && SGLIB___GET_VALUE(tl->rightt->bits)==RED) {\
|
1468 |
|
|
a = t; b = tl; ar=a->rightt;\
|
1469 |
|
|
bl=b->leftt; c=b->rightt;\
|
1470 |
|
|
cl=c->leftt; cr=c->rightt;\
|
1471 |
|
|
b->rightt = cl;\
|
1472 |
|
|
a->leftt = cr;\
|
1473 |
|
|
c->leftt = b;\
|
1474 |
|
|
c->rightt = a;\
|
1475 |
|
|
SGLIB___SET_VALUE(c->bits,BLACK);\
|
1476 |
|
|
SGLIB___SET_VALUE(a->bits,RED);\
|
1477 |
|
|
*tree = c;\
|
1478 |
|
|
}\
|
1479 |
|
|
}\
|
1480 |
|
|
}\
|
1481 |
|
|
}
|
1482 |
|
|
|
1483 |
|
|
#define SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, leftt, rightt, bits, RED, BLACK, res) {\
|
1484 |
|
|
type *t, *a, *b, *c, *d, *ar, *bl, *br, *cl, *cr, *dl, *dr;\
|
1485 |
|
|
t = a = *tree;\
|
1486 |
|
|
assert(t!=NULL);\
|
1487 |
|
|
ar = a->rightt;\
|
1488 |
|
|
b = t->leftt;\
|
1489 |
|
|
if (b==NULL) {\
|
1490 |
|
|
assert(SGLIB___GET_VALUE(t->bits)==RED);\
|
1491 |
|
|
SGLIB___SET_VALUE(t->bits,BLACK);\
|
1492 |
|
|
res = 0;\
|
1493 |
|
|
} else {\
|
1494 |
|
|
bl = b->leftt;\
|
1495 |
|
|
br = b->rightt;\
|
1496 |
|
|
if (SGLIB___GET_VALUE(b->bits)==RED) {\
|
1497 |
|
|
if (br==NULL) {\
|
1498 |
|
|
*tree = b;\
|
1499 |
|
|
SGLIB___SET_VALUE(b->bits,BLACK);\
|
1500 |
|
|
b->rightt = a;\
|
1501 |
|
|
a->leftt = br;\
|
1502 |
|
|
res = 0;\
|
1503 |
|
|
} else {\
|
1504 |
|
|
c = br;\
|
1505 |
|
|
assert(c!=NULL && SGLIB___GET_VALUE(c->bits)==BLACK);\
|
1506 |
|
|
cl = c->leftt;\
|
1507 |
|
|
cr = c->rightt;\
|
1508 |
|
|
if ((cl==NULL||SGLIB___GET_VALUE(cl->bits)==BLACK) && (cr==NULL||SGLIB___GET_VALUE(cr->bits)==BLACK)) {\
|
1509 |
|
|
*tree = b;\
|
1510 |
|
|
b->rightt = a;\
|
1511 |
|
|
SGLIB___SET_VALUE(b->bits,BLACK);\
|
1512 |
|
|
a->leftt = c;\
|
1513 |
|
|
SGLIB___SET_VALUE(c->bits,RED);\
|
1514 |
|
|
res = 0;\
|
1515 |
|
|
} else if (cl!=NULL && SGLIB___GET_VALUE(cl->bits)==RED) {\
|
1516 |
|
|
if (cr!=NULL && SGLIB___GET_VALUE(cr->bits)==RED) {\
|
1517 |
|
|
d = cr;\
|
1518 |
|
|
dl = d->leftt;\
|
1519 |
|
|
dr = d->rightt;\
|
1520 |
|
|
*tree = d;\
|
1521 |
|
|
SGLIB___SET_VALUE(d->bits,BLACK);\
|
1522 |
|
|
d->leftt = b;\
|
1523 |
|
|
c->rightt = dl;\
|
1524 |
|
|
d->rightt = a;\
|
1525 |
|
|
a->leftt = dr;\
|
1526 |
|
|
res = 0;\
|
1527 |
|
|
} else {\
|
1528 |
|
|
*tree = c;\
|
1529 |
|
|
c->leftt = b;\
|
1530 |
|
|
c->rightt = a;\
|
1531 |
|
|
b->leftt = bl;\
|
1532 |
|
|
b->rightt = cl;\
|
1533 |
|
|
a->leftt = cr;\
|
1534 |
|
|
SGLIB___SET_VALUE(cl->bits,BLACK);\
|
1535 |
|
|
res = 0;\
|
1536 |
|
|
}\
|
1537 |
|
|
} else if (cr!=NULL && SGLIB___GET_VALUE(cr->bits)==RED) {\
|
1538 |
|
|
assert(cl==NULL || SGLIB___GET_VALUE(cl->bits)==BLACK);\
|
1539 |
|
|
d = cr;\
|
1540 |
|
|
dl = d->leftt;\
|
1541 |
|
|
dr = d->rightt;\
|
1542 |
|
|
*tree = d;\
|
1543 |
|
|
SGLIB___SET_VALUE(d->bits,BLACK);\
|
1544 |
|
|
d->leftt = b;\
|
1545 |
|
|
c->rightt = dl;\
|
1546 |
|
|
d->rightt = a;\
|
1547 |
|
|
a->leftt = dr;\
|
1548 |
|
|
res = 0;\
|
1549 |
|
|
} else {\
|
1550 |
|
|
assert(0);\
|
1551 |
|
|
res = 0;\
|
1552 |
|
|
}\
|
1553 |
|
|
}\
|
1554 |
|
|
} else {\
|
1555 |
|
|
if ((bl==NULL || SGLIB___GET_VALUE(bl->bits)==BLACK) && (br==NULL || SGLIB___GET_VALUE(br->bits)==BLACK)) {\
|
1556 |
|
|
res = (SGLIB___GET_VALUE(a->bits)==BLACK);\
|
1557 |
|
|
SGLIB___SET_VALUE(a->bits,BLACK);\
|
1558 |
|
|
SGLIB___SET_VALUE(b->bits,RED);\
|
1559 |
|
|
} else if (bl!=NULL && SGLIB___GET_VALUE(bl->bits)==RED) {\
|
1560 |
|
|
if (br==NULL || SGLIB___GET_VALUE(br->bits)==BLACK) {\
|
1561 |
|
|
*tree = b;\
|
1562 |
|
|
SGLIB___SET_VALUE(b->bits,SGLIB___GET_VALUE(a->bits));\
|
1563 |
|
|
SGLIB___SET_VALUE(a->bits,BLACK);\
|
1564 |
|
|
b->rightt = a;\
|
1565 |
|
|
a->leftt = br;\
|
1566 |
|
|
SGLIB___SET_VALUE(bl->bits,BLACK);\
|
1567 |
|
|
res = 0;\
|
1568 |
|
|
} else {\
|
1569 |
|
|
assert(bl!=NULL);\
|
1570 |
|
|
assert(br!=NULL);\
|
1571 |
|
|
assert(SGLIB___GET_VALUE(bl->bits)==RED);\
|
1572 |
|
|
assert(SGLIB___GET_VALUE(br->bits)==RED);\
|
1573 |
|
|
c = br;\
|
1574 |
|
|
cl = c->leftt;\
|
1575 |
|
|
cr = c->rightt;\
|
1576 |
|
|
*tree = c;\
|
1577 |
|
|
SGLIB___SET_VALUE(c->bits,SGLIB___GET_VALUE(a->bits));\
|
1578 |
|
|
SGLIB___SET_VALUE(a->bits,BLACK);\
|
1579 |
|
|
c->leftt = b;\
|
1580 |
|
|
c->rightt = a;\
|
1581 |
|
|
b->rightt = cl;\
|
1582 |
|
|
a->leftt = cr;\
|
1583 |
|
|
res = 0;\
|
1584 |
|
|
}\
|
1585 |
|
|
} else {\
|
1586 |
|
|
assert(br!=NULL && SGLIB___GET_VALUE(br->bits)==RED);\
|
1587 |
|
|
c = br;\
|
1588 |
|
|
cl = c->leftt;\
|
1589 |
|
|
cr = c->rightt;\
|
1590 |
|
|
*tree = c;\
|
1591 |
|
|
SGLIB___SET_VALUE(c->bits,SGLIB___GET_VALUE(a->bits));\
|
1592 |
|
|
SGLIB___SET_VALUE(a->bits,BLACK);\
|
1593 |
|
|
c->leftt = b;\
|
1594 |
|
|
c->rightt = a;\
|
1595 |
|
|
b->rightt = cl;\
|
1596 |
|
|
a->leftt = cr;\
|
1597 |
|
|
res = 0;\
|
1598 |
|
|
}\
|
1599 |
|
|
}\
|
1600 |
|
|
}\
|
1601 |
|
|
}
|
1602 |
|
|
|
1603 |
|
|
|
1604 |
|
|
#define SGLIB_DEFINE_RBTREE_FUNCTIONS_GENERAL(type, left, right, bits, comparator, RED, BLACK) \
|
1605 |
|
|
static void sglib___##type##_fix_left_insertion_discrepancy(type **tree) {\
|
1606 |
|
|
SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, left, right, bits, RED, BLACK);\
|
1607 |
|
|
}\
|
1608 |
|
|
\
|
1609 |
|
|
static void sglib___##type##_fix_right_insertion_discrepancy(type **tree) {\
|
1610 |
|
|
SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, right, left, bits, RED, BLACK);\
|
1611 |
|
|
}\
|
1612 |
|
|
\
|
1613 |
|
|
static int sglib___##type##_fix_left_deletion_discrepancy(type **tree) {\
|
1614 |
|
|
int res;\
|
1615 |
|
|
SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, right, left, bits, RED, BLACK, res);\
|
1616 |
|
|
return(res);\
|
1617 |
|
|
}\
|
1618 |
|
|
\
|
1619 |
|
|
static int sglib___##type##_fix_right_deletion_discrepancy(type **tree) {\
|
1620 |
|
|
int res;\
|
1621 |
|
|
SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, left, right, bits, RED, BLACK, res);\
|
1622 |
|
|
return(res);\
|
1623 |
|
|
}\
|
1624 |
|
|
\
|
1625 |
|
|
static void sglib___##type##_add_recursive(type **tree, type *elem) {\
|
1626 |
|
|
int cmp;\
|
1627 |
|
|
type *t;\
|
1628 |
|
|
t = *tree;\
|
1629 |
|
|
if (t == NULL) {\
|
1630 |
|
|
SGLIB___SET_VALUE(elem->bits,RED);\
|
1631 |
|
|
*tree =elem;\
|
1632 |
|
|
} else {\
|
1633 |
|
|
cmp = comparator(elem, t);\
|
1634 |
|
|
if (cmp < 0 || (cmp==0 && elem<t)) {\
|
1635 |
|
|
sglib___##type##_add_recursive(&t->left, elem);\
|
1636 |
|
|
if (SGLIB___GET_VALUE(t->bits)==BLACK) sglib___##type##_fix_left_insertion_discrepancy(tree);\
|
1637 |
|
|
} else {\
|
1638 |
|
|
sglib___##type##_add_recursive(&t->right, elem);\
|
1639 |
|
|
if (SGLIB___GET_VALUE(t->bits)==BLACK) sglib___##type##_fix_right_insertion_discrepancy(tree);\
|
1640 |
|
|
}\
|
1641 |
|
|
}\
|
1642 |
|
|
}\
|
1643 |
|
|
\
|
1644 |
|
|
static int sglib___##type##_delete_rightmost_leaf(type **tree, type **theLeaf) {\
|
1645 |
|
|
type *t;\
|
1646 |
|
|
int res, deepDecreased;\
|
1647 |
|
|
t = *tree;\
|
1648 |
|
|
res = 0;\
|
1649 |
|
|
assert(t!=NULL);\
|
1650 |
|
|
if (t->right == NULL) {\
|
1651 |
|
|
*theLeaf = t;\
|
1652 |
|
|
if (t->left!=NULL) {\
|
1653 |
|
|
if (SGLIB___GET_VALUE(t->bits)==BLACK && SGLIB___GET_VALUE(t->left->bits)==BLACK) res = 1;\
|
1654 |
|
|
SGLIB___SET_VALUE(t->left->bits,BLACK);\
|
1655 |
|
|
*tree = t->left;\
|
1656 |
|
|
} else {\
|
1657 |
|
|
*tree = NULL;\
|
1658 |
|
|
res = (SGLIB___GET_VALUE(t->bits)==BLACK);\
|
1659 |
|
|
}\
|
1660 |
|
|
} else {\
|
1661 |
|
|
deepDecreased = sglib___##type##_delete_rightmost_leaf(&t->right, theLeaf);\
|
1662 |
|
|
if (deepDecreased) res = sglib___##type##_fix_right_deletion_discrepancy(tree);\
|
1663 |
|
|
}\
|
1664 |
|
|
return(res);\
|
1665 |
|
|
}\
|
1666 |
|
|
\
|
1667 |
|
|
int sglib___##type##_delete_recursive(type **tree, type *elem) {\
|
1668 |
|
|
type *t, *theLeaf;\
|
1669 |
|
|
int cmp, res, deepDecreased;\
|
1670 |
|
|
t = *tree;\
|
1671 |
|
|
res = 0;\
|
1672 |
|
|
if (t==NULL) {\
|
1673 |
|
|
assert(0 && "The element to delete not found in the tree, use 'delete_if_member'"!=NULL);\
|
1674 |
|
|
} else {\
|
1675 |
|
|
cmp = comparator(elem, t);\
|
1676 |
|
|
if (cmp < 0 || (cmp==0 && elem<t)) {\
|
1677 |
|
|
deepDecreased = sglib___##type##_delete_recursive(&t->left, elem);\
|
1678 |
|
|
if (deepDecreased) {\
|
1679 |
|
|
res = sglib___##type##_fix_left_deletion_discrepancy(tree);\
|
1680 |
|
|
}\
|
1681 |
|
|
} else if (cmp > 0 || (cmp==0 && elem>t)) {\
|
1682 |
|
|
deepDecreased = sglib___##type##_delete_recursive(&t->right, elem);\
|
1683 |
|
|
if (deepDecreased) {\
|
1684 |
|
|
res = sglib___##type##_fix_right_deletion_discrepancy(tree);\
|
1685 |
|
|
}\
|
1686 |
|
|
} else {\
|
1687 |
|
|
assert(elem==t && "Deleting an element which is non member of the tree, use 'delete_if_member'"!=NULL);\
|
1688 |
|
|
if (t->left == NULL) {\
|
1689 |
|
|
if (t->right == NULL) {\
|
1690 |
|
|
/* a leaf, delete, it; */\
|
1691 |
|
|
*tree = NULL;\
|
1692 |
|
|
res = (SGLIB___GET_VALUE(t->bits)==BLACK);\
|
1693 |
|
|
} else {\
|
1694 |
|
|
if (SGLIB___GET_VALUE(t->bits)==0 && SGLIB___GET_VALUE(t->right->bits)==0) res = 1;\
|
1695 |
|
|
SGLIB___SET_VALUE(t->right->bits,BLACK);\
|
1696 |
|
|
*tree = t->right;\
|
1697 |
|
|
}\
|
1698 |
|
|
} else {\
|
1699 |
|
|
/* propagate deletion until righmost leaf of left subtree */\
|
1700 |
|
|
deepDecreased = sglib___##type##_delete_rightmost_leaf(&t->left, &theLeaf);\
|
1701 |
|
|
theLeaf->left = t->left;\
|
1702 |
|
|
theLeaf->right = t->right;\
|
1703 |
|
|
SGLIB___SET_VALUE(theLeaf->bits,SGLIB___GET_VALUE(t->bits));\
|
1704 |
|
|
*tree = theLeaf;\
|
1705 |
|
|
if (deepDecreased) res = sglib___##type##_fix_left_deletion_discrepancy(tree);\
|
1706 |
|
|
}\
|
1707 |
|
|
}\
|
1708 |
|
|
}\
|
1709 |
|
|
return(res);\
|
1710 |
|
|
}\
|
1711 |
|
|
\
|
1712 |
|
|
void sglib_##type##_add(type **tree, type *elem) {\
|
1713 |
|
|
elem->left = elem->right = NULL;\
|
1714 |
|
|
sglib___##type##_add_recursive(tree, elem);\
|
1715 |
|
|
SGLIB___SET_VALUE((*tree)->bits,BLACK);\
|
1716 |
|
|
}\
|
1717 |
|
|
\
|
1718 |
|
|
void sglib_##type##_delete(type **tree, type *elem) {\
|
1719 |
|
|
sglib___##type##_delete_recursive(tree, elem);\
|
1720 |
|
|
if (*tree!=NULL) SGLIB___SET_VALUE((*tree)->bits,BLACK);\
|
1721 |
|
|
}\
|
1722 |
|
|
\
|
1723 |
|
|
type *sglib_##type##_find_member(type *t, type *elem) {\
|
1724 |
|
|
type *res;\
|
1725 |
|
|
SGLIB___BIN_TREE_FIND_MEMBER(type, t, elem, left, right, comparator, res);\
|
1726 |
|
|
return(res);\
|
1727 |
|
|
}\
|
1728 |
|
|
\
|
1729 |
|
|
int sglib_##type##_is_member(type *t, type *elem) {\
|
1730 |
|
|
int cmp;\
|
1731 |
|
|
while (t!=NULL) {\
|
1732 |
|
|
cmp = comparator(elem, t);\
|
1733 |
|
|
if (cmp < 0 || (cmp==0 && elem<t)) {\
|
1734 |
|
|
t = t->left;\
|
1735 |
|
|
} else if (cmp > 0 || (cmp==0 && elem>t)) {\
|
1736 |
|
|
t = t->right;\
|
1737 |
|
|
} else {\
|
1738 |
|
|
assert(t == elem);\
|
1739 |
|
|
return(1);\
|
1740 |
|
|
}\
|
1741 |
|
|
}\
|
1742 |
|
|
return(0);\
|
1743 |
|
|
}\
|
1744 |
|
|
\
|
1745 |
|
|
int sglib_##type##_delete_if_member(type **tree, type *elem, type **memb) {\
|
1746 |
|
|
if ((*memb=sglib_##type##_find_member(*tree, elem))!=NULL) {\
|
1747 |
|
|
sglib_##type##_delete(tree, *memb);\
|
1748 |
|
|
return(1);\
|
1749 |
|
|
} else {\
|
1750 |
|
|
return(0);\
|
1751 |
|
|
}\
|
1752 |
|
|
}\
|
1753 |
|
|
int sglib_##type##_add_if_not_member(type **tree, type *elem, type **memb) {\
|
1754 |
|
|
if ((*memb=sglib_##type##_find_member(*tree, elem))==NULL) {\
|
1755 |
|
|
sglib_##type##_add(tree, elem);\
|
1756 |
|
|
return(1);\
|
1757 |
|
|
} else {\
|
1758 |
|
|
return(0);\
|
1759 |
|
|
}\
|
1760 |
|
|
}\
|
1761 |
|
|
int sglib_##type##_len(type *t) {\
|
1762 |
|
|
int n;\
|
1763 |
|
|
type *e;\
|
1764 |
|
|
n = 0;\
|
1765 |
|
|
SGLIB_BIN_TREE_MAP_ON_ELEMENTS(type, t, e, left, right, n++);\
|
1766 |
|
|
return(n);\
|
1767 |
|
|
}\
|
1768 |
|
|
\
|
1769 |
|
|
void sglib__##type##_it_compute_current_elem(struct sglib_##type##_iterator *it) {\
|
1770 |
|
|
int i,j,cmp;\
|
1771 |
|
|
type *s, *eqt;\
|
1772 |
|
|
int (*subcomparator)(type *, type *);\
|
1773 |
|
|
eqt = it->equalto;\
|
1774 |
|
|
subcomparator = it->subcomparator;\
|
1775 |
|
|
it->currentelem = NULL;\
|
1776 |
|
|
while(it->pathi > 0 && it->currentelem==NULL) {\
|
1777 |
|
|
i = it->pathi-1;\
|
1778 |
|
|
if (i >= 0) {\
|
1779 |
|
|
if (it->pass[i] >= 2) {\
|
1780 |
|
|
/* goto up */\
|
1781 |
|
|
it->pathi --;\
|
1782 |
|
|
} else {\
|
1783 |
|
|
if (it->pass[i] == 0) {\
|
1784 |
|
|
/* goto left */\
|
1785 |
|
|
s = it->path[i]->left;\
|
1786 |
|
|
} else {\
|
1787 |
|
|
/* goto right */\
|
1788 |
|
|
s = it->path[i]->right;\
|
1789 |
|
|
}\
|
1790 |
|
|
if (eqt != NULL) {\
|
1791 |
|
|
if (subcomparator == NULL) {\
|
1792 |
|
|
SGLIB___BIN_TREE_FIND_MEMBER(type, s, eqt, left, right, comparator, s);\
|
1793 |
|
|
} else {\
|
1794 |
|
|
SGLIB___BIN_TREE_FIND_MEMBER(type, s, eqt, left, right, subcomparator, s);\
|
1795 |
|
|
}\
|
1796 |
|
|
}\
|
1797 |
|
|
if (s != NULL) {\
|
1798 |
|
|
j = i+1;\
|
1799 |
|
|
it->path[j] = s;\
|
1800 |
|
|
it->pass[j] = 0;\
|
1801 |
|
|
it->pathi ++;\
|
1802 |
|
|
}\
|
1803 |
|
|
it->pass[i] ++;\
|
1804 |
|
|
}\
|
1805 |
|
|
}\
|
1806 |
|
|
if (it->pathi>0 && it->order == it->pass[it->pathi-1]) {\
|
1807 |
|
|
it->currentelem = it->path[it->pathi-1];\
|
1808 |
|
|
}\
|
1809 |
|
|
}\
|
1810 |
|
|
}\
|
1811 |
|
|
type *sglib__##type##_it_init(struct sglib_##type##_iterator *it, type *tree, int order, int (*subcomparator)(type *, type *), type *equalto) {\
|
1812 |
|
|
type *t;\
|
1813 |
|
|
assert(it!=NULL);\
|
1814 |
|
|
it->order = order;\
|
1815 |
|
|
it->equalto = equalto;\
|
1816 |
|
|
it->subcomparator = subcomparator;\
|
1817 |
|
|
if (equalto == NULL) { \
|
1818 |
|
|
t = tree;\
|
1819 |
|
|
} else {\
|
1820 |
|
|
if (subcomparator == NULL) {\
|
1821 |
|
|
SGLIB___BIN_TREE_FIND_MEMBER(type, tree, equalto, left, right, comparator, t);\
|
1822 |
|
|
} else {\
|
1823 |
|
|
SGLIB___BIN_TREE_FIND_MEMBER(type, tree, equalto, left, right, subcomparator, t);\
|
1824 |
|
|
}\
|
1825 |
|
|
}\
|
1826 |
|
|
if (t == NULL) {\
|
1827 |
|
|
it->pathi = 0;\
|
1828 |
|
|
it->currentelem = NULL;\
|
1829 |
|
|
} else {\
|
1830 |
|
|
it->pathi = 1;\
|
1831 |
|
|
it->pass[0] = 0;\
|
1832 |
|
|
it->path[0] = t;\
|
1833 |
|
|
if (order == 0) {\
|
1834 |
|
|
it->currentelem = t;\
|
1835 |
|
|
} else {\
|
1836 |
|
|
sglib__##type##_it_compute_current_elem(it);\
|
1837 |
|
|
}\
|
1838 |
|
|
}\
|
1839 |
|
|
return(it->currentelem);\
|
1840 |
|
|
}\
|
1841 |
|
|
type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *tree) {\
|
1842 |
|
|
return(sglib__##type##_it_init(it, tree, 2, NULL, NULL));\
|
1843 |
|
|
}\
|
1844 |
|
|
type *sglib_##type##_it_init_preorder(struct sglib_##type##_iterator *it, type *tree) {\
|
1845 |
|
|
return(sglib__##type##_it_init(it, tree, 0, NULL, NULL));\
|
1846 |
|
|
}\
|
1847 |
|
|
type *sglib_##type##_it_init_inorder(struct sglib_##type##_iterator *it, type *tree) {\
|
1848 |
|
|
return(sglib__##type##_it_init(it, tree, 1, NULL, NULL));\
|
1849 |
|
|
}\
|
1850 |
|
|
type *sglib_##type##_it_init_postorder(struct sglib_##type##_iterator *it, type *tree) {\
|
1851 |
|
|
return(sglib__##type##_it_init(it, tree, 2, NULL, NULL));\
|
1852 |
|
|
}\
|
1853 |
|
|
type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *tree, int (*subcomparator)(type *, type *), type *equalto) {\
|
1854 |
|
|
return(sglib__##type##_it_init(it, tree, 1, subcomparator, equalto));\
|
1855 |
|
|
}\
|
1856 |
|
|
type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\
|
1857 |
|
|
return(it->currentelem);\
|
1858 |
|
|
}\
|
1859 |
|
|
type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\
|
1860 |
|
|
sglib__##type##_it_compute_current_elem(it);\
|
1861 |
|
|
return(it->currentelem);\
|
1862 |
|
|
}\
|
1863 |
|
|
\
|
1864 |
|
|
static void sglib___##type##_consistency_check_recursive(type *t, int *pathdeep, int cdeep) {\
|
1865 |
|
|
if (t==NULL) {\
|
1866 |
|
|
if (*pathdeep < 0) *pathdeep = cdeep;\
|
1867 |
|
|
else assert(*pathdeep == cdeep);\
|
1868 |
|
|
} else {\
|
1869 |
|
|
if (t->left!=NULL) assert(comparator(t->left, t) <= 0);\
|
1870 |
|
|
if (t->right!=NULL) assert(comparator(t, t->right) <= 0);\
|
1871 |
|
|
if (SGLIB___GET_VALUE(t->bits) == RED) {\
|
1872 |
|
|
assert(t->left == NULL || SGLIB___GET_VALUE(t->left->bits)==BLACK);\
|
1873 |
|
|
assert(t->right == NULL || SGLIB___GET_VALUE(t->right->bits)==BLACK);\
|
1874 |
|
|
sglib___##type##_consistency_check_recursive(t->left, pathdeep, cdeep);\
|
1875 |
|
|
sglib___##type##_consistency_check_recursive(t->right, pathdeep, cdeep);\
|
1876 |
|
|
} else {\
|
1877 |
|
|
sglib___##type##_consistency_check_recursive(t->left, pathdeep, cdeep+1);\
|
1878 |
|
|
sglib___##type##_consistency_check_recursive(t->right, pathdeep, cdeep+1);\
|
1879 |
|
|
}\
|
1880 |
|
|
}\
|
1881 |
|
|
}\
|
1882 |
|
|
\
|
1883 |
|
|
void sglib___##type##_consistency_check(type *t) {\
|
1884 |
|
|
int pathDeep;\
|
1885 |
|
|
assert(t==NULL || SGLIB___GET_VALUE(t->bits) == BLACK);\
|
1886 |
|
|
pathDeep = -1;\
|
1887 |
|
|
sglib___##type##_consistency_check_recursive(t, &pathDeep, 0);\
|
1888 |
|
|
}
|
1889 |
|
|
|
1890 |
|
|
|
1891 |
|
|
#define SGLIB_DEFINE_RBTREE_PROTOTYPES(type, left, right, colorbit, comparator) \
|
1892 |
|
|
struct sglib_##type##_iterator {\
|
1893 |
|
|
type *currentelem;\
|
1894 |
|
|
char pass[SGLIB_MAX_TREE_DEEP];\
|
1895 |
|
|
type *path[SGLIB_MAX_TREE_DEEP];\
|
1896 |
|
|
short int pathi;\
|
1897 |
|
|
short int order;\
|
1898 |
|
|
type *equalto;\
|
1899 |
|
|
int (*subcomparator)(type *, type *);\
|
1900 |
|
|
};\
|
1901 |
|
|
extern void sglib___##type##_consistency_check(type *t); \
|
1902 |
|
|
extern void sglib_##type##_add(type **tree, type *elem); \
|
1903 |
|
|
extern int sglib_##type##_add_if_not_member(type **tree, type *elem, type **memb); \
|
1904 |
|
|
extern void sglib_##type##_delete(type **tree, type *elem); \
|
1905 |
|
|
extern int sglib_##type##_delete_if_member(type **tree, type *elem, type **memb); \
|
1906 |
|
|
extern int sglib_##type##_is_member(type *t, type *elem); \
|
1907 |
|
|
extern type *sglib_##type##_find_member(type *t, type *elem); \
|
1908 |
|
|
extern int sglib_##type##_len(type *t); \
|
1909 |
|
|
extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *tree); \
|
1910 |
|
|
extern type *sglib_##type##_it_init_preorder(struct sglib_##type##_iterator *it, type *tree); \
|
1911 |
|
|
extern type *sglib_##type##_it_init_inorder(struct sglib_##type##_iterator *it, type *tree); \
|
1912 |
|
|
extern type *sglib_##type##_it_init_postorder(struct sglib_##type##_iterator *it, type *tree); \
|
1913 |
|
|
extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *tree, int (*subcomparator)(type *, type *), type *equalto); \
|
1914 |
|
|
extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \
|
1915 |
|
|
extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it); \
|
1916 |
|
|
|
1917 |
|
|
|
1918 |
|
|
#define SGLIB_DEFINE_RBTREE_FUNCTIONS(type, left, right, colorbit, comparator) \
|
1919 |
|
|
SGLIB_DEFINE_RBTREE_FUNCTIONS_GENERAL(type, left, right, colorbit, comparator, 1, 0)
|
1920 |
|
|
|
1921 |
|
|
|
1922 |
|
|
|
1923 |
|
|
/* ---------------------------------------------------------------------------- */
|
1924 |
|
|
/* ---------------------------------------------------------------------------- */
|
1925 |
|
|
/* - SUPPLEMENTARY DEFINITIONS - */
|
1926 |
|
|
/* ---------------------------------------------------------------------------- */
|
1927 |
|
|
/* ---------------------------------------------------------------------------- */
|
1928 |
|
|
|
1929 |
|
|
|
1930 |
|
|
#define SGLIB___GET_VALUE(x) (x)
|
1931 |
|
|
#define SGLIB___SET_VALUE(x, value) {(x) = (value);}
|
1932 |
|
|
#define SGLIB_ARRAY_ELEMENTS_EXCHANGER(type, a, i, j) {type _sgl_aee_tmp_; _sgl_aee_tmp_=(a)[(i)]; (a)[(i)]=(a)[(j)]; (a)[(j)]= _sgl_aee_tmp_;}
|
1933 |
|
|
|
1934 |
|
|
|
1935 |
|
|
#define SGLIB_NUMERIC_COMPARATOR(x, y) ((int)((x) - (y)))
|
1936 |
|
|
#define SGLIB_REVERSE_NUMERIC_COMPARATOR(x, y) ((int)((y) - (x)))
|
1937 |
|
|
|
1938 |
|
|
#ifndef SGLIB_MAX_TREE_DEEP
|
1939 |
|
|
#define SGLIB_MAX_TREE_DEEP 128
|
1940 |
|
|
#endif
|
1941 |
|
|
|
1942 |
|
|
#ifndef SGLIB_HASH_TAB_SHIFT_CONSTANT
|
1943 |
|
|
#define SGLIB_HASH_TAB_SHIFT_CONSTANT 211 /* should be a prime */
|
1944 |
|
|
#endif
|
1945 |
|
|
|
1946 |
|
|
#endif /* _SGLIB__h_ */
|