diff options
author | Bardur Arantsson <bardur@scientician.net> | 2014-12-18 00:00:35 +0100 |
---|---|---|
committer | Bardur Arantsson <bardur@scientician.net> | 2014-12-18 00:00:35 +0100 |
commit | 76d1d3f63fef965ba0a2d5ccea3408ad36e9ce4c (patch) | |
tree | 08b7758fc22456584b6fb3477c30bf569e79d500 /src | |
parent | d34f472970e6a9fa2257a63ed40d021fc2c6f045 (diff) |
Remove all uses of sglib
Diffstat (limited to 'src')
-rw-r--r-- | src/CMakeLists.txt | 2 | ||||
-rw-r--r-- | src/angband.h | 6 | ||||
-rw-r--r-- | src/cave.cc | 1 | ||||
-rw-r--r-- | src/cmd4.cc | 2 | ||||
-rw-r--r-- | src/cmd6.cc | 3 | ||||
-rw-r--r-- | src/device_allocation.cc | 10 | ||||
-rw-r--r-- | src/device_allocation.h | 6 | ||||
-rw-r--r-- | src/device_allocation_fwd.h | 1 | ||||
-rw-r--r-- | src/dice.cc | 2 | ||||
-rw-r--r-- | src/externs.h | 2 | ||||
-rw-r--r-- | src/generate.cc | 1 | ||||
-rw-r--r-- | src/gods.cc | 2 | ||||
-rw-r--r-- | src/include/sglib.h | 1952 | ||||
-rw-r--r-- | src/loadsave.cc | 1 | ||||
-rw-r--r-- | src/main-gtk2.c | 1 | ||||
-rw-r--r-- | src/melee2.cc | 2 | ||||
-rw-r--r-- | src/modules.cc | 1 | ||||
-rw-r--r-- | src/object2.cc | 2 | ||||
-rw-r--r-- | src/q_fireprof.cc | 2 | ||||
-rw-r--r-- | src/q_library.cc | 2 | ||||
-rw-r--r-- | src/quark.cc | 3 | ||||
-rw-r--r-- | src/range.cc | 2 | ||||
-rw-r--r-- | src/spell_idx_list.hpp | 11 | ||||
-rw-r--r-- | src/spell_idx_list_fwd.h | 3 | ||||
-rw-r--r-- | src/spell_type.cc | 99 | ||||
-rw-r--r-- | src/spell_type.h | 1 | ||||
-rw-r--r-- | src/spells2.cc | 1 | ||||
-rw-r--r-- | src/spells3.cc | 23 | ||||
-rw-r--r-- | src/spells4.cc | 86 | ||||
-rw-r--r-- | src/spells6.cc | 47 | ||||
-rw-r--r-- | src/store.cc | 3 | ||||
-rw-r--r-- | src/string_list.cc | 55 | ||||
-rw-r--r-- | src/string_list.h | 30 | ||||
-rw-r--r-- | src/types.h | 14 | ||||
-rw-r--r-- | src/types_fwd.h | 3 | ||||
-rw-r--r-- | src/xtra1.cc | 3 |
36 files changed, 140 insertions, 2245 deletions
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 3b2c5b2f..dbe722ad 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -22,7 +22,7 @@ SET(SRCS spells1.cc spells2.cc spells3.cc spells4.cc spells5.cc spells6.cc spell_type.cc device_allocation.cc corrupt.cc joke.cc mimic.cc - status.cc files.cc notes.cc loadsave.cc string_list.cc + status.cc files.cc notes.cc loadsave.cc cmd1.cc cmd2.cc cmd3.cc cmd4.cc cmd5.cc cmd6.cc cmd7.cc help.cc hiscore.cc range.cc dice.cc generate.cc gen_maze.cc gen_evol.cc wild.cc levels.cc store.cc bldg.cc diff --git a/src/angband.h b/src/angband.h index 12cdd822..306b1f45 100644 --- a/src/angband.h +++ b/src/angband.h @@ -44,12 +44,6 @@ extern "C" { /* - * SGLIB - */ -#include "sglib.h" - - -/* * Now, include the define's, the type's, and the extern's */ #include "defines.h" diff --git a/src/cave.cc b/src/cave.cc index d77c146b..c962829a 100644 --- a/src/cave.cc +++ b/src/cave.cc @@ -6,6 +6,7 @@ #include "angband.h" #include "q_rand.h" +#include <cassert> #include <vector> #include <iterator> #include <algorithm> diff --git a/src/cmd4.cc b/src/cmd4.cc index c2cde07b..13ce6d0f 100644 --- a/src/cmd4.cc +++ b/src/cmd4.cc @@ -11,10 +11,10 @@ */ #include "angband.h" - #include "messages.h" #include "hooks.h" +#include <cassert> #include <memory> #include <string> #include <vector> diff --git a/src/cmd6.cc b/src/cmd6.cc index 025a5c8b..05d87564 100644 --- a/src/cmd6.cc +++ b/src/cmd6.cc @@ -11,10 +11,11 @@ */ #include "angband.h" - #include "spell_type.h" #include "hooks.h" +#include <cassert> + /* * Forward declare */ diff --git a/src/device_allocation.cc b/src/device_allocation.cc index f97de2ec..9d8267e8 100644 --- a/src/device_allocation.cc +++ b/src/device_allocation.cc @@ -1,13 +1,8 @@ #include "device_allocation.h" -int compare_device_allocation(device_allocation *a, device_allocation *b) -{ - return SGLIB_NUMERIC_COMPARATOR(a->tval, b->tval); -} - -SGLIB_DEFINE_LIST_FUNCTIONS(device_allocation, compare_device_allocation, next); +#include <cassert> -void device_allocation_init(device_allocation *device_allocation, byte tval) +static void device_allocation_init(device_allocation *device_allocation, byte tval) { assert(device_allocation != NULL); @@ -15,7 +10,6 @@ void device_allocation_init(device_allocation *device_allocation, byte tval) device_allocation->rarity = 0; range_init(&device_allocation->base_level, 0, 0); range_init(&device_allocation->max_level, 0, 0); - device_allocation->next = NULL; } device_allocation *device_allocation_new(byte tval) diff --git a/src/device_allocation.h b/src/device_allocation.h index e620270f..f4fc5c38 100644 --- a/src/device_allocation.h +++ b/src/device_allocation.h @@ -16,14 +16,8 @@ struct device_allocation s32b rarity; range_type base_level; range_type max_level; - /* Next device allocation in the list */ - device_allocation *next; }; -int compare_device_allocation(device_allocation *a, device_allocation *b); -SGLIB_DEFINE_LIST_PROTOTYPES(device_allocation, compare_device_allocation, next); - -void device_allocation_init(struct device_allocation *device_allocation, byte tval); struct device_allocation *device_allocation_new(byte tval); #ifdef __cplusplus diff --git a/src/device_allocation_fwd.h b/src/device_allocation_fwd.h index 7bc0e0b0..1bfe41a1 100644 --- a/src/device_allocation_fwd.h +++ b/src/device_allocation_fwd.h @@ -9,7 +9,6 @@ extern "C" { typedef struct device_allocation device_allocation; struct device_allocation; -void device_allocation_init(struct device_allocation *device_allocation, byte tval); struct device_allocation *device_allocation_new(byte tval); #ifdef __cplusplus diff --git a/src/dice.cc b/src/dice.cc index ea9b7533..2f024d6a 100644 --- a/src/dice.cc +++ b/src/dice.cc @@ -1,5 +1,7 @@ #include "dice.h" +#include <cassert> + void dice_init(dice_type *dice, long base, long num, long sides) { assert(dice != NULL); diff --git a/src/externs.h b/src/externs.h index 430cef2b..281a4e8c 100644 --- a/src/externs.h +++ b/src/externs.h @@ -1831,8 +1831,6 @@ const char *varda_star_kindler_info(); /* spells4.c */ -SGLIB_DEFINE_LIST_PROTOTYPES(spell_idx_list, compare_spell_idx, next); - extern s32b SCHOOL_AIR; extern s32b SCHOOL_AULE; extern s32b SCHOOL_CONVEYANCE; diff --git a/src/generate.cc b/src/generate.cc index 4b8e1f3f..595e8f9f 100644 --- a/src/generate.cc +++ b/src/generate.cc @@ -13,6 +13,7 @@ #include "angband.h" #include "hooks.h" +#include <cassert> #include <memory> #include <vector> diff --git a/src/gods.cc b/src/gods.cc index f940e21a..9fdbfeb5 100644 --- a/src/gods.cc +++ b/src/gods.cc @@ -12,6 +12,8 @@ #include "angband.h" +#include <cassert> + /* * Add amt piety is god is god */ diff --git a/src/include/sglib.h b/src/include/sglib.h deleted file mode 100644 index 1a4780fa..00000000 --- a/src/include/sglib.h +++ /dev/null @@ -1,1952 +0,0 @@ -/* - - 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 <assert.h> - - -/* ---------------------------------------------------------------------------- */ -/* ---------------------------------------------------------------------------- */ -/* - 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_ = 1;\ - 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_;\ - for(_p_ = (list); _p_!=NULL && comparator(_p_, (elem)) < 0; _p_=_p_->next) ;\ - while (_p_ != NULL && _p_ != (elem) && 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) {\ - (comparator_result) = -1;\ - for((member_ptr) = &(list); \ - *(member_ptr)!=NULL && ((comparator_result)=comparator((*member_ptr), (elem))) < 0; \ - (member_ptr) = &(*(member_ptr))->next) ;\ -} - -#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 && elem<t)) {\ - sglib___##type##_add_recursive(&t->left, 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 && elem<t)) {\ - deepDecreased = sglib___##type##_delete_recursive(&t->left, 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 && elem<t)) {\ - t = t->left;\ - } 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_SAFE_NUMERIC_COMPARATOR(x, y) (((x)>(y)?1:((x)<(y)?-1:0))) -#define SGLIB_SAFE_REVERSE_NUMERIC_COMPARATOR(x, y) (((x)>(y)?-1:((x)<(y)?1:0))) -#define SGLIB_FAST_NUMERIC_COMPARATOR(x, y) ((int)((x) - (y))) -#define SGLIB_FAST_REVERSE_NUMERIC_COMPARATOR(x, y) ((int)((y) - (x))) -#define SGLIB_NUMERIC_COMPARATOR(x, y) SGLIB_SAFE_NUMERIC_COMPARATOR(x, y) -#define SGLIB_REVERSE_NUMERIC_COMPARATOR(x, y) SGLIB_SAFE_REVERSE_NUMERIC_COMPARATOR(x, y) - -#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_ */ diff --git a/src/loadsave.cc b/src/loadsave.cc index 5f2b6e69..b2f8962f 100644 --- a/src/loadsave.cc +++ b/src/loadsave.cc @@ -10,6 +10,7 @@ #include "quark.h" #include "hooks.h" +#include <cassert> #include <memory> static void do_byte(byte *, int); diff --git a/src/main-gtk2.c b/src/main-gtk2.c index 10e7d9f0..ab3ce50e 100644 --- a/src/main-gtk2.c +++ b/src/main-gtk2.c @@ -51,6 +51,7 @@ #include <sys/stat.h> #include <unistd.h> #include <dirent.h> +#include <assert.h> /* diff --git a/src/melee2.cc b/src/melee2.cc index a7975638..f35e1e80 100644 --- a/src/melee2.cc +++ b/src/melee2.cc @@ -21,6 +21,8 @@ #include "quark.h" #include "hooks.h" +#include <cassert> + #define SPEAK_CHANCE 8 #define GRINDNOISE 20 diff --git a/src/modules.cc b/src/modules.cc index 2e16adbc..cab3685b 100644 --- a/src/modules.cc +++ b/src/modules.cc @@ -9,6 +9,7 @@ #include "angband.h" #include "hooks.h" +#include <cassert> #include <chrono> #include <thread> diff --git a/src/object2.cc b/src/object2.cc index 2a17e140..4a3f295c 100644 --- a/src/object2.cc +++ b/src/object2.cc @@ -11,11 +11,11 @@ */ #include "angband.h" - #include "spell_type.h" #include "device_allocation.h" #include "hooks.h" +#include <cassert> #include <vector> /* diff --git a/src/q_fireprof.cc b/src/q_fireprof.cc index a515335f..bc1bae72 100644 --- a/src/q_fireprof.cc +++ b/src/q_fireprof.cc @@ -2,6 +2,8 @@ #include "quark.h" #include "hooks.h" +#include <cassert> + #define cquest (quest[QUEST_FIREPROOF]) #define print_hook(fmt,...) do { fprintf(hook_file, fmt, ##__VA_ARGS__); } while (0) diff --git a/src/q_library.cc b/src/q_library.cc index 5541da51..b0968f01 100644 --- a/src/q_library.cc +++ b/src/q_library.cc @@ -2,6 +2,8 @@ #include "quark.h" #include "hooks.h" +#include <cassert> + #define cquest (quest[QUEST_LIBRARY]) #define print_hook(fmt,...) do { fprintf(hook_file, fmt, ##__VA_ARGS__); } while (0) diff --git a/src/quark.cc b/src/quark.cc index 8a78b6f8..f6db6653 100644 --- a/src/quark.cc +++ b/src/quark.cc @@ -1,7 +1,8 @@ #include "quark.h" - #include "angband.h" +#include <cassert> + /* * The number of quarks */ diff --git a/src/range.cc b/src/range.cc index 0cb21469..412c187a 100644 --- a/src/range.cc +++ b/src/range.cc @@ -1,5 +1,7 @@ #include "range.h" +#include <cassert> + void range_init(range_type *range, s32b min, s32b max) { assert(range != NULL); diff --git a/src/spell_idx_list.hpp b/src/spell_idx_list.hpp new file mode 100644 index 00000000..ad913e83 --- /dev/null +++ b/src/spell_idx_list.hpp @@ -0,0 +1,11 @@ +#pragma once + +#include "spell_idx_list_fwd.h" +#include <vector> +// FIXME: h-basic for the s32b? + +struct spell_idx_list { + // FIXME: stupidity because we can't "override" a fwd-declared-struct directly + std::vector<s32b> v; +}; + diff --git a/src/spell_idx_list_fwd.h b/src/spell_idx_list_fwd.h new file mode 100644 index 00000000..b961eb4e --- /dev/null +++ b/src/spell_idx_list_fwd.h @@ -0,0 +1,3 @@ +#pragma once + +struct spell_idx_list; diff --git a/src/spell_type.cc b/src/spell_type.cc index 33de3d7a..50aadc30 100644 --- a/src/spell_type.cc +++ b/src/spell_type.cc @@ -1,11 +1,13 @@ #include "spell_type.h" -#include "string_list.h" #include "range.h" #include "device_allocation.h" #include "dice.h" #include "angband.h" +#include <cassert> +#include <vector> +#include <string> #include <type_traits> #define SCHOOL_IDXS_MAX 3 @@ -15,9 +17,10 @@ */ struct spell_type { + // FIXME: most of this stuff shouldn't be public cptr name; /* Name */ byte skill_level; /* Required level (to learn) */ - string_list *description; /* List of strings */ + std::vector<std::string> m_description; /* List of strings */ casting_result (*effect_func)(int o_idx); /* Spell effect function */ const char* (*info_func)(); /* Information function */ @@ -33,7 +36,7 @@ struct spell_type bool_ castable_while_confused; dice_type device_charges; /* Number of charges for devices */ - struct device_allocation *device_allocation; /* Allocation table for devices */ + std::vector<device_allocation *> m_device_allocation; /* Allocation table for devices */ /* FIXME: shouldn't really be pointer-to, but... */ s16b random_type; /* Type of random items in which skill may appear */ @@ -48,6 +51,36 @@ struct spell_type int school_idxs_count; s32b school_idxs[3]; + +public: + + // FIXME: forbi copy-ctor + move + etc? + + spell_type(cptr _name): + name(_name), + skill_level(0), + m_description(), + effect_func(nullptr), + info_func(nullptr), + lasting_func(nullptr), + depend_func(nullptr), + minimum_pval(0), + casting_type(USE_SPELL_POINTS /* FIXME: ??? */), + casting_stat(0), + castable_while_blind(FALSE), + castable_while_confused(FALSE), + device_charges({ 0, 0, 0 }), + m_device_allocation(), + random_type(-1), + failure_rate(0), + inertia_difficulty(-1), + inertia_delay(-1), + mana_range({ -1, -1 }), + activation_timeout({ 0, 0, 0 }), + school_idxs_count(0), + school_idxs({ -1, -1, -1 }) { + } + }; static void school_idx_add_new(spell_type *spell, s32b i) @@ -59,32 +92,6 @@ static void school_idx_add_new(spell_type *spell, s32b i) spell->school_idxs_count++; } -void spell_type_init(spell_type *spell, cptr name) -{ - assert(spell != NULL); - - static_assert(std::is_pod<spell_type>::value, "Cannot memset non-POD type"); - memset(spell, 0, sizeof(spell_type)); - - spell->name = name; - spell->description = NULL; - spell->effect_func = NULL; - spell->info_func = NULL; - spell->lasting_func = NULL; - spell->depend_func = NULL; - - spell->device_allocation = NULL; - - spell->school_idxs_count = 0; - - spell->random_type = -1; - - spell->castable_while_blind = FALSE; - spell->castable_while_confused = FALSE; - - spell_type_set_inertia(spell, -1, -1); -} - void spell_type_set_inertia(spell_type *spell, s32b difficulty, s32b delay) { assert(spell != NULL); @@ -253,7 +260,7 @@ void spell_type_describe(spell_type *spell, cptr line) { assert(spell != NULL); - string_list_append(&spell->description, line); + spell->m_description.push_back(std::string(line)); } void spell_type_add_school(spell_type *spell, s32b school_idx) @@ -272,15 +279,13 @@ void spell_type_add_device_allocation(spell_type *spell, struct device_allocatio { assert(spell != NULL); assert(a != NULL); - - sglib_device_allocation_add(&spell->device_allocation, a); + spell->m_device_allocation.push_back(a); } spell_type *spell_type_new(cptr name) { - spell_type *spell = new spell_type; + spell_type *spell = new spell_type(name); assert(spell != NULL); - spell_type_init(spell, name); return spell; } @@ -312,16 +317,10 @@ int spell_type_skill_level(spell_type *spell) void spell_type_description_foreach(spell_type *spell, void (*callback)(void *data, cptr text), void *data) { - string_list *sl; - struct sglib_string_list_iterator it; - assert(callback != NULL); - - for (sl = sglib_string_list_it_init(&it, spell->description); - sl != NULL; - sl = sglib_string_list_it_next(&it)) + for (auto line: spell->m_description) { - callback(data, sl->s); + callback(data, line.c_str()); // FIXME: inefficient and dangerous! } } @@ -336,10 +335,9 @@ void spell_type_activation_description(spell_type *spell, char *buf) dice_print(&spell->activation_timeout, turns); - assert(spell->description != NULL); - assert(spell->description->s != NULL); + assert(spell->m_description.size() > 0); - sprintf(buf, "%s every %s turns", spell->description->s, turns); + sprintf(buf, "%s every %s turns", spell->m_description.at(0).c_str() /* FIXME: ugh */, turns); } int spell_type_activation_roll_timeout(spell_type *spell) @@ -349,16 +347,11 @@ int spell_type_activation_roll_timeout(spell_type *spell) device_allocation *spell_type_device_allocation(spell_type *spell, byte tval) { - struct sglib_device_allocation_iterator it; - device_allocation *device_allocation; - - for (device_allocation = sglib_device_allocation_it_init(&it, spell->device_allocation); - device_allocation != NULL; - device_allocation = sglib_device_allocation_it_next(&it)) + for (auto device_allocation_ptr: spell->m_device_allocation) { - if (device_allocation->tval == tval) + if (device_allocation_ptr->tval == tval) { - return device_allocation; + return device_allocation_ptr; } } diff --git a/src/spell_type.h b/src/spell_type.h index eb96c0b9..14f30f1a 100644 --- a/src/spell_type.h +++ b/src/spell_type.h @@ -25,7 +25,6 @@ enum random_type { RANDOM, NO_RANDOM }; * Spell functions */ -void spell_type_init(spell_type *spell, cptr name); void spell_type_init_music(spell_type *spell, s16b minimum_pval, const char* (*info_func)(), diff --git a/src/spells2.cc b/src/spells2.cc index 2dbfff43..cbb55ecd 100644 --- a/src/spells2.cc +++ b/src/spells2.cc @@ -13,6 +13,7 @@ #include "angband.h" #include "hooks.h" +#include <cassert> #include <chrono> #include <thread> #include <vector> diff --git a/src/spells3.cc b/src/spells3.cc index 69b05aad..056d3de6 100644 --- a/src/spells3.cc +++ b/src/spells3.cc @@ -3,6 +3,7 @@ #include <assert.h> #include "spell_type.h" +#include "spell_idx_list.hpp" #include <vector> @@ -2960,8 +2961,6 @@ int udun_in_book(s32b sval, s32b pval) { int count = 0; school_book_type *school_book; - spell_idx_list *spell_idx = NULL; - struct sglib_spell_idx_list_iterator it; random_book_setup(sval, pval); @@ -2969,11 +2968,8 @@ int udun_in_book(s32b sval, s32b pval) school_book = school_books_at(sval); /* Go through spells */ - for (spell_idx = sglib_spell_idx_list_it_init(&it, school_book->spell_idx_list); - spell_idx != NULL; - spell_idx = sglib_spell_idx_list_it_next(&it)) - { - spell_type *spell = spell_at(spell_idx->i); + for (auto spell_idx : school_book->spell_idx_list->v) { + spell_type *spell = spell_at(spell_idx); spell_type_school_foreach(spell, check_school_is_udun, &count); } @@ -2983,23 +2979,16 @@ int udun_in_book(s32b sval, s32b pval) int levels_in_book(s32b sval, s32b pval) { int levels = 0; - school_book_type *school_book; - spell_idx_list *spell_idx = NULL; - struct sglib_spell_idx_list_iterator it; random_book_setup(sval, pval); /* Get the school book */ - school_book = school_books_at(sval); + school_book_type *school_book = school_books_at(sval); /* Parse all spells */ - for (spell_idx = sglib_spell_idx_list_it_init(&it, school_book->spell_idx_list); - spell_idx != NULL; - spell_idx = sglib_spell_idx_list_it_next(&it)) + for (auto spell_idx : school_book->spell_idx_list->v) { - s32b s = spell_idx->i; - spell_type *spell = spell_at(s); - + spell_type *spell = spell_at(spell_idx); levels += spell_type_skill_level(spell); } diff --git a/src/spells4.cc b/src/spells4.cc index ccf9e858..22215f04 100644 --- a/src/spells4.cc +++ b/src/spells4.cc @@ -3,6 +3,8 @@ #include <assert.h> #include "spell_type.h" +#include "spell_idx_list.hpp" +#include <algorithm> school_book_type school_books[SCHOOL_BOOKS_SIZE]; @@ -32,13 +34,6 @@ s32b SCHOOL_VARDA; s32b SCHOOL_WATER; s32b SCHOOL_YAVANNA; -static int compare_spell_idx(spell_idx_list *a, spell_idx_list *b) -{ - return SGLIB_NUMERIC_COMPARATOR(a->i, b->i); -} - -SGLIB_DEFINE_LIST_FUNCTIONS(spell_idx_list, compare_spell_idx, next); - static bool_ uses_piety_to_cast(int s) { return spell_type_uses_piety_to_cast(spell_at(s)); @@ -114,32 +109,14 @@ school_book_type *school_books_at(int i) static void school_book_init(school_book_type *school_book) { - school_book->spell_idx_list = NULL; -} - -static void spell_idx_init(spell_idx_list *p, s32b spell_idx) -{ - assert(p != NULL); - - p->i = spell_idx; - p->next = NULL; -} - -static spell_idx_list *new_spell_idx(void *ctx, s32b spell_idx) -{ - spell_idx_list *e = new spell_idx_list; - spell_idx_init(e, spell_idx); - return e; + school_book->spell_idx_list = new spell_idx_list(); // FIXME: This whole thing should really be in the ctor?!? } void school_book_add_spell(school_book_type *school_book, s32b spell_idx) { - spell_idx_list *e; - - assert(school_book != NULL); - - e = new_spell_idx(school_book, spell_idx); - sglib_spell_idx_list_add(&school_book->spell_idx_list, e); + assert(school_book != nullptr); + assert(school_book->spell_idx_list != nullptr); + school_book->spell_idx_list->v.push_back(spell_idx); } int school_book_length(int sval) @@ -151,8 +128,7 @@ int school_book_length(int sval) return 1; } - /* Parse all spells */ - return sglib_spell_idx_list_len(school_book->spell_idx_list); + return school_book->spell_idx_list->v.size(); } int spell_x(int sval, int pval, int i) @@ -165,36 +141,19 @@ int spell_x(int sval, int pval, int i) } else { - school_book_type *school_book; - spell_idx_list *spell_idx = NULL; - struct sglib_spell_idx_list_iterator it; - - school_book = school_books_at(sval); - - for (spell_idx = sglib_spell_idx_list_it_init(&it, school_book->spell_idx_list); - (spell_idx != NULL) && (i > 0); - spell_idx = sglib_spell_idx_list_it_next(&it)) - { - i--; - } - - assert(spell_idx != NULL); /* Went off the end of the list? */ - - return spell_idx->i; + school_book_type *school_book = school_books_at(sval); + return school_book->spell_idx_list->v.at(i); } } bool_ school_book_contains_spell(int sval, s32b spell_idx) { - school_book_type *school_book = NULL; - spell_idx_list e; - random_book_setup(sval, spell_idx); - - school_book = school_books_at(sval); - - spell_idx_init(&e, spell_idx); - return NULL != sglib_spell_idx_list_find_member(school_book->spell_idx_list, &e); + school_book_type *school_book = school_books_at(sval); + return (school_book->spell_idx_list->v.end() != // FIXME: Oh, the horror! Is there really no shortcut?!? + std::find(school_book->spell_idx_list->v.begin(), + school_book->spell_idx_list->v.end(), + spell_idx)); } void push_spell(int book_idx, s32b spell_idx) @@ -436,9 +395,7 @@ void random_book_setup(s16b sval, s32b spell_idx) if (sval == BOOK_RANDOM) { school_book_type *school_book = school_books_at(sval); - - assert(school_book->spell_idx_list != NULL); - school_book->spell_idx_list->i = spell_idx; + school_book->spell_idx_list->v.at(0) = spell_idx; } } @@ -505,8 +462,6 @@ int print_book(s16b sval, s32b pval, object_type *obj) int y = 2; int i; school_book_type *school_book; - spell_idx_list *spell_idx; - struct sglib_spell_idx_list_iterator it; random_book_setup(sval, pval); @@ -514,24 +469,21 @@ int print_book(s16b sval, s32b pval, object_type *obj) /* Parse all spells */ i = 0; - for (spell_idx = sglib_spell_idx_list_it_init(&it, school_book->spell_idx_list); - spell_idx != NULL; - spell_idx = sglib_spell_idx_list_it_next(&it)) + for (auto spell_idx : school_book->spell_idx_list->v) { - s32b s = spell_idx->i; byte color = TERM_L_DARK; bool_ is_ok; char label[8]; - is_ok = is_ok_spell(s, obj); + is_ok = is_ok_spell(spell_idx, obj); if (is_ok) { - color = (get_mana(s) > get_power(s)) ? TERM_ORANGE : TERM_L_GREEN; + color = (get_mana(spell_idx) > get_power(spell_idx)) ? TERM_ORANGE : TERM_L_GREEN; } sprintf(label, "%c) ", 'a' + i); - y = print_spell(label, color, y, s); + y = print_spell(label, color, y, spell_idx); i++; } diff --git a/src/spells6.cc b/src/spells6.cc index 7bd0d911..b829ea0e 100644 --- a/src/spells6.cc +++ b/src/spells6.cc @@ -1,13 +1,12 @@ #include <angband.h> - #include <assert.h> - #include "spell_type.h" +#include <vector> -typedef struct school_provider school_provider; struct school_provider { + // FIXME: make school_provider_new a ctor instead... byte deity_idx; /* Deity which provides school levels */ s16b skill_idx; /* Skill used for determining the boost */ @@ -15,26 +14,20 @@ struct school_provider long mul; /* Multiplier */ long div; /* Divisor */ - - school_provider *next; /* Next provider in list */ }; -static int compare_school_provider(school_provider *a, school_provider *b) -{ - return SGLIB_NUMERIC_COMPARATOR(a->deity_idx, b->deity_idx); -} - -SGLIB_DEFINE_LIST_PROTOTYPES(school_provider, compare_school_provider, next); -SGLIB_DEFINE_LIST_FUNCTIONS(school_provider, compare_school_provider, next); +struct school_provider_list { +public: // FIXME: because of lack of definition... + std::vector<school_provider> v; +}; -static school_provider *school_provider_new(byte deity_idx, long mul, long div) +static school_provider school_provider_new(byte deity_idx, long mul, long div) { - school_provider *p = new school_provider; - p->deity_idx = deity_idx; - p->skill_idx = SKILL_PRAY; - p->mul = mul; - p->div = div; - p->next = NULL; + school_provider p; + p.deity_idx = deity_idx; + p.skill_idx = SKILL_PRAY; + p.mul = mul; + p.div = div; return p; } @@ -111,8 +104,11 @@ static void school_god(school_type *school, byte god, int mul, int div) /* Ignore gods which aren't enabled for this module. */ if (god_enabled(deity)) { - school_provider *school_provider = school_provider_new(god, mul, div); - sglib_school_provider_add(&school->providers, school_provider); + if (school->providers == NULL) { + school->providers = new school_provider_list(); + } + + school->providers->v.push_back(school_provider_new(god, mul, div)); } } @@ -146,15 +142,12 @@ static bool_ geomancy_depends_satisfied() long get_provided_levels(school_type *school) { school_provider *school_provider = NULL; - struct sglib_school_provider_iterator school_provider_it; - for (school_provider = sglib_school_provider_it_init(&school_provider_it, school->providers); - school_provider != NULL; - school_provider = sglib_school_provider_it_next(&school_provider_it)) + for (auto school_provider: school->providers->v) { - if (school_provider->deity_idx == p_ptr->pgod) + if (school_provider.deity_idx == p_ptr->pgod) { - return (s_info[school_provider->skill_idx].value * school_provider->mul) / school_provider->div; + return (s_info[school_provider.skill_idx].value * school_provider.mul) / school_provider.div; } } diff --git a/src/store.cc b/src/store.cc index 94c0eab3..ef2a97a1 100644 --- a/src/store.cc +++ b/src/store.cc @@ -11,11 +11,12 @@ */ #include "angband.h" - #include "spell_type.h" #include "quark.h" #include "hooks.h" +#include <cassert> + #define STORE_GENERAL_STORE "General Store" #define STORE_ARMOURY "Armoury" #define STORE_WEAPONSMITH "Weaponsmith" diff --git a/src/string_list.cc b/src/string_list.cc deleted file mode 100644 index 41a1feaf..00000000 --- a/src/string_list.cc +++ /dev/null @@ -1,55 +0,0 @@ -#include "string_list.h" - -int compare_string_list(string_list *a, string_list *b) -{ - if (a == b) - { - return 0; - } - - return strcmp(a->s, b->s); -} - -SGLIB_DEFINE_LIST_FUNCTIONS(string_list, compare_string_list, next); - -/* - * Initialize a string_list value. Copies the input string. - */ -void string_list_init(string_list *sl, cptr s) -{ - assert(sl != NULL); - - sl->s = nullptr; - if (s) - { - sl->s = strdup(s); - } - - sl->next = NULL; -} - -/* - * Destroy string_value. - */ -void string_list_destroy(string_list *sl) -{ - assert(sl != NULL); - - /* Free contained string */ - free(sl->s); - sl->s = NULL; - - /* We do NOT free the rest of the list. */ - sl->next = NULL; -} - -/** - * Append a string to a string_list. - */ -void string_list_append(string_list **slist, cptr s) -{ - string_list *e = new string_list; - string_list_init(e, s); - - sglib_string_list_add(slist, e); -} diff --git a/src/string_list.h b/src/string_list.h deleted file mode 100644 index 8dfe0b83..00000000 --- a/src/string_list.h +++ /dev/null @@ -1,30 +0,0 @@ -#pragma once - -#include "sglib.h" -#include "angband.h" - -#ifdef __cplusplus -extern "C" { -#endif - -/* - * String list. - */ -typedef struct string_list string_list; -struct string_list { - /* The string list owns the string */ - char *s; - /* Next */ - string_list *next; -}; - -int compare_string_list(string_list *a, string_list *b); -SGLIB_DEFINE_LIST_PROTOTYPES(string_list, compare_string, next); - -void string_list_init(string_list *sl, cptr s); /* Initialize element; copies string */ -void string_list_destroy(string_list *sl); /* Destroy element */ -void string_list_append(string_list **slist, cptr s); /* Append string */ - -#ifdef __cplusplus -} // extern "C" -#endif diff --git a/src/types.h b/src/types.h index 6a1f8536..f5ce1d97 100644 --- a/src/types.h +++ b/src/types.h @@ -1,6 +1,7 @@ /* File: types.h */ #include "types_fwd.h" +#include "spell_idx_list_fwd.h" /* Purpose: global type declarations */ @@ -2466,16 +2467,7 @@ struct school_type bool_ (*depends_satisfied)(); /* Are dependendies satisfied? */ - struct school_provider *providers; /* List of secondary providers of this school */ -}; - -/* - * Spell index list. - */ -typedef struct spell_idx_list spell_idx_list; -struct spell_idx_list { - s32b i; /* Spell index */ - spell_idx_list *next; /* for list */ + struct school_provider_list *providers; /* List of secondary providers of this school */ }; /* @@ -2483,7 +2475,7 @@ struct spell_idx_list { */ typedef struct school_book_type school_book_type; struct school_book_type { - spell_idx_list *spell_idx_list; + struct spell_idx_list *spell_idx_list; }; /* diff --git a/src/types_fwd.h b/src/types_fwd.h index 8f49eae5..35b39368 100644 --- a/src/types_fwd.h +++ b/src/types_fwd.h @@ -83,9 +83,8 @@ struct cli_comm; struct skill_type; struct school_idx; struct spell_type; -struct school_provider; +struct school_provider_list; struct school_type; -struct spell_idx_list; struct school_book_type; struct gf_name_type; struct timer_type; diff --git a/src/xtra1.cc b/src/xtra1.cc index 1d07403d..6643a0c3 100644 --- a/src/xtra1.cc +++ b/src/xtra1.cc @@ -11,10 +11,11 @@ */ #include "angband.h" - #include "messages.h" #include "hooks.h" +#include <cassert> + /* * Converts stat num into a six-char (right justified) string */ |