summaryrefslogtreecommitdiff
path: root/src/common
diff options
context:
space:
mode:
authorPiotr HaƂaczkiewicz <piotr.halaczkiewicz@gmail.com>2013-07-22 22:50:45 +0200
committerPiotr HaƂaczkiewicz <piotr.halaczkiewicz@gmail.com>2013-07-22 22:50:45 +0200
commitc0c254f14d0d65a8b7ec50720ed8d98b5a04919a (patch)
tree0fc26c057880491c12358a6cc9d0f37d15155dc3 /src/common
parent0b63deefd251a06b50a333facd6ad0e099e942b2 (diff)
downloadhercules-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')
-rw-r--r--src/common/cbasetypes.h2
-rw-r--r--src/common/db.h19
-rw-r--r--src/common/timer.c8
3 files changed, 18 insertions, 11 deletions
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 ) {