RangeTree API rewrite

Rewrite the current range-tree API used by dyn-topo undo
to avoid inefficiencies from stdc++'s set use.

- every call to `take_any` (called for all verts & faces)
  removed and added to the set.
- further range adjustment also took 2x btree edits.

This patch inlines a btree which is modified in-place,
so common resizing operations don't need to perform a remove & insert.
Ranges are stored in a list so `take_any` can access the first item
without a btree lookup.

Since range-tree isn't a bottleneck in sculpting, this only gives minor speedups.
Measured approx ~15% overall faster calculation for sculpting,
although this number time doesn't include GPU updates and depends on how
much edits fragment the range-tree.

1 files changed, 48 insertions, 0 deletions

diff --git a/extern/rangetree/range_tree.h b/extern/rangetree/range_tree.h
new file mode 100644
index 00000000000..b46832b5cdb
--- /dev/null
+++ b/extern/rangetree/range_tree.h
@@ -0,0 +1,48 @@
+/*
+ * Copyright (c) 2016, Campbell Barton.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "Apache License")
+ * with the following modification; you may not use this file except in
+ * compliance with the Apache License and the following modification to it:
+ * Section 6. Trademarks. is deleted and replaced with:
+ *
+ * 6. Trademarks. This License does not grant permission to use the trade
+ *   names, trademarks, service marks, or product names of the Licensor
+ *   and its affiliates, except as required to comply with Section 4(c) of
+ *   the License and to reproduce the content of the NOTICE file.
+ *
+ * You may obtain a copy of the Apache License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the Apache License with the above modification is
+ * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the Apache License for the specific
+ * language governing permissions and limitations under the Apache License.
+ */
+
+#ifndef __RANGE_TREE_H__
+#define __RANGE_TREE_H__
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef struct RangeTreeUInt RangeTreeUInt;
+
+struct RangeTreeUInt *range_tree_uint_alloc(unsigned int min, unsigned int max);
+void                  range_tree_uint_free(struct RangeTreeUInt *rt);
+struct RangeTreeUInt *range_tree_uint_copy(const struct RangeTreeUInt *rt_src);
+
+bool         range_tree_uint_has(struct RangeTreeUInt *rt, const unsigned int value);
+void         range_tree_uint_take(struct RangeTreeUInt *rt, const unsigned int value);
+bool         range_tree_uint_retake(struct RangeTreeUInt *rt, const unsigned int value);
+unsigned int range_tree_uint_take_any(struct RangeTreeUInt *rt);
+void         range_tree_uint_release(struct RangeTreeUInt *rt, const unsigned int value);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __RANGE_TREE_H__ */