small optimization for BLI_heap(), give some speedup in decimeter.

- use unsigned ints only (where mixing signed/unsigned)
- turn heap_swap into an inline function, add SWAP_TVAL macro to swap values using a temp value as storage.
- added type checking SHIFT3/4 macros

also style cleanup for CTR_Map

6 files changed, 179 insertions, 125 deletions

diff --git a/intern/container/CTR_HashedPtr.h b/intern/container/CTR_HashedPtr.h
index 8d0ad2bb2a3..b7ac460f270 100644
--- a/intern/container/CTR_HashedPtr.h
+++ b/intern/container/CTR_HashedPtr.h
@@ -43,12 +43,19 @@ inline unsigned int CTR_Hash(void *inDWord)
 
 class CTR_HashedPtr
 {
-	void* m_valptr;
+	void *m_valptr;
 public:
-	CTR_HashedPtr(void* val) : m_valptr(val) {};
-	unsigned int hash() const { return CTR_Hash(m_valptr);};
-	inline friend bool operator ==(const CTR_HashedPtr & rhs, const CTR_HashedPtr & lhs) { return rhs.m_valptr == lhs.m_valptr;};
-	void *getValue() const { return m_valptr; }
+	CTR_HashedPtr(void *val) : m_valptr(val) {
+	};
+	unsigned int hash() const {
+		return CTR_Hash(m_valptr);
+	};
+	inline friend bool operator ==(const CTR_HashedPtr & rhs, const CTR_HashedPtr & lhs) {
+		return rhs.m_valptr == lhs.m_valptr;
+	};
+	void *getValue() const {
+		return m_valptr;
+	}
 };
 
 #endif  /* __CTR_HASHEDPTR_H__ */
diff --git a/intern/container/CTR_Map.h b/intern/container/CTR_Map.h
index d729f2a1b06..c278fe5330c 100644
--- a/intern/container/CTR_Map.h
+++ b/intern/container/CTR_Map.h
@@ -37,13 +37,14 @@ class CTR_Map {
 private:
 	struct Entry {
 		Entry (Entry *next, Key key, Value value) :
-		    m_next(next),
-		    m_key(key),
-		    m_value(value) {}
+			m_next(next),
+			m_key(key),
+			m_value(value) {
+		}
 
 		Entry *m_next;
-		Key    m_key;
-		Value  m_value;
+		Key m_key;
+		Value m_value;
 	};
 
 public:
@@ -62,18 +63,18 @@ public:
 		for (int i = 0; i < m_num_buckets; ++i) {
 			m_buckets[i] = 0;
 
-			for (Entry *entry = map.m_buckets[i]; entry; entry=entry->m_next)
+			for (Entry *entry = map.m_buckets[i]; entry; entry = entry->m_next) {
 				insert(entry->m_key, entry->m_value);
+			}
 		}
 	}
 
