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