RangeTree API rewrite
authorCampbell Barton <ideasman42@gmail.com>
Thu, 13 Oct 2016 04:51:20 +0000 (15:51 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Wed, 26 Oct 2016 12:33:41 +0000 (23:33 +1100)
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.

extern/rangetree/CMakeLists.txt
extern/rangetree/README.blender
extern/rangetree/README.org [deleted file]
extern/rangetree/intern/generic_alloc_impl.h [new file with mode: 0644]
extern/rangetree/intern/range_tree.c [new file with mode: 0644]
extern/rangetree/range_tree.h [new file with mode: 0644]
extern/rangetree/range_tree.hh [deleted file]
extern/rangetree/range_tree_c_api.cc [deleted file]
extern/rangetree/range_tree_c_api.h [deleted file]
source/blender/bmesh/intern/bmesh_log.c

index ba682233381f66d546ed4b0fcbfeaf34046fa9b0..e8e9b15f8b132485a2ba83888f6c28eed0d58a31 100644 (file)
@@ -21,10 +21,10 @@ set(INC
 )
 
 set(SRC
-       range_tree.hh
-       range_tree_c_api.h
+       range_tree.h
+       intern/generic_alloc_impl.h
 
-       range_tree_c_api.cc
+       intern/range_tree.c
 )
 
 blender_add_lib(extern_rangetree "${SRC}" "${INC}" "")
index cb5967137ac675e55149cda523e21a33596ed7b6..6a940c14d60dbb116906e9a718075fc66b592ca7 100644 (file)
@@ -1,5 +1,5 @@
 Project: RangeTree
-URL: https://github.com/nicholasbishop/RangeTree
-License: GPLv2+
-Upstream version: c4ecf6bb7dfd
+URL: https://github.com/ideasman42/rangetree-c
+License: Apache 2.0
+Upstream version: 40ebed8aa209
 Local modifications: None
diff --git a/extern/rangetree/README.org b/extern/rangetree/README.org
deleted file mode 100644 (file)
index 46a4ced..0000000
+++ /dev/null
@@ -1,13 +0,0 @@
-* Overview
-  Basic class for storing non-overlapping scalar ranges. Underlying
-  representation is a C++ STL set for fast lookups.
-
-* License
-  GPL version 2 or later (see COPYING)
-
-* Author Note
-  This implementation is intended for storing free unique IDs in a new
-  undo system for BMesh in Blender, but could be useful elsewhere.
-
-* Website
-  https://github.com/nicholasbishop/RangeTree
diff --git a/extern/rangetree/intern/generic_alloc_impl.h b/extern/rangetree/intern/generic_alloc_impl.h
new file mode 100644 (file)
index 0000000..0f9f518
--- /dev/null
@@ -0,0 +1,215 @@
+/*
+ * Copyright (c) 2016, Blender Foundation.
+ *
+ * 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.
+ */
+
+/**
+ * Simple Memory Chunking Allocator
+ * ================================
+ *
+ * Defines need to be set:
+ * - #TPOOL_IMPL_PREFIX: Prefix to use for the API.
+ * - #TPOOL_ALLOC_TYPE: Struct type this pool handles.
+ * - #TPOOL_STRUCT: Name for pool struct name.
+ * - #TPOOL_CHUNK_SIZE: Chunk size (optional), use 64kb when not defined.
+ *
+ * \note #TPOOL_ALLOC_TYPE must be at least ``sizeof(void *)``.
+ *
+ * Defines the API, uses #TPOOL_IMPL_PREFIX to prefix each function.
+ *
+ * - *_pool_create()
+ * - *_pool_destroy()
+ * - *_pool_clear()
+ *
+ * - *_pool_elem_alloc()
+ * - *_pool_elem_calloc()
+ * - *_pool_elem_free()
+ */
+
+/* check we're not building directly */
+#if !defined(TPOOL_IMPL_PREFIX) || \
+    !defined(TPOOL_ALLOC_TYPE) || \
+    !defined(TPOOL_STRUCT)
+#  error "This file can't be compiled directly, include in another source file"
+#endif
+
+#define _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1 ## MACRO_ARG2
+#define _CONCAT(MACRO_ARG1, MACRO_ARG2) _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)
+#define _TPOOL_PREFIX(id) _CONCAT(TPOOL_IMPL_PREFIX, _##id)
+
+/* local identifiers */
+#define pool_create            _TPOOL_PREFIX(pool_create)
+#define pool_destroy   _TPOOL_PREFIX(pool_destroy)
+#define pool_clear             _TPOOL_PREFIX(pool_clear)
+
+#define pool_elem_alloc                _TPOOL_PREFIX(pool_elem_alloc)
+#define pool_elem_calloc       _TPOOL_PREFIX(pool_elem_calloc)
+#define pool_elem_free         _TPOOL_PREFIX(pool_elem_free)
+
+/* private identifiers (only for this file, undefine after) */
+#define pool_alloc_chunk       _TPOOL_PREFIX(pool_alloc_chunk)
+#define TPoolChunk                     _TPOOL_PREFIX(TPoolChunk)
+#define TPoolChunkElemFree     _TPOOL_PREFIX(TPoolChunkElemFree)
+
+#ifndef TPOOL_CHUNK_SIZE
+#define  TPOOL_CHUNK_SIZE (1 << 16)  /* 64kb */
+#define _TPOOL_CHUNK_SIZE_UNDEF
+#endif
+
+#ifndef UNLIKELY
+#  ifdef __GNUC__
+#    define UNLIKELY(x)     __builtin_expect(!!(x), 0)
+#  else
+#    define UNLIKELY(x)     (x)
+#  endif
+#endif
+
+#ifdef __GNUC__
+#  define MAYBE_UNUSED __attribute__((unused))
+#else
+#  define MAYBE_UNUSED
+#endif
+
+
+struct TPoolChunk {
+       struct TPoolChunk *prev;
+       unsigned int    size;
+       unsigned int    bufsize;
+       TPOOL_ALLOC_TYPE buf[0];
+};
+
+struct TPoolChunkElemFree {
+       struct TPoolChunkElemFree *next;
+};
+
+struct TPOOL_STRUCT {
+       /* Always keep at least one chunk (never NULL) */
+       struct TPoolChunk *chunk;
+       /* when NULL, allocate a new chunk */
+       struct TPoolChunkElemFree *free;
+};
+
+/**
+ * Number of elems to include per #TPoolChunk when no reserved size is passed,
+ * or we allocate past the reserved number.
+ *
+ * \note Optimize number for 64kb allocs.
+ */
+#define _TPOOL_CHUNK_DEFAULT_NUM \
+       (((1 << 16) - sizeof(struct TPoolChunk)) / sizeof(TPOOL_ALLOC_TYPE))
+
+
+/** \name Internal Memory Management
+ * \{ */
+
+static struct TPoolChunk *pool_alloc_chunk(
+        unsigned int tot_elems, struct TPoolChunk *chunk_prev)
+{
+       struct TPoolChunk *chunk = malloc(
+               sizeof(struct TPoolChunk) + (sizeof(TPOOL_ALLOC_TYPE) * tot_elems));
+       chunk->prev = chunk_prev;
+       chunk->bufsize = tot_elems;
+       chunk->size = 0;
+       return chunk;
+}
+
+static TPOOL_ALLOC_TYPE *pool_elem_alloc(struct TPOOL_STRUCT *pool)
+{
+       TPOOL_ALLOC_TYPE *elem;
+
+       if (pool->free) {
+               elem = (TPOOL_ALLOC_TYPE *)pool->free;
+               pool->free = pool->free->next;
+       }
+       else {
+               struct TPoolChunk *chunk = pool->chunk;
+               if (UNLIKELY(chunk->size == chunk->bufsize)) {
+                       chunk = pool->chunk = pool_alloc_chunk(_TPOOL_CHUNK_DEFAULT_NUM, chunk);
+               }
+               elem = &chunk->buf[chunk->size++];
+       }
+
+       return elem;
+}
+
+MAYBE_UNUSED
+static TPOOL_ALLOC_TYPE *pool_elem_calloc(struct TPOOL_STRUCT *pool)
+{
+       TPOOL_ALLOC_TYPE *elem = pool_elem_alloc(pool);
+       memset(elem, 0, sizeof(*elem));
+       return elem;
+}
+
+static void pool_elem_free(struct TPOOL_STRUCT *pool, TPOOL_ALLOC_TYPE *elem)
+{
+       struct TPoolChunkElemFree *elem_free = (struct TPoolChunkElemFree *)elem;
+       elem_free->next = pool->free;
+       pool->free = elem_free;
+}
+
+static void pool_create(struct TPOOL_STRUCT *pool, unsigned int tot_reserve)
+{
+       pool->chunk = pool_alloc_chunk((tot_reserve > 1) ? tot_reserve : _TPOOL_CHUNK_DEFAULT_NUM, NULL);
+       pool->free = NULL;
+}
+
+MAYBE_UNUSED
+static void pool_clear(struct TPOOL_STRUCT *pool)
+{
+       /* Remove all except the last chunk */
+       while (pool->chunk->prev) {
+               struct TPoolChunk *chunk_prev = pool->chunk->prev;
+               free(pool->chunk);
+               pool->chunk = chunk_prev;
+       }
+       pool->chunk->size = 0;
+       pool->free = NULL;
+}
+
+static void pool_destroy(struct TPOOL_STRUCT *pool)
+{
+       struct TPoolChunk *chunk = pool->chunk;
+       do {
+               struct TPoolChunk *chunk_prev;
+               chunk_prev = chunk->prev;
+               free(chunk);
+               chunk = chunk_prev;
+       } while (chunk);
+
+       pool->chunk = NULL;
+       pool->free = NULL;
+}
+
+/** \} */
+
+#undef _TPOOL_CHUNK_DEFAULT_NUM
+#undef _CONCAT_AUX
+#undef _CONCAT
+#undef _TPOOL_PREFIX
+
+#undef TPoolChunk
+#undef TPoolChunkElemFree
+
+#ifdef _TPOOL_CHUNK_SIZE_UNDEF
+#  undef  TPOOL_CHUNK_SIZE
+#  undef _TPOOL_CHUNK_SIZE_UNDEF
+#endif
diff --git a/extern/rangetree/intern/range_tree.c b/extern/rangetree/intern/range_tree.c
new file mode 100644 (file)
index 0000000..766dd22
--- /dev/null
@@ -0,0 +1,869 @@
+/*
+ * 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.
+ */
+
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+
+#include <assert.h>
+
+#include "range_tree.h"
+
+typedef unsigned int uint;
+
+/* Use binary-tree for lookups, else fallback to full search */
+#define USE_BTREE
+/* Use memory pool for nodes, else do individual allocations */
+#define USE_TPOOL
+
+/* Node representing a range in the RangeTreeUInt. */
+typedef struct Node {
+       struct Node *next, *prev;
+
+       /* range (inclusive) */
+       uint min, max;
+
+#ifdef USE_BTREE
+       /* Left leaning red-black tree, for reference implementation see:
+        * https://gitlab.com/ideasman42/btree-mini-py */
+       struct Node *left, *right;
+       /* RED/BLACK */
+       bool color;
+#endif
+} Node;
+
+#ifdef USE_TPOOL
+/* rt_pool_* pool allocator */
+#define TPOOL_IMPL_PREFIX  rt_node
+#define TPOOL_ALLOC_TYPE   Node
+#define TPOOL_STRUCT       ElemPool_Node
+#include "generic_alloc_impl.h"
+#undef TPOOL_IMPL_PREFIX
+#undef TPOOL_ALLOC_TYPE
+#undef TPOOL_STRUCT
+#endif  /* USE_TPOOL */
+
+typedef struct LinkedList {
+       Node *first, *last;
+} LinkedList;
+
+typedef struct RangeTreeUInt {
+       uint range[2];
+       LinkedList list;
+#ifdef USE_BTREE
+       Node *root;
+#endif
+#ifdef USE_TPOOL
+       struct ElemPool_Node epool;
+#endif
+} RangeTreeUInt;
+
+/* ------------------------------------------------------------------------- */
+/* List API */
+
+static void list_push_front(LinkedList *list, Node *node)
+{
+       if (list->first != NULL) {
+               node->next = list->first;
+               node->next->prev = node;
+               node->prev = NULL;
+       }
+       else {
+               list->last = node;
+       }
+       list->first = node;
+}
+
+static void list_push_back(LinkedList *list, Node *node)
+{
+       if (list->first != NULL) {
+               node->prev = list->last;
+               node->prev->next = node;
+               node->next = NULL;
+       }
+       else {
+               list->first = node;
+       }
+       list->last = node;
+}
+
+static void list_push_after(LinkedList *list, Node *node_prev, Node *node_new)
+{
+       /* node_new before node_next */
+
+       /* empty list */
+       if (list->first == NULL) {
+               list->first = node_new;
+               list->last = node_new;
+               return;
+       }
+
+       /* insert at head of list */
+       if (node_prev == NULL) {
+               node_new->prev = NULL;
+               node_new->next = list->first;
+               node_new->next->prev = node_new;
+               list->first = node_new;
+               return;
+       }
+
+       /* at end of list */
+       if (list->last == node_prev) {
+               list->last = node_new;
+       }
+
+       node_new->next = node_prev->next;
+       node_new->prev = node_prev;
+       node_prev->next = node_new;
+       if (node_new->next) {
+               node_new->next->prev = node_new;
+       }
+}
+
+static void list_push_before(LinkedList *list, Node *node_next, Node *node_new)
+{
+       /* node_new before node_next */
+
+       /* empty list */
+       if (list->first == NULL) {
+               list->first = node_new;
+               list->last = node_new;
+               return;
+       }
+
+       /* insert at end of list */
+       if (node_next == NULL) {
+               node_new->prev = list->last;
+               node_new->next = NULL;
+               list->last->next = node_new;
+               list->last = node_new;
+               return;
+       }
+
+       /* at beginning of list */
+       if (list->first == node_next) {
+               list->first = node_new;
+       }
+
+       node_new->next = node_next;
+       node_new->prev = node_next->prev;
+       node_next->prev = node_new;
+       if (node_new->prev) {
+               node_new->prev->next = node_new;
+       }
+}
+
+static void list_remove(LinkedList *list, Node *node)
+{
+       if (node->next != NULL) {
+               node->next->prev = node->prev;
+       }
+       if (node->prev != NULL) {
+               node->prev->next = node->next;
+       }
+
+       if (list->last == node) {
+               list->last = node->prev;
+       }
+       if (list->first == node) {
+               list->first = node->next;
+       }
+}
+
+static void list_clear(LinkedList *list)
+{
+       list->first = NULL;
+       list->last = NULL;
+}
+
+/* end list API */
+
+
+/* forward declarations */
+static void rt_node_free(RangeTreeUInt *rt, Node *node);
+
+
+#ifdef USE_BTREE
+
+#ifdef DEBUG
+static bool rb_is_balanced_root(const Node *root);
+#endif
+
+/* ------------------------------------------------------------------------- */
+/* Internal BTree API
+ *
+ * Left-leaning red-black tree.
+ */
+
+/* use minimum, could use max too since nodes never overlap */
+#define KEY(n) ((n)->min)
+
+enum {
+       RED = 0,
+       BLACK = 1,
+};
+
+
+static bool is_red(const Node *node)
+{
+       return (node && (node->color == RED));
+}
+
+static int key_cmp(uint key1, uint key2)
+{
+       return (key1 == key2) ? 0 : ((key1 < key2) ? -1 : 1);
+}
+
+/* removed from the tree */
+static void rb_node_invalidate(Node *node)
+{
+#ifdef DEBUG
+       node->left = NULL;
+       node->right = NULL;
+       node->color = false;
+#else
+       (void)node;
+#endif
+}
+
+static void rb_flip_color(Node *node)
+{
+       node->color ^= 1;
+       node->left->color ^= 1;
+       node->right->color ^= 1;
+}
+
+static Node *rb_rotate_left(Node *left)
+{
+       /* Make a right-leaning 3-node lean to the left. */
+       Node *right = left->right;
+       left->right = right->left;
+       right->left = left;
+       right->color = left->color;
+       left->color = RED;
+       return right;
+}
+
+static Node *rb_rotate_right(Node *right)
+{
+       /* Make a left-leaning 3-node lean to the right. */
+       Node *left = right->left;
+       right->left = left->right;
+       left->right = right;
+       left->color = right->color;
+       right->color = RED;
+       return left;
+}
+
+/* Fixup colors when insert happened */
+static Node *rb_fixup_insert(Node *node)
+{
+       if (is_red(node->right) && !is_red(node->left)) {
+               node = rb_rotate_left(node);
+       }
+       if (is_red(node->left) && is_red(node->left->left)) {
+               node = rb_rotate_right(node);
+       }
+
+       if (is_red(node->left) && is_red(node->right)) {
+               rb_flip_color(node);
+       }
+
+       return node;
+}
+
+static Node *rb_insert_recursive(Node *node, Node *node_to_insert)
+{
+       if (node == NULL) {
+               return node_to_insert;
+       }
+
+       const int cmp = key_cmp(KEY(node_to_insert), KEY(node));
+       if (cmp == 0) {
+               /* caller ensures no collisions */
+               assert(0);
+       }
+       else if (cmp == -1) {
+               node->left = rb_insert_recursive(node->left, node_to_insert);
+       }
+       else {
+               node->right = rb_insert_recursive(node->right, node_to_insert);
+       }
+
+       return rb_fixup_insert(node);
+}
+
+static Node *rb_insert_root(Node *root, Node *node_to_insert)
+{
+       root = rb_insert_recursive(root, node_to_insert);
+       root->color = BLACK;
+       return root;
+}
+
+static Node *rb_move_red_to_left(Node *node)
+{
+       /* Assuming that h is red and both h->left and h->left->left
+        * are black, make h->left or one of its children red.
+        */
+       rb_flip_color(node);
+       if (node->right && is_red(node->right->left)) {
+               node->right = rb_rotate_right(node->right);
+               node = rb_rotate_left(node);
+               rb_flip_color(node);
+       }
+       return node;
+}
+
+static Node *rb_move_red_to_right(Node *node)
+{
+       /* Assuming that h is red and both h->right and h->right->left
+        * are black, make h->right or one of its children red.
+        */
+       rb_flip_color(node);
+       if (node->left && is_red(node->left->left)) {
+               node = rb_rotate_right(node);
+               rb_flip_color(node);
+       }
+       return node;
+}
+
+/* Fixup colors when remove happened */
+static Node *rb_fixup_remove(Node *node)
+{
+       if (is_red(node->right)) {
+               node = rb_rotate_left(node);
+       }
+       if (is_red(node->left) && is_red(node->left->left)) {
+               node = rb_rotate_right(node);
+       }
+       if (is_red(node->left) && is_red(node->right)) {
+               rb_flip_color(node);
+       }
+       return node;
+}
+
+static Node *rb_pop_min_recursive(Node *node, Node **r_node_pop)
+{
+       if (node == NULL) {
+               return NULL;
+       }
+       if (node->left == NULL) {
+               rb_node_invalidate(node);
+               *r_node_pop = node;
+               return NULL;
+       }
+       if ((!is_red(node->left)) && (!is_red(node->left->left))) {
+               node = rb_move_red_to_left(node);
+       }
+       node->left = rb_pop_min_recursive(node->left, r_node_pop);
+       return rb_fixup_remove(node);
+}
+
+static Node *rb_remove_recursive(Node *node, const Node *node_to_remove)
+{
+       if (node == NULL) {
+               return NULL;
+       }
+       if (key_cmp(KEY(node_to_remove), KEY(node)) == -1) {
+               if (node->left != NULL) {
+                       if ((!is_red(node->left)) && (!is_red(node->left->left))) {
+                               node = rb_move_red_to_left(node);
+                       }
+               }
+               node->left = rb_remove_recursive(node->left, node_to_remove);
+       }
+       else {
+               if (is_red(node->left)) {
+                       node = rb_rotate_right(node);
+               }
+               if ((node == node_to_remove) && (node->right == NULL)) {
+                       rb_node_invalidate(node);
+                       return NULL;
+               }
+               assert(node->right != NULL);
+               if ((!is_red(node->right)) && (!is_red(node->right->left))) {
+                       node = rb_move_red_to_right(node);
+               }
+
+               if (node == node_to_remove) {
+                       /* minor improvement over original method:
+                        * no need to double lookup min */
+                       Node *node_free;  /* will always be set */
+                       node->right = rb_pop_min_recursive(node->right, &node_free);
+
+                       node_free->left = node->left;
+                       node_free->right = node->right;
+                       node_free->color = node->color;
+
+                       rb_node_invalidate(node);
+                       node = node_free;
+               }
+               else {
+                       node->right = rb_remove_recursive(node->right, node_to_remove);
+               }
+       }
+       return rb_fixup_remove(node);
+}
+
+static Node *rb_btree_remove(Node *root, const Node *node_to_remove)
+{
+       root = rb_remove_recursive(root, node_to_remove);
+       if (root != NULL) {
+               root->color = BLACK;
+       }
+       return root;
+}
+
+/*
+ * Returns the node closest to and including 'key',
+ * excluding anything below.
+ */
+static Node *rb_get_or_upper_recursive(Node *n, const uint key)
+{
+       if (n == NULL) {
+               return NULL;
+       }
+       const int cmp_upper = key_cmp(KEY(n), key);
+       if (cmp_upper == 0) {
+               return n;  // exact match
+       }
+       else if (cmp_upper == 1) {
+               assert(KEY(n) >= key);
+               Node *n_test = rb_get_or_upper_recursive(n->left, key);
+               return n_test ? n_test : n;
+       }
+       else {  // cmp_upper == -1
+               return rb_get_or_upper_recursive(n->right, key);
+       }
+}
+
+/*
+ * Returns the node closest to and including 'key',
+ * excluding anything above.
+ */
+static Node *rb_get_or_lower_recursive(Node *n, const uint key)
+{
+       if (n == NULL) {
+               return NULL;
+       }
+       const int cmp_lower = key_cmp(KEY(n), key);
+       if (cmp_lower == 0) {
+               return n;  // exact match
+       }
+       else if (cmp_lower == -1) {
+               assert(KEY(n) <= key);
+               Node *n_test = rb_get_or_lower_recursive(n->right, key);
+               return n_test ? n_test : n;
+       }
+       else {  // cmp_lower == 1
+               return rb_get_or_lower_recursive(n->left, key);
+       }
+}
+
+#ifdef DEBUG
+
+static bool rb_is_balanced_recursive(const Node *node, int black)
+{
+       // Does every path from the root to a leaf have the given number
+       // of black links?
+       if (node == NULL) {
+               return black == 0;
+       }
+       if (!is_red(node)) {
+               black--;
+       }
+       return rb_is_balanced_recursive(node->left, black) &&
+              rb_is_balanced_recursive(node->right, black);
+}
+
+static bool rb_is_balanced_root(const Node *root)
+{
+       // Do all paths from root to leaf have same number of black edges?
+       int black = 0;     // number of black links on path from root to min
+       const Node *node = root;
+       while (node != NULL) {
+               if (!is_red(node)) {
+                       black++;
+               }
+               node = node->left;
+       }
+       return rb_is_balanced_recursive(root, black);
+}
+
+#endif  // DEBUG
+
+
+/* End BTree API */
+#endif  // USE_BTREE
+
+
+/* ------------------------------------------------------------------------- */
+/* Internal RangeTreeUInt API */
+
+static inline Node *rt_node_alloc(RangeTreeUInt *rt)
+{
+#ifdef USE_TPOOL
+       return rt_node_pool_elem_alloc(&rt->epool);
+#else
+       (void)rt;
+       return malloc(sizeof(Node));
+#endif
+}
+
+static Node *rt_node_new(RangeTreeUInt *rt, uint min, uint max)
+{
+       Node *node = rt_node_alloc(rt);
+
+       assert(min <= max);
+       node->prev = NULL;
+       node->next = NULL;
+       node->min = min;
+       node->max = max;
+#ifdef USE_BTREE
+       node->left = NULL;
+       node->right = NULL;
+#endif
+       return node;
+}
+
+static void rt_node_free(RangeTreeUInt *rt, Node *node)
+{
+#ifdef USE_TPOOL
+       rt_node_pool_elem_free(&rt->epool, node);
+#else
+       (void)rt;
+       free(node);
+#endif
+}
+
+#ifdef USE_BTREE
+static void rt_btree_insert(RangeTreeUInt *rt, Node *node)
+{
+       node->color = RED;
+       node->left = NULL;
+       node->right = NULL;
+       rt->root = rb_insert_root(rt->root, node);
+}
+#endif
+
+static void rt_node_add_back(RangeTreeUInt *rt, Node *node)
+{
+       list_push_back(&rt->list, node);
+#ifdef USE_BTREE
+       rt_btree_insert(rt, node);
+#endif
+}
+static void rt_node_add_front(RangeTreeUInt *rt, Node *node)
+{
+       list_push_front(&rt->list, node);
+#ifdef USE_BTREE
+       rt_btree_insert(rt, node);
+#endif
+}
+static void rt_node_add_before(RangeTreeUInt *rt, Node *node_next, Node *node)
+{
+       list_push_before(&rt->list, node_next, node);
+#ifdef USE_BTREE
+       rt_btree_insert(rt, node);
+#endif
+}
+static void rt_node_add_after(RangeTreeUInt *rt, Node *node_prev, Node *node)
+{
+       list_push_after(&rt->list, node_prev, node);
+#ifdef USE_BTREE
+       rt_btree_insert(rt, node);
+#endif
+}
+
+static void rt_node_remove(RangeTreeUInt *rt, Node *node)
+{
+       list_remove(&rt->list, node);
+#ifdef USE_BTREE
+       rt->root = rb_btree_remove(rt->root, node);
+#endif
+       rt_node_free(rt, node);
+}
+
+static Node *rt_find_node_from_value(RangeTreeUInt *rt, const uint value)
+{
+#ifdef USE_BTREE
+       Node *node = rb_get_or_lower_recursive(rt->root, value);
+       if (node != NULL) {
+               if ((value >= node->min) && (value <= node->max)) {
+                       return node;
+               }
+       }
+       return NULL;
+#else
+       for (Node *node = rt->list.first; node; node = node->next) {
+               if ((value >= node->min) && (value <= node->max)) {
+                       return node;
+               }
+       }
+       return NULL;
+#endif // USE_BTREE
+}
+
+static void rt_find_node_pair_around_value(RangeTreeUInt *rt, const uint value,
+                                           Node **r_node_prev, Node **r_node_next)
+{
+       if (value < rt->list.first->min) {
+               *r_node_prev = NULL;
+               *r_node_next = rt->list.first;
+               return;
+       }
+       else if (value > rt->list.last->max) {
+               *r_node_prev = rt->list.last;
+               *r_node_next = NULL;
+               return;
+       }
+       else {
+#ifdef USE_BTREE
+               Node *node_next = rb_get_or_upper_recursive(rt->root, value);
+               if (node_next != NULL) {
+                       Node *node_prev = node_next->prev;
+                       if ((node_prev->max < value) && (value < node_next->min)) {
+                               *r_node_prev = node_prev;
+                               *r_node_next = node_next;
+                               return;
+                       }
+               }
+#else
+               Node *node_prev = rt->list.first;
+               Node *node_next;
+               while ((node_next = node_prev->next)) {
+                       if ((node_prev->max < value) && (value < node_next->min)) {
+                               *r_node_prev = node_prev;
+                               *r_node_next = node_next;
+                               return;
+                       }
+                       node_prev = node_next;
+               }
+#endif // USE_BTREE
+       }
+       *r_node_prev = NULL;
+       *r_node_next = NULL;
+}
+
+
+/* ------------------------------------------------------------------------- */
+/* Public API */
+
+static RangeTreeUInt *rt_create_empty(uint min, uint max)
+{
+       RangeTreeUInt *rt = malloc(sizeof(*rt));
+       rt->range[0] = min;
+       rt->range[1] = max;
+
+       list_clear(&rt->list);
+
+#ifdef USE_BTREE
+       rt->root = NULL;
+#endif
+#ifdef USE_TPOOL
+       rt_node_pool_create(&rt->epool, 512);
+#endif
+
+       return rt;
+}
+
+RangeTreeUInt *range_tree_uint_alloc(uint min, uint max)
+{
+       RangeTreeUInt *rt = rt_create_empty(min, max);
+
+       Node *node = rt_node_new(rt, min, max);
+       rt_node_add_front(rt, node);
+       return rt;
+}
+
+void range_tree_uint_free(RangeTreeUInt *rt)
+{
+#ifdef DEBUG
+#ifdef USE_BTREE
+       assert(rb_is_balanced_root(rt->root));
+#endif
+#endif
+
+#ifdef USE_TPOOL
+
+       rt_node_pool_destroy(&rt->epool);
+#else
+       for (Node *node = rt->list.first, *node_next; node; node = node_next) {
+               node_next = node->next;
+               rt_node_free(rt, node);
+       }
+#endif
+
+       free(rt);
+}
+
+#ifdef USE_BTREE
+static Node *rt_copy_recursive(RangeTreeUInt *rt_dst, const Node *node_src)
+{
+       if (node_src == NULL) {
+               return NULL;
+       }
+
+       Node *node_dst = rt_node_alloc(rt_dst);
+
+       *node_dst = *node_src;
+       node_dst->left = rt_copy_recursive(rt_dst, node_dst->left);
+       list_push_back(&rt_dst->list, node_dst);
+       node_dst->right = rt_copy_recursive(rt_dst, node_dst->right);
+
+       return node_dst;
+}
+#endif  // USE_BTREE
+
+RangeTreeUInt *range_tree_uint_copy(const RangeTreeUInt *rt_src)
+{
+       RangeTreeUInt *rt_dst = rt_create_empty(rt_src->range[0], rt_src->range[1]);
+#ifdef USE_BTREE
+       rt_dst->root = rt_copy_recursive(rt_dst, rt_src->root);
+#else
+       for (Node *node_src = rt_src->list.first; node_src; node_src = node_src->next) {
+               Node *node_dst = rt_node_alloc(rt_dst);
+               *node_dst = *node_src;
+               list_push_back(&rt_dst->list, node_dst);
+       }
+#endif
+       return rt_dst;
+}
+
+/**
+ * Return true if the tree has the value (not taken).
+ */
+bool range_tree_uint_has(RangeTreeUInt *rt, const uint value)
+{
+       assert(value >= rt->range[0] && value <= rt->range[1]);
+       Node *node = rt_find_node_from_value(rt, value);
+       return (node != NULL);
+}
+
+static void range_tree_uint_take_impl(RangeTreeUInt *rt, const uint value, Node *node)
+{
+       assert(node == rt_find_node_from_value(rt, value));
+       if (node->min == value) {
+               if (node->max != value) {
+                       node->min += 1;
+               }
+               else {
+                       assert(node->min == node->max);
+                       rt_node_remove(rt, node);
+               }
+       }
+       else if (node->max == value) {
+               node->max -= 1;
+       }
+       else {
+               Node *node_next = rt_node_new(rt, value + 1, node->max);
+               node->max = value - 1;
+               rt_node_add_after(rt, node, node_next);
+       }
+}
+
+void range_tree_uint_take(RangeTreeUInt *rt, const uint value)
+{
+       Node *node = rt_find_node_from_value(rt, value);
+       assert(node != NULL);
+       range_tree_uint_take_impl(rt, value, node);
+}
+
+bool range_tree_uint_retake(RangeTreeUInt *rt, const uint value)
+{
+       Node *node = rt_find_node_from_value(rt, value);
+       if (node != NULL) {
+               range_tree_uint_take_impl(rt, value, node);
+               return true;
+       }
+       else {
+               return false;
+       }
+}
+
+uint range_tree_uint_take_any(RangeTreeUInt *rt)
+{
+       Node *node = node = rt->list.first;
+       uint value = node->min;
+       if (value == node->max) {
+               rt_node_remove(rt, node);
+       }
+       else {
+               node->min += 1;
+       }
+       return value;
+}
+
+void range_tree_uint_release(RangeTreeUInt *rt, const uint value)
+{
+       bool touch_prev, touch_next;
+       Node *node_prev, *node_next;
+
+       if (rt->list.first != NULL) {
+               rt_find_node_pair_around_value(rt, value, &node_prev, &node_next);
+               /* the value must have been already taken */
+               assert(node_prev || node_next);
+
+               /* Cases:
+                * 1) fill the gap between prev & next (two spans into one span).
+                * 2) touching prev, (grow node_prev->max up one).
+                * 3) touching next, (grow node_next->min down one).
+                * 4) touching neither, add a new segment. */
+               touch_prev = (node_prev != NULL && node_prev->max + 1 == value);
+               touch_next = (node_next != NULL && node_next->min - 1 == value);
+       }
+       else {
+               // we could handle this case (4) inline,
+               // since its not a common case - use regular logic.
+               node_prev = node_next = NULL;
+               touch_prev = false;
+               touch_next = false;
+       }
+
+       if (touch_prev && touch_next) {  // 1)
+               node_prev->max = node_next->max;
+               rt_node_remove(rt, node_next);
+       }
+       else if (touch_prev) {  // 2)
+               assert(node_prev->max + 1 == value);
+               node_prev->max = value;
+       }
+       else if (touch_next) {  // 3)
+               assert(node_next->min - 1 == value);
+               node_next->min = value;
+       }
+       else {  // 4)
+               Node *node_new = rt_node_new(rt, value, value);
+               if (node_prev != NULL) {
+                       rt_node_add_after(rt, node_prev, node_new);
+               }
+               else if (node_next != NULL) {
+                       rt_node_add_before(rt, node_next, node_new);
+               }
+               else {
+                       assert(rt->list.first == NULL);
+                       rt_node_add_back(rt, node_new);
+               }
+       }
+}
diff --git a/extern/rangetree/range_tree.h b/extern/rangetree/range_tree.h
new file mode 100644 (file)
index 0000000..b46832b
--- /dev/null
@@ -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__ */
diff --git a/extern/rangetree/range_tree.hh b/extern/rangetree/range_tree.hh
deleted file mode 100644 (file)
index b247a0c..0000000
+++ /dev/null
@@ -1,251 +0,0 @@
-/* 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.
-*/
-
-#include <cassert>
-#include <climits>
-#include <iostream>
-#include <set>
-
-#ifndef RANGE_TREE_DEBUG_PRINT_FUNCTION
-#    define RANGE_TREE_DEBUG_PRINT_FUNCTION 0
-#endif
-
-template <typename T>
-struct RangeTree {
-       struct Range {
-               Range(T min_, T max_)
-                       : min(min_), max(max_), single(min_ == max_) {
-                       assert(min_ <= max_);
-               }
-
-               Range(T t)
-                       : min(t), max(t), single(true)
-               {}
-
-               Range& operator=(const Range& v) {
-                       *this = v;
-                       return *this;
-               }
-
-               bool operator<(const Range& v) const {
-                       return max < v.min;
-               }
-
-               const T min;
-               const T max;
-               const bool single;
-       };
-
-       typedef std::set<Range> Tree;
-       typedef typename Tree::iterator TreeIter;
-       typedef typename Tree::reverse_iterator TreeIterReverse;
-       typedef typename Tree::const_iterator TreeIterConst;
-
-       /* Initialize with a single range from 'min' to 'max', inclusive. */
-       RangeTree(T min, T max) {
-               tree.insert(Range(min, max));
-       }
-
-       /* Initialize with a single range from 0 to 'max', inclusive. */
-       RangeTree(T max) {
-               tree.insert(Range(0, max));
-       }
-
-       RangeTree(const RangeTree<T>& src) {
-               tree = src.tree;
-       }
-
-       /* Remove 't' from the associated range in the tree. Precondition:
-          a range including 't' must exist in the tree. */
-       void take(T t) {
-               #if RANGE_TREE_DEBUG_PRINT_FUNCTION
-               std::cout << __func__ << "(" << t << ")\n";
-               #endif
-
-               /* Find the range that includes 't' and its neighbors */
-               TreeIter iter = tree.find(Range(t));
-               assert(iter != tree.end());
-               Range cur = *iter;
-
-               /* Remove the original range (note that this does not
-                  invalidate the prev/next iterators) */
-               tree.erase(iter);
-
-               /* Construct two new ranges that together cover the original
-                  range, except for 't' */
-               if (t > cur.min)
-                       tree.insert(Range(cur.min, t - 1));
-               if (t + 1 <= cur.max)
-                       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() {
-               #if RANGE_TREE_DEBUG_PRINT_FUNCTION
-               std::cout << __func__ << "()\n";
-               #endif
-
-               /* Find the first element */
-               TreeIter iter = tree.begin();
-               assert(iter != tree.end());
-               T first = iter->min;
-
-               /* Take the first element */
-               take(first);
-               return first;
-       }
-
-       /* Return 't' to the tree, either expanding/merging existing
-          ranges or adding a range to cover it. Precondition: 't' cannot
-          be in an existing range. */
-       void release(T t) {
-               #if RANGE_TREE_DEBUG_PRINT_FUNCTION
-               std::cout << __func__ << "(" << t << ")\n";
-               #endif
-
-               /* TODO: these cases should be simplified/unified */
-
-               TreeIter right = tree.upper_bound(t);
-               if (right != tree.end()) {
-                       TreeIter left = right;
-                       if (left != tree.begin())
-                               --left;
-
-                       if (left == right) {
-                               /* 't' lies before any existing ranges */
-                               if (t + 1 == left->min) {
-                                       /* 't' lies directly before the first range,
-                                          resize and replace that range */
-                                       const Range r(t, left->max);
-                                       tree.erase(left);
-                                       tree.insert(r);
-                               }
-                               else {
-                                       /* There's a gap between 't' and the first range,
-                                          add a new range */
-                                       tree.insert(Range(t));
-                               }
-                       }
-                       else if ((left->max + 1 == t) &&
-                               (t + 1 == right->min)) {
-                               /* 't' fills a hole. Remove left and right, and insert a
-                                  new range that covers both. */
-                               const Range r(left->min, right->max);
-                               tree.erase(left);
-                               tree.erase(right);
-                               tree.insert(r);
-                       }
-                       else if (left->max + 1 == t) {
-                               /* 't' lies directly after 'left' range, resize and
-                                  replace that range */
-                               const Range r(left->min, t);
-                               tree.erase(left);
-                               tree.insert(r);
-                       }
-                       else if (t + 1 == right->min) {
-                               /* 't' lies directly before 'right' range, resize and
-                                  replace that range */
-                               const Range r(t, right->max);
-                               tree.erase(right);
-                               tree.insert(r);
-                       }
-                       else {
-                               /* There's a gap between 't' and both adjacent ranges,
-                                  add a new range */
-                               tree.insert(Range(t));
-                       }
-               }
-               else {
-                       /* 't' lies after any existing ranges */
-                       right = tree.end();
-                       right--;
-                       if (right->max + 1 == t) {
-                               /* 't' lies directly after last range, resize and
-                                  replace that range */
-                               const Range r(right->min, t);
-                               tree.erase(right);
-                               tree.insert(r);
-                       }
-                       else {
-                               /* There's a gap between the last range and 't', add a
-                                  new range */
-                               tree.insert(Range(t));
-                       }
-               }
-       }
-
-       bool has(T t) const {
-               TreeIterConst iter = tree.find(Range(t));
-               return (iter != tree.end()) && (t <= iter->max);
-       }
-
-       bool has_range(T min, T max) const {
-               TreeIterConst iter = tree.find(Range(min, max));
-               return (iter != tree.end()) && (min == iter->min && max == iter->max);
-       }
-
-       bool empty() const {
-               return tree.empty();
-       }
-
-       int size() const {
-               return tree.size();
-       }
-
-       void print() const {
-               std::cout << "RangeTree:\n";
-               for (TreeIterConst iter = tree.begin(); iter != tree.end(); ++iter) {
-                       const Range& r = *iter;
-                       if (r.single)
-                               std::cout << "  [" << r.min << "]\n";
-                       else
-                               std::cout << "  [" << r.min << ", " << r.max << "]\n";
-               }
-               if (empty())
-                       std::cout << "  <empty>";
-               std::cout << "\n";
-       }
-
-       unsigned int allocation_lower_bound() const {
-               return tree.size() * sizeof(Range);
-       }
-
-private:
-       Tree tree;
-};
diff --git a/extern/rangetree/range_tree_c_api.cc b/extern/rangetree/range_tree_c_api.cc
deleted file mode 100644 (file)
index f040b5e..0000000
+++ /dev/null
@@ -1,92 +0,0 @@
-/* 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.
-*/
-
-#include "range_tree.hh"
-
-/* Give RangeTreeUInt a real type rather than the opaque struct type
-   defined for external use. */
-#define RANGE_TREE_C_API_INTERNAL
-typedef RangeTree<unsigned> RangeTreeUInt;
-
-#include "range_tree_c_api.h"
-
-RangeTreeUInt *range_tree_uint_alloc(unsigned min, unsigned max)
-{
-       return new RangeTreeUInt(min, max);
-}
-
-RangeTreeUInt *range_tree_uint_copy(RangeTreeUInt *src)
-{
-       return new RangeTreeUInt(*src);
-}
-
-void range_tree_uint_free(RangeTreeUInt *rt)
-{
-       delete rt;
-}
-
-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();
-}
-
-void range_tree_uint_release(RangeTreeUInt *rt, unsigned v)
-{
-       rt->release(v);
-}
-
-bool range_tree_uint_has(const RangeTreeUInt *rt, unsigned v)
-{
-       return rt->has(v);
-}
-
-bool range_tree_uint_has_range(
-        const RangeTreeUInt *rt,
-        unsigned vmin,
-        unsigned vmax)
-{
-       return rt->has_range(vmin, vmax);
-}
-
-bool range_tree_uint_empty(const RangeTreeUInt *rt)
-{
-       return rt->empty();
-}
-
-unsigned range_tree_uint_size(const RangeTreeUInt *rt)
-{
-       return rt->size();
-}
-
-void range_tree_uint_print(const RangeTreeUInt *rt)
-{
-       rt->print();
-}
-
-unsigned int range_tree_uint_allocation_lower_bound(const RangeTreeUInt *rt)
-{
-       return rt->allocation_lower_bound();
-}
diff --git a/extern/rangetree/range_tree_c_api.h b/extern/rangetree/range_tree_c_api.h
deleted file mode 100644 (file)
index 6abfb6b..0000000
+++ /dev/null
@@ -1,62 +0,0 @@
-/* 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.
-*/
-
-#ifndef __RANGE_TREE_C_API_H__
-#define __RANGE_TREE_C_API_H__
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/* Simple C-accessible wrapper for RangeTree<unsigned> */
-
-#ifndef RANGE_TREE_C_API_INTERNAL
-typedef struct RangeTreeUInt RangeTreeUInt;
-#endif
-
-RangeTreeUInt *range_tree_uint_alloc(unsigned min, unsigned max);
-
-RangeTreeUInt *range_tree_uint_copy(RangeTreeUInt *src);
-
-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);
-
-bool range_tree_uint_has(const RangeTreeUInt *rt, unsigned v);
-
-bool range_tree_uint_has_range(
-        const RangeTreeUInt *rt,
-        unsigned vmin, unsigned vmax);
-
-bool range_tree_uint_empty(const RangeTreeUInt *rt);
-
-unsigned range_tree_uint_size(const RangeTreeUInt *rt);
-
-void range_tree_uint_print(const RangeTreeUInt *rt);
-
-unsigned int range_tree_uint_allocation_lower_bound(const RangeTreeUInt *rt);
-
-#ifdef __cplusplus
-}
-#endif
-
-#endif /* __RANGE_TREE_C_API_H__ */
index 1f64f7b74cc9c2da603ef980c6c2c2a4311965af..2591c33fc730fe4a017c623a3519d49a23dd9dbf 100644 (file)
@@ -45,7 +45,7 @@
 
 #include "bmesh.h"
 #include "bmesh_log.h"
-#include "range_tree_c_api.h"
+#include "range_tree.h"
 
 #include "BLI_strict_flags.h"