-	int size() {
-		int count=0;
-		for (int i=0;i<m_num_buckets;i++)
-		{
-			Entry* bucket = m_buckets[i];
-			while(bucket)
-			{
+	int size()
+	{
+		int count = 0;
+		for (int i = 0; i < m_num_buckets; i++) {
+			Entry *bucket = m_buckets[i];
+			while (bucket) {
 				bucket = bucket->m_next;
 				count++;
 			}
@@ -81,15 +82,13 @@ public:
 		return count;
 	}
 
-	Value* at(int index) {
-		int count=0;
-		for (int i=0;i<m_num_buckets;i++)
-		{
-			Entry* bucket = m_buckets[i];
-			while(bucket)
-			{
-				if (count==index)
-				{
+	Value *at(int index)
+	{
+		int count = 0;
+		for (int i = 0; i < m_num_buckets; i++) {
+			Entry *bucket = m_buckets[i];
+			while (bucket) {
+				if (count == index) {
 					return &bucket->m_value;
 				}
 				bucket = bucket->m_next;
@@ -99,15 +98,13 @@ public:
 		return 0;
 	}
 
-	Key* getKey(int index) {
-		int count=0;
-		for (int i=0;i<m_num_buckets;i++)
-		{
-			Entry* bucket = m_buckets[i];
-			while(bucket)
-			{
-				if (count==index)
-				{
+	Key *getKey(int index)
+	{
+		int count = 0;
+		for (int i = 0; i < m_num_buckets; i++) {
+			Entry *bucket = m_buckets[i];
+			while (bucket) {
+				if (count == index) {
 					return &bucket->m_key;
 				}
 				bucket = bucket->m_next;
@@ -117,7 +114,8 @@ public:
 		return 0;
 	}
 
-	void clear() {
+	void clear()
+	{
 		for (int i = 0; i < m_num_buckets; ++i) {
 			Entry *entry_ptr = m_buckets[i];
 
@@ -130,12 +128,14 @@ public:
 		}
 	}
 
-	~CTR_Map() {
+	~CTR_Map()
+	{
 		clear();
-		delete [] m_buckets;
+		delete[] m_buckets;
 	}
 
-	void insert(const Key& key, const Value& value) {
+	void insert(const Key& key, const Value& value)
+	{
 		Entry *entry_ptr = m_buckets[key.hash() % m_num_buckets];
 		while ((entry_ptr != 0) && !(key == entry_ptr->m_key)) {
 			entry_ptr = entry_ptr->m_next;
@@ -150,7 +150,8 @@ public:
 		}
 	}
 
-	void remove(const Key& key) {
+	void remove(const Key& key)
+	{
 		Entry **entry_ptr = &m_buckets[key.hash() % m_num_buckets];
 		while ((*entry_ptr != 0) && !(key == (*entry_ptr)->m_key)) {
 			entry_ptr = &(*entry_ptr)->m_next;
@@ -163,7 +164,8 @@ public:
 		}
 	}
 
-	Value *operator[](Key key) {
+	Value *operator[](Key key)
+	{
 		Entry *bucket = m_buckets[key.hash() % m_num_buckets];
 		while ((bucket != 0) && !(key == bucket->m_key)) {
 			bucket = bucket->m_next;
diff --git a/source/blender/blenlib/BLI_heap.h b/source/blender/blenlib/BLI_heap.h
index adbbf266b4e..c0941e00c9b 100644
--- a/source/blender/blenlib/BLI_heap.h
+++ b/source/blender/blenlib/BLI_heap.h
@@ -57,7 +57,7 @@ void            BLI_heap_remove(Heap *heap, HeapNode *node);
 int             BLI_heap_is_empty(Heap *heap);
 
 /* Return the size of the heap. */
-int             BLI_heap_size(Heap *heap);
+unsigned int    BLI_heap_size(Heap *heap);
 
 /* Return the top node of the heap. This is the node with the lowest value. */
 HeapNode       *BLI_heap_top(Heap *heap);
diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h
index 47c2256c1e1..0dab51154eb 100644
--- a/source/blender/blenlib/BLI_utildefines.h
+++ b/source/blender/blenlib/BLI_utildefines.h
@@ -41,34 +41,6 @@
 #endif
 
 
-#define ELEM(a, b, c)           ((a) == (b) || (a) == (c))
-#define ELEM3(a, b, c, d)       (ELEM(a, b, c) || (a) == (d) )
-#define ELEM4(a, b, c, d, e)    (ELEM(a, b, c) || ELEM(a, d, e) )
-#define ELEM5(a, b, c, d, e, f) (ELEM(a, b, c) || ELEM3(a, d, e, f) )
-#define ELEM6(a, b, c, d, e, f, g)      (ELEM(a, b, c) || ELEM4(a, d, e, f, g) )
-#define ELEM7(a, b, c, d, e, f, g, h)   (ELEM3(a, b, c, d) || ELEM4(a, e, f, g, h) )
-#define ELEM8(a, b, c, d, e, f, g, h, i)        (ELEM4(a, b, c, d, e) || ELEM4(a, f, g, h, i) )
-#define ELEM9(a, b, c, d, e, f, g, h, i, j)        (ELEM4(a, b, c, d, e) || ELEM5(a, f, g, h, i, j) )
-#define ELEM10(a, b, c, d, e, f, g, h, i, j, k)        (ELEM4(a, b, c, d, e) || ELEM6(a, f, g, h, i, j, k) )
-#define ELEM11(a, b, c, d, e, f, g, h, i, j, k, l)        (ELEM4(a, b, c, d, e) || ELEM7(a, f, g, h, i, j, k, l) )
-
-/* shift around elements */
-#define SHIFT3(type, a, b, c)  {                                              \
-		type tmp;                                                             \
-		tmp = a;                                                              \
-		a = c;                                                                \
-		c = b;                                                                \
-		b = tmp;                                                              \
-} (void)0
-#define SHIFT4(type, a, b, c, d)  {                                           \
-		type tmp;                                                             \
-		tmp = a;                                                              \
-		a = d;                                                                \
-		d = c;                                                                \
-		c = b;                                                                \
-		b = tmp;                                                              \
-} (void)0
-
 /* min/max */
 #define MIN2(x, y)               ( (x) < (y) ? (x) : (y) )
 #define MIN3(x, y, z)             MIN2(MIN2((x), (y)), (z) )
@@ -116,22 +88,28 @@
 /* Causes warning:
  * incompatible types when assigning to type 'Foo' from type 'Bar'
  * ... the compiler optimizes away the temp var */
-#ifndef CHECK_TYPE
 #ifdef __GNUC__
 #define CHECK_TYPE(var, type)  {  \
 	__typeof(var) *__tmp;         \
 	__tmp = (type *)NULL;         \
 	(void)__tmp;                  \
 } (void)0
+
+#define CHECK_TYPE_PAIR(var_a, var_b)  {  \
+	__typeof(var_a) *__tmp;               \
+	__tmp = (__typeof(var_b) *)NULL;      \
+	(void)__tmp;                          \
+} (void)0
 #else
-#define CHECK_TYPE(var, type)
-#endif
+#  define CHECK_TYPE(var, type)
+#  define CHECK_TYPE_PAIR(var_a, var_b)
 #endif
 
 /* can be used in simple macros */
 #define CHECK_TYPE_INLINE(val, type) \
 	((void)(((type *)0) != (val)))
 
+
 #ifndef SWAP
 #  define SWAP(type, a, b)  {  \
 	type sw_ap;                \
@@ -143,6 +121,53 @@
 } (void)0
 #endif
 
+/* swap with a temp value */
+#define SWAP_TVAL(tval, a, b)  {  \
+	CHECK_TYPE_PAIR(tval, a);     \
+	CHECK_TYPE_PAIR(tval, b);     \
+	(tval) = (a);                 \
+	(a) = (b);                    \
+	(b) = (tval);                 \
+} (void)0
+
+
+#define ELEM(a, b, c)           ((a) == (b) || (a) == (c))
+#define ELEM3(a, b, c, d)       (ELEM(a, b, c) || (a) == (d) )
+#define ELEM4(a, b, c, d, e)    (ELEM(a, b, c) || ELEM(a, d, e) )
+#define ELEM5(a, b, c, d, e, f) (ELEM(a, b, c) || ELEM3(a, d, e, f) )
+#define ELEM6(a, b, c, d, e, f, g)      (ELEM(a, b, c) || ELEM4(a, d, e, f, g) )
+#define ELEM7(a, b, c, d, e, f, g, h)   (ELEM3(a, b, c, d) || ELEM4(a, e, f, g, h) )
+#define ELEM8(a, b, c, d, e, f, g, h, i)        (ELEM4(a, b, c, d, e) || ELEM4(a, f, g, h, i) )
+#define ELEM9(a, b, c, d, e, f, g, h, i, j)        (ELEM4(a, b, c, d, e) || ELEM5(a, f, g, h, i, j) )
+#define ELEM10(a, b, c, d, e, f, g, h, i, j, k)        (ELEM4(a, b, c, d, e) || ELEM6(a, f, g, h, i, j, k) )
+#define ELEM11(a, b, c, d, e, f, g, h, i, j, k, l)        (ELEM4(a, b, c, d, e) || ELEM7(a, f, g, h, i, j, k, l) )
+
+/* shift around elements */
+#define SHIFT3(type, a, b, c)  {                                              \
+	type tmp;                                                                 \
+	CHECK_TYPE(a, type);                                                      \
+	CHECK_TYPE(b, type);                                                      \
+	CHECK_TYPE(c, type);                                                      \
+	tmp = a;                                                                  \
+	a = c;                                                                    \
+	c = b;                                                                    \
+	b = tmp;                                                                  \
+} (void)0
+
+#define SHIFT4(type, a, b, c, d)  {                                           \
+	type tmp;                                                                 \
+	CHECK_TYPE(a, type);                                                      \
+	CHECK_TYPE(b, type);                                                      \
+	CHECK_TYPE(c, type);                                                      \
+	CHECK_TYPE(d, type);                                                      \
+	tmp = a;                                                                  \
+	a = d;                                                                    \
+	d = c;                                                                    \
+	c = b;                                                                    \
+	b = tmp;                                                                  \
+} (void)0
+
+
 #define ABS(a)          ( (a) < 0 ? (-(a)) : (a) )
 
 #define FTOCHAR(val) ((val) <= 0.0f) ? 0 : (((val) > (1.0f - 0.5f / 255.0f)) ? 255 : (char)((255.0f * (val)) + 0.5f))
diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c
index 5a33e998561..3f88e336325 100644
--- a/source/blender/blenlib/intern/BLI_heap.c
+++ b/source/blender/blenlib/intern/BLI_heap.c
@@ -40,9 +40,9 @@
 /***/
 
 struct HeapNode {
-	void *ptr;
-	float value;
-	int index;
+	void        *ptr;
+	float        value;
+	unsigned int index;
 };
 
 struct Heap {
@@ -54,54 +54,40 @@ struct Heap {
 	HeapNode **tree;
 };
 
+/* internal functions */
+
 #define HEAP_PARENT(i) ((i - 1) >> 1)
 #define HEAP_LEFT(i)   ((i << 1) + 1)
 #define HEAP_RIGHT(i)  ((i << 1) + 2)
 #define HEAP_COMPARE(a, b) (a->value < b->value)
-// #define HEAP_EQUALS(a, b) (a->value == b->value) // UNUSED
-#define HEAP_SWAP(heap, i, j) \
-	{                                                                            \
-		SWAP(int, heap->tree[i]->index, heap->tree[j]->index);                   \
-		SWAP(HeapNode *, heap->tree[i], heap->tree[j]);                          \
-	} (void)0
 
-/***/
+#if 0  /* UNUSED */
+#define HEAP_EQUALS(a, b) (a->value == b->value)
+#endif
 
-/* use when the size of the heap is known in advance */
-Heap *BLI_heap_new_ex(unsigned int tot_reserve)
+BLI_INLINE void heap_swap(Heap *heap, const unsigned int i, const unsigned int j)
 {
-	Heap *heap = (Heap *)MEM_callocN(sizeof(Heap), __func__);
-	heap->bufsize = tot_reserve;
-	heap->tree = (HeapNode **)MEM_mallocN(tot_reserve * sizeof(HeapNode *), "BLIHeapTree");
-	heap->arena = BLI_memarena_new(1 << 16, "heap arena");
 
-	return heap;
+#if 0
+	SWAP(unsigned int,  heap->tree[i]->index, heap->tree[j]->index);
+	SWAP(HeapNode *,    heap->tree[i],        heap->tree[j]);
+#else
+	HeapNode **tree = heap->tree;
+	union {
+		unsigned int  index;
+		HeapNode     *node;
+	} tmp;
+	SWAP_TVAL(tmp.index, tree[i]->index, tree[j]->index);
+	SWAP_TVAL(tmp.node,  tree[i],        tree[j]);
+#endif
 }
 
-Heap *BLI_heap_new(void)
-{
-	return BLI_heap_new_ex(1);
-}
-
-void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp)
-{
-	int i;
-
-	if (ptrfreefp)
-		for (i = 0; i < heap->size; i++)
-			ptrfreefp(heap->tree[i]->ptr);
-
-	MEM_freeN(heap->tree);
-	BLI_memarena_free(heap->arena);
-	MEM_freeN(heap);
-}
-
-static void BLI_heap_down(Heap *heap, int i)
+static void heap_down(Heap *heap, unsigned int i)
 {
 	while (1) {
-		int size = heap->size, smallest;
-		int l = HEAP_LEFT(i);
-		int r = HEAP_RIGHT(i);
+		unsigned int size = heap->size,smallest ;
+		unsigned int l = HEAP_LEFT(i);
+		unsigned int r = HEAP_RIGHT(i);
 
 		smallest = ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[i])) ? l : i;
 
@@ -111,30 +97,62 @@ static void BLI_heap_down(Heap *heap, int i)
 		if (smallest == i)
 			break;
 
-		HEAP_SWAP(heap, i, smallest);
+		heap_swap(heap, i, smallest);
 		i = smallest;
 	}
 }
 
-static void BLI_heap_up(Heap *heap, int i)
+static void heap_up(Heap *heap, unsigned int i)
 {
 	while (i > 0) {
-		int p = HEAP_PARENT(i);
+		unsigned int p = HEAP_PARENT(i);
 
 		if (HEAP_COMPARE(heap->tree[p], heap->tree[i]))
 			break;
 
-		HEAP_SWAP(heap, p, i);
+		heap_swap(heap, p, i);
 		i = p;
 	}
 }
 
+
+/***/
+
+/* use when the size of the heap is known in advance */
+Heap *BLI_heap_new_ex(unsigned int tot_reserve)
+{
+	Heap *heap = (Heap *)MEM_callocN(sizeof(Heap), __func__);
+	heap->bufsize = tot_reserve;
+	heap->tree = (HeapNode **)MEM_mallocN(tot_reserve * sizeof(HeapNode *), "BLIHeapTree");
+	heap->arena = BLI_memarena_new(1 << 16, "heap arena");
+
+	return heap;
+}
+
+Heap *BLI_heap_new(void)
+{
+	return BLI_heap_new_ex(1);
+}
+
+void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp)
+{
+	unsigned int i;
+
+	if (ptrfreefp)
+		for (i = 0; i < heap->size; i++)
+			ptrfreefp(heap->tree[i]->ptr);
+
+	MEM_freeN(heap->tree);
+	BLI_memarena_free(heap->arena);
+	MEM_freeN(heap);
+}
+
 HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
 {
 	HeapNode *node;
 
 	if ((heap->size + 1) > heap->bufsize) {
-		int newsize = heap->bufsize * 2;
+		unsigned int newsize = heap->bufsize * 2;
 		HeapNode **newtree;
 
 		newtree = (HeapNode **)MEM_mallocN(newsize * sizeof(*newtree), __func__);
@@ -160,7 +178,7 @@ HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
 
 	heap->size++;
 
-	BLI_heap_up(heap, heap->size - 1);
+	heap_up(heap, heap->size - 1);
 
 	return node;
 }
@@ -170,7 +188,7 @@ int BLI_heap_is_empty(Heap *heap)
 	return (heap->size == 0);
 }
 
-int BLI_heap_size(Heap *heap)
+unsigned int BLI_heap_size(Heap *heap)
 {
 	return heap->size;
 }
@@ -190,10 +208,10 @@ void *BLI_heap_popmin(Heap *heap)
 	if (heap->size == 1)
 		heap->size--;
 	else {
-		HEAP_SWAP(heap, 0, heap->size - 1);
+		heap_swap(heap, 0, heap->size - 1);
 		heap->size--;
 
-		BLI_heap_down(heap, 0);
+		heap_down(heap, 0);
 	}
 
 	return ptr;
@@ -201,12 +219,12 @@ void *BLI_heap_popmin(Heap *heap)
 
 void BLI_heap_remove(Heap *heap, HeapNode *node)
 {
-	int i = node->index;
+	unsigned int i = node->index;
 
 	while (i > 0) {
-		int p = HEAP_PARENT(i);
+		unsigned int p = HEAP_PARENT(i);
 
-		HEAP_SWAP(heap, p, i);
+		heap_swap(heap, p, i);
 		i = p;
 	}
 
diff --git a/source/blender/modifiers/intern/MOD_decimate.c b/source/blender/modifiers/intern/MOD_decimate.c
index 7bcf56a1bfc..d55bc7ab9b1 100644
--- a/source/blender/modifiers/intern/MOD_decimate.c
+++ b/source/blender/modifiers/intern/MOD_decimate.c
@@ -49,6 +49,8 @@
 #include "BKE_tessmesh.h"
 #include "bmesh.h"
 
+// #define USE_TIMEIT
+
 #ifdef USE_TIMEIT
 #  include "PIL_time.h"
 #endif