diff options
| author | Flipp <mysteriousragnarok@hotmail.com> | 2013-07-22 14:20:58 -0700 |
|---|---|---|
| committer | Flipp <mysteriousragnarok@hotmail.com> | 2013-07-22 14:20:58 -0700 |
| commit | 056c181e1c163b7d49c87bc07bf82ef11fdbd539 (patch) | |
| tree | 3d0e0857b3e6bdaff5ca5a9461d1d1e530b57dba /src/common/db.h | |
| parent | 0090e0303d9dd56e91b88fa331c3952097c592da (diff) | |
| parent | c0c254f14d0d65a8b7ec50720ed8d98b5a04919a (diff) | |
| download | hercules-056c181e1c163b7d49c87bc07bf82ef11fdbd539.tar.gz hercules-056c181e1c163b7d49c87bc07bf82ef11fdbd539.tar.bz2 hercules-056c181e1c163b7d49c87bc07bf82ef11fdbd539.tar.xz hercules-056c181e1c163b7d49c87bc07bf82ef11fdbd539.zip | |
Merge pull request #64 from piotrhalaczkiewicz/master
Binary heap fix & improvement.
Diffstat (limited to 'src/common/db.h')
| -rw-r--r-- | src/common/db.h | 19 |
1 files changed, 12 insertions, 7 deletions
diff --git a/src/common/db.h b/src/common/db.h index 5a555b2fa..aa4bfb054 100644 --- a/src/common/db.h +++ b/src/common/db.h @@ -1392,7 +1392,8 @@ void linkdb_foreach( struct linkdb_node** head, LinkDBFunc func, ... ); /// @param __heap Binary heap /// @param __val Value /// @param __topcmp Comparator -#define BHEAP_PUSH(__heap,__val,__topcmp) \ +/// @param __swp Swapper +#define BHEAP_PUSH(__heap,__val,__topcmp,__swp) \ do{ \ size_t _i_ = VECTOR_LENGTH(__heap); \ VECTOR_PUSH(__heap,__val); /* insert at end */ \ @@ -1401,7 +1402,7 @@ void linkdb_foreach( struct linkdb_node** head, LinkDBFunc func, ... ); size_t _parent_ = (_i_-1)/2; \ if( __topcmp(VECTOR_INDEX(__heap,_parent_),VECTOR_INDEX(__heap,_i_)) < 0 ) \ break; /* done */ \ - swap(VECTOR_INDEX(__heap,_parent_),VECTOR_INDEX(__heap,_i_)); \ + __swp(VECTOR_INDEX(__heap,_parent_),VECTOR_INDEX(__heap,_i_)); \ _i_ = _parent_; \ } \ }while(0) @@ -1418,7 +1419,8 @@ void linkdb_foreach( struct linkdb_node** head, LinkDBFunc func, ... ); /// /// @param __heap Binary heap /// @param __topcmp Comparator -#define BHEAP_POP(__heap,__topcmp) BHEAP_POPINDEX(__heap,0,__topcmp) +/// @param __swp Swapper +#define BHEAP_POP(__heap,__topcmp,__swp) BHEAP_POPINDEX(__heap,0,__topcmp,__swp) @@ -1433,16 +1435,19 @@ void linkdb_foreach( struct linkdb_node** head, LinkDBFunc func, ... ); /// @param __heap Binary heap /// @param __idx Index /// @param __topcmp Comparator -#define BHEAP_POPINDEX(__heap,__idx,__topcmp) \ +/// @param __swp Swapper +#define BHEAP_POPINDEX(__heap,__idx,__topcmp,__swp) \ do{ \ size_t _i_ = __idx; \ VECTOR_INDEX(__heap,__idx) = VECTOR_POP(__heap); /* put last at index */ \ + if( _i_ >= VECTOR_LENGTH(__heap)) /* removed last, nothing to do */ \ + break; \ while( _i_ ) \ { /* restore heap property in parents */ \ size_t _parent_ = (_i_-1)/2; \ if( __topcmp(VECTOR_INDEX(__heap,_parent_),VECTOR_INDEX(__heap,_i_)) < 0 ) \ break; /* done */ \ - swap(VECTOR_INDEX(__heap,_parent_),VECTOR_INDEX(__heap,_i_)); \ + __swp(VECTOR_INDEX(__heap,_parent_),VECTOR_INDEX(__heap,_i_)); \ _i_ = _parent_; \ } \ while( _i_ < VECTOR_LENGTH(__heap) ) \ @@ -1454,12 +1459,12 @@ void linkdb_foreach( struct linkdb_node** head, LinkDBFunc func, ... ); break; /* done */ \ else if( _rchild_ >= VECTOR_LENGTH(__heap) || __topcmp(VECTOR_INDEX(__heap,_lchild_),VECTOR_INDEX(__heap,_rchild_)) <= 0 ) \ { /* left child */ \ - swap(VECTOR_INDEX(__heap,_i_),VECTOR_INDEX(__heap,_lchild_)); \ + __swp(VECTOR_INDEX(__heap,_i_),VECTOR_INDEX(__heap,_lchild_)); \ _i_ = _lchild_; \ } \ else \ { /* right child */ \ - swap(VECTOR_INDEX(__heap,_i_),VECTOR_INDEX(__heap,_rchild_)); \ + __swp(VECTOR_INDEX(__heap,_i_),VECTOR_INDEX(__heap,_rchild_)); \ _i_ = _rchild_; \ } \ } \ |