From c0c254f14d0d65a8b7ec50720ed8d98b5a04919a Mon Sep 17 00:00:00 2001 From: Piotr Hałaczkiewicz Date: Mon, 22 Jul 2013 22:50:45 +0200 Subject: 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. --- src/common/cbasetypes.h | 2 ++ src/common/db.h | 19 ++++++++++++------- src/common/timer.c | 8 ++++---- 3 files changed, 18 insertions(+), 11 deletions(-) (limited to 'src/common') diff --git a/src/common/cbasetypes.h b/src/common/cbasetypes.h index bfe8bf8f8..82ca9df69 100644 --- a/src/common/cbasetypes.h +++ b/src/common/cbasetypes.h @@ -300,6 +300,8 @@ typedef char bool; #endif #endif +#define swap_ptr(a,b) if ((a) != (b)) ((a) = (void*)((intptr_t)(a) ^ (intptr_t)(b)), (b) = (void*)((intptr_t)(a) ^ (intptr_t)(b)), (a) = (void*)((intptr_t)(a) ^ (intptr_t)(b))) + #ifndef max #define max(a,b) (((a) > (b)) ? (a) : (b)) #endif 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_; \ } \ } \ diff --git a/src/common/timer.c b/src/common/timer.c index 955a971c8..f019c6927 100644 --- a/src/common/timer.c +++ b/src/common/timer.c @@ -195,7 +195,7 @@ unsigned int timer_gettick(void) { /// Adds a timer to the timer_heap static void push_timer_heap(int tid) { BHEAP_ENSURE(timer_heap, 1, 256); - BHEAP_PUSH(timer_heap, tid, DIFFTICK_MINTOPCMP); + BHEAP_PUSH(timer_heap, tid, DIFFTICK_MINTOPCMP, swap); } /*========================== @@ -322,9 +322,9 @@ int timer_settick(int tid, unsigned int tick) { return (int)tick;// nothing to do, already in propper position // pop and push adjusted timer - BHEAP_POPINDEX(timer_heap, i, DIFFTICK_MINTOPCMP); + BHEAP_POPINDEX(timer_heap, i, DIFFTICK_MINTOPCMP, swap); timer_data[tid].tick = tick; - BHEAP_PUSH(timer_heap, tid, DIFFTICK_MINTOPCMP); + BHEAP_PUSH(timer_heap, tid, DIFFTICK_MINTOPCMP, swap); return (int)tick; } @@ -342,7 +342,7 @@ int do_timer(unsigned int tick) { break; // no more expired timers to process // remove timer - BHEAP_POP(timer_heap, DIFFTICK_MINTOPCMP); + BHEAP_POP(timer_heap, DIFFTICK_MINTOPCMP, swap); timer_data[tid].type |= TIMER_REMOVE_HEAP; if( timer_data[tid].func ) { -- cgit v1.2.3-60-g2f50