Cleanup: move fast heap into own source & header
authorCampbell Barton <ideasman42@gmail.com>
Tue, 6 Nov 2018 01:52:34 +0000 (12:52 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Tue, 6 Nov 2018 01:52:34 +0000 (12:52 +1100)
12 files changed:
source/blender/blenkernel/intern/pbvh_bmesh.c
source/blender/blenlib/BLI_heap.h
source/blender/blenlib/BLI_heap_simple.h [new file with mode: 0644]
source/blender/blenlib/CMakeLists.txt
source/blender/blenlib/intern/BLI_heap.c
source/blender/blenlib/intern/BLI_heap_simple.c [new file with mode: 0644]
source/blender/blenlib/intern/astar.c
source/blender/bmesh/operators/bmo_connect_pair.c
source/blender/bmesh/tools/bmesh_path.c
source/blender/editors/curve/editcurve_select.c
source/blender/editors/mesh/editmesh_tools.c
source/blender/modifiers/intern/MOD_skin.c

index 0180bdc..35c02a2 100644 (file)
@@ -27,7 +27,7 @@
 #include "BLI_utildefines.h"
 #include "BLI_buffer.h"
 #include "BLI_ghash.h"
-#include "BLI_heap.h"
+#include "BLI_heap_simple.h"
 #include "BLI_math.h"
 #include "BLI_memarena.h"
 
index 08adb0d..35c8df3 100644 (file)
@@ -54,19 +54,4 @@ 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__ */
diff --git a/source/blender/blenlib/BLI_heap_simple.h b/source/blender/blenlib/BLI_heap_simple.h
new file mode 100644 (file)
index 0000000..077c8cc
--- /dev/null
@@ -0,0 +1,45 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BLI_HEAP_SIMPLE_H__
+#define __BLI_HEAP_SIMPLE_H__
+
+/** \file BLI_heap_simple.h
+ *  \ingroup bli
+ *  \brief A min-heap / priority queue ADT
+ */
+
+
+struct FastHeap;
+typedef struct FastHeap FastHeap;
+
+typedef void (*HeapSimpleFreeFP)(void *ptr);
+
+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, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1);
+void        BLI_fastheap_free(FastHeap *heap, HeapSimpleFreeFP 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);
+uint        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_SIMPLE_H__ */
index 6c56b06..5e6764a 100644 (file)
@@ -47,6 +47,7 @@ set(SRC
        intern/BLI_ghash.c
        intern/BLI_ghash_utils.c
        intern/BLI_heap.c
+       intern/BLI_heap_simple.c
        intern/BLI_kdopbvh.c
        intern/BLI_kdtree.c
        intern/BLI_linklist.c
@@ -163,6 +164,7 @@ set(SRC
        BLI_hash_mm2a.h
        BLI_hash_mm3.h
        BLI_heap.h
+       BLI_heap_simple.h
        BLI_iterator.h
        BLI_jitter_2d.h
        BLI_kdopbvh.h
index 4d662f0..c785c1a 100644 (file)
@@ -73,17 +73,6 @@ struct Heap {
        } nodes;
 };
 
-typedef struct FastHeapNode {
-       float value;
-       void *ptr;
-} FastHeapNode;
-
-struct FastHeap {
-       uint size;
-       uint bufsize;
-       FastHeapNode *tree;
-};
-
 /** \name Internal Functions
  * \{ */
 
@@ -452,191 +441,3 @@ bool BLI_heap_is_valid(const Heap *heap)
 }
 
 /** \} */
