diff options
author | Campbell Barton <ideasman42@gmail.com> | 2014-10-07 23:02:08 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2014-10-07 23:02:08 +0400 |
commit | a8705e99ee8ec9de2f25c3bac1e9895c2f98c224 (patch) | |
tree | 096cddaf9ebe5018b5df72c0eb1460b5ab9b3ad4 /extern/rangetree | |
parent | 37474e50cefe703331fc3042e4d009e8db0519cf (diff) |
Sculpt: minor speedup for dyntopo
Add retake to range-tree to avoid double lookup.
Diffstat (limited to 'extern/rangetree')
-rw-r--r-- | extern/rangetree/range_tree.hh | 22 | ||||
-rw-r--r-- | extern/rangetree/range_tree_c_api.cc | 5 | ||||
-rw-r--r-- | extern/rangetree/range_tree_c_api.h | 2 |
3 files changed, 29 insertions, 0 deletions
diff --git a/extern/rangetree/range_tree.hh b/extern/rangetree/range_tree.hh index 919e0b04933..b247a0c6a1e 100644 --- a/extern/rangetree/range_tree.hh +++ b/extern/rangetree/range_tree.hh @@ -92,6 +92,28 @@ struct RangeTree { tree.insert(Range(t + 1, cur.max)); } + /* clone of 'take' that checks if the item exists */ + bool retake(T t) { + #if RANGE_TREE_DEBUG_PRINT_FUNCTION + std::cout << __func__ << "(" << t << ")\n"; + #endif + + TreeIter iter = tree.find(Range(t)); + if (iter == tree.end()) { + return false; + } + + Range cur = *iter; + tree.erase(iter); + if (t > cur.min) + tree.insert(Range(cur.min, t - 1)); + if (t + 1 <= cur.max) + tree.insert(Range(t + 1, cur.max)); + + return true; + } + + /* Take the first element out of the first range in the tree. Precondition: tree must not be empty. */ T take_any() { diff --git a/extern/rangetree/range_tree_c_api.cc b/extern/rangetree/range_tree_c_api.cc index 79d3df5792b..f040b5eaeb6 100644 --- a/extern/rangetree/range_tree_c_api.cc +++ b/extern/rangetree/range_tree_c_api.cc @@ -43,6 +43,11 @@ void range_tree_uint_take(RangeTreeUInt *rt, unsigned v) rt->take(v); } +bool range_tree_uint_retake(RangeTreeUInt *rt, unsigned v) +{ + return rt->retake(v); +} + unsigned range_tree_uint_take_any(RangeTreeUInt *rt) { return rt->take_any(); diff --git a/extern/rangetree/range_tree_c_api.h b/extern/rangetree/range_tree_c_api.h index d78dc959a6c..f0a2af4a29a 100644 --- a/extern/rangetree/range_tree_c_api.h +++ b/extern/rangetree/range_tree_c_api.h @@ -35,6 +35,8 @@ void range_tree_uint_free(RangeTreeUInt *rt); void range_tree_uint_take(RangeTreeUInt *rt, unsigned v); +bool range_tree_uint_retake(RangeTreeUInt *rt, unsigned v); + unsigned range_tree_uint_take_any(RangeTreeUInt *rt); void range_tree_uint_release(RangeTreeUInt *rt, unsigned v); |