Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/blenlib/intern/BLI_heap_simple.c
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/blenlib/intern/BLI_heap_simple.c')
-rw-r--r--source/blender/blenlib/intern/BLI_heap_simple.c186
1 files changed, 93 insertions, 93 deletions
diff --git a/source/blender/blenlib/intern/BLI_heap_simple.c b/source/blender/blenlib/intern/BLI_heap_simple.c
index 50eb06e5d5d..6b27799b808 100644
--- a/source/blender/blenlib/intern/BLI_heap_simple.c
+++ b/source/blender/blenlib/intern/BLI_heap_simple.c
@@ -33,21 +33,21 @@
#include "BLI_heap_simple.h"
#include "BLI_strict_flags.h"
-#define HEAP_PARENT(i) (((i) - 1) >> 1)
+#define HEAP_PARENT(i) (((i)-1) >> 1)
/* -------------------------------------------------------------------- */
/** \name HeapSimple Internal Structs
* \{ */
typedef struct HeapSimpleNode {
- float value;
- void *ptr;
+ float value;
+ void *ptr;
} HeapSimpleNode;
struct HeapSimple {
- uint size;
- uint bufsize;
- HeapSimpleNode *tree;
+ uint size;
+ uint bufsize;
+ HeapSimpleNode *tree;
};
/** \} */
@@ -59,63 +59,63 @@ struct HeapSimple {
static void heapsimple_down(HeapSimple *heap, uint start_i, const HeapSimpleNode *init)
{
#if 1
- /* The compiler isn't smart enough to realize that all computations
- * using index here can be modified to work with byte offset. */
- uint8_t * const tree_buf = (uint8_t *)heap->tree;
+ /* The compiler isn't smart enough to realize that all computations
+ * using index here can be modified to work with byte offset. */
+ uint8_t *const tree_buf = (uint8_t *)heap->tree;
-#define OFFSET(i) (i * (uint)sizeof(HeapSimpleNode))
-#define NODE(offset) (*(HeapSimpleNode*)(tree_buf + (offset)))
+# define OFFSET(i) (i * (uint)sizeof(HeapSimpleNode))
+# define NODE(offset) (*(HeapSimpleNode *)(tree_buf + (offset)))
#else
- HeapSimpleNode *const tree = heap->tree;
+ HeapSimpleNode *const tree = heap->tree;
-#define OFFSET(i) (i)
-#define NODE(i) tree[i]
+# define OFFSET(i) (i)
+# define NODE(i) tree[i]
#endif
#define HEAP_LEFT_OFFSET(i) (((i) << 1) + OFFSET(1))
- const uint size = OFFSET(heap->size);
+ const uint size = OFFSET(heap->size);
- /* Pull the active node values into locals. This allows spilling
- * the data from registers instead of literally swapping nodes. */
- float active_val = init->value;
- void *active_ptr = init->ptr;
+ /* Pull the active node values into locals. This allows spilling
+ * the data from registers instead of literally swapping nodes. */
+ float active_val = init->value;
+ void *active_ptr = init->ptr;
- /* Prepare the first iteration and spill value. */
- uint i = OFFSET(start_i);
+ /* Prepare the first iteration and spill value. */
+ uint i = OFFSET(start_i);
- NODE(i).value = active_val;
+ NODE(i).value = active_val;
- for (;;) {
- const uint l = HEAP_LEFT_OFFSET(i);
- const uint r = l + OFFSET(1); /* right */
+ for (;;) {
+ const uint l = HEAP_LEFT_OFFSET(i);
+ const uint r = l + OFFSET(1); /* right */
- /* Find the child with the smallest value. */
- uint smallest = i;
+ /* Find the child with the smallest value. */
+ uint smallest = i;
- if (LIKELY(l < size) && NODE(l).value < active_val) {
- smallest = l;
- }
- if (LIKELY(r < size) && NODE(r).value < NODE(smallest).value) {
- smallest = r;
- }
+ if (LIKELY(l < size) && NODE(l).value < active_val) {
+ smallest = l;
+ }
+ if (LIKELY(r < size) && NODE(r).value < NODE(smallest).value) {
+ smallest = r;
+ }
- if (UNLIKELY(smallest == i)) {
- break;
- }
+ if (UNLIKELY(smallest == i)) {
+ break;
+ }
- /* Move the smallest child into the current node.
- * Skip padding: for some reason that makes it faster here. */
- NODE(i).value = NODE(smallest).value;
- NODE(i).ptr = NODE(smallest).ptr;
+ /* Move the smallest child into the current node.
+ * Skip padding: for some reason that makes it faster here. */
+ NODE(i).value = NODE(smallest).value;
+ NODE(i).ptr = NODE(smallest).ptr;
- /* Proceed to next iteration and spill value. */
- i = smallest;
- NODE(i).value = active_val;
- }
+ /* Proceed to next iteration and spill value. */
+ i = smallest;
+ NODE(i).value = active_val;
+ }
- /* Spill the pointer into the final position of the node. */
- NODE(i).ptr = active_ptr;
+ /* Spill the pointer into the final position of the node. */
+ NODE(i).ptr = active_ptr;
#undef NODE
#undef OFFSET
@@ -124,21 +124,21 @@ static void heapsimple_down(HeapSimple *heap, uint start_i, const HeapSimpleNode
static void heapsimple_up(HeapSimple *heap, uint i, float active_val, void *active_ptr)
{
- HeapSimpleNode *const tree = heap->tree;
+ HeapSimpleNode *const tree = heap->tree;
- while (LIKELY(i > 0)) {
- const uint p = HEAP_PARENT(i);
+ while (LIKELY(i > 0)) {
+ const uint p = HEAP_PARENT(i);
- if (active_val >= tree[p].value) {
- break;
- }
+ if (active_val >= tree[p].value) {
+ break;
+ }
- tree[i] = tree[p];
- i = p;
- }
+ tree[i] = tree[p];
+ i = p;
+ }
- tree[i].value = active_val;
- tree[i].ptr = active_ptr;
+ tree[i].value = active_val;
+ tree[i].ptr = active_ptr;
}
/** \} */
@@ -154,40 +154,40 @@ static void heapsimple_up(HeapSimple *heap, uint i, float active_val, void *acti
*/
HeapSimple *BLI_heapsimple_new_ex(uint tot_reserve)
{
- HeapSimple *heap = MEM_mallocN(sizeof(HeapSimple), __func__);
- /* ensure we have at least one so we can keep doubling it */
- heap->size = 0;
- heap->bufsize = MAX2(1u, tot_reserve);
- heap->tree = MEM_mallocN(heap->bufsize * sizeof(HeapSimpleNode), "BLIHeapSimpleTree");
- return heap;
+ HeapSimple *heap = MEM_mallocN(sizeof(HeapSimple), __func__);
+ /* ensure we have at least one so we can keep doubling it */
+ heap->size = 0;
+ heap->bufsize = MAX2(1u, tot_reserve);
+ heap->tree = MEM_mallocN(heap->bufsize * sizeof(HeapSimpleNode), "BLIHeapSimpleTree");
+ return heap;
}
HeapSimple *BLI_heapsimple_new(void)
{
- return BLI_heapsimple_new_ex(1);
+ return BLI_heapsimple_new_ex(1);
}
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp)
{
- if (ptrfreefp) {
- for (uint i = 0; i < heap->size; i++) {
- ptrfreefp(heap->tree[i].ptr);
- }
- }
-
- MEM_freeN(heap->tree);
- MEM_freeN(heap);
+ if (ptrfreefp) {
+ for (uint i = 0; i < heap->size; i++) {
+ ptrfreefp(heap->tree[i].ptr);
+ }
+ }
+
+ MEM_freeN(heap->tree);
+ MEM_freeN(heap);
}
void BLI_heapsimple_clear(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp)
{
- if (ptrfreefp) {
- for (uint i = 0; i < heap->size; i++) {
- ptrfreefp(heap->tree[i].ptr);
- }
- }
+ if (ptrfreefp) {
+ for (uint i = 0; i < heap->size; i++) {
+ ptrfreefp(heap->tree[i].ptr);
+ }
+ }
- heap->size = 0;
+ heap->size = 0;
}
/**
@@ -196,22 +196,22 @@ void BLI_heapsimple_clear(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp)
*/
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr)
{
- if (UNLIKELY(heap->size >= heap->bufsize)) {
- heap->bufsize *= 2;
- heap->tree = MEM_reallocN(heap->tree, heap->bufsize * sizeof(*heap->tree));
- }
+ if (UNLIKELY(heap->size >= heap->bufsize)) {
+ heap->bufsize *= 2;
+ heap->tree = MEM_reallocN(heap->tree, heap->bufsize * sizeof(*heap->tree));
+ }
- heapsimple_up(heap, heap->size++, value, ptr);
+ heapsimple_up(heap, heap->size++, value, ptr);
}
bool BLI_heapsimple_is_empty(const HeapSimple *heap)
{
- return (heap->size == 0);
+ return (heap->size == 0);
}
uint BLI_heapsimple_len(const HeapSimple *heap)
{
- return heap->size;
+ return heap->size;
}
/**
@@ -219,9 +219,9 @@ uint BLI_heapsimple_len(const HeapSimple *heap)
*/
float BLI_heapsimple_top_value(const HeapSimple *heap)
{
- BLI_assert(heap->size != 0);
+ BLI_assert(heap->size != 0);
- return heap->tree[0].value;
+ return heap->tree[0].value;
}
/**
@@ -229,15 +229,15 @@ float BLI_heapsimple_top_value(const HeapSimple *heap)
*/
void *BLI_heapsimple_pop_min(HeapSimple *heap)
{
- BLI_assert(heap->size != 0);
+ BLI_assert(heap->size != 0);
- void *ptr = heap->tree[0].ptr;
+ void *ptr = heap->tree[0].ptr;
- if (--heap->size) {
- heapsimple_down(heap, 0, &heap->tree[heap->size]);
- }
+ if (--heap->size) {
+ heapsimple_down(heap, 0, &heap->tree[heap->size]);
+ }
- return ptr;
+ return ptr;
}
/** \} */
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-09 16:02:43 +0300