diff options
author | Alexander Gavrilov <angavrilov@gmail.com> | 2018-11-05 19:14:40 +0300 |
---|---|---|
committer | Alexander Gavrilov <angavrilov@gmail.com> | 2018-11-05 20:49:17 +0300 |
commit | fee6ab18e7e9a38203bf8eb95d114ac837578aa7 (patch) | |
tree | 8dc1830ce6dabf781e8d0c2d709db76fab1fd1b9 /source/blender/blenlib/BLI_heap.h | |
parent | a120b120ce380017324e982c2277cb8fca52f39d (diff) |
BLI_heap: implement a limited but faster version of heap.
If the user only needs insertion and removal from top, there is
no need to allocate and manage separate HeapNode objects: the
data can be stored directly in the main tree array.
This measured a 24% FPS increase on a ~50% heap-heavy workload.
Reviewers: brecht
Differential Revision: https://developer.blender.org/D3898
Diffstat (limited to 'source/blender/blenlib/BLI_heap.h')
-rw-r--r-- | source/blender/blenlib/BLI_heap.h | 15 |
1 files changed, 15 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_heap.h b/source/blender/blenlib/BLI_heap.h index 35c8df3075c..08adb0d538c 100644 --- a/source/blender/blenlib/BLI_heap.h +++ b/source/blender/blenlib/BLI_heap.h @@ -54,4 +54,19 @@ void *BLI_heap_node_ptr(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT /* only for gtest */ bool BLI_heap_is_valid(const Heap *heap); +/* Simplified version of the heap that only supports insertion and removal from top. */ + +struct FastHeap; +typedef struct FastHeap FastHeap; + +FastHeap *BLI_fastheap_new_ex(unsigned int tot_reserve) ATTR_WARN_UNUSED_RESULT; +FastHeap *BLI_fastheap_new(void) ATTR_WARN_UNUSED_RESULT; +void BLI_fastheap_clear(FastHeap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1); +void BLI_fastheap_free(FastHeap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1); +void BLI_fastheap_insert(FastHeap *heap, float value, void *ptr) ATTR_NONNULL(1); +bool BLI_fastheap_is_empty(const FastHeap *heap) ATTR_NONNULL(1); +unsigned int BLI_fastheap_len(const FastHeap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); +float BLI_fastheap_top_value(const FastHeap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); +void *BLI_fastheap_pop_min(FastHeap *heap) ATTR_NONNULL(1); + #endif /* __BLI_HEAP_H__ */ |