diff options
author | Campbell Barton <ideasman42@gmail.com> | 2012-10-22 07:25:53 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2012-10-22 07:25:53 +0400 |
commit | a4b27831693eed988bcdf957bbe9ad7609e7bdf7 (patch) | |
tree | 3494d520b807cf40ebfc32650b67e32e5287f723 | |
parent | 226a5ee83446f91cfeccc73912de85e89fe2169f (diff) |
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
-rw-r--r-- | intern/container/CTR_HashedPtr.h | 17 | ||||
-rw-r--r-- | intern/container/CTR_Map.h | 76 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_heap.h | 2 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_utildefines.h | 87 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_heap.c | 120 | ||||
-rw-r--r-- | source/blender/modifiers/intern/MOD_decimate.c | 2 |
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 |