diff options
| author | Piotr Hałaczkiewicz <piotr.halaczkiewicz@gmail.com> | 2013-07-22 22:50:45 +0200 |
|---|---|---|
| committer | Piotr Hałaczkiewicz <piotr.halaczkiewicz@gmail.com> | 2013-07-22 22:50:45 +0200 |
| commit | c0c254f14d0d65a8b7ec50720ed8d98b5a04919a (patch) | |
| tree | 0fc26c057880491c12358a6cc9d0f37d15155dc3 /src/common/db.h | |
| parent | 0b63deefd251a06b50a333facd6ad0e099e942b2 (diff) | |
| download | hercules-c0c254f14d0d65a8b7ec50720ed8d98b5a04919a.tar.gz hercules-c0c254f14d0d65a8b7ec50720ed8d98b5a04919a.tar.bz2 hercules-c0c254f14d0d65a8b7ec50720ed8d98b5a04919a.tar.xz hercules-c0c254f14d0d65a8b7ec50720ed8d98b5a04919a.zip | |
Binary heap fix & improvement.
Fixed a bug when removing last element of binary heap (its parent would
be removed instead if it had the same value).
Binary heap now allows custom swapper function/macro. Added `swap_ptr`
macro to swap two pointers in place (`swap` is not suitable for
pointers). This allows to store pointers in binary heap.
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_; \ } \ } \ |