-
-/** \name FastHeap Internal Functions
- * \{ */
-
-static void fastheap_down(FastHeap *heap, uint start_i, const FastHeapNode *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;
-
-#define OFFSET(i) (i * (uint)sizeof(FastHeapNode))
-#define NODE(offset) (*(FastHeapNode*)(tree_buf + (offset)))
-#else
-       FastHeapNode *const tree = heap->tree;
-
-#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);
-
-       /* 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);
-
-       NODE(i).value = active_val;
-
-       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;
-
-               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;
-               }
-
-               /* 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;
-       }
-
-       /* Spill the pointer into the final position of the node. */
-       NODE(i).ptr = active_ptr;
-
-#undef NODE
-#undef OFFSET
-#undef HEAP_LEFT_OFFSET
-}
-
-static void fastheap_up(FastHeap *heap, uint i, float active_val, void *active_ptr)
-{
-       FastHeapNode *const tree = heap->tree;
-
-       while (LIKELY(i > 0)) {
-               const uint p = HEAP_PARENT(i);
-
-               if (active_val >= tree[p].value) {
-                       break;
-               }
-
-               tree[i] = tree[p];
-               i = p;
-       }
-
-       tree[i].value = active_val;
-       tree[i].ptr = active_ptr;
-}
-
-/** \} */
-
-/** \name Public FastHeap API
- * \{ */
-
-/**
- * Creates a new fast heap, which only supports insertion and removal from top.
- *
- * \note Use when the size of the heap is known in advance.
- */
-FastHeap *BLI_fastheap_new_ex(uint tot_reserve)
-{
-       FastHeap *heap = MEM_mallocN(sizeof(FastHeap), __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(FastHeapNode), "BLIFastHeapTree");
-       return heap;
-}
-
-FastHeap *BLI_fastheap_new(void)
-{
-       return BLI_fastheap_new_ex(1);
-}
-
-void BLI_fastheap_free(FastHeap *heap, HeapFreeFP ptrfreefp)
-{
-       if (ptrfreefp) {
-               for (uint i = 0; i < heap->size; i++) {
-                       ptrfreefp(heap->tree[i].ptr);
-               }
-       }
-
-       MEM_freeN(heap->tree);
-       MEM_freeN(heap);
-}
-
-void BLI_fastheap_clear(FastHeap *heap, HeapFreeFP ptrfreefp)
-{
-       if (ptrfreefp) {
-               for (uint i = 0; i < heap->size; i++) {
-                       ptrfreefp(heap->tree[i].ptr);
-               }
-       }
-
-       heap->size = 0;
-}
-
-/**
- * Insert heap node with a value (often a 'cost') and pointer into the heap,
- * duplicate values are allowed.
- */
-void BLI_fastheap_insert(FastHeap *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));
-       }
-
-       fastheap_up(heap, heap->size++, value, ptr);
-}
-
-bool BLI_fastheap_is_empty(const FastHeap *heap)
-{
-       return (heap->size == 0);
-}
-
-uint BLI_fastheap_len(const FastHeap *heap)
-{
-       return heap->size;
-}
-
-/**
- * Return the lowest value of the heap.
- */
-float BLI_fastheap_top_value(const FastHeap *heap)
-{
-       BLI_assert(heap->size != 0);
-
-       return heap->tree[0].value;
-}
-
-/**
- * Pop the top node off the heap and return it's pointer.
- */
-void *BLI_fastheap_pop_min(FastHeap *heap)
-{
-       BLI_assert(heap->size != 0);
-
-       void *ptr = heap->tree[0].ptr;
-
-       if (--heap->size) {
-               fastheap_down(heap, 0, &heap->tree[heap->size]);
-       }
-
-       return ptr;
-}
-
-/** \} */
diff --git a/source/blender/blenlib/intern/BLI_heap_simple.c b/source/blender/blenlib/intern/BLI_heap_simple.c
new file mode 100644 (file)
index 0000000..6676648
--- /dev/null
@@ -0,0 +1,245 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/blenlib/intern/BLI_heap_simple.c
+ *  \ingroup bli
+ *
+ * A min-heap / priority queue ADT.
+ *
+ * Simplified version of the heap that only supports insertion and removal from top.
+ */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_utildefines.h"
+#include "BLI_heap_simple.h"
+#include "BLI_strict_flags.h"
+
+#define HEAP_PARENT(i) (((i) - 1) >> 1)
+
+/* -------------------------------------------------------------------- */
+/** \name FastHeap Internal Structs
+ * \{ */
+
+typedef struct FastHeapNode {
+       float value;
+       void *ptr;
+} FastHeapNode;
+
+struct FastHeap {
+       uint size;
+       uint bufsize;
+       FastHeapNode *tree;
+};
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name FastHeap Internal Functions
+ * \{ */
+
+static void fastheap_down(FastHeap *heap, uint start_i, const FastHeapNode *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;
+
+#define OFFSET(i) (i * (uint)sizeof(FastHeapNode))
+#define NODE(offset) (*(FastHeapNode*)(tree_buf + (offset)))
+#else
+       FastHeapNode *const tree = heap->tree;
+
+#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);
+
+       /* 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);
+
+       NODE(i).value = active_val;
+
+       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;
+
+               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;
+               }
+
+               /* 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;
+       }
+
+       /* Spill the pointer into the final position of the node. */
+       NODE(i).ptr = active_ptr;
+
+#undef NODE
+#undef OFFSET
+#undef HEAP_LEFT_OFFSET
+}
+
+static void fastheap_up(FastHeap *heap, uint i, float active_val, void *active_ptr)
+{
+       FastHeapNode *const tree = heap->tree;
+
+       while (LIKELY(i > 0)) {
+               const uint p = HEAP_PARENT(i);
+
+               if (active_val >= tree[p].value) {
+                       break;
+               }
+
+               tree[i] = tree[p];
+               i = p;
+       }
+
+       tree[i].value = active_val;
+       tree[i].ptr = active_ptr;
+}
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name Public FastHeap API
+ * \{ */
+
+/**
+ * Creates a new fast heap, which only supports insertion and removal from top.
+ *
+ * \note Use when the size of the heap is known in advance.
+ */
+FastHeap *BLI_fastheap_new_ex(uint tot_reserve)
+{
+       FastHeap *heap = MEM_mallocN(sizeof(FastHeap), __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(FastHeapNode), "BLIFastHeapTree");
+       return heap;
+}
+
+FastHeap *BLI_fastheap_new(void)
+{
+       return BLI_fastheap_new_ex(1);
+}
+
+void BLI_fastheap_free(FastHeap *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);
+}
+
+void BLI_fastheap_clear(FastHeap *heap, HeapSimpleFreeFP ptrfreefp)
+{
+       if (ptrfreefp) {
+               for (uint i = 0; i < heap->size; i++) {
+                       ptrfreefp(heap->tree[i].ptr);
+               }
+       }
+
+       heap->size = 0;
+}
+
+/**
+ * Insert heap node with a value (often a 'cost') and pointer into the heap,
+ * duplicate values are allowed.
+ */
+void BLI_fastheap_insert(FastHeap *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));
+       }
+
+       fastheap_up(heap, heap->size++, value, ptr);
+}
+
+bool BLI_fastheap_is_empty(const FastHeap *heap)
+{
+       return (heap->size == 0);
+}
+
+uint BLI_fastheap_len(const FastHeap *heap)
+{
+       return heap->size;
+}
+
+/**
+ * Return the lowest value of the heap.
+ */
+float BLI_fastheap_top_value(const FastHeap *heap)
+{
+       BLI_assert(heap->size != 0);
+
+       return heap->tree[0].value;
+}
+
+/**
+ * Pop the top node off the heap and return it's pointer.
+ */
+void *BLI_fastheap_pop_min(FastHeap *heap)
+{
+       BLI_assert(heap->size != 0);
+
+       void *ptr = heap->tree[0].ptr;
+
+       if (--heap->size) {
+               fastheap_down(heap, 0, &heap->tree[heap->size]);
+       }
+
+       return ptr;
+}
+
+/** \} */
index 54c80de..959d1a4 100644 (file)
@@ -52,7 +52,7 @@
 #include "BLI_compiler_attrs.h"
 
 #include "BLI_alloca.h"
