From c0c254f14d0d65a8b7ec50720ed8d98b5a04919a Mon Sep 17 00:00:00 2001
From: Piotr Hałaczkiewicz <piotr.halaczkiewicz@gmail.com>
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/db.h | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

(limited to 'src/common/db.h')

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_; \
 			} \
 		} \
-- 
cgit v1.2.3-70-g09d2