/*
|
/*
|
|
|
This is SGLIB version 1.0.1
|
This is SGLIB version 1.0.1
|
|
|
(C) by Marian Vittek, Bratislava, http://www.xref-tech.com/sglib, 2003,2004
|
(C) by Marian Vittek, Bratislava, http://www.xref-tech.com/sglib, 2003,2004
|
|
|
License Conditions: You can use this software:
|
License Conditions: You can use this software:
|
- freely for non-commercial purposes,
|
- freely for non-commercial purposes,
|
- or under the terms of the Open Source Software License,
|
- or under the terms of the Open Source Software License,
|
- or under the terms of the GNU Public License.
|
- or under the terms of the GNU Public License.
|
If you wish to receive it under other (commercial) license conditions,
|
If you wish to receive it under other (commercial) license conditions,
|
contact the author.
|
contact the author.
|
|
|
*/
|
*/
|
|
|
|
|
#ifndef _SGLIB__h_
|
#ifndef _SGLIB__h_
|
#define _SGLIB__h_
|
#define _SGLIB__h_
|
|
|
/* the assert is used exclusively to write unexpected error messages */
|
/* the assert is used exclusively to write unexpected error messages */
|
#include <assert.h>
|
#include <assert.h>
|
|
|
|
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* - LEVEL - 0 INTERFACE - */
|
/* - LEVEL - 0 INTERFACE - */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
|
|
|
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ------------------------------ STATIC ARRAYS ------------------------------- */
|
/* ------------------------------ STATIC ARRAYS ------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
|
|
/*
|
/*
|
|
|
Basic algorithms for sorting arrays. Multiple depending arrays can
|
Basic algorithms for sorting arrays. Multiple depending arrays can
|
be rearranged using user defined 'elem_exchangers'
|
be rearranged using user defined 'elem_exchangers'
|
|
|
*/
|
*/
|
|
|
/* HEAP - SORT (level 0) */
|
/* HEAP - SORT (level 0) */
|
|
|
#define SGLIB_ARRAY_SINGLE_HEAP_SORT(type, a, max, comparator) {\
|
#define SGLIB_ARRAY_SINGLE_HEAP_SORT(type, a, max, comparator) {\
|
SGLIB_ARRAY_HEAP_SORT(type, a, max, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\
|
SGLIB_ARRAY_HEAP_SORT(type, a, max, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\
|
}
|
}
|
|
|
#define SGLIB_ARRAY_HEAP_SORT(type, a, max, comparator, elem_exchanger) {\
|
#define SGLIB_ARRAY_HEAP_SORT(type, a, max, comparator, elem_exchanger) {\
|
int _k_;\
|
int _k_;\
|
for(_k_=(max)/2; _k_>=0; _k_--) {\
|
for(_k_=(max)/2; _k_>=0; _k_--) {\
|
SGLIB___ARRAY_HEAP_DOWN(type, a, _k_, max, comparator, elem_exchanger);\
|
SGLIB___ARRAY_HEAP_DOWN(type, a, _k_, max, comparator, elem_exchanger);\
|
}\
|
}\
|
for(_k_=(max)-1; _k_>=0; _k_--) {\
|
for(_k_=(max)-1; _k_>=0; _k_--) {\
|
elem_exchanger(type, a, 0, _k_);\
|
elem_exchanger(type, a, 0, _k_);\
|
SGLIB___ARRAY_HEAP_DOWN(type, a, 0, _k_, comparator, elem_exchanger);\
|
SGLIB___ARRAY_HEAP_DOWN(type, a, 0, _k_, comparator, elem_exchanger);\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB___ARRAY_HEAP_DOWN(type, a, ind, max, comparator, elem_exchanger) {\
|
#define SGLIB___ARRAY_HEAP_DOWN(type, a, ind, max, comparator, elem_exchanger) {\
|
type _t_;\
|
type _t_;\
|
int _m_, _l_, _r_, _i_;\
|
int _m_, _l_, _r_, _i_;\
|
_i_ = (ind);\
|
_i_ = (ind);\
|
_m_ = _i_;\
|
_m_ = _i_;\
|
do {\
|
do {\
|
_i_ = _m_; \
|
_i_ = _m_; \
|
_l_ = 2*_i_+1;\
|
_l_ = 2*_i_+1;\
|
_r_ = _l_+1;\
|
_r_ = _l_+1;\
|
if (_l_ < (max)){\
|
if (_l_ < (max)){\
|
if (comparator(((a)[_m_]), ((a)[_l_])) < 0) _m_ = _l_;\
|
if (comparator(((a)[_m_]), ((a)[_l_])) < 0) _m_ = _l_;\
|
if (_r_ < (max)) {\
|
if (_r_ < (max)) {\
|
if (comparator(((a)[_m_]), ((a)[_r_])) < 0) _m_ = _r_;\
|
if (comparator(((a)[_m_]), ((a)[_r_])) < 0) _m_ = _r_;\
|
}\
|
}\
|
}\
|
}\
|
if (_m_ != _i_) {\
|
if (_m_ != _i_) {\
|
elem_exchanger(type, a, _i_, _m_);\
|
elem_exchanger(type, a, _i_, _m_);\
|
}\
|
}\
|
} while (_m_ != _i_);\
|
} while (_m_ != _i_);\
|
}
|
}
|
|
|
|
|
/* QUICK - SORT (level 0) */
|
/* QUICK - SORT (level 0) */
|
|
|
#define SGLIB_ARRAY_SINGLE_QUICK_SORT(type, a, max, comparator) {\
|
#define SGLIB_ARRAY_SINGLE_QUICK_SORT(type, a, max, comparator) {\
|
SGLIB_ARRAY_QUICK_SORT(type, a, max, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\
|
SGLIB_ARRAY_QUICK_SORT(type, a, max, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\
|
}
|
}
|
|
|
#define SGLIB_ARRAY_QUICK_SORT(type, a, max, comparator, elem_exchanger) {\
|
#define SGLIB_ARRAY_QUICK_SORT(type, a, max, comparator, elem_exchanger) {\
|
int _i_, _j_, _p_, _stacki_, _start_, _end_;\
|
int _i_, _j_, _p_, _stacki_, _start_, _end_;\
|
/* can sort up to 2^64 elements */\
|
/* can sort up to 2^64 elements */\
|
int _startStack_[64]; \
|
int _startStack_[64]; \
|
int _endStack_[64];\
|
int _endStack_[64];\
|
type _tmp_;\
|
type _tmp_;\
|
_startStack_[0] = 0;\
|
_startStack_[0] = 0;\
|
_endStack_[0] = (max);\
|
_endStack_[0] = (max);\
|
_stacki_ = 1;\
|
_stacki_ = 1;\
|
while (_stacki_ > 0) {\
|
while (_stacki_ > 0) {\
|
_stacki_ --;\
|
_stacki_ --;\
|
_start_ = _startStack_[_stacki_];\
|
_start_ = _startStack_[_stacki_];\
|
_end_ = _endStack_[_stacki_];\
|
_end_ = _endStack_[_stacki_];\
|
while (_end_ - _start_ > 2) {\
|
while (_end_ - _start_ > 2) {\
|
_p_ = _start_;\
|
_p_ = _start_;\
|
_i_ = _start_ + 1;\
|
_i_ = _start_ + 1;\
|
_j_ = _end_ - 1;\
|
_j_ = _end_ - 1;\
|
while (_i_<_j_) {\
|
while (_i_<_j_) {\
|
for(; _i_<=_j_ && comparator(((a)[_i_]),((a)[_p_]))<=0; _i_++) ;\
|
for(; _i_<=_j_ && comparator(((a)[_i_]),((a)[_p_]))<=0; _i_++) ;\
|
if (_i_ > _j_) {\
|
if (_i_ > _j_) {\
|
/* all remaining elements lesseq than pivot */\
|
/* all remaining elements lesseq than pivot */\
|
elem_exchanger(type, a, _j_, _p_);\
|
elem_exchanger(type, a, _j_, _p_);\
|
_i_ = _j_;\
|
_i_ = _j_;\
|
} else {\
|
} else {\
|
for(; _i_<=_j_ && comparator(((a)[_j_]),((a)[_p_]))>=0; _j_--) ;\
|
for(; _i_<=_j_ && comparator(((a)[_j_]),((a)[_p_]))>=0; _j_--) ;\
|
if (_i_ > _j_) {\
|
if (_i_ > _j_) {\
|
/* all remaining elements greater than pivot */\
|
/* all remaining elements greater than pivot */\
|
elem_exchanger(type, a, _j_, _p_);\
|
elem_exchanger(type, a, _j_, _p_);\
|
_i_ = _j_;\
|
_i_ = _j_;\
|
} else if (_i_ < _j_) {\
|
} else if (_i_ < _j_) {\
|
elem_exchanger(type, a, _i_, _j_);\
|
elem_exchanger(type, a, _i_, _j_);\
|
if (_i_+2 < _j_) {_i_++; _j_--;}\
|
if (_i_+2 < _j_) {_i_++; _j_--;}\
|
else if (_i_+1 < _j_) _i_++;\
|
else if (_i_+1 < _j_) _i_++;\
|
}\
|
}\
|
}\
|
}\
|
}\
|
}\
|
/* O.K. i==j and pivot is on a[i] == a[j] */\
|
/* O.K. i==j and pivot is on a[i] == a[j] */\
|
/* handle recursive calls without recursion */\
|
/* handle recursive calls without recursion */\
|
if (_i_-_start_ > 1 && _end_-_j_ > 1) {\
|
if (_i_-_start_ > 1 && _end_-_j_ > 1) {\
|
/* two recursive calls, use array-stack */\
|
/* two recursive calls, use array-stack */\
|
if (_i_-_start_ < _end_-_j_-1) {\
|
if (_i_-_start_ < _end_-_j_-1) {\
|
_startStack_[_stacki_] = _j_+1;\
|
_startStack_[_stacki_] = _j_+1;\
|
_endStack_[_stacki_] = _end_;\
|
_endStack_[_stacki_] = _end_;\
|
_stacki_ ++;\
|
_stacki_ ++;\
|
_end_ = _i_;\
|
_end_ = _i_;\
|
} else {\
|
} else {\
|
_startStack_[_stacki_] = _start_;\
|
_startStack_[_stacki_] = _start_;\
|
_endStack_[_stacki_] = _i_;\
|
_endStack_[_stacki_] = _i_;\
|
_stacki_ ++;\
|
_stacki_ ++;\
|
_start_ = _j_+1;\
|
_start_ = _j_+1;\
|
}\
|
}\
|
} else {\
|
} else {\
|
if (_i_-_start_ > 1) {\
|
if (_i_-_start_ > 1) {\
|
_end_ = _i_;\
|
_end_ = _i_;\
|
} else {\
|
} else {\
|
_start_ = _j_+1;\
|
_start_ = _j_+1;\
|
}\
|
}\
|
}\
|
}\
|
}\
|
}\
|
if (_end_ - _start_ == 2) {\
|
if (_end_ - _start_ == 2) {\
|
if (comparator(((a)[_start_]),((a)[_end_-1])) > 0) {\
|
if (comparator(((a)[_start_]),((a)[_end_-1])) > 0) {\
|
elem_exchanger(type, a, _start_, _end_-1);\
|
elem_exchanger(type, a, _start_, _end_-1);\
|
}\
|
}\
|
}\
|
}\
|
}\
|
}\
|
}
|
}
|
|
|
/* BINARY SEARCH (level 0) */
|
/* BINARY SEARCH (level 0) */
|
|
|
#define SGLIB_ARRAY_BINARY_SEARCH(type, a, start_index, end_index, key, comparator, found, result_index) {\
|
#define SGLIB_ARRAY_BINARY_SEARCH(type, a, start_index, end_index, key, comparator, found, result_index) {\
|
int _kk_, _cc_, _ii_, _jj_, _ff_;\
|
int _kk_, _cc_, _ii_, _jj_, _ff_;\
|
_ii_ = (start_index); \
|
_ii_ = (start_index); \
|
_jj_ = (end_index);\
|
_jj_ = (end_index);\
|
_ff_ = 0;\
|
_ff_ = 0;\
|
while (_ii_ <= _jj_ && _ff_==0) {\
|
while (_ii_ <= _jj_ && _ff_==0) {\
|
_kk_ = (_jj_+_ii_)/2;\
|
_kk_ = (_jj_+_ii_)/2;\
|
_cc_ = comparator(((a)[_kk_]), (key));\
|
_cc_ = comparator(((a)[_kk_]), (key));\
|
if (_cc_ == 0) {\
|
if (_cc_ == 0) {\
|
(result_index) = _kk_; \
|
(result_index) = _kk_; \
|
_ff_ = 1;\
|
_ff_ = 1;\
|
} else if (_cc_ < 0) {\
|
} else if (_cc_ < 0) {\
|
_ii_ = _kk_+1;\
|
_ii_ = _kk_+1;\
|
} else {\
|
} else {\
|
_jj_ = _kk_-1;\
|
_jj_ = _kk_-1;\
|
}\
|
}\
|
}\
|
}\
|
if (_ff_ == 0) {\
|
if (_ff_ == 0) {\
|
/* not found, but set its resulting place in the array */\
|
/* not found, but set its resulting place in the array */\
|
(result_index) = _jj_+1;\
|
(result_index) = _jj_+1;\
|
}\
|
}\
|
(found) = _ff_;\
|
(found) = _ff_;\
|
}
|
}
|
|
|
/* -------------------------------- queue (in an array) ------------------ */
|
/* -------------------------------- queue (in an array) ------------------ */
|
/* queue is a quadruple (a,i,j,dim) such that: */
|
/* queue is a quadruple (a,i,j,dim) such that: */
|
/* a is the array storing values */
|
/* a is the array storing values */
|
/* i is the index of the first used element in the array */
|
/* i is the index of the first used element in the array */
|
/* j is the index of the first free element in the array */
|
/* j is the index of the first free element in the array */
|
/* dim is the size of the array a */
|
/* dim is the size of the array a */
|
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */
|
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */
|
|
|
#define SGLIB_QUEUE_INIT(type, a, i, j) { i = j = 0; }
|
#define SGLIB_QUEUE_INIT(type, a, i, j) { i = j = 0; }
|
#define SGLIB_QUEUE_IS_EMPTY(type, a, i, j) ((i)==(j))
|
#define SGLIB_QUEUE_IS_EMPTY(type, a, i, j) ((i)==(j))
|
#define SGLIB_QUEUE_IS_FULL(type, a, i, j, dim) ((i)==((j)+1)%(dim))
|
#define SGLIB_QUEUE_IS_FULL(type, a, i, j, dim) ((i)==((j)+1)%(dim))
|
#define SGLIB_QUEUE_FIRST_ELEMENT(type, a, i, j) (a[i])
|
#define SGLIB_QUEUE_FIRST_ELEMENT(type, a, i, j) (a[i])
|
#define SGLIB_QUEUE_ADD_NEXT(type, a, i, j, dim) {\
|
#define SGLIB_QUEUE_ADD_NEXT(type, a, i, j, dim) {\
|
if (SGLIB_QUEUE_IS_FULL(type, a, i, j, dim)) assert(0 && "the queue is full");\
|
if (SGLIB_QUEUE_IS_FULL(type, a, i, j, dim)) assert(0 && "the queue is full");\
|
(j) = ((j)+1) % (dim);\
|
(j) = ((j)+1) % (dim);\
|
}
|
}
|
#define SGLIB_QUEUE_ADD(type, a, elem, i, j, dim) {\
|
#define SGLIB_QUEUE_ADD(type, a, elem, i, j, dim) {\
|
a[j] = (elem);\
|
a[j] = (elem);\
|
SGLIB_QUEUE_ADD_NEXT(type, a, i, j, dim);\
|
SGLIB_QUEUE_ADD_NEXT(type, a, i, j, dim);\
|
}
|
}
|
#define SGLIB_QUEUE_DELETE_FIRST(type, a, i, j, dim) {\
|
#define SGLIB_QUEUE_DELETE_FIRST(type, a, i, j, dim) {\
|
if (SGLIB_QUEUE_IS_EMPTY(type, a, i, j)) assert(0 && "the queue is empty");\
|
if (SGLIB_QUEUE_IS_EMPTY(type, a, i, j)) assert(0 && "the queue is empty");\
|
(i) = ((i)+1) % (dim);\
|
(i) = ((i)+1) % (dim);\
|
}
|
}
|
#define SGLIB_QUEUE_DELETE(type, a, i, j, dim) {\
|
#define SGLIB_QUEUE_DELETE(type, a, i, j, dim) {\
|
SGLIB_QUEUE_DELETE_FIRST(type, a, i, j, dim);\
|
SGLIB_QUEUE_DELETE_FIRST(type, a, i, j, dim);\
|
}
|
}
|
|
|
/* ----------------- priority queue (heap) (in an array) -------------------- */
|
/* ----------------- priority queue (heap) (in an array) -------------------- */
|
/* heap is a triple (a,i,dim) such that: */
|
/* heap is a triple (a,i,dim) such that: */
|
/* a is the array storing values */
|
/* a is the array storing values */
|
/* i is the index of the first free element in the array */
|
/* i is the index of the first free element in the array */
|
/* dim is the size of the array a */
|
/* dim is the size of the array a */
|
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */
|
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */
|
|
|
#define SGLIB_HEAP_INIT(type, a, i) { i = 0; }
|
#define SGLIB_HEAP_INIT(type, a, i) { i = 0; }
|
#define SGLIB_HEAP_IS_EMPTY(type, a, i) ((i)==0)
|
#define SGLIB_HEAP_IS_EMPTY(type, a, i) ((i)==0)
|
#define SGLIB_HEAP_IS_FULL(type, a, i, dim) ((i)==(dim))
|
#define SGLIB_HEAP_IS_FULL(type, a, i, dim) ((i)==(dim))
|
#define SGLIB_HEAP_FIRST_ELEMENT(type, a, i) (a[0])
|
#define SGLIB_HEAP_FIRST_ELEMENT(type, a, i) (a[0])
|
#define SGLIB_HEAP_ADD_NEXT(type, a, i, dim, comparator, elem_exchanger) {\
|
#define SGLIB_HEAP_ADD_NEXT(type, a, i, dim, comparator, elem_exchanger) {\
|
int _i_;\
|
int _i_;\
|
if (SGLIB_HEAP_IS_FULL(type, a, i, dim)) assert(0 && "the heap is full");\
|
if (SGLIB_HEAP_IS_FULL(type, a, i, dim)) assert(0 && "the heap is full");\
|
_i_ = (i)++;\
|
_i_ = (i)++;\
|
while (_i_ > 0 && comparator(a[_i_/2], a[_i_]) < 0) {\
|
while (_i_ > 0 && comparator(a[_i_/2], a[_i_]) < 0) {\
|
elem_exchanger(type, a, (_i_/2), _i_);\
|
elem_exchanger(type, a, (_i_/2), _i_);\
|
_i_ = _i_/2;\
|
_i_ = _i_/2;\
|
}\
|
}\
|
}
|
}
|
#define SGLIB_HEAP_ADD(type, a, elem, i, dim, comparator) {\
|
#define SGLIB_HEAP_ADD(type, a, elem, i, dim, comparator) {\
|
if (SGLIB_HEAP_IS_FULL(type, a, i, dim)) assert(0 && "the heap is full");\
|
if (SGLIB_HEAP_IS_FULL(type, a, i, dim)) assert(0 && "the heap is full");\
|
a[i] = (elem);\
|
a[i] = (elem);\
|
SGLIB_HEAP_ADD_NEXT(type, a, i, dim, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\
|
SGLIB_HEAP_ADD_NEXT(type, a, i, dim, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\
|
}
|
}
|
#define SGLIB_HEAP_DELETE_FIRST(type, a, i, dim, comparator, elem_exchanger) {\
|
#define SGLIB_HEAP_DELETE_FIRST(type, a, i, dim, comparator, elem_exchanger) {\
|
if (SGLIB_HEAP_IS_EMPTY(type, a, i)) assert(0 && "the heap is empty");\
|
if (SGLIB_HEAP_IS_EMPTY(type, a, i)) assert(0 && "the heap is empty");\
|
(i)--;\
|
(i)--;\
|
a[0] = a[i];\
|
a[0] = a[i];\
|
SGLIB___ARRAY_HEAP_DOWN(type, a, 0, i, comparator, elem_exchanger);\
|
SGLIB___ARRAY_HEAP_DOWN(type, a, 0, i, comparator, elem_exchanger);\
|
}
|
}
|
#define SGLIB_HEAP_DELETE(type, a, i, dim, comparator) {\
|
#define SGLIB_HEAP_DELETE(type, a, i, dim, comparator) {\
|
SGLIB_HEAP_DELETE_FIRST(type, a, i, dim, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\
|
SGLIB_HEAP_DELETE_FIRST(type, a, i, dim, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\
|
}
|
}
|
|
|
|
|
/* ----------------- hashed table of pointers (in an array) -------------------- */
|
/* ----------------- hashed table of pointers (in an array) -------------------- */
|
|
|
/*
|
/*
|
|
|
This hashed table is storing pointers to objects (not containers).
|
This hashed table is storing pointers to objects (not containers).
|
In this table there is a one-to-one mapping between 'objects' stored
|
In this table there is a one-to-one mapping between 'objects' stored
|
in the table and indexes where they are placed. Each index is
|
in the table and indexes where they are placed. Each index is
|
pointing to exactly one 'object' and each 'object' stored in the
|
pointing to exactly one 'object' and each 'object' stored in the
|
table occurs on exactly one index. Once an object is stored in the
|
table occurs on exactly one index. Once an object is stored in the
|
table, it can be represented via its index.
|
table, it can be represented via its index.
|
|
|
In case of collision while adding an object the index shifted
|
In case of collision while adding an object the index shifted
|
by SGLIB_HASH_TAB_SHIFT_CONSTANT (constant can be redefined)
|
by SGLIB_HASH_TAB_SHIFT_CONSTANT (constant can be redefined)
|
|
|
You can NOT delete an element from such hash table. The only
|
You can NOT delete an element from such hash table. The only
|
justification (I can see) for this data structure is an exchange
|
justification (I can see) for this data structure is an exchange
|
file format, having an index table at the beginning and then
|
file format, having an index table at the beginning and then
|
refering objects via indexes.
|
refering objects via indexes.
|
|
|
!!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!!
|
!!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!!
|
|
|
*/
|
*/
|
|
|
#define SGLIB_HASH_TAB_INIT(type, table, dim) {\
|
#define SGLIB_HASH_TAB_INIT(type, table, dim) {\
|
int _i_;\
|
int _i_;\
|
for(_i_ = 0; _i_ < (dim); _i_++) (table)[_i_] = NULL;\
|
for(_i_ = 0; _i_ < (dim); _i_++) (table)[_i_] = NULL;\
|
}
|
}
|
|
|
#define SGLIB_HASH_TAB_ADD_IF_NOT_MEMBER(type, table, dim, elem, hash_function, comparator, member){\
|
#define SGLIB_HASH_TAB_ADD_IF_NOT_MEMBER(type, table, dim, elem, hash_function, comparator, member){\
|
unsigned _pos_;\
|
unsigned _pos_;\
|
type *_elem_;\
|
type *_elem_;\
|
SGLIB_HASH_TAB_FIND_MEMBER(type, table, dim, elem, _pos_, _elem_);\
|
SGLIB_HASH_TAB_FIND_MEMBER(type, table, dim, elem, _pos_, _elem_);\
|
(member) = (table)[_pos_];\
|
(member) = (table)[_pos_];\
|
if (_elem_ == NULL) {\
|
if (_elem_ == NULL) {\
|
if ((table)[_pos_] != NULL) assert(0 && "the hash table is full");\
|
if ((table)[_pos_] != NULL) assert(0 && "the hash table is full");\
|
(table)[_pos_] = (elem);\
|
(table)[_pos_] = (elem);\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_HASH_TAB_FIND_MEMBER(type, table, dim, elem, hash_function, comparator, resultIndex, resultMember) {\
|
#define SGLIB_HASH_TAB_FIND_MEMBER(type, table, dim, elem, hash_function, comparator, resultIndex, resultMember) {\
|
unsigned _i_;\
|
unsigned _i_;\
|
int _count_;\
|
int _count_;\
|
type *_e_;\
|
type *_e_;\
|
_count = 0;\
|
_count = 0;\
|
_i_ = hash_function(elem);\
|
_i_ = hash_function(elem);\
|
_i_ %= (dim);\
|
_i_ %= (dim);\
|
while ((_e_=(table)[_i_])!=NULL && comparator(_e_, (elem))!=0 && _count_<(dim)) {\
|
while ((_e_=(table)[_i_])!=NULL && comparator(_e_, (elem))!=0 && _count_<(dim)) {\
|
_count_ ++;\
|
_count_ ++;\
|
_i_ = (_i_ + SGLIB_HASH_TAB_SHIFT_CONSTANT) % (dim);\
|
_i_ = (_i_ + SGLIB_HASH_TAB_SHIFT_CONSTANT) % (dim);\
|
}\
|
}\
|
(resultIndex) = _i_;\
|
(resultIndex) = _i_;\
|
if (_count_ < (dim)) (resultMember) = _e_;\
|
if (_count_ < (dim)) (resultMember) = _e_;\
|
else (resultMember) = NULL;\
|
else (resultMember) = NULL;\
|
}
|
}
|
|
|
#define SGLIB_HASH_TAB_IS_MEMBER(type, table, dim, elem, hash_function, resultIndex) {\
|
#define SGLIB_HASH_TAB_IS_MEMBER(type, table, dim, elem, hash_function, resultIndex) {\
|
unsigned _i_;\
|
unsigned _i_;\
|
int _c_;\
|
int _c_;\
|
type *_e_;\
|
type *_e_;\
|
_count = 0;\
|
_count = 0;\
|
_i_ = hash_function(elem);\
|
_i_ = hash_function(elem);\
|
_i_ %= (dim);\
|
_i_ %= (dim);\
|
while ((_e_=(table)[_i_])!=NULL && _e_!=(elem) && _c_<(dim)) {\
|
while ((_e_=(table)[_i_])!=NULL && _e_!=(elem) && _c_<(dim)) {\
|
_c_ ++;\
|
_c_ ++;\
|
_i_ = (_i_ + SGLIB_HASH_TAB_SHIFT_CONSTANT) % (dim);\
|
_i_ = (_i_ + SGLIB_HASH_TAB_SHIFT_CONSTANT) % (dim);\
|
}\
|
}\
|
if (_e_==(elem)) (resultIndex) = _i_;\
|
if (_e_==(elem)) (resultIndex) = _i_;\
|
else (resultIndex) = -1;\
|
else (resultIndex) = -1;\
|
}
|
}
|
|
|
#define SGLIB_HASH_TAB_MAP_ON_ELEMENTS(type, table, dim, iteratedIndex, iteratedVariable, command) {\
|
#define SGLIB_HASH_TAB_MAP_ON_ELEMENTS(type, table, dim, iteratedIndex, iteratedVariable, command) {\
|
unsigned iteratedIndex;\
|
unsigned iteratedIndex;\
|
type *iteratedVariable;\
|
type *iteratedVariable;\
|
for(iteratedIndex=0; iteratedIndex < (dim); iteratedIndex++) {\
|
for(iteratedIndex=0; iteratedIndex < (dim); iteratedIndex++) {\
|
iteratedVariable = (table)[iteratedIndex];\
|
iteratedVariable = (table)[iteratedIndex];\
|
if (iteratedVariable != NULL) {command;}\
|
if (iteratedVariable != NULL) {command;}\
|
}\
|
}\
|
}
|
}
|
|
|
|
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ------------------------- DYNAMIC DATA STRUCTURES -------------------------- */
|
/* ------------------------- DYNAMIC DATA STRUCTURES -------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
|
|
/* ------------------------------------ lists (level 0) --------------------- */
|
/* ------------------------------------ lists (level 0) --------------------- */
|
|
|
#define SGLIB_LIST_ADD(type, list, elem, next) {\
|
#define SGLIB_LIST_ADD(type, list, elem, next) {\
|
(elem)->next = (list);\
|
(elem)->next = (list);\
|
(list) = (elem);\
|
(list) = (elem);\
|
}
|
}
|
|
|
#define SGLIB_LIST_CONCAT(type, first, second, next) {\
|
#define SGLIB_LIST_CONCAT(type, first, second, next) {\
|
if ((first)==NULL) {\
|
if ((first)==NULL) {\
|
(first) = (second);\
|
(first) = (second);\
|
} else {\
|
} else {\
|
type *_p_;\
|
type *_p_;\
|
for(_p_ = (first); _p_->next!=NULL; _p_=_p_->next) ;\
|
for(_p_ = (first); _p_->next!=NULL; _p_=_p_->next) ;\
|
_p_->next = (second);\
|
_p_->next = (second);\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_LIST_DELETE(type, list, elem, next) {\
|
#define SGLIB_LIST_DELETE(type, list, elem, next) {\
|
type **_p_;\
|
type **_p_;\
|
for(_p_ = &(list); *_p_!=NULL && *_p_!=(elem); _p_= &(*_p_)->next) ;\
|
for(_p_ = &(list); *_p_!=NULL && *_p_!=(elem); _p_= &(*_p_)->next) ;\
|
assert(*_p_!=NULL && "element is not member of the container, use DELETE_IF_MEMBER instead"!=NULL);\
|
assert(*_p_!=NULL && "element is not member of the container, use DELETE_IF_MEMBER instead"!=NULL);\
|
*_p_ = (*_p_)->next;\
|
*_p_ = (*_p_)->next;\
|
}
|
}
|
|
|
#define SGLIB_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, next, member) {\
|
#define SGLIB_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, next, member) {\
|
type *_p_;\
|
type *_p_;\
|
for(_p_ = (list); _p_!=NULL && comparator(_p_, (elem)) != 0; _p_= _p_->next) ;\
|
for(_p_ = (list); _p_!=NULL && comparator(_p_, (elem)) != 0; _p_= _p_->next) ;\
|
(member) = _p_;\
|
(member) = _p_;\
|
if (_p_ == NULL) {\
|
if (_p_ == NULL) {\
|
SGLIB_LIST_ADD(type, list, elem, next);\
|
SGLIB_LIST_ADD(type, list, elem, next);\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, next, member) {\
|
#define SGLIB_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, next, member) {\
|
type **_p_;\
|
type **_p_;\
|
for(_p_ = &(list); *_p_!=NULL && comparator((*_p_), (elem)) != 0; _p_= &(*_p_)->next) ;\
|
for(_p_ = &(list); *_p_!=NULL && comparator((*_p_), (elem)) != 0; _p_= &(*_p_)->next) ;\
|
(member) = *_p_;\
|
(member) = *_p_;\
|
if (*_p_ != NULL) {\
|
if (*_p_ != NULL) {\
|
*_p_ = (*_p_)->next;\
|
*_p_ = (*_p_)->next;\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_LIST_IS_MEMBER(type, list, elem, next, result) {\
|
#define SGLIB_LIST_IS_MEMBER(type, list, elem, next, result) {\
|
type *_p_;\
|
type *_p_;\
|
for(_p_ = (list); _p_!=NULL && _p_ != (elem); _p_= _p_->next) ;\
|
for(_p_ = (list); _p_!=NULL && _p_ != (elem); _p_= _p_->next) ;\
|
(result) = (_p_!=NULL);\
|
(result) = (_p_!=NULL);\
|
}
|
}
|
|
|
#define SGLIB_LIST_FIND_MEMBER(type, list, elem, comparator, next, member) {\
|
#define SGLIB_LIST_FIND_MEMBER(type, list, elem, comparator, next, member) {\
|
type *_p_;\
|
type *_p_;\
|
for(_p_ = (list); _p_!=NULL && comparator(_p_, (elem)) != 0; _p_= _p_->next) ;\
|
for(_p_ = (list); _p_!=NULL && comparator(_p_, (elem)) != 0; _p_= _p_->next) ;\
|
(member) = _p_;\
|
(member) = _p_;\
|
}
|
}
|
|
|
#define SGLIB_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, next, command) {\
|
#define SGLIB_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, next, command) {\
|
type *_ne_;\
|
type *_ne_;\
|
type *iteratedVariable;\
|
type *iteratedVariable;\
|
(iteratedVariable) = (list); \
|
(iteratedVariable) = (list); \
|
while ((iteratedVariable)!=NULL) {\
|
while ((iteratedVariable)!=NULL) {\
|
_ne_ = (iteratedVariable)->next;\
|
_ne_ = (iteratedVariable)->next;\
|
{command;};\
|
{command;};\
|
(iteratedVariable) = _ne_;\
|
(iteratedVariable) = _ne_;\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_LIST_LEN(type, list, next, result) {\
|
#define SGLIB_LIST_LEN(type, list, next, result) {\
|
type *_ce_;\
|
type *_ce_;\
|
(result) = 0;\
|
(result) = 0;\
|
SGLIB_LIST_MAP_ON_ELEMENTS(type, list, _ce_, next, (result)++);\
|
SGLIB_LIST_MAP_ON_ELEMENTS(type, list, _ce_, next, (result)++);\
|
}
|
}
|
|
|
#define SGLIB_LIST_REVERSE(type, list, next) {\
|
#define SGLIB_LIST_REVERSE(type, list, next) {\
|
type *_list_,*_tmp_,*_res_;\
|
type *_list_,*_tmp_,*_res_;\
|
_list_ = (list);\
|
_list_ = (list);\
|
_res_ = NULL;\
|
_res_ = NULL;\
|
while (_list_!=NULL) {\
|
while (_list_!=NULL) {\
|
_tmp_ = _list_->next; _list_->next = _res_;\
|
_tmp_ = _list_->next; _list_->next = _res_;\
|
_res_ = _list_; _list_ = _tmp_;\
|
_res_ = _list_; _list_ = _tmp_;\
|
}\
|
}\
|
(list) = _res_;\
|
(list) = _res_;\
|
}
|
}
|
|
|
#define SGLIB_LIST_SORT(type, list, comparator, next) {\
|
#define SGLIB_LIST_SORT(type, list, comparator, next) {\
|
/* a non-recursive merge sort on lists */\
|
/* a non-recursive merge sort on lists */\
|
type *_r_;\
|
type *_r_;\
|
type *_a_, *_b_, *_todo_, *_t_, **_restail_;\
|
type *_a_, *_b_, *_todo_, *_t_, **_restail_;\
|
int _i_, _n_, _contFlag_;\
|
int _i_, _n_, _contFlag_;\
|
_r_ = (list);\
|
_r_ = (list);\
|
_contFlag_ = 1;\
|
_contFlag_ = 1;\
|
for(_n_ = 1; _contFlag_; _n_ = _n_+_n_) {\
|
for(_n_ = 1; _contFlag_; _n_ = _n_+_n_) {\
|
_todo_ = _r_; _r_ = NULL; _restail_ = &_r_; _contFlag_ =0;\
|
_todo_ = _r_; _r_ = NULL; _restail_ = &_r_; _contFlag_ =0;\
|
while (_todo_!=NULL) {\
|
while (_todo_!=NULL) {\
|
_a_ = _todo_;\
|
_a_ = _todo_;\
|
for(_i_ = 1, _t_ = _a_; _i_ < _n_ && _t_!=NULL; _i_++, _t_ = _t_->next) ;\
|
for(_i_ = 1, _t_ = _a_; _i_ < _n_ && _t_!=NULL; _i_++, _t_ = _t_->next) ;\
|
if (_t_ ==NULL) {\
|
if (_t_ ==NULL) {\
|
*_restail_ = _a_;\
|
*_restail_ = _a_;\
|
break;\
|
break;\
|
}\
|
}\
|
_b_ = _t_->next; _t_->next=NULL;\
|
_b_ = _t_->next; _t_->next=NULL;\
|
for(_i_ =1, _t_ = _b_; _i_<_n_ && _t_!=NULL; _i_++, _t_ = _t_->next) ;\
|
for(_i_ =1, _t_ = _b_; _i_<_n_ && _t_!=NULL; _i_++, _t_ = _t_->next) ;\
|
if (_t_ ==NULL) {\
|
if (_t_ ==NULL) {\
|
_todo_ =NULL;\
|
_todo_ =NULL;\
|
} else {\
|
} else {\
|
_todo_ = _t_->next; _t_->next=NULL;\
|
_todo_ = _t_->next; _t_->next=NULL;\
|
}\
|
}\
|
/* merge */\
|
/* merge */\
|
while (_a_!=NULL && _b_!=NULL) {\
|
while (_a_!=NULL && _b_!=NULL) {\
|
if (comparator(_a_, _b_) < 0) {\
|
if (comparator(_a_, _b_) < 0) {\
|
*_restail_ = _a_; _restail_ = &(_a_->next); _a_ = _a_->next;\
|
*_restail_ = _a_; _restail_ = &(_a_->next); _a_ = _a_->next;\
|
} else {\
|
} else {\
|
*_restail_ = _b_; _restail_ = &(_b_->next); _b_ = _b_->next;\
|
*_restail_ = _b_; _restail_ = &(_b_->next); _b_ = _b_->next;\
|
}\
|
}\
|
}\
|
}\
|
if (_a_!=NULL) *_restail_ = _a_;\
|
if (_a_!=NULL) *_restail_ = _a_;\
|
else *_restail_ = _b_;\
|
else *_restail_ = _b_;\
|
while (*_restail_!=NULL) _restail_ = &((*_restail_)->next);\
|
while (*_restail_!=NULL) _restail_ = &((*_restail_)->next);\
|
_contFlag_ =1;\
|
_contFlag_ =1;\
|
}\
|
}\
|
}\
|
}\
|
(list) = _r_;\
|
(list) = _r_;\
|
}
|
}
|
|
|
/* --------------------------------- sorted list (level 0) --------------------- */
|
/* --------------------------------- sorted list (level 0) --------------------- */
|
/*
|
/*
|
All operations suppose that the list is sorted and they preserve
|
All operations suppose that the list is sorted and they preserve
|
this property.
|
this property.
|
*/
|
*/
|
|
|
|
|
#define SGLIB_SORTED_LIST_ADD(type, list, elem, comparator, next) {\
|
#define SGLIB_SORTED_LIST_ADD(type, list, elem, comparator, next) {\
|
type **_e_;\
|
type **_e_;\
|
int _cmpres_;\
|
int _cmpres_;\
|
SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, _cmpres_, _e_);\
|
SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, _cmpres_, _e_);\
|
(elem)->next = *_e_;\
|
(elem)->next = *_e_;\
|
*_e_ = (elem);\
|
*_e_ = (elem);\
|
}
|
}
|
|
|
#define SGLIB_SORTED_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, next, member) {\
|
#define SGLIB_SORTED_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, next, member) {\
|
type **_e_;\
|
type **_e_;\
|
int _cmp_res_;\
|
int _cmp_res_;\
|
SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, _cmp_res_, _e_);\
|
SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, _cmp_res_, _e_);\
|
if (_cmp_res_ != 0) {\
|
if (_cmp_res_ != 0) {\
|
(elem)->next = *_e_;\
|
(elem)->next = *_e_;\
|
*_e_ = (elem);\
|
*_e_ = (elem);\
|
(member) = NULL;\
|
(member) = NULL;\
|
} else {\
|
} else {\
|
(member) = *_e_;\
|
(member) = *_e_;\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_SORTED_LIST_DELETE(type, list, elem, next) {\
|
#define SGLIB_SORTED_LIST_DELETE(type, list, elem, next) {\
|
SGLIB_LIST_DELETE(type, list, elem, next);\
|
SGLIB_LIST_DELETE(type, list, elem, next);\
|
}
|
}
|
|
|
#define SGLIB_SORTED_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, next, member) {\
|
#define SGLIB_SORTED_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, next, member) {\
|
type **_e_;\
|
type **_e_;\
|
int _cmp_res_;\
|
int _cmp_res_;\
|
SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, _cmp_res_, _e_);\
|
SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, _cmp_res_, _e_);\
|
if (_cmp_res_ == 0) {\
|
if (_cmp_res_ == 0) {\
|
(member) = *_e_;\
|
(member) = *_e_;\
|
*_e_ = (*_e_)->next;\
|
*_e_ = (*_e_)->next;\
|
} else {\
|
} else {\
|
(member) = NULL;\
|
(member) = NULL;\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_SORTED_LIST_FIND_MEMBER(type, list, elem, comparator, next, member) {\
|
#define SGLIB_SORTED_LIST_FIND_MEMBER(type, list, elem, comparator, next, member) {\
|
type *_p_;\
|
type *_p_;\
|
int _cmpres_;\
|
int _cmpres_;\
|
for(_p_ = (list); _p_!=NULL && (_cmpres_=comparator(_p_, (elem))) < 0; _p_=_p_->next) ;\
|
for(_p_ = (list); _p_!=NULL && (_cmpres_=comparator(_p_, (elem))) < 0; _p_=_p_->next) ;\
|
if (_cmpres_ != 0) (member) = NULL;\
|
if (_cmpres_ != 0) (member) = NULL;\
|
else (member) = _p_;\
|
else (member) = _p_;\
|
}
|
}
|
|
|
#define SGLIB_SORTED_LIST_IS_MEMBER(type, list, elem, comparator, next, result) {\
|
#define SGLIB_SORTED_LIST_IS_MEMBER(type, list, elem, comparator, next, result) {\
|
type *_p_;\
|
type *_p_;\
|
int _cmpres_;\
|
int _cmpres_;\
|
for(_p_ = (list); _p_!=NULL && (_cmpres_=comparator(_p_, (elem))) < 0; _p_=_p_->next) ;\
|
for(_p_ = (list); _p_!=NULL && (_cmpres_=comparator(_p_, (elem))) < 0; _p_=_p_->next) ;\
|
while (_p_ != NULL && _p_ != (elem) && (_cmpres_ = comparator(_p_, (elem))) == 0) _p_=_p_->next;\
|
while (_p_ != NULL && _p_ != (elem) && (_cmpres_ = comparator(_p_, (elem))) == 0) _p_=_p_->next;\
|
(result) = (_p_ == (elem));\
|
(result) = (_p_ == (elem));\
|
}
|
}
|
|
|
#define SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, comparator_result, member_ptr) {\
|
#define SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, comparator_result, member_ptr) {\
|
for((member_ptr) = &(list); \
|
for((member_ptr) = &(list); \
|
*(member_ptr)!=NULL && ((comparator_result)=comparator((*member_ptr), (elem))) < 0; \
|
*(member_ptr)!=NULL && ((comparator_result)=comparator((*member_ptr), (elem))) < 0; \
|
(member_ptr) = &(*(member_ptr))->next) ;\
|
(member_ptr) = &(*(member_ptr))->next) ;\
|
if (*(member_ptr) == NULL) (comparator_result) = -1;\
|
if (*(member_ptr) == NULL) (comparator_result) = -1;\
|
}
|
}
|
|
|
#define SGLIB_SORTED_LIST_LEN(type, list, next, result) {\
|
#define SGLIB_SORTED_LIST_LEN(type, list, next, result) {\
|
SGLIB_LIST_LEN(type, list, next, result);\
|
SGLIB_LIST_LEN(type, list, next, result);\
|
}
|
}
|
|
|
#define SGLIB_SORTED_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, next, command) {\
|
#define SGLIB_SORTED_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, next, command) {\
|
SGLIB_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, next, command);\
|
SGLIB_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, next, command);\
|
}
|
}
|
|
|
|
|
/* ------------------------------- double linked list (level 0) ------------------------- */
|
/* ------------------------------- double linked list (level 0) ------------------------- */
|
/*
|
/*
|
Lists with back pointer to previous element. Those lists implements deletion
|
Lists with back pointer to previous element. Those lists implements deletion
|
of an element in a constant time.
|
of an element in a constant time.
|
*/
|
*/
|
|
|
#define SGLIB___DL_LIST_CREATE_SINGLETON(type, list, elem, previous, next) {\
|
#define SGLIB___DL_LIST_CREATE_SINGLETON(type, list, elem, previous, next) {\
|
(list) = (elem);\
|
(list) = (elem);\
|
(list)->next = (list)->previous = NULL;\
|
(list)->next = (list)->previous = NULL;\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_ADD_AFTER(type, place, elem, previous, next) {\
|
#define SGLIB_DL_LIST_ADD_AFTER(type, place, elem, previous, next) {\
|
if ((place) == NULL) {\
|
if ((place) == NULL) {\
|
SGLIB___DL_LIST_CREATE_SINGLETON(type, place, elem, previous, next);\
|
SGLIB___DL_LIST_CREATE_SINGLETON(type, place, elem, previous, next);\
|
} else {\
|
} else {\
|
(elem)->next = (place)->next;\
|
(elem)->next = (place)->next;\
|
(elem)->previous = (place);\
|
(elem)->previous = (place);\
|
(place)->next = (elem);\
|
(place)->next = (elem);\
|
if ((elem)->next != NULL) (elem)->next->previous = (elem);\
|
if ((elem)->next != NULL) (elem)->next->previous = (elem);\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_ADD_BEFORE(type, place, elem, previous, next) {\
|
#define SGLIB_DL_LIST_ADD_BEFORE(type, place, elem, previous, next) {\
|
if ((place) == NULL) {\
|
if ((place) == NULL) {\
|
SGLIB___DL_LIST_CREATE_SINGLETON(type, place, elem, previous, next);\
|
SGLIB___DL_LIST_CREATE_SINGLETON(type, place, elem, previous, next);\
|
} else {\
|
} else {\
|
(elem)->next = (place);\
|
(elem)->next = (place);\
|
(elem)->previous = (place)->previous;\
|
(elem)->previous = (place)->previous;\
|
(place)->previous = (elem);\
|
(place)->previous = (elem);\
|
if ((elem)->previous != NULL) (elem)->previous->next = (elem);\
|
if ((elem)->previous != NULL) (elem)->previous->next = (elem);\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_ADD(type, list, elem, previous, next) {\
|
#define SGLIB_DL_LIST_ADD(type, list, elem, previous, next) {\
|
SGLIB_DL_LIST_ADD_BEFORE(type, list, elem, previous, next)\
|
SGLIB_DL_LIST_ADD_BEFORE(type, list, elem, previous, next)\
|
}
|
}
|
|
|
#define SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, the_add_operation) {\
|
#define SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, the_add_operation) {\
|
type *_dlp_;\
|
type *_dlp_;\
|
for(_dlp_ = (list); _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->previous) ;\
|
for(_dlp_ = (list); _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->previous) ;\
|
if (_dlp_ == NULL && (list) != NULL) {\
|
if (_dlp_ == NULL && (list) != NULL) {\
|
for(_dlp_ = (list)->next; _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->next) ;\
|
for(_dlp_ = (list)->next; _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->next) ;\
|
}\
|
}\
|
(member) = _dlp_;\
|
(member) = _dlp_;\
|
if (_dlp_ == NULL) {\
|
if (_dlp_ == NULL) {\
|
the_add_operation(type, list, elem, previous, next);\
|
the_add_operation(type, list, elem, previous, next);\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_ADD_BEFORE_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
#define SGLIB_DL_LIST_ADD_BEFORE_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, SGLIB_DL_LIST_ADD_BEFORE);\
|
SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, SGLIB_DL_LIST_ADD_BEFORE);\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_ADD_AFTER_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
#define SGLIB_DL_LIST_ADD_AFTER_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, SGLIB_DL_LIST_ADD_AFTER);\
|
SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, SGLIB_DL_LIST_ADD_AFTER);\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
#define SGLIB_DL_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, SGLIB_DL_LIST_ADD);\
|
SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, SGLIB_DL_LIST_ADD);\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_CONCAT(type, first, second, previous, next) {\
|
#define SGLIB_DL_LIST_CONCAT(type, first, second, previous, next) {\
|
if ((first)==NULL) {\
|
if ((first)==NULL) {\
|
(first) = (second);\
|
(first) = (second);\
|
} else {\
|
} else {\
|
type *_dlp_;\
|
type *_dlp_;\
|
for(_dlp_ = (first); _dlp_->next!=NULL; _dlp_=_dlp_->next) ;\
|
for(_dlp_ = (first); _dlp_->next!=NULL; _dlp_=_dlp_->next) ;\
|
SGLIB_DL_LIST_ADD_AFTER(type, _dlp_, second, previous, next);\
|
SGLIB_DL_LIST_ADD_AFTER(type, _dlp_, second, previous, next);\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_DELETE(type, list, elem, previous, next) {\
|
#define SGLIB_DL_LIST_DELETE(type, list, elem, previous, next) {\
|
type *_l_;\
|
type *_l_;\
|
_l_ = (list);\
|
_l_ = (list);\
|
if (_l_ == (elem)) {\
|
if (_l_ == (elem)) {\
|
if ((elem)->previous != NULL) _l_ = (elem)->previous;\
|
if ((elem)->previous != NULL) _l_ = (elem)->previous;\
|
else _l_ = (elem)->next;\
|
else _l_ = (elem)->next;\
|
}\
|
}\
|
if ((elem)->next != NULL) (elem)->next->previous = (elem)->previous;\
|
if ((elem)->next != NULL) (elem)->next->previous = (elem)->previous;\
|
if ((elem)->previous != NULL) (elem)->previous->next = (elem)->next;\
|
if ((elem)->previous != NULL) (elem)->previous->next = (elem)->next;\
|
(list) = _l_;\
|
(list) = _l_;\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
#define SGLIB_DL_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
type *_dlp_;\
|
type *_dlp_;\
|
for(_dlp_ = (list); _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->previous) ;\
|
for(_dlp_ = (list); _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->previous) ;\
|
if (_dlp_ == NULL && (list) != NULL) {\
|
if (_dlp_ == NULL && (list) != NULL) {\
|
for(_dlp_ = (list)->next; _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->next) ;\
|
for(_dlp_ = (list)->next; _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->next) ;\
|
}\
|
}\
|
(member) = _dlp_;\
|
(member) = _dlp_;\
|
if (_dlp_ != NULL) {\
|
if (_dlp_ != NULL) {\
|
SGLIB_DL_LIST_DELETE(type, list, _dlp_, previous, next);\
|
SGLIB_DL_LIST_DELETE(type, list, _dlp_, previous, next);\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_IS_MEMBER(type, list, elem, previous, next, result) {\
|
#define SGLIB_DL_LIST_IS_MEMBER(type, list, elem, previous, next, result) {\
|
type *_dlp_;\
|
type *_dlp_;\
|
SGLIB_LIST_IS_MEMBER(type, list, elem, previous, result);\
|
SGLIB_LIST_IS_MEMBER(type, list, elem, previous, result);\
|
if (result == 0 && (list) != NULL) {\
|
if (result == 0 && (list) != NULL) {\
|
_dlp_ = (list)->next;\
|
_dlp_ = (list)->next;\
|
SGLIB_LIST_IS_MEMBER(type, _dlp_, elem, next, result);\
|
SGLIB_LIST_IS_MEMBER(type, _dlp_, elem, next, result);\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_FIND_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
#define SGLIB_DL_LIST_FIND_MEMBER(type, list, elem, comparator, previous, next, member) {\
|
type *_dlp_;\
|
type *_dlp_;\
|
SGLIB_LIST_FIND_MEMBER(type, list, elem, comparator, previous, member);\
|
SGLIB_LIST_FIND_MEMBER(type, list, elem, comparator, previous, member);\
|
if ((member) == NULL && (list) != NULL) {\
|
if ((member) == NULL && (list) != NULL) {\
|
_dlp_ = (list)->next;\
|
_dlp_ = (list)->next;\
|
SGLIB_LIST_FIND_MEMBER(type, _dlp_, elem, comparator, next, member);\
|
SGLIB_LIST_FIND_MEMBER(type, _dlp_, elem, comparator, next, member);\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, previous, next, command) {\
|
#define SGLIB_DL_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, previous, next, command) {\
|
type *_dl_;\
|
type *_dl_;\
|
type *iteratedVariable;\
|
type *iteratedVariable;\
|
if ((list)!=NULL) {\
|
if ((list)!=NULL) {\
|
_dl_ = (list)->next;\
|
_dl_ = (list)->next;\
|
SGLIB_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, previous, command);\
|
SGLIB_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, previous, command);\
|
SGLIB_LIST_MAP_ON_ELEMENTS(type, _dl_, iteratedVariable, next, command);\
|
SGLIB_LIST_MAP_ON_ELEMENTS(type, _dl_, iteratedVariable, next, command);\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_SORT(type, list, comparator, previous, next) {\
|
#define SGLIB_DL_LIST_SORT(type, list, comparator, previous, next) {\
|
type *_dll_, *_dlp_, *_dlt_;\
|
type *_dll_, *_dlp_, *_dlt_;\
|
_dll_ = (list);\
|
_dll_ = (list);\
|
if (_dll_ != NULL) {\
|
if (_dll_ != NULL) {\
|
for(; _dll_->previous!=NULL; _dll_=_dll_->previous) ;\
|
for(; _dll_->previous!=NULL; _dll_=_dll_->previous) ;\
|
SGLIB_LIST_SORT(type, _dll_, comparator, next);\
|
SGLIB_LIST_SORT(type, _dll_, comparator, next);\
|
SGLIB___DL_LIST_CREATE_FROM_LIST(type, _dll_, previous, next);\
|
SGLIB___DL_LIST_CREATE_FROM_LIST(type, _dll_, previous, next);\
|
(list) = _dll_;\
|
(list) = _dll_;\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_GET_FIRST(type, list, previous, next, result) {\
|
#define SGLIB_DL_LIST_GET_FIRST(type, list, previous, next, result) {\
|
type *_dll_;\
|
type *_dll_;\
|
_dll_ = (list);\
|
_dll_ = (list);\
|
if (_dll_ != NULL) {\
|
if (_dll_ != NULL) {\
|
for(; _dll_->previous!=NULL; _dll_=_dll_->previous) ;\
|
for(; _dll_->previous!=NULL; _dll_=_dll_->previous) ;\
|
}\
|
}\
|
(result) = _dll_;\
|
(result) = _dll_;\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_GET_LAST(type, list, previous, next, result) {\
|
#define SGLIB_DL_LIST_GET_LAST(type, list, previous, next, result) {\
|
type *_dll_;\
|
type *_dll_;\
|
_dll_ = (list);\
|
_dll_ = (list);\
|
if (_dll_ != NULL) {\
|
if (_dll_ != NULL) {\
|
for(; _dll_->next!=NULL; _dll_=_dll_->next) ;\
|
for(; _dll_->next!=NULL; _dll_=_dll_->next) ;\
|
}\
|
}\
|
(result) = _dll_;\
|
(result) = _dll_;\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_LEN(type, list, previous, next, result) {\
|
#define SGLIB_DL_LIST_LEN(type, list, previous, next, result) {\
|
type *_dl_;\
|
type *_dl_;\
|
int _r1_, _r2_;\
|
int _r1_, _r2_;\
|
if ((list)==NULL) {\
|
if ((list)==NULL) {\
|
(result) = 0;\
|
(result) = 0;\
|
} else {\
|
} else {\
|
SGLIB_LIST_LEN(type, list, previous, _r1_);\
|
SGLIB_LIST_LEN(type, list, previous, _r1_);\
|
_dl_ = (list)->next;\
|
_dl_ = (list)->next;\
|
SGLIB_LIST_LEN(type, _dl_, next, _r2_);\
|
SGLIB_LIST_LEN(type, _dl_, next, _r2_);\
|
(result) = _r1_ + _r2_;\
|
(result) = _r1_ + _r2_;\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_DL_LIST_REVERSE(type, list, previous, next) {\
|
#define SGLIB_DL_LIST_REVERSE(type, list, previous, next) {\
|
type *_list_,*_nlist_,*_dlp_,*_dln_;\
|
type *_list_,*_nlist_,*_dlp_,*_dln_;\
|
_list_ = (list);\
|
_list_ = (list);\
|
if (_list_!=NULL) {\
|
if (_list_!=NULL) {\
|
_nlist_ = _list_->next;\
|
_nlist_ = _list_->next;\
|
while (_list_!=NULL) {\
|
while (_list_!=NULL) {\
|
_dln_ = _list_->next; \
|
_dln_ = _list_->next; \
|
_dlp_ = _list_->previous; \
|
_dlp_ = _list_->previous; \
|
_list_->next = _dlp_;\
|
_list_->next = _dlp_;\
|
_list_->previous = _dln_;\
|
_list_->previous = _dln_;\
|
_list_ = _dlp_;\
|
_list_ = _dlp_;\
|
}\
|
}\
|
while (_nlist_!=NULL) {\
|
while (_nlist_!=NULL) {\
|
_dln_ = _nlist_->next; \
|
_dln_ = _nlist_->next; \
|
_dlp_ = _nlist_->previous; \
|
_dlp_ = _nlist_->previous; \
|
_nlist_->next = _dlp_;\
|
_nlist_->next = _dlp_;\
|
_nlist_->previous = _dln_;\
|
_nlist_->previous = _dln_;\
|
_nlist_ = _dln_;\
|
_nlist_ = _dln_;\
|
}\
|
}\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB___DL_LIST_CREATE_FROM_LIST(type, list, previous, next) {\
|
#define SGLIB___DL_LIST_CREATE_FROM_LIST(type, list, previous, next) {\
|
type *_dlp_, *_dlt_;\
|
type *_dlp_, *_dlt_;\
|
_dlp_ = NULL;\
|
_dlp_ = NULL;\
|
for(_dlt_ = (list); _dlt_!=NULL; _dlt_ = _dlt_->next) {\
|
for(_dlt_ = (list); _dlt_!=NULL; _dlt_ = _dlt_->next) {\
|
_dlt_->previous = _dlp_;\
|
_dlt_->previous = _dlp_;\
|
_dlp_ = _dlt_;\
|
_dlp_ = _dlt_;\
|
}\
|
}\
|
}
|
}
|
|
|
|
|
/* ------------------------------- binary tree traversal (level 0) -------------------- */
|
/* ------------------------------- binary tree traversal (level 0) -------------------- */
|
|
|
|
|
#define SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, iteratedVariable, order, left, right, command) {\
|
#define SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, iteratedVariable, order, left, right, command) {\
|
/* this is non-recursive implementation of tree traversal */\
|
/* this is non-recursive implementation of tree traversal */\
|
/* it maintains the path to the current node in the array '_path_' */\
|
/* it maintains the path to the current node in the array '_path_' */\
|
/* the _path_[0] contains the root of the tree; */\
|
/* the _path_[0] contains the root of the tree; */\
|
/* the _path_[_pathi_] contains the _current_element_ */\
|
/* the _path_[_pathi_] contains the _current_element_ */\
|
/* the macro does not use the _current_element_ after execution of command */\
|
/* the macro does not use the _current_element_ after execution of command */\
|
/* command can destroy it, it can free the element for example */\
|
/* command can destroy it, it can free the element for example */\
|
type *_path_[SGLIB_MAX_TREE_DEEP];\
|
type *_path_[SGLIB_MAX_TREE_DEEP];\
|
type *_right_[SGLIB_MAX_TREE_DEEP];\
|
type *_right_[SGLIB_MAX_TREE_DEEP];\
|
char _pass_[SGLIB_MAX_TREE_DEEP];\
|
char _pass_[SGLIB_MAX_TREE_DEEP];\
|
type *_cn_;\
|
type *_cn_;\
|
int _pathi_;\
|
int _pathi_;\
|
type *iteratedVariable;\
|
type *iteratedVariable;\
|
_cn_ = (tree);\
|
_cn_ = (tree);\
|
_pathi_ = 0;\
|
_pathi_ = 0;\
|
while (_cn_!=NULL) {\
|
while (_cn_!=NULL) {\
|
/* push down to leftmost innermost element */\
|
/* push down to leftmost innermost element */\
|
while(_cn_!=NULL) {\
|
while(_cn_!=NULL) {\
|
_path_[_pathi_] = _cn_;\
|
_path_[_pathi_] = _cn_;\
|
_right_[_pathi_] = _cn_->right;\
|
_right_[_pathi_] = _cn_->right;\
|
_pass_[_pathi_] = 0;\
|
_pass_[_pathi_] = 0;\
|
_cn_ = _cn_->left;\
|
_cn_ = _cn_->left;\
|
if (order == 0) {\
|
if (order == 0) {\
|
iteratedVariable = _path_[_pathi_];\
|
iteratedVariable = _path_[_pathi_];\
|
{command;}\
|
{command;}\
|
}\
|
}\
|
_pathi_ ++;\
|
_pathi_ ++;\
|
if (_pathi_ >= SGLIB_MAX_TREE_DEEP) assert(0 && "the binary_tree is too deep");\
|
if (_pathi_ >= SGLIB_MAX_TREE_DEEP) assert(0 && "the binary_tree is too deep");\
|
}\
|
}\
|
do {\
|
do {\
|
_pathi_ --;\
|
_pathi_ --;\
|
if ((order==1 && _pass_[_pathi_] == 0)\
|
if ((order==1 && _pass_[_pathi_] == 0)\
|
|| (order == 2 && (_pass_[_pathi_] == 1 || _right_[_pathi_]==NULL))) {\
|
|| (order == 2 && (_pass_[_pathi_] == 1 || _right_[_pathi_]==NULL))) {\
|
iteratedVariable = _path_[_pathi_];\
|
iteratedVariable = _path_[_pathi_];\
|
{command;}\
|
{command;}\
|
}\
|
}\
|
_pass_[_pathi_] ++;\
|
_pass_[_pathi_] ++;\
|
} while (_pathi_>0 && _right_[_pathi_]==NULL) ;\
|
} while (_pathi_>0 && _right_[_pathi_]==NULL) ;\
|
_cn_ = _right_[_pathi_];\
|
_cn_ = _right_[_pathi_];\
|
_right_[_pathi_] = NULL;\
|
_right_[_pathi_] = NULL;\
|
_pathi_ ++;\
|
_pathi_ ++;\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, left, right, command) {\
|
#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, left, right, command) {\
|
SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 1, left, right, command);\
|
SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 1, left, right, command);\
|
}
|
}
|
|
|
#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS_PREORDER(type, tree, _current_element_, left, right, command) {\
|
#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS_PREORDER(type, tree, _current_element_, left, right, command) {\
|
SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 0, left, right, command);\
|
SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 0, left, right, command);\
|
}
|
}
|
|
|
#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS_POSTORDER(type, tree, _current_element_, left, right, command) {\
|
#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS_POSTORDER(type, tree, _current_element_, left, right, command) {\
|
SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 2, left, right, command);\
|
SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 2, left, right, command);\
|
}
|
}
|
|
|
#define SGLIB___BIN_TREE_FIND_MEMBER(type, tree, elem, left, right, comparator, res) {\
|
#define SGLIB___BIN_TREE_FIND_MEMBER(type, tree, elem, left, right, comparator, res) {\
|
type *_s_;\
|
type *_s_;\
|
int _c_;\
|
int _c_;\
|
_s_ = (tree);\
|
_s_ = (tree);\
|
while (_s_!=NULL) {\
|
while (_s_!=NULL) {\
|
_c_ = comparator((elem), _s_);\
|
_c_ = comparator((elem), _s_);\
|
if (_c_ < 0) _s_ = _s_->left;\
|
if (_c_ < 0) _s_ = _s_->left;\
|
else if (_c_ > 0) _s_ = _s_->right;\
|
else if (_c_ > 0) _s_ = _s_->right;\
|
else break;\
|
else break;\
|
}\
|
}\
|
(res) = _s_;\
|
(res) = _s_;\
|
}
|
}
|
|
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* - LEVEL - 1 INTERFACE - */
|
/* - LEVEL - 1 INTERFACE - */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
|
|
|
|
|
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ------------------------------ STATIC ARRAYS ------------------------------- */
|
/* ------------------------------ STATIC ARRAYS ------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
|
|
/* ----------------------------- array sorting (level 1) ---------------------- */
|
/* ----------------------------- array sorting (level 1) ---------------------- */
|
|
|
#define SGLIB_DEFINE_ARRAY_SORTING_PROTOTYPES(type, comparator) \
|
#define SGLIB_DEFINE_ARRAY_SORTING_PROTOTYPES(type, comparator) \
|
extern void sglib_##type##_array_quick_sort(type *a, int max);\
|
extern void sglib_##type##_array_quick_sort(type *a, int max);\
|
extern void sglib_##type##_array_heap_sort(type *a, int max);\
|
extern void sglib_##type##_array_heap_sort(type *a, int max);\
|
|
|
|
|
#define SGLIB_DEFINE_ARRAY_SORTING_FUNCTIONS(type, comparator) \
|
#define SGLIB_DEFINE_ARRAY_SORTING_FUNCTIONS(type, comparator) \
|
void sglib_##type##_array_quick_sort(type *a, int max) {\
|
void sglib_##type##_array_quick_sort(type *a, int max) {\
|
SGLIB_ARRAY_SINGLE_QUICK_SORT(type, a, max, comparator);\
|
SGLIB_ARRAY_SINGLE_QUICK_SORT(type, a, max, comparator);\
|
}\
|
}\
|
void sglib_##type##_array_heap_sort(type *a, int max) {\
|
void sglib_##type##_array_heap_sort(type *a, int max) {\
|
SGLIB_ARRAY_SINGLE_HEAP_SORT(type, a, max, comparator);\
|
SGLIB_ARRAY_SINGLE_HEAP_SORT(type, a, max, comparator);\
|
}\
|
}\
|
|
|
|
|
/* ----------------------------- array queue (level 1) ------------------- */
|
/* ----------------------------- array queue (level 1) ------------------- */
|
/* sglib's queue is stored in a fixed sized array */
|
/* sglib's queue is stored in a fixed sized array */
|
/* queue_type MUST be a structure containing fields: */
|
/* queue_type MUST be a structure containing fields: */
|
/* afield is the array storing elem_type */
|
/* afield is the array storing elem_type */
|
/* ifield is the index of the first element in the queue */
|
/* ifield is the index of the first element in the queue */
|
/* jfield is the index of the first free element after the queue */
|
/* jfield is the index of the first free element after the queue */
|
/* dim is the size of the array afield */
|
/* dim is the size of the array afield */
|
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */
|
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */
|
|
|
|
|
#define SGLIB_DEFINE_QUEUE_PROTOTYPES(queue_type, elem_type, afield, ifield, jfield, dim) \
|
#define SGLIB_DEFINE_QUEUE_PROTOTYPES(queue_type, elem_type, afield, ifield, jfield, dim) \
|
extern void sglib_##queue_type##_init(queue_type *q); \
|
extern void sglib_##queue_type##_init(queue_type *q); \
|
extern int sglib_##queue_type##_is_empty(queue_type *q); \
|
extern int sglib_##queue_type##_is_empty(queue_type *q); \
|
extern int sglib_##queue_type##_is_full(queue_type *q); \
|
extern int sglib_##queue_type##_is_full(queue_type *q); \
|
extern elem_type sglib_##queue_type##_first_element(queue_type *q); \
|
extern elem_type sglib_##queue_type##_first_element(queue_type *q); \
|
extern elem_type *sglib_##queue_type##_first_element_ptr(queue_type *q); \
|
extern elem_type *sglib_##queue_type##_first_element_ptr(queue_type *q); \
|
extern void sglib_##queue_type##_add_next(queue_type *q); \
|
extern void sglib_##queue_type##_add_next(queue_type *q); \
|
extern void sglib_##queue_type##_add(queue_type *q, elem_type elem); \
|
extern void sglib_##queue_type##_add(queue_type *q, elem_type elem); \
|
extern void sglib_##queue_type##_delete_first(queue_type *q); \
|
extern void sglib_##queue_type##_delete_first(queue_type *q); \
|
extern void sglib_##queue_type##_delete(queue_type *q);
|
extern void sglib_##queue_type##_delete(queue_type *q);
|
|
|
|
|
#define SGLIB_DEFINE_QUEUE_FUNCTIONS(queue_type, elem_type, afield, ifield, jfield, dim) \
|
#define SGLIB_DEFINE_QUEUE_FUNCTIONS(queue_type, elem_type, afield, ifield, jfield, dim) \
|
void sglib_##queue_type##_init(queue_type *q) {\
|
void sglib_##queue_type##_init(queue_type *q) {\
|
SGLIB_QUEUE_INIT(elem_type, q->afield, q->ifield, q->jfield);\
|
SGLIB_QUEUE_INIT(elem_type, q->afield, q->ifield, q->jfield);\
|
}\
|
}\
|
int sglib_##queue_type##_is_empty(queue_type *q) {\
|
int sglib_##queue_type##_is_empty(queue_type *q) {\
|
return(SGLIB_QUEUE_IS_EMPTY(elem_type, q->afield, q->ifield, q->jfield));\
|
return(SGLIB_QUEUE_IS_EMPTY(elem_type, q->afield, q->ifield, q->jfield));\
|
}\
|
}\
|
int sglib_##queue_type##_is_full(queue_type *q) {\
|
int sglib_##queue_type##_is_full(queue_type *q) {\
|
return(SGLIB_QUEUE_IS_FULL(elem_type, q->afield, q->ifield, q->jfield));\
|
return(SGLIB_QUEUE_IS_FULL(elem_type, q->afield, q->ifield, q->jfield));\
|
}\
|
}\
|
elem_type sglib_##queue_type##_first_element(queue_type *q) {\
|
elem_type sglib_##queue_type##_first_element(queue_type *q) {\
|
return(SGLIB_QUEUE_FIRST_ELEMENT(elem_type, q->afield, q->ifield, q->jfield));\
|
return(SGLIB_QUEUE_FIRST_ELEMENT(elem_type, q->afield, q->ifield, q->jfield));\
|
}\
|
}\
|
elem_type *sglib_##queue_type##_first_element_ptr(queue_type *q) {\
|
elem_type *sglib_##queue_type##_first_element_ptr(queue_type *q) {\
|
return(& SGLIB_QUEUE_FIRST_ELEMENT(elem_type, q->afield, q->ifield, q->jfield));\
|
return(& SGLIB_QUEUE_FIRST_ELEMENT(elem_type, q->afield, q->ifield, q->jfield));\
|
}\
|
}\
|
void sglib_##queue_type##_add_next(queue_type *q) {\
|
void sglib_##queue_type##_add_next(queue_type *q) {\
|
SGLIB_QUEUE_ADD_NEXT(elem_type, q->afield, q->ifield, q->jfield, dim);\
|
SGLIB_QUEUE_ADD_NEXT(elem_type, q->afield, q->ifield, q->jfield, dim);\
|
}\
|
}\
|
void sglib_##queue_type##_add(queue_type *q, elem_type elem) {\
|
void sglib_##queue_type##_add(queue_type *q, elem_type elem) {\
|
SGLIB_QUEUE_ADD(elem_type, q->afield, elem, q->ifield, q->jfield, dim);\
|
SGLIB_QUEUE_ADD(elem_type, q->afield, elem, q->ifield, q->jfield, dim);\
|
}\
|
}\
|
void sglib_##queue_type##_delete_first(queue_type *q) {\
|
void sglib_##queue_type##_delete_first(queue_type *q) {\
|
SGLIB_QUEUE_DELETE_FIRST(elem_type, q->afield, q->ifield, q->jfield, dim);\
|
SGLIB_QUEUE_DELETE_FIRST(elem_type, q->afield, q->ifield, q->jfield, dim);\
|
}\
|
}\
|
void sglib_##queue_type##_delete(queue_type *q) {\
|
void sglib_##queue_type##_delete(queue_type *q) {\
|
SGLIB_QUEUE_DELETE_FIRST(elem_type, q->afield, q->ifield, q->jfield, dim);\
|
SGLIB_QUEUE_DELETE_FIRST(elem_type, q->afield, q->ifield, q->jfield, dim);\
|
}
|
}
|
|
|
|
|
/* ------------------------ array heap (level 1) ------------------------- */
|
/* ------------------------ array heap (level 1) ------------------------- */
|
/* sglib's heap is a priority queue implemented in a fixed sized array */
|
/* sglib's heap is a priority queue implemented in a fixed sized array */
|
/* heap_type MUST be a structure containing fields: */
|
/* heap_type MUST be a structure containing fields: */
|
/* afield is the array of size dim storing elem_type */
|
/* afield is the array of size dim storing elem_type */
|
/* ifield is the index of the first free element after the queue */
|
/* ifield is the index of the first free element after the queue */
|
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */
|
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */
|
|
|
|
|
#define SGLIB_DEFINE_HEAP_PROTOTYPES(heap_type, elem_type, afield, ifield, dim, comparator, elem_exchanger) \
|
#define SGLIB_DEFINE_HEAP_PROTOTYPES(heap_type, elem_type, afield, ifield, dim, comparator, elem_exchanger) \
|
extern void sglib_##heap_type##_init(heap_type *q); \
|
extern void sglib_##heap_type##_init(heap_type *q); \
|
extern int sglib_##heap_type##_is_empty(heap_type *q); \
|
extern int sglib_##heap_type##_is_empty(heap_type *q); \
|
extern int sglib_##heap_type##_is_full(heap_type *q); \
|
extern int sglib_##heap_type##_is_full(heap_type *q); \
|
extern elem_type sglib_##heap_type##_first_element(heap_type *q); \
|
extern elem_type sglib_##heap_type##_first_element(heap_type *q); \
|
extern elem_type *sglib_##heap_type##_first_element_ptr(heap_type *q); \
|
extern elem_type *sglib_##heap_type##_first_element_ptr(heap_type *q); \
|
extern void sglib_##heap_type##_add_next(heap_type *q); \
|
extern void sglib_##heap_type##_add_next(heap_type *q); \
|
extern void sglib_##heap_type##_add(heap_type *q, elem_type elem); \
|
extern void sglib_##heap_type##_add(heap_type *q, elem_type elem); \
|
extern void sglib_##heap_type##_delete_first(heap_type *q); \
|
extern void sglib_##heap_type##_delete_first(heap_type *q); \
|
extern void sglib_##heap_type##_delete(heap_type *q)
|
extern void sglib_##heap_type##_delete(heap_type *q)
|
|
|
#define SGLIB_DEFINE_HEAP_FUNCTIONS(heap_type, elem_type, afield, ifield, dim, comparator, elem_exchanger) \
|
#define SGLIB_DEFINE_HEAP_FUNCTIONS(heap_type, elem_type, afield, ifield, dim, comparator, elem_exchanger) \
|
void sglib_##heap_type##_init(heap_type *q) {\
|
void sglib_##heap_type##_init(heap_type *q) {\
|
SGLIB_HEAP_INIT(elem_type, q->afield, q->ifield);\
|
SGLIB_HEAP_INIT(elem_type, q->afield, q->ifield);\
|
}\
|
}\
|
int sglib_##heap_type##_is_empty(heap_type *q) {\
|
int sglib_##heap_type##_is_empty(heap_type *q) {\
|
return(SGLIB_HEAP_IS_EMPTY(elem_type, q->afield, q->ifield));\
|
return(SGLIB_HEAP_IS_EMPTY(elem_type, q->afield, q->ifield));\
|
}\
|
}\
|
int sglib_##heap_type##_is_full(heap_type *q) {\
|
int sglib_##heap_type##_is_full(heap_type *q) {\
|
return(SGLIB_HEAP_IS_FULL(elem_type, q->afield, q->ifield));\
|
return(SGLIB_HEAP_IS_FULL(elem_type, q->afield, q->ifield));\
|
}\
|
}\
|
elem_type sglib_##heap_type##_first_element(heap_type *q) {\
|
elem_type sglib_##heap_type##_first_element(heap_type *q) {\
|
return(SGLIB_HEAP_FIRST_ELEMENT(elem_type, q->afield, q->ifield));\
|
return(SGLIB_HEAP_FIRST_ELEMENT(elem_type, q->afield, q->ifield));\
|
}\
|
}\
|
elem_type *sglib_##heap_type##_first_element_ptr(heap_type *q) {\
|
elem_type *sglib_##heap_type##_first_element_ptr(heap_type *q) {\
|
return(& SGLIB_HEAP_FIRST_ELEMENT(elem_type, q->afield, q->ifield));\
|
return(& SGLIB_HEAP_FIRST_ELEMENT(elem_type, q->afield, q->ifield));\
|
}\
|
}\
|
void sglib_##heap_type##_add_next(heap_type *q) {\
|
void sglib_##heap_type##_add_next(heap_type *q) {\
|
SGLIB_HEAP_ADD_NEXT(elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger);\
|
SGLIB_HEAP_ADD_NEXT(elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger);\
|
}\
|
}\
|
void sglib_##heap_type##_add(heap_type *q, elem_type elem) {\
|
void sglib_##heap_type##_add(heap_type *q, elem_type elem) {\
|
SGLIB_HEAP_ADD(elem_type, q->afield, elem, q->ifield, dim, comparator, elem_exchanger);\
|
SGLIB_HEAP_ADD(elem_type, q->afield, elem, q->ifield, dim, comparator, elem_exchanger);\
|
}\
|
}\
|
void sglib_##heap_type##_delete_first(heap_type *q) {\
|
void sglib_##heap_type##_delete_first(heap_type *q) {\
|
SGLIB_HEAP_DELETE_FIRST(elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger);\
|
SGLIB_HEAP_DELETE_FIRST(elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger);\
|
}\
|
}\
|
void sglib_##heap_type##_delete(heap_type *q) {\
|
void sglib_##heap_type##_delete(heap_type *q) {\
|
SGLIB_HEAP_DELETE_FIRST(elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger);\
|
SGLIB_HEAP_DELETE_FIRST(elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger);\
|
}
|
}
|
|
|
|
|
/* ------------------------ hashed table (level 1) ------------------------- */
|
/* ------------------------ hashed table (level 1) ------------------------- */
|
/*
|
/*
|
|
|
sglib's hash table is an array storing directly pointers to objects (not containers).
|
sglib's hash table is an array storing directly pointers to objects (not containers).
|
In this table there is a one-to-one mapping between 'objects' stored
|
In this table there is a one-to-one mapping between 'objects' stored
|
in the table and indexes where they are placed. Each index is
|
in the table and indexes where they are placed. Each index is
|
pointing to exactly one 'object' and each 'object' stored in the
|
pointing to exactly one 'object' and each 'object' stored in the
|
table occurs on exactly one index. Once an object is stored in the
|
table occurs on exactly one index. Once an object is stored in the
|
table, it can be represented via its index.
|
table, it can be represented via its index.
|
|
|
type - is the type of elements
|
type - is the type of elements
|
dim - is the size of the hash array
|
dim - is the size of the hash array
|
hash_function - is a hashing function mapping type* to unsigned
|
hash_function - is a hashing function mapping type* to unsigned
|
comparator - is a comparator on elements
|
comparator - is a comparator on elements
|
|
|
!!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!!
|
!!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!!
|
*/
|
*/
|
|
|
#define SGLIB_DEFINE_HASHED_TABLE_PROTOTYPES(type, dim, hash_function, comparator) \
|
#define SGLIB_DEFINE_HASHED_TABLE_PROTOTYPES(type, dim, hash_function, comparator) \
|
struct sglib_hashed_##type##_iterator {\
|
struct sglib_hashed_##type##_iterator {\
|
int currentIndex;\
|
int currentIndex;\
|
int (*subcomparator)(type *, type *);\
|
int (*subcomparator)(type *, type *);\
|
type *equalto;\
|
type *equalto;\
|
};\
|
};\
|
extern void sglib_hashed_##type##_init(type *table[dim]);\
|
extern void sglib_hashed_##type##_init(type *table[dim]);\
|
extern int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member);\
|
extern int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member);\
|
extern int sglib_hashed_##type##_is_member(type *table[dim], type *elem);\
|
extern int sglib_hashed_##type##_is_member(type *table[dim], type *elem);\
|
extern type * sglib_hashed_##type##_find_member(type *table[dim], type *elem);\
|
extern type * sglib_hashed_##type##_find_member(type *table[dim], type *elem);\
|
extern type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]); \
|
extern type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]); \
|
extern type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto); \
|
extern type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto); \
|
extern type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it); \
|
extern type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it); \
|
extern type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it);
|
extern type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it);
|
|
|
#define SGLIB_DEFINE_HASHED_TABLE_FUNCTIONS(type, dim, hash_function, comparator) \
|
#define SGLIB_DEFINE_HASHED_TABLE_FUNCTIONS(type, dim, hash_function, comparator) \
|
struct sglib_hashed_##type##_iterator {\
|
struct sglib_hashed_##type##_iterator {\
|
int currentIndex;\
|
int currentIndex;\
|
type **table;\
|
type **table;\
|
int (*subcomparator)(type *, type *);\
|
int (*subcomparator)(type *, type *);\
|
type *equalto;\
|
type *equalto;\
|
};\
|
};\
|
void sglib_hashed_##type##_init(type *table[dim]) {\
|
void sglib_hashed_##type##_init(type *table[dim]) {\
|
SGLIB_HASH_TAB_INIT(type, table, dim);\
|
SGLIB_HASH_TAB_INIT(type, table, dim);\
|
}\
|
}\
|
int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member) {\
|
int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member) {\
|
SGLIB_HASH_TAB_ADD_IF_NOT_MEMBER(type, table, dim, elem, hash_function, comparator, *member);\
|
SGLIB_HASH_TAB_ADD_IF_NOT_MEMBER(type, table, dim, elem, hash_function, comparator, *member);\
|
}\
|
}\
|
int sglib_hashed_##type##_is_member(type *table[dim], type *elem) {\
|
int sglib_hashed_##type##_is_member(type *table[dim], type *elem) {\
|
int ind;\
|
int ind;\
|
SGLIB_HASH_TAB_IS_MEMBER(type, table, dim, elem, hash_function, ind);\
|
SGLIB_HASH_TAB_IS_MEMBER(type, table, dim, elem, hash_function, ind);\
|
return(ind != -1);\
|
return(ind != -1);\
|
}\
|
}\
|
type * sglib_hashed_##type##_find_member(type *table[dim], type *elem) {\
|
type * sglib_hashed_##type##_find_member(type *table[dim], type *elem) {\
|
type *mmb;\
|
type *mmb;\
|
int ind;\
|
int ind;\
|
SGLIB_HASH_TAB_FIND_MEMBER(type, table, dim, elem, hash_function, comparator, ind, mmb);\
|
SGLIB_HASH_TAB_FIND_MEMBER(type, table, dim, elem, hash_function, comparator, ind, mmb);\
|
return(mmb);\
|
return(mmb);\
|
}\
|
}\
|
type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto) {\
|
type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto) {\
|
int i;\
|
int i;\
|
it->table = table;\
|
it->table = table;\
|
it->subcomparator = subcomparator;\
|
it->subcomparator = subcomparator;\
|
it->equalto = equalto;\
|
it->equalto = equalto;\
|
for(i=0; i<(dim) && table[i]==NULL; i++) ;\
|
for(i=0; i<(dim) && table[i]==NULL; i++) ;\
|
it->currentIndex = i;\
|
it->currentIndex = i;\
|
if (i<(dim)) return(table[i]);\
|
if (i<(dim)) return(table[i]);\
|
return(NULL);\
|
return(NULL);\
|
}\
|
}\
|
type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]) {\
|
type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]) {\
|
sglib_hashed_##type##_it_init_on_equal(it, table, NULL, NULL);\
|
sglib_hashed_##type##_it_init_on_equal(it, table, NULL, NULL);\
|
}\
|
}\
|
type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it) {\
|
type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it) {\
|
return(table[it->currentIndex]);\
|
return(table[it->currentIndex]);\
|
}\
|
}\
|
type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it) {\
|
type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it) {\
|
i=it->currentIndex;\
|
i=it->currentIndex;\
|
if (i<(dim)) {\
|
if (i<(dim)) {\
|
for(i++; i<(dim) && table[i]==NULL; i++) ;\
|
for(i++; i<(dim) && table[i]==NULL; i++) ;\
|
}\
|
}\
|
it->currentIndex = i;\
|
it->currentIndex = i;\
|
if (i<(dim)) return(table[i]);\
|
if (i<(dim)) return(table[i]);\
|
return(NULL);\
|
return(NULL);\
|
}
|
}
|
|
|
|
|
/* ------------------- hashed container (only for level 1) -------------------- */
|
/* ------------------- hashed container (only for level 1) -------------------- */
|
/*
|
/*
|
hashed container is a table of given fixed size containing another
|
hashed container is a table of given fixed size containing another
|
(dynamic) base container in each cell. Once an object should be
|
(dynamic) base container in each cell. Once an object should be
|
inserted into the hashed container, a hash function is used to
|
inserted into the hashed container, a hash function is used to
|
determine the cell where the object belongs and the object is
|
determine the cell where the object belongs and the object is
|
inserted into the base container stored in this cell. Usually the
|
inserted into the base container stored in this cell. Usually the
|
base container is simply a list or a sorted list, but it can be a
|
base container is simply a list or a sorted list, but it can be a
|
red-black tree as well.
|
red-black tree as well.
|
|
|
parameters:
|
parameters:
|
type - the type of the container stored in each cell.
|
type - the type of the container stored in each cell.
|
dim - the size of the hashed array
|
dim - the size of the hashed array
|
hash_function - the hashing function hashing 'type *' to unsigned.
|
hash_function - the hashing function hashing 'type *' to unsigned.
|
|
|
*/
|
*/
|
|
|
#define SGLIB_DEFINE_HASHED_CONTAINER_PROTOTYPES(type, dim, hash_function) \
|
#define SGLIB_DEFINE_HASHED_CONTAINER_PROTOTYPES(type, dim, hash_function) \
|
struct sglib_hashed_##type##_iterator {\
|
struct sglib_hashed_##type##_iterator {\
|
struct sglib_##type##_iterator containerIt;\
|
struct sglib_##type##_iterator containerIt;\
|
type **table;\
|
type **table;\
|
int currentIndex;\
|
int currentIndex;\
|
int (*subcomparator)(type *, type *);\
|
int (*subcomparator)(type *, type *);\
|
type *equalto;\
|
type *equalto;\
|
};\
|
};\
|
extern void sglib_hashed_##type##_init(type *table[dim]);\
|
extern void sglib_hashed_##type##_init(type *table[dim]);\
|
extern void sglib_hashed_##type##_add(type *table[dim], type *elem);\
|
extern void sglib_hashed_##type##_add(type *table[dim], type *elem);\
|
extern int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member);\
|
extern int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member);\
|
extern void sglib_hashed_##type##_delete(type *table[dim], type *elem);\
|
extern void sglib_hashed_##type##_delete(type *table[dim], type *elem);\
|
extern int sglib_hashed_##type##_delete_if_member(type *table[dim], type *elem, type **memb);\
|
extern int sglib_hashed_##type##_delete_if_member(type *table[dim], type *elem, type **memb);\
|
extern int sglib_hashed_##type##_is_member(type *table[dim], type *elem);\
|
extern int sglib_hashed_##type##_is_member(type *table[dim], type *elem);\
|
extern type * sglib_hashed_##type##_find_member(type *table[dim], type *elem);\
|
extern type * sglib_hashed_##type##_find_member(type *table[dim], type *elem);\
|
extern type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]); \
|
extern type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]); \
|
extern type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto); \
|
extern type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto); \
|
extern type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it); \
|
extern type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it); \
|
extern type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it);
|
extern type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it);
|
|
|
#define SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS(type, dim, hash_function) \
|
#define SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS(type, dim, hash_function) \
|
/*extern unsigned hash_function(type *elem);*/\
|
/*extern unsigned hash_function(type *elem);*/\
|
void sglib_hashed_##type##_init(type *table[dim]) {\
|
void sglib_hashed_##type##_init(type *table[dim]) {\
|
unsigned i;\
|
unsigned i;\
|
for(i=0; i<(dim); i++) table[i] = NULL;\
|
for(i=0; i<(dim); i++) table[i] = NULL;\
|
}\
|
}\
|
void sglib_hashed_##type##_add(type *table[dim], type *elem) {\
|
void sglib_hashed_##type##_add(type *table[dim], type *elem) {\
|
unsigned i;\
|
unsigned i;\
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
sglib_##type##_add(&(table)[i], elem);\
|
sglib_##type##_add(&(table)[i], elem);\
|
}\
|
}\
|
int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member) {\
|
int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member) {\
|
unsigned i;\
|
unsigned i;\
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
return(sglib_##type##_add_if_not_member(&(table)[i], elem, member));\
|
return(sglib_##type##_add_if_not_member(&(table)[i], elem, member));\
|
}\
|
}\
|
void sglib_hashed_##type##_delete(type *table[dim], type *elem) {\
|
void sglib_hashed_##type##_delete(type *table[dim], type *elem) {\
|
unsigned i;\
|
unsigned i;\
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
sglib_##type##_delete(&(table)[i], elem);\
|
sglib_##type##_delete(&(table)[i], elem);\
|
}\
|
}\
|
int sglib_hashed_##type##_delete_if_member(type *table[dim], type *elem, type **memb) {\
|
int sglib_hashed_##type##_delete_if_member(type *table[dim], type *elem, type **memb) {\
|
unsigned i;\
|
unsigned i;\
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
return(sglib_##type##_delete_if_member(&(table)[i], elem, memb));\
|
return(sglib_##type##_delete_if_member(&(table)[i], elem, memb));\
|
}\
|
}\
|
int sglib_hashed_##type##_is_member(type *table[dim], type *elem) {\
|
int sglib_hashed_##type##_is_member(type *table[dim], type *elem) {\
|
unsigned i;\
|
unsigned i;\
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
return(sglib_##type##_is_member((table)[i], elem));\
|
return(sglib_##type##_is_member((table)[i], elem));\
|
}\
|
}\
|
type * sglib_hashed_##type##_find_member(type *table[dim], type *elem) {\
|
type * sglib_hashed_##type##_find_member(type *table[dim], type *elem) {\
|
unsigned i;\
|
unsigned i;\
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
i = ((unsigned)hash_function(elem)) % (dim);\
|
return(sglib_##type##_find_member((table)[i], elem));\
|
return(sglib_##type##_find_member((table)[i], elem));\
|
}\
|
}\
|
type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto) {\
|
type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto) {\
|
type *e;\
|
type *e;\
|
it->table = table;\
|
it->table = table;\
|
it->currentIndex = 0;\
|
it->currentIndex = 0;\
|
it->subcomparator = subcomparator;\
|
it->subcomparator = subcomparator;\
|
it->equalto = equalto;\
|
it->equalto = equalto;\
|
e = sglib_##type##_it_init_on_equal(&it->containerIt, table[it->currentIndex], it->subcomparator, it->equalto);\
|
e = sglib_##type##_it_init_on_equal(&it->containerIt, table[it->currentIndex], it->subcomparator, it->equalto);\
|
if (e==NULL) e = sglib_hashed_##type##_it_next(it);\
|
if (e==NULL) e = sglib_hashed_##type##_it_next(it);\
|
return(e);\
|
return(e);\
|
}\
|
}\
|
type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]) {\
|
type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]) {\
|
return(sglib_hashed_##type##_it_init_on_equal(it, table, NULL, NULL));\
|
return(sglib_hashed_##type##_it_init_on_equal(it, table, NULL, NULL));\
|
}\
|
}\
|
type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it) {\
|
type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it) {\
|
return(sglib_##type##_it_current(&it->containerIt));\
|
return(sglib_##type##_it_current(&it->containerIt));\
|
}\
|
}\
|
type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it) {\
|
type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it) {\
|
type *e;\
|
type *e;\
|
e = sglib_##type##_it_next(&it->containerIt);\
|
e = sglib_##type##_it_next(&it->containerIt);\
|
while (e==NULL && (++(it->currentIndex))<(dim)) {\
|
while (e==NULL && (++(it->currentIndex))<(dim)) {\
|
e = sglib_##type##_it_init_on_equal(&it->containerIt, it->table[it->currentIndex], it->subcomparator, it->equalto);\
|
e = sglib_##type##_it_init_on_equal(&it->containerIt, it->table[it->currentIndex], it->subcomparator, it->equalto);\
|
}\
|
}\
|
return(e);\
|
return(e);\
|
}
|
}
|
|
|
|
|
|
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ------------------------- DYNAMIC DATA STRUCTURES -------------------------- */
|
/* ------------------------- DYNAMIC DATA STRUCTURES -------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
|
|
|
|
|
|
/* ------------------------------------ list (level 1) -------------------------------- */
|
/* ------------------------------------ list (level 1) -------------------------------- */
|
|
|
#define SGLIB_DEFINE_LIST_PROTOTYPES(type, comparator, next) \
|
#define SGLIB_DEFINE_LIST_PROTOTYPES(type, comparator, next) \
|
struct sglib_##type##_iterator {\
|
struct sglib_##type##_iterator {\
|
type *currentelem;\
|
type *currentelem;\
|
type *nextelem;\
|
type *nextelem;\
|
int (*subcomparator)(type *, type *);\
|
int (*subcomparator)(type *, type *);\
|
type *equalto;\
|
type *equalto;\
|
};\
|
};\
|
extern void sglib_##type##_add(type **list, type *elem);\
|
extern void sglib_##type##_add(type **list, type *elem);\
|
extern int sglib_##type##_add_if_not_member(type **list, type *elem, type **member);\
|
extern int sglib_##type##_add_if_not_member(type **list, type *elem, type **member);\
|
extern void sglib_##type##_concat(type **first, type *second);\
|
extern void sglib_##type##_concat(type **first, type *second);\
|
extern void sglib_##type##_delete(type **list, type *elem);\
|
extern void sglib_##type##_delete(type **list, type *elem);\
|
extern int sglib_##type##_delete_if_member(type **list, type *elem, type **member);\
|
extern int sglib_##type##_delete_if_member(type **list, type *elem, type **member);\
|
extern int sglib_##type##_is_member(type *list, type *elem);\
|
extern int sglib_##type##_is_member(type *list, type *elem);\
|
extern type *sglib_##type##_find_member(type *list, type *elem);\
|
extern type *sglib_##type##_find_member(type *list, type *elem);\
|
extern void sglib_##type##_sort(type **list);\
|
extern void sglib_##type##_sort(type **list);\
|
extern int sglib_##type##_len(type *list);\
|
extern int sglib_##type##_len(type *list);\
|
extern void sglib_##type##_reverse(type **list);\
|
extern void sglib_##type##_reverse(type **list);\
|
extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list); \
|
extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list); \
|
extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto); \
|
extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto); \
|
extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \
|
extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \
|
extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it);
|
extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it);
|
|
|
|
|
#define SGLIB_DEFINE_LIST_FUNCTIONS(type, comparator, next) \
|
#define SGLIB_DEFINE_LIST_FUNCTIONS(type, comparator, next) \
|
int sglib_##type##_is_member(type *list, type *elem) {\
|
int sglib_##type##_is_member(type *list, type *elem) {\
|
int result;\
|
int result;\
|
SGLIB_LIST_IS_MEMBER(type, list, elem, next, result);\
|
SGLIB_LIST_IS_MEMBER(type, list, elem, next, result);\
|
return(result);\
|
return(result);\
|
}\
|
}\
|
type *sglib_##type##_find_member(type *list, type *elem) {\
|
type *sglib_##type##_find_member(type *list, type *elem) {\
|
type *result;\
|
type *result;\
|
SGLIB_LIST_FIND_MEMBER(type, list, elem, comparator, next, result);\
|
SGLIB_LIST_FIND_MEMBER(type, list, elem, comparator, next, result);\
|
return(result);\
|
return(result);\
|
}\
|
}\
|
int sglib_##type##_add_if_not_member(type **list, type *elem, type **member) {\
|
int sglib_##type##_add_if_not_member(type **list, type *elem, type **member) {\
|
SGLIB_LIST_ADD_IF_NOT_MEMBER(type, *list, elem, comparator, next, *member);\
|
SGLIB_LIST_ADD_IF_NOT_MEMBER(type, *list, elem, comparator, next, *member);\
|
return(*member==NULL);\
|
return(*member==NULL);\
|
}\
|
}\
|
void sglib_##type##_add(type **list, type *elem) {\
|
void sglib_##type##_add(type **list, type *elem) {\
|
SGLIB_LIST_ADD(type, *list, elem, next);\
|
SGLIB_LIST_ADD(type, *list, elem, next);\
|
}\
|
}\
|
void sglib_##type##_concat(type **first, type *second) {\
|
void sglib_##type##_concat(type **first, type *second) {\
|
SGLIB_LIST_CONCAT(type, *first, second, next);\
|
SGLIB_LIST_CONCAT(type, *first, second, next);\
|
}\
|
}\
|
void sglib_##type##_delete(type **list, type *elem) {\
|
void sglib_##type##_delete(type **list, type *elem) {\
|
SGLIB_LIST_DELETE(type, *list, elem, next);\
|
SGLIB_LIST_DELETE(type, *list, elem, next);\
|
}\
|
}\
|
int sglib_##type##_delete_if_member(type **list, type *elem, type **member) {\
|
int sglib_##type##_delete_if_member(type **list, type *elem, type **member) {\
|
SGLIB_LIST_DELETE_IF_MEMBER(type, *list, elem, comparator, next, *member);\
|
SGLIB_LIST_DELETE_IF_MEMBER(type, *list, elem, comparator, next, *member);\
|
return(*member!=NULL);\
|
return(*member!=NULL);\
|
}\
|
}\
|
void sglib_##type##_sort(type **list) { \
|
void sglib_##type##_sort(type **list) { \
|
SGLIB_LIST_SORT(type, *list, comparator, next);\
|
SGLIB_LIST_SORT(type, *list, comparator, next);\
|
}\
|
}\
|
int sglib_##type##_len(type *list) {\
|
int sglib_##type##_len(type *list) {\
|
int res;\
|
int res;\
|
SGLIB_LIST_LEN(type, list, next, res);\
|
SGLIB_LIST_LEN(type, list, next, res);\
|
return(res);\
|
return(res);\
|
}\
|
}\
|
void sglib_##type##_reverse(type **list) {\
|
void sglib_##type##_reverse(type **list) {\
|
SGLIB_LIST_REVERSE(type, *list, next);\
|
SGLIB_LIST_REVERSE(type, *list, next);\
|
}\
|
}\
|
\
|
\
|
type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto) {\
|
type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto) {\
|
it->subcomparator = subcomparator;\
|
it->subcomparator = subcomparator;\
|
it->equalto = equalto;\
|
it->equalto = equalto;\
|
it->nextelem = list;\
|
it->nextelem = list;\
|
return(sglib_##type##_it_next(it));\
|
return(sglib_##type##_it_next(it));\
|
}\
|
}\
|
type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list) {\
|
type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list) {\
|
return(sglib_##type##_it_init_on_equal(it, list, NULL, NULL));\
|
return(sglib_##type##_it_init_on_equal(it, list, NULL, NULL));\
|
}\
|
}\
|
type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\
|
type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\
|
return(it->currentelem);\
|
return(it->currentelem);\
|
}\
|
}\
|
type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\
|
type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\
|
type *ce, *eq;\
|
type *ce, *eq;\
|
int (*scp)(type *, type *);\
|
int (*scp)(type *, type *);\
|
ce = it->nextelem;\
|
ce = it->nextelem;\
|
it->nextelem = NULL;\
|
it->nextelem = NULL;\
|
if (it->subcomparator != NULL) {\
|
if (it->subcomparator != NULL) {\
|
eq = it->equalto; \
|
eq = it->equalto; \
|
scp = it->subcomparator;\
|
scp = it->subcomparator;\
|
while (ce!=NULL && scp(ce, eq)!=0) ce = ce->next;\
|
while (ce!=NULL && scp(ce, eq)!=0) ce = ce->next;\
|
}\
|
}\
|
it->currentelem = ce;\
|
it->currentelem = ce;\
|
if (ce != NULL) it->nextelem = ce->next;\
|
if (ce != NULL) it->nextelem = ce->next;\
|
return(ce);\
|
return(ce);\
|
}
|
}
|
|
|
/* ----------------------------- sorted list (level 1) ----------------------------------- */
|
/* ----------------------------- sorted list (level 1) ----------------------------------- */
|
|
|
|
|
#define SGLIB_DEFINE_SORTED_LIST_PROTOTYPES(type, comparator, next) \
|
#define SGLIB_DEFINE_SORTED_LIST_PROTOTYPES(type, comparator, next) \
|
struct sglib_##type##_iterator {\
|
struct sglib_##type##_iterator {\
|
type *currentelem;\
|
type *currentelem;\
|
type *nextelem;\
|
type *nextelem;\
|
int (*subcomparator)(type *, type *);\
|
int (*subcomparator)(type *, type *);\
|
type *equalto;\
|
type *equalto;\
|
};\
|
};\
|
extern void sglib_##type##_add(type **list, type *elem);\
|
extern void sglib_##type##_add(type **list, type *elem);\
|
extern int sglib_##type##_add_if_not_member(type **list, type *elem, type **member);\
|
extern int sglib_##type##_add_if_not_member(type **list, type *elem, type **member);\
|
extern void sglib_##type##_delete(type **list, type *elem);\
|
extern void sglib_##type##_delete(type **list, type *elem);\
|
extern int sglib_##type##_delete_if_member(type **list, type *elem, type **member);\
|
extern int sglib_##type##_delete_if_member(type **list, type *elem, type **member);\
|
extern int sglib_##type##_is_member(type *list, type *elem);\
|
extern int sglib_##type##_is_member(type *list, type *elem);\
|
extern type *sglib_##type##_find_member(type *list, type *elem);\
|
extern type *sglib_##type##_find_member(type *list, type *elem);\
|
extern int sglib_##type##_len(type *list);\
|
extern int sglib_##type##_len(type *list);\
|
extern void sglib_##type##_sort(type **list);\
|
extern void sglib_##type##_sort(type **list);\
|
extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list); \
|
extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list); \
|
extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto); \
|
extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto); \
|
extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \
|
extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \
|
extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it);
|
extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it);
|
|
|
|
|
#define SGLIB_DEFINE_SORTED_LIST_FUNCTIONS(type, comparator, next) \
|
#define SGLIB_DEFINE_SORTED_LIST_FUNCTIONS(type, comparator, next) \
|
int sglib_##type##_is_member(type *list, type *elem) {\
|
int sglib_##type##_is_member(type *list, type *elem) {\
|
int result;\
|
int result;\
|
SGLIB_SORTED_LIST_IS_MEMBER(type, list, elem, comparator, next, result);\
|
SGLIB_SORTED_LIST_IS_MEMBER(type, list, elem, comparator, next, result);\
|
return(result);\
|
return(result);\
|
}\
|
}\
|
type *sglib_##type##_find_member(type *list, type *elem) {\
|
type *sglib_##type##_find_member(type *list, type *elem) {\
|
type *result;\
|
type *result;\
|
SGLIB_SORTED_LIST_FIND_MEMBER(type, list, elem, comparator, next, result);\
|
SGLIB_SORTED_LIST_FIND_MEMBER(type, list, elem, comparator, next, result);\
|
return(result);\
|
return(result);\
|
}\
|
}\
|
int sglib_##type##_add_if_not_member(type **list, type *elem, type **member) {\
|
int sglib_##type##_add_if_not_member(type **list, type *elem, type **member) {\
|
SGLIB_SORTED_LIST_ADD_IF_NOT_MEMBER(type, *list, elem, comparator, next, *member);\
|
SGLIB_SORTED_LIST_ADD_IF_NOT_MEMBER(type, *list, elem, comparator, next, *member);\
|
return(*member==NULL);\
|
return(*member==NULL);\
|
}\
|
}\
|
void sglib_##type##_add(type **list, type *elem) {\
|
void sglib_##type##_add(type **list, type *elem) {\
|
SGLIB_SORTED_LIST_ADD(type, *list, elem, comparator, next);\
|
SGLIB_SORTED_LIST_ADD(type, *list, elem, comparator, next);\
|
}\
|
}\
|
void sglib_##type##_delete(type **list, type *elem) {\
|
void sglib_##type##_delete(type **list, type *elem) {\
|
SGLIB_SORTED_LIST_DELETE(type, *list, elem, next);\
|
SGLIB_SORTED_LIST_DELETE(type, *list, elem, next);\
|
}\
|
}\
|
int sglib_##type##_delete_if_member(type **list, type *elem, type **member) {\
|
int sglib_##type##_delete_if_member(type **list, type *elem, type **member) {\
|
SGLIB_SORTED_LIST_DELETE_IF_MEMBER(type, *list, elem, comparator, next, *member);\
|
SGLIB_SORTED_LIST_DELETE_IF_MEMBER(type, *list, elem, comparator, next, *member);\
|
return(*member!=NULL);\
|
return(*member!=NULL);\
|
}\
|
}\
|
int sglib_##type##_len(type *list) {\
|
int sglib_##type##_len(type *list) {\
|
int res;\
|
int res;\
|
SGLIB_SORTED_LIST_LEN(type, list, next, res);\
|
SGLIB_SORTED_LIST_LEN(type, list, next, res);\
|
return(res);\
|
return(res);\
|
}\
|
}\
|
void sglib_##type##_sort(type **list) { \
|
void sglib_##type##_sort(type **list) { \
|
SGLIB_LIST_SORT(type, *list, comparator, next);\
|
SGLIB_LIST_SORT(type, *list, comparator, next);\
|
}\
|
}\
|
\
|
\
|
type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto) {\
|
type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto) {\
|
it->subcomparator = subcomparator;\
|
it->subcomparator = subcomparator;\
|
it->equalto = equalto;\
|
it->equalto = equalto;\
|
it->nextelem = list;\
|
it->nextelem = list;\
|
return(sglib_##type##_it_next(it));\
|
return(sglib_##type##_it_next(it));\
|
}\
|
}\
|
type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list) {\
|
type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list) {\
|
return(sglib_##type##_it_init_on_equal(it, list, NULL, NULL));\
|
return(sglib_##type##_it_init_on_equal(it, list, NULL, NULL));\
|
}\
|
}\
|
type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\
|
type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\
|
return(it->currentelem);\
|
return(it->currentelem);\
|
}\
|
}\
|
type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\
|
type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\
|
type *ce, *eq;\
|
type *ce, *eq;\
|
int (*scp)(type *, type *);\
|
int (*scp)(type *, type *);\
|
int c;\
|
int c;\
|
ce = it->nextelem;\
|
ce = it->nextelem;\
|
it->nextelem = NULL;\
|
it->nextelem = NULL;\
|
if (it->subcomparator != NULL) {\
|
if (it->subcomparator != NULL) {\
|
eq = it->equalto; \
|
eq = it->equalto; \
|
scp = it->subcomparator;\
|
scp = it->subcomparator;\
|
while (ce!=NULL && (c=scp(ce, eq)) < 0) ce = ce->next;\
|
while (ce!=NULL && (c=scp(ce, eq)) < 0) ce = ce->next;\
|
if (ce != NULL && c > 0) ce = NULL;\
|
if (ce != NULL && c > 0) ce = NULL;\
|
}\
|
}\
|
it->currentelem = ce;\
|
it->currentelem = ce;\
|
if (ce != NULL) it->nextelem = ce->next;\
|
if (ce != NULL) it->nextelem = ce->next;\
|
return(ce);\
|
return(ce);\
|
}
|
}
|
|
|
|
|
/* ----------------------------- double linked list (level 1) ------------------------------ */
|
/* ----------------------------- double linked list (level 1) ------------------------------ */
|
|
|
|
|
#define SGLIB_DEFINE_DL_LIST_PROTOTYPES(type, comparator, previous, next) \
|
#define SGLIB_DEFINE_DL_LIST_PROTOTYPES(type, comparator, previous, next) \
|
struct sglib_##type##_iterator {\
|
struct sglib_##type##_iterator {\
|
type *currentelem;\
|
type *currentelem;\
|
type *prevelem;\
|
type *prevelem;\
|
type *nextelem;\
|
type *nextelem;\
|
int (*subcomparator)(type *, type *);\
|
int (*subcomparator)(type *, type *);\
|
type *equalto;\
|
type *equalto;\
|
};\
|
};\
|
extern void sglib_##type##_add(type **list, type *elem);\
|
extern void sglib_##type##_add(type **list, type *elem);\
|
extern void sglib_##type##_add_before(type **list, type *elem);\
|
extern void sglib_##type##_add_before(type **list, type *elem);\
|
extern void sglib_##type##_add_after(type **list, type *elem);\
|
extern void sglib_##type##_add_after(type **list, type *elem);\
|
extern int sglib_##type##_add_if_not_member(type **list, type *elem, type **member);\
|
extern int sglib_##type##_add_if_not_member(type **list, type *elem, type **member);\
|
extern int sglib_##type##_add_before_if_not_member(type **list, type *elem, type **member);\
|
extern int sglib_##type##_add_before_if_not_member(type **list, type *elem, type **member);\
|
extern int sglib_##type##_add_after_if_not_member(type **list, type *elem, type **member);\
|
extern int sglib_##type##_add_after_if_not_member(type **list, type *elem, type **member);\
|
extern void sglib_##type##_concat(type **first, type *second);\
|
extern void sglib_##type##_concat(type **first, type *second);\
|
extern void sglib_##type##_delete(type **list, type *elem);\
|
extern void sglib_##type##_delete(type **list, type *elem);\
|
extern int sglib_##type##_delete_if_member(type **list, type *elem, type **member);\
|
extern int sglib_##type##_delete_if_member(type **list, type *elem, type **member);\
|
extern int sglib_##type##_is_member(type *list, type *elem);\
|
extern int sglib_##type##_is_member(type *list, type *elem);\
|
extern type *sglib_##type##_find_member(type *list, type *elem);\
|
extern type *sglib_##type##_find_member(type *list, type *elem);\
|
extern type *sglib_##type##_get_first(type *list);\
|
extern type *sglib_##type##_get_first(type *list);\
|
extern type *sglib_##type##_get_last(type *list);\
|
extern type *sglib_##type##_get_last(type *list);\
|
extern void sglib_##type##_sort(type **list);\
|
extern void sglib_##type##_sort(type **list);\
|
extern int sglib_##type##_len(type *list);\
|
extern int sglib_##type##_len(type *list);\
|
extern void sglib_##type##_reverse(type **list);\
|
extern void sglib_##type##_reverse(type **list);\
|
extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list); \
|
extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list); \
|
extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto); \
|
extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto); \
|
extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \
|
extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \
|
extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it);
|
extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it);
|
|
|
|
|
#define SGLIB_DEFINE_DL_LIST_FUNCTIONS(type, comparator, previous, next) \
|
#define SGLIB_DEFINE_DL_LIST_FUNCTIONS(type, comparator, previous, next) \
|
void sglib_##type##_add(type **list, type *elem) {\
|
void sglib_##type##_add(type **list, type *elem) {\
|
SGLIB_DL_LIST_ADD(type, *list, elem, previous, next);\
|
SGLIB_DL_LIST_ADD(type, *list, elem, previous, next);\
|
}\
|
}\
|
void sglib_##type##_add_after(type **list, type *elem) {\
|
void sglib_##type##_add_after(type **list, type *elem) {\
|
SGLIB_DL_LIST_ADD_AFTER(type, *list, elem, previous, next);\
|
SGLIB_DL_LIST_ADD_AFTER(type, *list, elem, previous, next);\
|
}\
|
}\
|
void sglib_##type##_add_before(type **list, type *elem) {\
|
void sglib_##type##_add_before(type **list, type *elem) {\
|
SGLIB_DL_LIST_ADD_BEFORE(type, *list, elem, previous, next);\
|
SGLIB_DL_LIST_ADD_BEFORE(type, *list, elem, previous, next);\
|
}\
|
}\
|
int sglib_##type##_add_if_not_member(type **list, type *elem, type **member) {\
|
int sglib_##type##_add_if_not_member(type **list, type *elem, type **member) {\
|
SGLIB_DL_LIST_ADD_IF_NOT_MEMBER(type, *list, elem, comparator, previous, next, *member);\
|
SGLIB_DL_LIST_ADD_IF_NOT_MEMBER(type, *list, elem, comparator, previous, next, *member);\
|
return(*member==NULL);\
|
return(*member==NULL);\
|
}\
|
}\
|
int sglib_##type##_add_after_if_not_member(type **list, type *elem, type **member) {\
|
int sglib_##type##_add_after_if_not_member(type **list, type *elem, type **member) {\
|
SGLIB_DL_LIST_ADD_AFTER_IF_NOT_MEMBER(type, *list, elem, comparator, previous, next, *member);\
|
SGLIB_DL_LIST_ADD_AFTER_IF_NOT_MEMBER(type, *list, elem, comparator, previous, next, *member);\
|
return(*member==NULL);\
|
return(*member==NULL);\
|
}\
|
}\
|
int sglib_##type##_add_before_if_not_member(type **list, type *elem, type **member) {\
|
int sglib_##type##_add_before_if_not_member(type **list, type *elem, type **member) {\
|
SGLIB_DL_LIST_ADD_BEFORE_IF_NOT_MEMBER(type, *list, elem, comparator, previous, next, *member);\
|
SGLIB_DL_LIST_ADD_BEFORE_IF_NOT_MEMBER(type, *list, elem, comparator, previous, next, *member);\
|
return(*member==NULL);\
|
return(*member==NULL);\
|
}\
|
}\
|
void sglib_##type##_concat(type **first, type *second) {\
|
void sglib_##type##_concat(type **first, type *second) {\
|
SGLIB_DL_LIST_CONCAT(type, *first, second, previous, next);\
|
SGLIB_DL_LIST_CONCAT(type, *first, second, previous, next);\
|
}\
|
}\
|
void sglib_##type##_delete(type **list, type *elem) {\
|
void sglib_##type##_delete(type **list, type *elem) {\
|
SGLIB_DL_LIST_DELETE(type, *list, elem, previous, next);\
|
SGLIB_DL_LIST_DELETE(type, *list, elem, previous, next);\
|
}\
|
}\
|
int sglib_##type##_delete_if_member(type **list, type *elem, type **member) {\
|
int sglib_##type##_delete_if_member(type **list, type *elem, type **member) {\
|
SGLIB_DL_LIST_DELETE_IF_MEMBER(type, *list, elem, comparator, previous, next, *member);\
|
SGLIB_DL_LIST_DELETE_IF_MEMBER(type, *list, elem, comparator, previous, next, *member);\
|
return(*member!=NULL);\
|
return(*member!=NULL);\
|
}\
|
}\
|
int sglib_##type##_is_member(type *list, type *elem) {\
|
int sglib_##type##_is_member(type *list, type *elem) {\
|
int result;\
|
int result;\
|
SGLIB_DL_LIST_IS_MEMBER(type, list, elem, previous, next, result);\
|
SGLIB_DL_LIST_IS_MEMBER(type, list, elem, previous, next, result);\
|
return(result);\
|
return(result);\
|
}\
|
}\
|
type *sglib_##type##_find_member(type *list, type *elem) {\
|
type *sglib_##type##_find_member(type *list, type *elem) {\
|
type *result;\
|
type *result;\
|
SGLIB_DL_LIST_FIND_MEMBER(type, list, elem, comparator, previous, next, result);\
|
SGLIB_DL_LIST_FIND_MEMBER(type, list, elem, comparator, previous, next, result);\
|
return(result);\
|
return(result);\
|
}\
|
}\
|
type *sglib_##type##_get_first(type *list) {\
|
type *sglib_##type##_get_first(type *list) {\
|
type *result;\
|
type *result;\
|
SGLIB_DL_LIST_GET_FIRST(type, list, previous, next, result);\
|
SGLIB_DL_LIST_GET_FIRST(type, list, previous, next, result);\
|
return(result);\
|
return(result);\
|
}\
|
}\
|
type *sglib_##type##_get_last(type *list) {\
|
type *sglib_##type##_get_last(type *list) {\
|
type *result;\
|
type *result;\
|
SGLIB_DL_LIST_GET_LAST(type, list, previous, next, result);\
|
SGLIB_DL_LIST_GET_LAST(type, list, previous, next, result);\
|
return(result);\
|
return(result);\
|
}\
|
}\
|
void sglib_##type##_sort(type **list) {\
|
void sglib_##type##_sort(type **list) {\
|
SGLIB_DL_LIST_SORT(type, *list, comparator, previous, next);\
|
SGLIB_DL_LIST_SORT(type, *list, comparator, previous, next);\
|
}\
|
}\
|
int sglib_##type##_len(type *list) {\
|
int sglib_##type##_len(type *list) {\
|
int res;\
|
int res;\
|
SGLIB_DL_LIST_LEN(type, list, previous, next, res);\
|
SGLIB_DL_LIST_LEN(type, list, previous, next, res);\
|
return(res);\
|
return(res);\
|
}\
|
}\
|
void sglib_##type##_reverse(type **list) {\
|
void sglib_##type##_reverse(type **list) {\
|
SGLIB_DL_LIST_REVERSE(type, *list, previous, next);\
|
SGLIB_DL_LIST_REVERSE(type, *list, previous, next);\
|
}\
|
}\
|
\
|
\
|
type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto) {\
|
type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto) {\
|
it->subcomparator = subcomparator;\
|
it->subcomparator = subcomparator;\
|
it->equalto = equalto;\
|
it->equalto = equalto;\
|
it->prevelem = list;\
|
it->prevelem = list;\
|
it->nextelem = list;\
|
it->nextelem = list;\
|
if (list != NULL) it->nextelem = list->next;\
|
if (list != NULL) it->nextelem = list->next;\
|
return(sglib_##type##_it_next(it));\
|
return(sglib_##type##_it_next(it));\
|
}\
|
}\
|
type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list) {\
|
type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list) {\
|
return(sglib_##type##_it_init_on_equal(it, list, NULL, NULL));\
|
return(sglib_##type##_it_init_on_equal(it, list, NULL, NULL));\
|
}\
|
}\
|
type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\
|
type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\
|
return(it->currentelem);\
|
return(it->currentelem);\
|
}\
|
}\
|
type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\
|
type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\
|
type *ce, *eq;\
|
type *ce, *eq;\
|
int (*scp)(type *, type *);\
|
int (*scp)(type *, type *);\
|
ce = it->prevelem;\
|
ce = it->prevelem;\
|
it->prevelem = NULL;\
|
it->prevelem = NULL;\
|
if (it->subcomparator != NULL) {\
|
if (it->subcomparator != NULL) {\
|
eq = it->equalto; \
|
eq = it->equalto; \
|
scp = it->subcomparator;\
|
scp = it->subcomparator;\
|
while (ce!=NULL && scp(eq, ce)!=0) ce = ce->previous;\
|
while (ce!=NULL && scp(eq, ce)!=0) ce = ce->previous;\
|
}\
|
}\
|
if (ce != NULL) {\
|
if (ce != NULL) {\
|
it->prevelem = ce->previous;\
|
it->prevelem = ce->previous;\
|
} else {\
|
} else {\
|
ce = it->nextelem;\
|
ce = it->nextelem;\
|
it->nextelem = NULL;\
|
it->nextelem = NULL;\
|
if (it->subcomparator != NULL) {\
|
if (it->subcomparator != NULL) {\
|
eq = it->equalto; \
|
eq = it->equalto; \
|
scp = it->subcomparator;\
|
scp = it->subcomparator;\
|
while (ce!=NULL && scp(ce, eq)!=0) ce = ce->next;\
|
while (ce!=NULL && scp(ce, eq)!=0) ce = ce->next;\
|
}\
|
}\
|
if (ce != NULL) it->nextelem = ce->next;\
|
if (ce != NULL) it->nextelem = ce->next;\
|
}\
|
}\
|
it->currentelem = ce;\
|
it->currentelem = ce;\
|
return(ce);\
|
return(ce);\
|
}
|
}
|
|
|
|
|
/* --------------------------------- red-black trees (level 1) -------------------------------- */
|
/* --------------------------------- red-black trees (level 1) -------------------------------- */
|
|
|
/*
|
/*
|
|
|
This implementation requires pointers to left and right sons (no
|
This implementation requires pointers to left and right sons (no
|
parent pointer is needed) and one bit of additional information
|
parent pointer is needed) and one bit of additional information
|
storing the color of the node. The implementation follows discrepancy
|
storing the color of the node. The implementation follows discrepancy
|
fixing rules from:
|
fixing rules from:
|
http://www.cis.ohio-state.edu/~gurari/course/cis680/cis680Ch11.html
|
http://www.cis.ohio-state.edu/~gurari/course/cis680/cis680Ch11.html
|
|
|
*/
|
*/
|
|
|
#define SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, leftt, rightt, bits, RED, BLACK) {\
|
#define SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, leftt, rightt, bits, RED, BLACK) {\
|
type *t, *tl, *a, *b, *c, *ar, *bl, *br, *cl, *cr;\
|
type *t, *tl, *a, *b, *c, *ar, *bl, *br, *cl, *cr;\
|
t = *tree;\
|
t = *tree;\
|
tl = t->leftt;\
|
tl = t->leftt;\
|
if (t->rightt!=NULL && SGLIB___GET_VALUE(t->rightt->bits)==RED) {\
|
if (t->rightt!=NULL && SGLIB___GET_VALUE(t->rightt->bits)==RED) {\
|
if (SGLIB___GET_VALUE(tl->bits)==RED) {\
|
if (SGLIB___GET_VALUE(tl->bits)==RED) {\
|
if ((tl->leftt!=NULL && SGLIB___GET_VALUE(tl->leftt->bits)==RED) \
|
if ((tl->leftt!=NULL && SGLIB___GET_VALUE(tl->leftt->bits)==RED) \
|
|| (tl->rightt!=NULL && SGLIB___GET_VALUE(tl->rightt->bits)==RED)) {\
|
|| (tl->rightt!=NULL && SGLIB___GET_VALUE(tl->rightt->bits)==RED)) {\
|
SGLIB___SET_VALUE(t->leftt->bits,BLACK);\
|
SGLIB___SET_VALUE(t->leftt->bits,BLACK);\
|
SGLIB___SET_VALUE(t->rightt->bits,BLACK);\
|
SGLIB___SET_VALUE(t->rightt->bits,BLACK);\
|
SGLIB___SET_VALUE(t->bits,RED);\
|
SGLIB___SET_VALUE(t->bits,RED);\
|
}\
|
}\
|
}\
|
}\
|
} else {\
|
} else {\
|
if (SGLIB___GET_VALUE(tl->bits)==RED) {\
|
if (SGLIB___GET_VALUE(tl->bits)==RED) {\
|
if (tl->leftt!=NULL && SGLIB___GET_VALUE(tl->leftt->bits)==RED) {\
|
if (tl->leftt!=NULL && SGLIB___GET_VALUE(tl->leftt->bits)==RED) {\
|
a = t; b = tl; c = tl->leftt;\
|
a = t; b = tl; c = tl->leftt;\
|
br = b->rightt;\
|
br = b->rightt;\
|
a->leftt = br;\
|
a->leftt = br;\
|
b->leftt = c; b->rightt = a;\
|
b->leftt = c; b->rightt = a;\
|
SGLIB___SET_VALUE(a->bits,RED);\
|
SGLIB___SET_VALUE(a->bits,RED);\
|
SGLIB___SET_VALUE(b->bits,BLACK);\
|
SGLIB___SET_VALUE(b->bits,BLACK);\
|
*tree = b;\
|
*tree = b;\
|
} else if (tl->rightt!=NULL && SGLIB___GET_VALUE(tl->rightt->bits)==RED) {\
|
} else if (tl->rightt!=NULL && SGLIB___GET_VALUE(tl->rightt->bits)==RED) {\
|
a = t; b = tl; ar=a->rightt;\
|
a = t; b = tl; ar=a->rightt;\
|
bl=b->leftt; c=b->rightt;\
|
bl=b->leftt; c=b->rightt;\
|
cl=c->leftt; cr=c->rightt;\
|
cl=c->leftt; cr=c->rightt;\
|
b->rightt = cl;\
|
b->rightt = cl;\
|
a->leftt = cr;\
|
a->leftt = cr;\
|
c->leftt = b;\
|
c->leftt = b;\
|
c->rightt = a;\
|
c->rightt = a;\
|
SGLIB___SET_VALUE(c->bits,BLACK);\
|
SGLIB___SET_VALUE(c->bits,BLACK);\
|
SGLIB___SET_VALUE(a->bits,RED);\
|
SGLIB___SET_VALUE(a->bits,RED);\
|
*tree = c;\
|
*tree = c;\
|
}\
|
}\
|
}\
|
}\
|
}\
|
}\
|
}
|
}
|
|
|
#define SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, leftt, rightt, bits, RED, BLACK, res) {\
|
#define SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, leftt, rightt, bits, RED, BLACK, res) {\
|
type *t, *a, *b, *c, *d, *ar, *bl, *br, *cl, *cr, *dl, *dr;\
|
type *t, *a, *b, *c, *d, *ar, *bl, *br, *cl, *cr, *dl, *dr;\
|
t = a = *tree;\
|
t = a = *tree;\
|
assert(t!=NULL);\
|
assert(t!=NULL);\
|
ar = a->rightt;\
|
ar = a->rightt;\
|
b = t->leftt;\
|
b = t->leftt;\
|
if (b==NULL) {\
|
if (b==NULL) {\
|
assert(SGLIB___GET_VALUE(t->bits)==RED);\
|
assert(SGLIB___GET_VALUE(t->bits)==RED);\
|
SGLIB___SET_VALUE(t->bits,BLACK);\
|
SGLIB___SET_VALUE(t->bits,BLACK);\
|
res = 0;\
|
res = 0;\
|
} else {\
|
} else {\
|
bl = b->leftt;\
|
bl = b->leftt;\
|
br = b->rightt;\
|
br = b->rightt;\
|
if (SGLIB___GET_VALUE(b->bits)==RED) {\
|
if (SGLIB___GET_VALUE(b->bits)==RED) {\
|
if (br==NULL) {\
|
if (br==NULL) {\
|
*tree = b;\
|
*tree = b;\
|
SGLIB___SET_VALUE(b->bits,BLACK);\
|
SGLIB___SET_VALUE(b->bits,BLACK);\
|
b->rightt = a;\
|
b->rightt = a;\
|
a->leftt = br;\
|
a->leftt = br;\
|
res = 0;\
|
res = 0;\
|
} else {\
|
} else {\
|
c = br;\
|
c = br;\
|
assert(c!=NULL && SGLIB___GET_VALUE(c->bits)==BLACK);\
|
assert(c!=NULL && SGLIB___GET_VALUE(c->bits)==BLACK);\
|
cl = c->leftt;\
|
cl = c->leftt;\
|
cr = c->rightt;\
|
cr = c->rightt;\
|
if ((cl==NULL||SGLIB___GET_VALUE(cl->bits)==BLACK) && (cr==NULL||SGLIB___GET_VALUE(cr->bits)==BLACK)) {\
|
if ((cl==NULL||SGLIB___GET_VALUE(cl->bits)==BLACK) && (cr==NULL||SGLIB___GET_VALUE(cr->bits)==BLACK)) {\
|
*tree = b;\
|
*tree = b;\
|
b->rightt = a;\
|
b->rightt = a;\
|
SGLIB___SET_VALUE(b->bits,BLACK);\
|
SGLIB___SET_VALUE(b->bits,BLACK);\
|
a->leftt = c;\
|
a->leftt = c;\
|
SGLIB___SET_VALUE(c->bits,RED);\
|
SGLIB___SET_VALUE(c->bits,RED);\
|
res = 0;\
|
res = 0;\
|
} else if (cl!=NULL && SGLIB___GET_VALUE(cl->bits)==RED) {\
|
} else if (cl!=NULL && SGLIB___GET_VALUE(cl->bits)==RED) {\
|
if (cr!=NULL && SGLIB___GET_VALUE(cr->bits)==RED) {\
|
if (cr!=NULL && SGLIB___GET_VALUE(cr->bits)==RED) {\
|
d = cr;\
|
d = cr;\
|
dl = d->leftt;\
|
dl = d->leftt;\
|
dr = d->rightt;\
|
dr = d->rightt;\
|
*tree = d;\
|
*tree = d;\
|
SGLIB___SET_VALUE(d->bits,BLACK);\
|
SGLIB___SET_VALUE(d->bits,BLACK);\
|
d->leftt = b;\
|
d->leftt = b;\
|
c->rightt = dl;\
|
c->rightt = dl;\
|
d->rightt = a;\
|
d->rightt = a;\
|
a->leftt = dr;\
|
a->leftt = dr;\
|
res = 0;\
|
res = 0;\
|
} else {\
|
} else {\
|
*tree = c;\
|
*tree = c;\
|
c->leftt = b;\
|
c->leftt = b;\
|
c->rightt = a;\
|
c->rightt = a;\
|
b->leftt = bl;\
|
b->leftt = bl;\
|
b->rightt = cl;\
|
b->rightt = cl;\
|
a->leftt = cr;\
|
a->leftt = cr;\
|
SGLIB___SET_VALUE(cl->bits,BLACK);\
|
SGLIB___SET_VALUE(cl->bits,BLACK);\
|
res = 0;\
|
res = 0;\
|
}\
|
}\
|
} else if (cr!=NULL && SGLIB___GET_VALUE(cr->bits)==RED) {\
|
} else if (cr!=NULL && SGLIB___GET_VALUE(cr->bits)==RED) {\
|
assert(cl==NULL || SGLIB___GET_VALUE(cl->bits)==BLACK);\
|
assert(cl==NULL || SGLIB___GET_VALUE(cl->bits)==BLACK);\
|
d = cr;\
|
d = cr;\
|
dl = d->leftt;\
|
dl = d->leftt;\
|
dr = d->rightt;\
|
dr = d->rightt;\
|
*tree = d;\
|
*tree = d;\
|
SGLIB___SET_VALUE(d->bits,BLACK);\
|
SGLIB___SET_VALUE(d->bits,BLACK);\
|
d->leftt = b;\
|
d->leftt = b;\
|
c->rightt = dl;\
|
c->rightt = dl;\
|
d->rightt = a;\
|
d->rightt = a;\
|
a->leftt = dr;\
|
a->leftt = dr;\
|
res = 0;\
|
res = 0;\
|
} else {\
|
} else {\
|
assert(0);\
|
assert(0);\
|
res = 0;\
|
res = 0;\
|
}\
|
}\
|
}\
|
}\
|
} else {\
|
} else {\
|
if ((bl==NULL || SGLIB___GET_VALUE(bl->bits)==BLACK) && (br==NULL || SGLIB___GET_VALUE(br->bits)==BLACK)) {\
|
if ((bl==NULL || SGLIB___GET_VALUE(bl->bits)==BLACK) && (br==NULL || SGLIB___GET_VALUE(br->bits)==BLACK)) {\
|
res = (SGLIB___GET_VALUE(a->bits)==BLACK);\
|
res = (SGLIB___GET_VALUE(a->bits)==BLACK);\
|
SGLIB___SET_VALUE(a->bits,BLACK);\
|
SGLIB___SET_VALUE(a->bits,BLACK);\
|
SGLIB___SET_VALUE(b->bits,RED);\
|
SGLIB___SET_VALUE(b->bits,RED);\
|
} else if (bl!=NULL && SGLIB___GET_VALUE(bl->bits)==RED) {\
|
} else if (bl!=NULL && SGLIB___GET_VALUE(bl->bits)==RED) {\
|
if (br==NULL || SGLIB___GET_VALUE(br->bits)==BLACK) {\
|
if (br==NULL || SGLIB___GET_VALUE(br->bits)==BLACK) {\
|
*tree = b;\
|
*tree = b;\
|
SGLIB___SET_VALUE(b->bits,SGLIB___GET_VALUE(a->bits));\
|
SGLIB___SET_VALUE(b->bits,SGLIB___GET_VALUE(a->bits));\
|
SGLIB___SET_VALUE(a->bits,BLACK);\
|
SGLIB___SET_VALUE(a->bits,BLACK);\
|
b->rightt = a;\
|
b->rightt = a;\
|
a->leftt = br;\
|
a->leftt = br;\
|
SGLIB___SET_VALUE(bl->bits,BLACK);\
|
SGLIB___SET_VALUE(bl->bits,BLACK);\
|
res = 0;\
|
res = 0;\
|
} else {\
|
} else {\
|
assert(bl!=NULL);\
|
assert(bl!=NULL);\
|
assert(br!=NULL);\
|
assert(br!=NULL);\
|
assert(SGLIB___GET_VALUE(bl->bits)==RED);\
|
assert(SGLIB___GET_VALUE(bl->bits)==RED);\
|
assert(SGLIB___GET_VALUE(br->bits)==RED);\
|
assert(SGLIB___GET_VALUE(br->bits)==RED);\
|
c = br;\
|
c = br;\
|
cl = c->leftt;\
|
cl = c->leftt;\
|
cr = c->rightt;\
|
cr = c->rightt;\
|
*tree = c;\
|
*tree = c;\
|
SGLIB___SET_VALUE(c->bits,SGLIB___GET_VALUE(a->bits));\
|
SGLIB___SET_VALUE(c->bits,SGLIB___GET_VALUE(a->bits));\
|
SGLIB___SET_VALUE(a->bits,BLACK);\
|
SGLIB___SET_VALUE(a->bits,BLACK);\
|
c->leftt = b;\
|
c->leftt = b;\
|
c->rightt = a;\
|
c->rightt = a;\
|
b->rightt = cl;\
|
b->rightt = cl;\
|
a->leftt = cr;\
|
a->leftt = cr;\
|
res = 0;\
|
res = 0;\
|
}\
|
}\
|
} else {\
|
} else {\
|
assert(br!=NULL && SGLIB___GET_VALUE(br->bits)==RED);\
|
assert(br!=NULL && SGLIB___GET_VALUE(br->bits)==RED);\
|
c = br;\
|
c = br;\
|
cl = c->leftt;\
|
cl = c->leftt;\
|
cr = c->rightt;\
|
cr = c->rightt;\
|
*tree = c;\
|
*tree = c;\
|
SGLIB___SET_VALUE(c->bits,SGLIB___GET_VALUE(a->bits));\
|
SGLIB___SET_VALUE(c->bits,SGLIB___GET_VALUE(a->bits));\
|
SGLIB___SET_VALUE(a->bits,BLACK);\
|
SGLIB___SET_VALUE(a->bits,BLACK);\
|
c->leftt = b;\
|
c->leftt = b;\
|
c->rightt = a;\
|
c->rightt = a;\
|
b->rightt = cl;\
|
b->rightt = cl;\
|
a->leftt = cr;\
|
a->leftt = cr;\
|
res = 0;\
|
res = 0;\
|
}\
|
}\
|
}\
|
}\
|
}\
|
}\
|
}
|
}
|
|
|
|
|
#define SGLIB_DEFINE_RBTREE_FUNCTIONS_GENERAL(type, left, right, bits, comparator, RED, BLACK) \
|
#define SGLIB_DEFINE_RBTREE_FUNCTIONS_GENERAL(type, left, right, bits, comparator, RED, BLACK) \
|
static void sglib___##type##_fix_left_insertion_discrepancy(type **tree) {\
|
static void sglib___##type##_fix_left_insertion_discrepancy(type **tree) {\
|
SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, left, right, bits, RED, BLACK);\
|
SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, left, right, bits, RED, BLACK);\
|
}\
|
}\
|
\
|
\
|
static void sglib___##type##_fix_right_insertion_discrepancy(type **tree) {\
|
static void sglib___##type##_fix_right_insertion_discrepancy(type **tree) {\
|
SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, right, left, bits, RED, BLACK);\
|
SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, right, left, bits, RED, BLACK);\
|
}\
|
}\
|
\
|
\
|
static int sglib___##type##_fix_left_deletion_discrepancy(type **tree) {\
|
static int sglib___##type##_fix_left_deletion_discrepancy(type **tree) {\
|
int res;\
|
int res;\
|
SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, right, left, bits, RED, BLACK, res);\
|
SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, right, left, bits, RED, BLACK, res);\
|
return(res);\
|
return(res);\
|
}\
|
}\
|
\
|
\
|
static int sglib___##type##_fix_right_deletion_discrepancy(type **tree) {\
|
static int sglib___##type##_fix_right_deletion_discrepancy(type **tree) {\
|
int res;\
|
int res;\
|
SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, left, right, bits, RED, BLACK, res);\
|
SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, left, right, bits, RED, BLACK, res);\
|
return(res);\
|
return(res);\
|
}\
|
}\
|
\
|
\
|
static void sglib___##type##_add_recursive(type **tree, type *elem) {\
|
static void sglib___##type##_add_recursive(type **tree, type *elem) {\
|
int cmp;\
|
int cmp;\
|
type *t;\
|
type *t;\
|
t = *tree;\
|
t = *tree;\
|
if (t == NULL) {\
|
if (t == NULL) {\
|
SGLIB___SET_VALUE(elem->bits,RED);\
|
SGLIB___SET_VALUE(elem->bits,RED);\
|
*tree =elem;\
|
*tree =elem;\
|
} else {\
|
} else {\
|
cmp = comparator(elem, t);\
|
cmp = comparator(elem, t);\
|
if (cmp < 0 || (cmp==0 && elem<t)) {\
|
if (cmp < 0 || (cmp==0 && elem<t)) {\
|
sglib___##type##_add_recursive(&t->left, elem);\
|
sglib___##type##_add_recursive(&t->left, elem);\
|
if (SGLIB___GET_VALUE(t->bits)==BLACK) sglib___##type##_fix_left_insertion_discrepancy(tree);\
|
if (SGLIB___GET_VALUE(t->bits)==BLACK) sglib___##type##_fix_left_insertion_discrepancy(tree);\
|
} else {\
|
} else {\
|
sglib___##type##_add_recursive(&t->right, elem);\
|
sglib___##type##_add_recursive(&t->right, elem);\
|
if (SGLIB___GET_VALUE(t->bits)==BLACK) sglib___##type##_fix_right_insertion_discrepancy(tree);\
|
if (SGLIB___GET_VALUE(t->bits)==BLACK) sglib___##type##_fix_right_insertion_discrepancy(tree);\
|
}\
|
}\
|
}\
|
}\
|
}\
|
}\
|
\
|
\
|
static int sglib___##type##_delete_rightmost_leaf(type **tree, type **theLeaf) {\
|
static int sglib___##type##_delete_rightmost_leaf(type **tree, type **theLeaf) {\
|
type *t;\
|
type *t;\
|
int res, deepDecreased;\
|
int res, deepDecreased;\
|
t = *tree;\
|
t = *tree;\
|
res = 0;\
|
res = 0;\
|
assert(t!=NULL);\
|
assert(t!=NULL);\
|
if (t->right == NULL) {\
|
if (t->right == NULL) {\
|
*theLeaf = t;\
|
*theLeaf = t;\
|
if (t->left!=NULL) {\
|
if (t->left!=NULL) {\
|
if (SGLIB___GET_VALUE(t->bits)==BLACK && SGLIB___GET_VALUE(t->left->bits)==BLACK) res = 1;\
|
if (SGLIB___GET_VALUE(t->bits)==BLACK && SGLIB___GET_VALUE(t->left->bits)==BLACK) res = 1;\
|
SGLIB___SET_VALUE(t->left->bits,BLACK);\
|
SGLIB___SET_VALUE(t->left->bits,BLACK);\
|
*tree = t->left;\
|
*tree = t->left;\
|
} else {\
|
} else {\
|
*tree = NULL;\
|
*tree = NULL;\
|
res = (SGLIB___GET_VALUE(t->bits)==BLACK);\
|
res = (SGLIB___GET_VALUE(t->bits)==BLACK);\
|
}\
|
}\
|
} else {\
|
} else {\
|
deepDecreased = sglib___##type##_delete_rightmost_leaf(&t->right, theLeaf);\
|
deepDecreased = sglib___##type##_delete_rightmost_leaf(&t->right, theLeaf);\
|
if (deepDecreased) res = sglib___##type##_fix_right_deletion_discrepancy(tree);\
|
if (deepDecreased) res = sglib___##type##_fix_right_deletion_discrepancy(tree);\
|
}\
|
}\
|
return(res);\
|
return(res);\
|
}\
|
}\
|
\
|
\
|
int sglib___##type##_delete_recursive(type **tree, type *elem) {\
|
int sglib___##type##_delete_recursive(type **tree, type *elem) {\
|
type *t, *theLeaf;\
|
type *t, *theLeaf;\
|
int cmp, res, deepDecreased;\
|
int cmp, res, deepDecreased;\
|
t = *tree;\
|
t = *tree;\
|
res = 0;\
|
res = 0;\
|
if (t==NULL) {\
|
if (t==NULL) {\
|
assert(0 && "The element to delete not found in the tree, use 'delete_if_member'"!=NULL);\
|
assert(0 && "The element to delete not found in the tree, use 'delete_if_member'"!=NULL);\
|
} else {\
|
} else {\
|
cmp = comparator(elem, t);\
|
cmp = comparator(elem, t);\
|
if (cmp < 0 || (cmp==0 && elem<t)) {\
|
if (cmp < 0 || (cmp==0 && elem<t)) {\
|
deepDecreased = sglib___##type##_delete_recursive(&t->left, elem);\
|
deepDecreased = sglib___##type##_delete_recursive(&t->left, elem);\
|
if (deepDecreased) {\
|
if (deepDecreased) {\
|
res = sglib___##type##_fix_left_deletion_discrepancy(tree);\
|
res = sglib___##type##_fix_left_deletion_discrepancy(tree);\
|
}\
|
}\
|
} else if (cmp > 0 || (cmp==0 && elem>t)) {\
|
} else if (cmp > 0 || (cmp==0 && elem>t)) {\
|
deepDecreased = sglib___##type##_delete_recursive(&t->right, elem);\
|
deepDecreased = sglib___##type##_delete_recursive(&t->right, elem);\
|
if (deepDecreased) {\
|
if (deepDecreased) {\
|
res = sglib___##type##_fix_right_deletion_discrepancy(tree);\
|
res = sglib___##type##_fix_right_deletion_discrepancy(tree);\
|
}\
|
}\
|
} else {\
|
} else {\
|
assert(elem==t && "Deleting an element which is non member of the tree, use 'delete_if_member'"!=NULL);\
|
assert(elem==t && "Deleting an element which is non member of the tree, use 'delete_if_member'"!=NULL);\
|
if (t->left == NULL) {\
|
if (t->left == NULL) {\
|
if (t->right == NULL) {\
|
if (t->right == NULL) {\
|
/* a leaf, delete, it; */\
|
/* a leaf, delete, it; */\
|
*tree = NULL;\
|
*tree = NULL;\
|
res = (SGLIB___GET_VALUE(t->bits)==BLACK);\
|
res = (SGLIB___GET_VALUE(t->bits)==BLACK);\
|
} else {\
|
} else {\
|
if (SGLIB___GET_VALUE(t->bits)==0 && SGLIB___GET_VALUE(t->right->bits)==0) res = 1;\
|
if (SGLIB___GET_VALUE(t->bits)==0 && SGLIB___GET_VALUE(t->right->bits)==0) res = 1;\
|
SGLIB___SET_VALUE(t->right->bits,BLACK);\
|
SGLIB___SET_VALUE(t->right->bits,BLACK);\
|
*tree = t->right;\
|
*tree = t->right;\
|
}\
|
}\
|
} else {\
|
} else {\
|
/* propagate deletion until righmost leaf of left subtree */\
|
/* propagate deletion until righmost leaf of left subtree */\
|
deepDecreased = sglib___##type##_delete_rightmost_leaf(&t->left, &theLeaf);\
|
deepDecreased = sglib___##type##_delete_rightmost_leaf(&t->left, &theLeaf);\
|
theLeaf->left = t->left;\
|
theLeaf->left = t->left;\
|
theLeaf->right = t->right;\
|
theLeaf->right = t->right;\
|
SGLIB___SET_VALUE(theLeaf->bits,SGLIB___GET_VALUE(t->bits));\
|
SGLIB___SET_VALUE(theLeaf->bits,SGLIB___GET_VALUE(t->bits));\
|
*tree = theLeaf;\
|
*tree = theLeaf;\
|
if (deepDecreased) res = sglib___##type##_fix_left_deletion_discrepancy(tree);\
|
if (deepDecreased) res = sglib___##type##_fix_left_deletion_discrepancy(tree);\
|
}\
|
}\
|
}\
|
}\
|
}\
|
}\
|
return(res);\
|
return(res);\
|
}\
|
}\
|
\
|
\
|
void sglib_##type##_add(type **tree, type *elem) {\
|
void sglib_##type##_add(type **tree, type *elem) {\
|
elem->left = elem->right = NULL;\
|
elem->left = elem->right = NULL;\
|
sglib___##type##_add_recursive(tree, elem);\
|
sglib___##type##_add_recursive(tree, elem);\
|
SGLIB___SET_VALUE((*tree)->bits,BLACK);\
|
SGLIB___SET_VALUE((*tree)->bits,BLACK);\
|
}\
|
}\
|
\
|
\
|
void sglib_##type##_delete(type **tree, type *elem) {\
|
void sglib_##type##_delete(type **tree, type *elem) {\
|
sglib___##type##_delete_recursive(tree, elem);\
|
sglib___##type##_delete_recursive(tree, elem);\
|
if (*tree!=NULL) SGLIB___SET_VALUE((*tree)->bits,BLACK);\
|
if (*tree!=NULL) SGLIB___SET_VALUE((*tree)->bits,BLACK);\
|
}\
|
}\
|
\
|
\
|
type *sglib_##type##_find_member(type *t, type *elem) {\
|
type *sglib_##type##_find_member(type *t, type *elem) {\
|
type *res;\
|
type *res;\
|
SGLIB___BIN_TREE_FIND_MEMBER(type, t, elem, left, right, comparator, res);\
|
SGLIB___BIN_TREE_FIND_MEMBER(type, t, elem, left, right, comparator, res);\
|
return(res);\
|
return(res);\
|
}\
|
}\
|
\
|
\
|
int sglib_##type##_is_member(type *t, type *elem) {\
|
int sglib_##type##_is_member(type *t, type *elem) {\
|
int cmp;\
|
int cmp;\
|
while (t!=NULL) {\
|
while (t!=NULL) {\
|
cmp = comparator(elem, t);\
|
cmp = comparator(elem, t);\
|
if (cmp < 0 || (cmp==0 && elem<t)) {\
|
if (cmp < 0 || (cmp==0 && elem<t)) {\
|
t = t->left;\
|
t = t->left;\
|
} else if (cmp > 0 || (cmp==0 && elem>t)) {\
|
} else if (cmp > 0 || (cmp==0 && elem>t)) {\
|
t = t->right;\
|
t = t->right;\
|
} else {\
|
} else {\
|
assert(t == elem);\
|
assert(t == elem);\
|
return(1);\
|
return(1);\
|
}\
|
}\
|
}\
|
}\
|
return(0);\
|
return(0);\
|
}\
|
}\
|
\
|
\
|
int sglib_##type##_delete_if_member(type **tree, type *elem, type **memb) {\
|
int sglib_##type##_delete_if_member(type **tree, type *elem, type **memb) {\
|
if ((*memb=sglib_##type##_find_member(*tree, elem))!=NULL) {\
|
if ((*memb=sglib_##type##_find_member(*tree, elem))!=NULL) {\
|
sglib_##type##_delete(tree, *memb);\
|
sglib_##type##_delete(tree, *memb);\
|
return(1);\
|
return(1);\
|
} else {\
|
} else {\
|
return(0);\
|
return(0);\
|
}\
|
}\
|
}\
|
}\
|
int sglib_##type##_add_if_not_member(type **tree, type *elem, type **memb) {\
|
int sglib_##type##_add_if_not_member(type **tree, type *elem, type **memb) {\
|
if ((*memb=sglib_##type##_find_member(*tree, elem))==NULL) {\
|
if ((*memb=sglib_##type##_find_member(*tree, elem))==NULL) {\
|
sglib_##type##_add(tree, elem);\
|
sglib_##type##_add(tree, elem);\
|
return(1);\
|
return(1);\
|
} else {\
|
} else {\
|
return(0);\
|
return(0);\
|
}\
|
}\
|
}\
|
}\
|
int sglib_##type##_len(type *t) {\
|
int sglib_##type##_len(type *t) {\
|
int n;\
|
int n;\
|
type *e;\
|
type *e;\
|
n = 0;\
|
n = 0;\
|
SGLIB_BIN_TREE_MAP_ON_ELEMENTS(type, t, e, left, right, n++);\
|
SGLIB_BIN_TREE_MAP_ON_ELEMENTS(type, t, e, left, right, n++);\
|
return(n);\
|
return(n);\
|
}\
|
}\
|
\
|
\
|
void sglib__##type##_it_compute_current_elem(struct sglib_##type##_iterator *it) {\
|
void sglib__##type##_it_compute_current_elem(struct sglib_##type##_iterator *it) {\
|
int i,j,cmp;\
|
int i,j,cmp;\
|
type *s, *eqt;\
|
type *s, *eqt;\
|
int (*subcomparator)(type *, type *);\
|
int (*subcomparator)(type *, type *);\
|
eqt = it->equalto;\
|
eqt = it->equalto;\
|
subcomparator = it->subcomparator;\
|
subcomparator = it->subcomparator;\
|
it->currentelem = NULL;\
|
it->currentelem = NULL;\
|
while(it->pathi > 0 && it->currentelem==NULL) {\
|
while(it->pathi > 0 && it->currentelem==NULL) {\
|
i = it->pathi-1;\
|
i = it->pathi-1;\
|
if (i >= 0) {\
|
if (i >= 0) {\
|
if (it->pass[i] >= 2) {\
|
if (it->pass[i] >= 2) {\
|
/* goto up */\
|
/* goto up */\
|
it->pathi --;\
|
it->pathi --;\
|
} else {\
|
} else {\
|
if (it->pass[i] == 0) {\
|
if (it->pass[i] == 0) {\
|
/* goto left */\
|
/* goto left */\
|
s = it->path[i]->left;\
|
s = it->path[i]->left;\
|
} else {\
|
} else {\
|
/* goto right */\
|
/* goto right */\
|
s = it->path[i]->right;\
|
s = it->path[i]->right;\
|
}\
|
}\
|
if (eqt != NULL) {\
|
if (eqt != NULL) {\
|
if (subcomparator == NULL) {\
|
if (subcomparator == NULL) {\
|
SGLIB___BIN_TREE_FIND_MEMBER(type, s, eqt, left, right, comparator, s);\
|
SGLIB___BIN_TREE_FIND_MEMBER(type, s, eqt, left, right, comparator, s);\
|
} else {\
|
} else {\
|
SGLIB___BIN_TREE_FIND_MEMBER(type, s, eqt, left, right, subcomparator, s);\
|
SGLIB___BIN_TREE_FIND_MEMBER(type, s, eqt, left, right, subcomparator, s);\
|
}\
|
}\
|
}\
|
}\
|
if (s != NULL) {\
|
if (s != NULL) {\
|
j = i+1;\
|
j = i+1;\
|
it->path[j] = s;\
|
it->path[j] = s;\
|
it->pass[j] = 0;\
|
it->pass[j] = 0;\
|
it->pathi ++;\
|
it->pathi ++;\
|
}\
|
}\
|
it->pass[i] ++;\
|
it->pass[i] ++;\
|
}\
|
}\
|
}\
|
}\
|
if (it->pathi>0 && it->order == it->pass[it->pathi-1]) {\
|
if (it->pathi>0 && it->order == it->pass[it->pathi-1]) {\
|
it->currentelem = it->path[it->pathi-1];\
|
it->currentelem = it->path[it->pathi-1];\
|
}\
|
}\
|
}\
|
}\
|
}\
|
}\
|
type *sglib__##type##_it_init(struct sglib_##type##_iterator *it, type *tree, int order, int (*subcomparator)(type *, type *), type *equalto) {\
|
type *sglib__##type##_it_init(struct sglib_##type##_iterator *it, type *tree, int order, int (*subcomparator)(type *, type *), type *equalto) {\
|
type *t;\
|
type *t;\
|
assert(it!=NULL);\
|
assert(it!=NULL);\
|
it->order = order;\
|
it->order = order;\
|
it->equalto = equalto;\
|
it->equalto = equalto;\
|
it->subcomparator = subcomparator;\
|
it->subcomparator = subcomparator;\
|
if (equalto == NULL) { \
|
if (equalto == NULL) { \
|
t = tree;\
|
t = tree;\
|
} else {\
|
} else {\
|
if (subcomparator == NULL) {\
|
if (subcomparator == NULL) {\
|
SGLIB___BIN_TREE_FIND_MEMBER(type, tree, equalto, left, right, comparator, t);\
|
SGLIB___BIN_TREE_FIND_MEMBER(type, tree, equalto, left, right, comparator, t);\
|
} else {\
|
} else {\
|
SGLIB___BIN_TREE_FIND_MEMBER(type, tree, equalto, left, right, subcomparator, t);\
|
SGLIB___BIN_TREE_FIND_MEMBER(type, tree, equalto, left, right, subcomparator, t);\
|
}\
|
}\
|
}\
|
}\
|
if (t == NULL) {\
|
if (t == NULL) {\
|
it->pathi = 0;\
|
it->pathi = 0;\
|
it->currentelem = NULL;\
|
it->currentelem = NULL;\
|
} else {\
|
} else {\
|
it->pathi = 1;\
|
it->pathi = 1;\
|
it->pass[0] = 0;\
|
it->pass[0] = 0;\
|
it->path[0] = t;\
|
it->path[0] = t;\
|
if (order == 0) {\
|
if (order == 0) {\
|
it->currentelem = t;\
|
it->currentelem = t;\
|
} else {\
|
} else {\
|
sglib__##type##_it_compute_current_elem(it);\
|
sglib__##type##_it_compute_current_elem(it);\
|
}\
|
}\
|
}\
|
}\
|
return(it->currentelem);\
|
return(it->currentelem);\
|
}\
|
}\
|
type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *tree) {\
|
type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *tree) {\
|
return(sglib__##type##_it_init(it, tree, 2, NULL, NULL));\
|
return(sglib__##type##_it_init(it, tree, 2, NULL, NULL));\
|
}\
|
}\
|
type *sglib_##type##_it_init_preorder(struct sglib_##type##_iterator *it, type *tree) {\
|
type *sglib_##type##_it_init_preorder(struct sglib_##type##_iterator *it, type *tree) {\
|
return(sglib__##type##_it_init(it, tree, 0, NULL, NULL));\
|
return(sglib__##type##_it_init(it, tree, 0, NULL, NULL));\
|
}\
|
}\
|
type *sglib_##type##_it_init_inorder(struct sglib_##type##_iterator *it, type *tree) {\
|
type *sglib_##type##_it_init_inorder(struct sglib_##type##_iterator *it, type *tree) {\
|
return(sglib__##type##_it_init(it, tree, 1, NULL, NULL));\
|
return(sglib__##type##_it_init(it, tree, 1, NULL, NULL));\
|
}\
|
}\
|
type *sglib_##type##_it_init_postorder(struct sglib_##type##_iterator *it, type *tree) {\
|
type *sglib_##type##_it_init_postorder(struct sglib_##type##_iterator *it, type *tree) {\
|
return(sglib__##type##_it_init(it, tree, 2, NULL, NULL));\
|
return(sglib__##type##_it_init(it, tree, 2, NULL, NULL));\
|
}\
|
}\
|
type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *tree, int (*subcomparator)(type *, type *), type *equalto) {\
|
type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *tree, int (*subcomparator)(type *, type *), type *equalto) {\
|
return(sglib__##type##_it_init(it, tree, 1, subcomparator, equalto));\
|
return(sglib__##type##_it_init(it, tree, 1, subcomparator, equalto));\
|
}\
|
}\
|
type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\
|
type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\
|
return(it->currentelem);\
|
return(it->currentelem);\
|
}\
|
}\
|
type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\
|
type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\
|
sglib__##type##_it_compute_current_elem(it);\
|
sglib__##type##_it_compute_current_elem(it);\
|
return(it->currentelem);\
|
return(it->currentelem);\
|
}\
|
}\
|
\
|
\
|
static void sglib___##type##_consistency_check_recursive(type *t, int *pathdeep, int cdeep) {\
|
static void sglib___##type##_consistency_check_recursive(type *t, int *pathdeep, int cdeep) {\
|
if (t==NULL) {\
|
if (t==NULL) {\
|
if (*pathdeep < 0) *pathdeep = cdeep;\
|
if (*pathdeep < 0) *pathdeep = cdeep;\
|
else assert(*pathdeep == cdeep);\
|
else assert(*pathdeep == cdeep);\
|
} else {\
|
} else {\
|
if (t->left!=NULL) assert(comparator(t->left, t) <= 0);\
|
if (t->left!=NULL) assert(comparator(t->left, t) <= 0);\
|
if (t->right!=NULL) assert(comparator(t, t->right) <= 0);\
|
if (t->right!=NULL) assert(comparator(t, t->right) <= 0);\
|
if (SGLIB___GET_VALUE(t->bits) == RED) {\
|
if (SGLIB___GET_VALUE(t->bits) == RED) {\
|
assert(t->left == NULL || SGLIB___GET_VALUE(t->left->bits)==BLACK);\
|
assert(t->left == NULL || SGLIB___GET_VALUE(t->left->bits)==BLACK);\
|
assert(t->right == NULL || SGLIB___GET_VALUE(t->right->bits)==BLACK);\
|
assert(t->right == NULL || SGLIB___GET_VALUE(t->right->bits)==BLACK);\
|
sglib___##type##_consistency_check_recursive(t->left, pathdeep, cdeep);\
|
sglib___##type##_consistency_check_recursive(t->left, pathdeep, cdeep);\
|
sglib___##type##_consistency_check_recursive(t->right, pathdeep, cdeep);\
|
sglib___##type##_consistency_check_recursive(t->right, pathdeep, cdeep);\
|
} else {\
|
} else {\
|
sglib___##type##_consistency_check_recursive(t->left, pathdeep, cdeep+1);\
|
sglib___##type##_consistency_check_recursive(t->left, pathdeep, cdeep+1);\
|
sglib___##type##_consistency_check_recursive(t->right, pathdeep, cdeep+1);\
|
sglib___##type##_consistency_check_recursive(t->right, pathdeep, cdeep+1);\
|
}\
|
}\
|
}\
|
}\
|
}\
|
}\
|
\
|
\
|
void sglib___##type##_consistency_check(type *t) {\
|
void sglib___##type##_consistency_check(type *t) {\
|
int pathDeep;\
|
int pathDeep;\
|
assert(t==NULL || SGLIB___GET_VALUE(t->bits) == BLACK);\
|
assert(t==NULL || SGLIB___GET_VALUE(t->bits) == BLACK);\
|
pathDeep = -1;\
|
pathDeep = -1;\
|
sglib___##type##_consistency_check_recursive(t, &pathDeep, 0);\
|
sglib___##type##_consistency_check_recursive(t, &pathDeep, 0);\
|
}
|
}
|
|
|
|
|
#define SGLIB_DEFINE_RBTREE_PROTOTYPES(type, left, right, colorbit, comparator) \
|
#define SGLIB_DEFINE_RBTREE_PROTOTYPES(type, left, right, colorbit, comparator) \
|
struct sglib_##type##_iterator {\
|
struct sglib_##type##_iterator {\
|
type *currentelem;\
|
type *currentelem;\
|
char pass[SGLIB_MAX_TREE_DEEP];\
|
char pass[SGLIB_MAX_TREE_DEEP];\
|
type *path[SGLIB_MAX_TREE_DEEP];\
|
type *path[SGLIB_MAX_TREE_DEEP];\
|
short int pathi;\
|
short int pathi;\
|
short int order;\
|
short int order;\
|
type *equalto;\
|
type *equalto;\
|
int (*subcomparator)(type *, type *);\
|
int (*subcomparator)(type *, type *);\
|
};\
|
};\
|
extern void sglib___##type##_consistency_check(type *t); \
|
extern void sglib___##type##_consistency_check(type *t); \
|
extern void sglib_##type##_add(type **tree, type *elem); \
|
extern void sglib_##type##_add(type **tree, type *elem); \
|
extern int sglib_##type##_add_if_not_member(type **tree, type *elem, type **memb); \
|
extern int sglib_##type##_add_if_not_member(type **tree, type *elem, type **memb); \
|
extern void sglib_##type##_delete(type **tree, type *elem); \
|
extern void sglib_##type##_delete(type **tree, type *elem); \
|
extern int sglib_##type##_delete_if_member(type **tree, type *elem, type **memb); \
|
extern int sglib_##type##_delete_if_member(type **tree, type *elem, type **memb); \
|
extern int sglib_##type##_is_member(type *t, type *elem); \
|
extern int sglib_##type##_is_member(type *t, type *elem); \
|
extern type *sglib_##type##_find_member(type *t, type *elem); \
|
extern type *sglib_##type##_find_member(type *t, type *elem); \
|
extern int sglib_##type##_len(type *t); \
|
extern int sglib_##type##_len(type *t); \
|
extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *tree); \
|
extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *tree); \
|
extern type *sglib_##type##_it_init_preorder(struct sglib_##type##_iterator *it, type *tree); \
|
extern type *sglib_##type##_it_init_preorder(struct sglib_##type##_iterator *it, type *tree); \
|
extern type *sglib_##type##_it_init_inorder(struct sglib_##type##_iterator *it, type *tree); \
|
extern type *sglib_##type##_it_init_inorder(struct sglib_##type##_iterator *it, type *tree); \
|
extern type *sglib_##type##_it_init_postorder(struct sglib_##type##_iterator *it, type *tree); \
|
extern type *sglib_##type##_it_init_postorder(struct sglib_##type##_iterator *it, type *tree); \
|
extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *tree, int (*subcomparator)(type *, type *), type *equalto); \
|
extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *tree, int (*subcomparator)(type *, type *), type *equalto); \
|
extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \
|
extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \
|
extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it); \
|
extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it); \
|
|
|
|
|
#define SGLIB_DEFINE_RBTREE_FUNCTIONS(type, left, right, colorbit, comparator) \
|
#define SGLIB_DEFINE_RBTREE_FUNCTIONS(type, left, right, colorbit, comparator) \
|
SGLIB_DEFINE_RBTREE_FUNCTIONS_GENERAL(type, left, right, colorbit, comparator, 1, 0)
|
SGLIB_DEFINE_RBTREE_FUNCTIONS_GENERAL(type, left, right, colorbit, comparator, 1, 0)
|
|
|
|
|
|
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* - SUPPLEMENTARY DEFINITIONS - */
|
/* - SUPPLEMENTARY DEFINITIONS - */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
/* ---------------------------------------------------------------------------- */
|
|
|
|
|
#define SGLIB___GET_VALUE(x) (x)
|
#define SGLIB___GET_VALUE(x) (x)
|
#define SGLIB___SET_VALUE(x, value) {(x) = (value);}
|
#define SGLIB___SET_VALUE(x, value) {(x) = (value);}
|
#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_;}
|
#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_;}
|
|
|
|
|
#define SGLIB_NUMERIC_COMPARATOR(x, y) ((int)((x) - (y)))
|
#define SGLIB_NUMERIC_COMPARATOR(x, y) ((int)((x) - (y)))
|
#define SGLIB_REVERSE_NUMERIC_COMPARATOR(x, y) ((int)((y) - (x)))
|
#define SGLIB_REVERSE_NUMERIC_COMPARATOR(x, y) ((int)((y) - (x)))
|
|
|
#ifndef SGLIB_MAX_TREE_DEEP
|
#ifndef SGLIB_MAX_TREE_DEEP
|
#define SGLIB_MAX_TREE_DEEP 128
|
#define SGLIB_MAX_TREE_DEEP 128
|
#endif
|
#endif
|
|
|
#ifndef SGLIB_HASH_TAB_SHIFT_CONSTANT
|
#ifndef SGLIB_HASH_TAB_SHIFT_CONSTANT
|
#define SGLIB_HASH_TAB_SHIFT_CONSTANT 211 /* should be a prime */
|
#define SGLIB_HASH_TAB_SHIFT_CONSTANT 211 /* should be a prime */
|
#endif
|
#endif
|
|
|
#endif /* _SGLIB__h_ */
|
#endif /* _SGLIB__h_ */
|
|
|