-#include "BLI_heap.h"
+#include "BLI_heap_simple.h"
 #include "BLI_listbase.h"
 #include "BLI_math.h"
 #include "BLI_memarena.h"
index 3b3766b..4deffb8 100644 (file)
@@ -30,7 +30,7 @@
 
 #include "BLI_math.h"
 #include "BLI_utildefines.h"
-#include "BLI_heap.h"
+#include "BLI_heap_simple.h"
 
 #include "bmesh.h"
 
index 57abd2c..76ab3b3 100644 (file)
@@ -29,7 +29,7 @@
 
 #include "BLI_math.h"
 #include "BLI_linklist.h"
-#include "BLI_heap.h"
+#include "BLI_heap_simple.h"
 
 #include "bmesh.h"
 #include "bmesh_path.h"  /* own include */
index 573161d..d8db1bb 100644 (file)
@@ -38,6 +38,7 @@
 #include "BLI_math.h"
 #include "BLI_rand.h"
 #include "BLI_heap.h"
+#include "BLI_heap_simple.h"
 
 #include "BKE_context.h"
 #include "BKE_curve.h"
index 71dbdfd..9fe4ea4 100644 (file)
@@ -42,7 +42,7 @@
 #include "DNA_scene_types.h"
 
 #include "BLI_bitmap.h"
-#include "BLI_heap.h"
+#include "BLI_heap_simple.h"
 #include "BLI_listbase.h"
 #include "BLI_linklist.h"
 #include "BLI_linklist_stack.h"
index f93512b..098f405 100644 (file)
@@ -66,7 +66,7 @@
 
 #include "BLI_utildefines.h"
 #include "BLI_array.h"
-#include "BLI_heap.h"
+#include "BLI_heap_simple.h"
 #include "BLI_math.h"
 #include "BLI_stack.h"
 #include "BLI_bitmap.h"