OpenCores
URL https://opencores.org/ocsvn/sc2v/sc2v/trunk

Subversion Repositories sc2v

[/] [sc2v/] [trunk/] [src/] [sglib.h] - Blame information for rev 36

Details | Compare with Previous | View Log

Line No. Rev Author Line
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_ */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.