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