aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_rbtree.h
diff options
context:
space:
mode:
authorRickard Green <[email protected]>2015-05-05 20:03:17 +0200
committerRickard Green <[email protected]>2015-05-06 16:33:08 +0200
commit7ba91b64862e29bfd579b04c73e2bccacde6a003 (patch)
tree1ac07e9b5ab19f8646189cd3f3f962be9fd2c037 /erts/emulator/beam/erl_rbtree.h
parent6b5905e49c74c4034b55824ce4d1a62455f670bc (diff)
downloadotp-7ba91b64862e29bfd579b04c73e2bccacde6a003.tar.gz
otp-7ba91b64862e29bfd579b04c73e2bccacde6a003.tar.bz2
otp-7ba91b64862e29bfd579b04c73e2bccacde6a003.zip
Reusable red-black tree implementation
Diffstat (limited to 'erts/emulator/beam/erl_rbtree.h')
-rw-r--r--erts/emulator/beam/erl_rbtree.h1740
1 files changed, 1740 insertions, 0 deletions
diff --git a/erts/emulator/beam/erl_rbtree.h b/erts/emulator/beam/erl_rbtree.h
new file mode 100644
index 0000000000..ea0a8976bb
--- /dev/null
+++ b/erts/emulator/beam/erl_rbtree.h
@@ -0,0 +1,1740 @@
+/*
+ * %CopyrightBegin%
+ *
+ * Copyright Ericsson AB 2015. All Rights Reserved.
+ *
+ * The contents of this file are subject to the Erlang Public License,
+ * Version 1.1, (the "License"); you may not use this file except in
+ * compliance with the License. You should have received a copy of the
+ * Erlang Public License along with this software. If not, it can be
+ * retrieved online at http://www.erlang.org/.
+ *
+ * Software distributed under the License is distributed on an "AS IS"
+ * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+ * the License for the specific language governing rights and limitations
+ * under the License.
+ *
+ * %CopyrightEnd%
+ */
+
+/*
+ * Description: A Red-Black (binary search) Tree implementation. The search,
+ * insert, and delete operations are all O(log n) operations
+ * on a Red-Black Tree. Red-Black Trees are described in
+ * "Introduction to Algorithms", by Thomas H. Cormen, Charles
+ * E. Leiserson, and Ronald L. Riverest.
+ *
+ * Use by defining mandatory defines as well as defines for
+ * API functions wanted, and include this header.
+ *
+ * Author: Rickard Green
+ *
+ *
+ * Mandatory defines:
+ * - ERTS_RBT_PREFIX - Prefix to use on functions.
+ * - ERTS_RBT_T - Type of a tree node.
+ * - ERTS_RBT_KEY_T - Type of key for a tree node.
+ * - ERTS_RBT_FLAGS_T - Type of flags for a tree node.
+ * - ERTS_RBT_INIT_EMPTY_TNODE(T) -Initialize an empty tree node.
+ * - ERTS_RBT_IS_RED(T) - Is tree node red?
+ * - ERTS_RBT_SET_RED(T) - Set tree node red.
+ * - ERTS_RBT_IS_BLACK(T) - Is tree node back?
+ * - ERTS_RBT_SET_BLACK(T) - Set tree node black.
+ * - ERTS_RBT_GET_FLAGS(T) - Get flags of tree node (incl colors).
+ * - ERTS_RBT_SET_FLAGS(T, F) - Set flags of tree note.
+ * - ERTS_RBT_GET_PARENT(T) - Get parent node.
+ * - ERTS_RBT_SET_PARENT(T, P) - Set parent node.
+ * - ERTS_RBT_GET_RIGHT(T) - Get right child node.
+ * - ERTS_RBT_SET_RIGHT(T, R) - Set right child node.
+ * - ERTS_RBT_GET_LEFT(T) - Get left child node.
+ * - ERTS_RBT_SET_LEFT(T, L) - Set left child node.
+ * - ERTS_RBT_GET_KEY(T) - Get key of node.
+ * - ERTS_RBT_IS_LT(KX, KY) - Is key KX less than key KY?
+ * - ERTS_RBT_IS_EQ(KX, KY) - Is key KX equal to key KY?
+ *
+ * Optional defines:
+ *
+ * - ERTS_RBT_UNDEF - Undefine all user defined ERTS_RBT_*
+ * defines after use.
+ *
+ * - ERTS_RBT_NO_API_INLINE - Do not inline API functions.
+ *
+ * Attached data management:
+ * - ERTS_RBT_UPDATE_ATTACHED_DATA_ROTATE(L, OP, NP) - Called
+ * when a rotate operation has been performed. If L (in int)
+ * is a non zero, a left rotation was performed; otherwise,
+ * a right rotation was performed. OR points to the old
+ * parent node and NP points to the new parent node.
+ * - ERTS_RBT_UPDATE_ATTACHED_DATA_DMOD(F, T) - Called when
+ * a delete operation modifies a tree node. A delete
+ * modification is either a removal or replacement of a
+ * node. F points to the parent of the tree node that was
+ * modified. T points to the next ancestor that will be
+ * modified. If T is NULL, no more removal and/or
+ * replacements will be made. One typically wants to update
+ * the attached data of each node between F and T. If T is
+ * NULL all the way up to the root.
+ * - ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT(OR, NR) - Called
+ * when the root node changes. OR points to the old
+ * root node and NP points to the new root node.
+ *
+ * Request implementation of API functions:
+ * - ERTS_RBT_WANT_DELETE
+ * - ERTS_RBT_WANT_INSERT
+ * - ERTS_RBT_WANT_LOOKUP_INSERT
+ * - ERTS_RBT_WANT_REPLACE
+ * - ERTS_RBT_WANT_LOOKUP
+ * - ERTS_RBT_WANT_SMALLEST
+ * - ERTS_RBT_WANT_LARGEST
+ * - ERTS_RBT_WANT_FOREACH
+ * - ERTS_RBT_WANT_FOREACH_DESTROY
+ * - ERTS_RBT_WANT_FOREACH_YIELDING
+ * - ERTS_RBT_WANT_FOREACH_DESTROY_YIELDING
+ * - ERTS_RBT_WANT_FOREACH_SMALL
+ * - ERTS_RBT_WANT_FOREACH_LARGE
+ * - ERTS_RBT_WANT_FOREACH_SMALL_DESTROY
+ * - ERTS_RBT_WANT_FOREACH_LARGE_DESTROY
+ * - ERTS_RBT_WANT_FOREACH_SMALL_YIELDING
+ * - ERTS_RBT_WANT_FOREACH_LARGE_YIELDING
+ * - ERTS_RBT_WANT_FOREACH_SMALL_DESTROY_YIELDING
+ * - ERTS_RBT_WANT_FOREACH_LARGE_DESTROY_YIELDING
+ * - ERTS_RBT_WANT_DEBUG_PRINT
+ *
+ * The yield state data type will equal
+ * <ERTS_RBT_PREFIX>_rbt_yield_state_t.
+ *
+ * The yield state should be statically initialized by
+ * ERTS_RBT_YIELD_STAT_INITER.
+ *
+ *
+ * The following API functions are implemented if corresponding
+ * ERTS_RBT_WANT_<OPERATION> is defined:
+ *
+ * - void <ERTS_RBT_PREFIX>_rbt_delete(
+ * ERTS_RBT_T **tree,
+ * ERTS_RBT_T *element);
+ * Delete element from tree.
+ *
+ * - void <ERTS_RBT_PREFIX>_rbt_insert(
+ * ERTS_RBT_T **tree,
+ * ERTS_RBT_T *element);
+ * Insert element into tree.
+ *
+ * - ERTS_RBT_T * <ERTS_RBT_PREFIX>_rbt_lookup_insert(
+ * ERTS_RBT_T **tree,
+ * ERTS_RBT_T *element);
+ * Look up an element in the tree that compares as equal to the
+ * element passed as argument, and return the looked up element.
+ * If no element compared as equal, insert the element passed as
+ * argument into the tree, and return NULL.
+ *
+ * - void <ERTS_RBT_PREFIX>_rbt_replace(
+ * ERTS_RBT_T **tree,
+ * ERTS_RBT_T *old_element,
+ * ERTS_RBT_T *new_element);
+ * Replace old_element in the tree with new_element. Both elements
+ * *should* compare as equal.
+ *
+ * - ERTS_RBT_T * <ERTS_RBT_PREFIX>_rbt_lookup(
+ * ERTS_RBT_T *tree,
+ * ERTS_RBT_KEY_T key);
+ * Look up an element with a key that compares as equal to
+ * the key passed as argument.
+ *
+ * - ERTS_RBT_T * <ERTS_RBT_PREFIX>_rbt_smallest(
+ * ERTS_RBT_T *tree);
+ * Look up the element with the smallest key.
+ *
+ * - ERTS_RBT_T * <ERTS_RBT_PREFIX>_rbt_largest(
+ * ERTS_RBT_T *tree);
+ * Look up the element with the largest key.
+ *
+ * - void <ERTS_RBT_PREFIX>_rbt_foreach(
+ * ERTS_RBT_T *tree,
+ * void (*op)(ERTS_RBT_T *, void *),
+ * void *arg);
+ * Operate by calling the operator 'op' on each element.
+ * Order is undefined.
+ *
+ * 'arg' is passed as argument to 'op'.
+ *
+ * - void <ERTS_RBT_PREFIX>_rbt_foreach_destroy(
+ * ERTS_RBT_T *tree,
+ * void (*op)(ERTS_RBT_T *, void *),
+ * void *arg);
+ * Operate by calling the operator 'op' on each element.
+ * Order is undefined. Each element should be destroyed
+ * by 'op'.
+ *
+ * 'arg' is passed as argument to 'op'.
+ *
+ * - int <ERTS_RBT_PREFIX>_rbt_foreach_yielding(
+ * ERTS_RBT_T *tree,
+ * void (*op)(ERTS_RBT_T *, void *),
+ * void *arg,
+ * <ERTS_RBT_PREFIX>_rbt_yield_state_t *ystate,
+ * Sint ylimit);
+ * Operate by calling the operator 'op' on each element.
+ * Order is undefined.
+ *
+ * Yield when 'ylimit' elements has been processed. Zero is
+ * returned when yielding, and a non-zero value is returned when
+ * the whole tree has been processed. The tree should not be
+ * modified until all of it has been processed.
+ *
+ * 'arg' is passed as argument to 'op'.
+ *
+ * - int <ERTS_RBT_PREFIX>_rbt_foreach_destroy_yielding(
+ * ERTS_RBT_T *tree,
+ * void (*op)(ERTS_RBT_T *, void *),
+ * void *arg,
+ * <ERTS_RBT_PREFIX>_rbt_yield_state_t *ystate,
+ * Sint ylimit);
+ * Operate by calling the operator 'op' on each element.
+ * Order is undefined. Each element should be destroyed
+ * by 'op'.
+ *
+ * Yield when 'ylimit' elements has been processed. Zero is
+ * returned when yielding, and a non-zero value is returned when
+ * the whole tree has been processed.
+ *
+ * 'arg' is passed as argument to 'op'.
+ *
+ * - void <ERTS_RBT_PREFIX>_rbt_foreach_small(
+ * ERTS_RBT_T *tree,
+ * void (*op)(ERTS_RBT_T *, void *),
+ * void *arg);
+ * Operate by calling the operator 'op' on each element from
+ * smallest towards larger elements.
+ *
+ * 'arg' is passed as argument to 'op'.
+ *
+ * - void <ERTS_RBT_PREFIX>_rbt_foreach_large(
+ * ERTS_RBT_T *tree,
+ * void (*op)(ERTS_RBT_T *, void *),
+ * void *arg);
+ * Operate by calling the operator 'op' on each element from
+ * largest towards smaller elements.
+ *
+ * 'arg' is passed as argument to 'op'.
+ *
+ * - int <ERTS_RBT_PREFIX>_rbt_foreach_small_yielding(
+ * ERTS_RBT_T *tree,
+ * void (*op)(ERTS_RBT_T *, void *),
+ * void *arg,
+ * <ERTS_RBT_PREFIX>_rbt_yield_state_t *ystate,
+ * Sint ylimit);
+ * Operate by calling the operator 'op' on each element from
+ * smallest towards larger elements.
+ *
+ * Yield when 'ylimit' elements has been processed. Zero is
+ * returned when yielding, and a non-zero value is returned when
+ * the whole tree has been processed. The tree should not be
+ * modified until all of it has been processed.
+ *
+ * 'arg' is passed as argument to 'op'.
+ *
+ * - int <ERTS_RBT_PREFIX>_rbt_foreach_large_yielding(
+ * ERTS_RBT_T *tree,
+ * void (*op)(ERTS_RBT_T *, void *),
+ * void *arg,
+ * <ERTS_RBT_PREFIX>_rbt_yield_state_t *ystate,
+ * Sint ylimit);
+ * Operate by calling the operator 'op' on each element from
+ * largest towards smaller elements.
+ *
+ * Yield when 'ylimit' elements has been processed. Zero is
+ * returned when yielding, and a non-zero value is returned when
+ * the whole tree has been processed. The tree should not be
+ * modified until all of it has been processed.
+ *
+ * 'arg' is passed as argument to 'op'.
+ *
+ * - void <ERTS_RBT_PREFIX>_rbt_foreach_small_destroy(
+ * ERTS_RBT_T **tree,
+ * void (*op)(ERTS_RBT_T *, void *),
+ * void (*destr)(ERTS_RBT_T *, void *),
+ * void *arg);
+ * Operate by calling the operator 'op' on each element from
+ * smallest towards larger elements.
+ *
+ * Destroy elements by calling the destructor 'destr'. Elements
+ * are destroyed when not needed by the tree structure anymore.
+ * Note that elements are often *not* destroyed in another order
+ * than the order that the elements are operated on.
+ *
+ * 'arg' is passed as argument to 'op' and 'destroy'.
+ *
+ * - void <ERTS_RBT_PREFIX>_rbt_foreach_large_destroy(
+ * ERTS_RBT_T **tree,
+ * void (*op)(ERTS_RBT_T *, void *),
+ * void (*destr)(ERTS_RBT_T *, void *),
+ * void *arg);
+ * Operate by calling the operator 'op' on each element from
+ * largest towards smaller elements.
+ *
+ * Destroy elements by calling the destructor 'destr'. Elements
+ * are destroyed when not needed by the tree structure anymore.
+ * Note that elements are often destroyed in another order
+ * than the order that the elements are operated on.
+ *
+ * 'arg' is passed as argument to 'op' and 'destroy'.
+ *
+ * - int <ERTS_RBT_PREFIX>_rbt_foreach_small_destroy_yielding(
+ * ERTS_RBT_T **tree,
+ * void (*op)(ERTS_RBT_T *, void *),
+ * void (*destr)(ERTS_RBT_T *, void *),
+ * void *arg,
+ * <ERTS_RBT_PREFIX>_rbt_yield_state_t *ystate,
+ * Sint ylimit);
+ * Operate by calling the operator 'op' on each element from
+ * smallest towards larger elements.
+ *
+ * Destroy elements by calling the destructor 'destr'. Elements
+ * are destroyed when not needed by the tree structure anymore.
+ * Note that elements are often destroyed in another order
+ * than the order that the elements are operated on.
+ *
+ * Yield when 'ylimit' elements has been processed. Zero is
+ * returned when yielding, and a non-zero value is returned when
+ * the whole tree has been processed. The tree should not be
+ * modified until all of it has been processed.
+ *
+ * 'arg' is passed as argument to 'op' and 'destroy'.
+ *
+ * - int <ERTS_RBT_PREFIX>_rbt_foreach_large_destroy_yielding(
+ * ERTS_RBT_T **tree,
+ * void (*op)(ERTS_RBT_T *, void *),
+ * void (*destr)(ERTS_RBT_T *, void *),
+ * void *arg,
+ * <ERTS_RBT_PREFIX>_rbt_yield_state_t *ystate,
+ * Sint ylimit);
+ * Operate by calling the operator 'op' on each element from
+ * largest towards smaller elements.
+ *
+ * Destroy elements by calling the destructor 'destr'. Elements
+ * are destroyed when not needed by the tree structure anymore.
+ * Note that elements are often destroyed in another order
+ * than the order that the elements are operated on.
+ *
+ * Yield when 'ylimit' elements has been processed. Zero is
+ * returned when yielding, and a non-zero value is returned when
+ * the whole tree has been processed. The tree should not be
+ * modified until all of it has been processed.
+ *
+ * 'arg' is passed as argument to 'op' and 'destroy'.
+ *
+ * - void <ERTS_RBT_PREFIX>_rbt_debug_print(
+ * FILE *filep,
+ * ERTS_RBT_T *x,
+ * int indent,
+ * (void)(*print_node)(ERTS_RBT_T *));
+ * Prints the tree. Note that this function is recursive.
+ * Should only be used for debuging.
+ */
+
+
+/*
+ * Check that we have all mandatory defines
+ */
+#ifndef ERTS_RBT_PREFIX
+# error Missing definition of ERTS_RBT_PREFIX
+#endif
+#ifndef ERTS_RBT_T
+# error Missing definition of ERTS_RBT_T
+#endif
+#ifndef ERTS_RBT_KEY_T
+# error Missing definition of ERTS_RBT_KEY_T
+#endif
+#ifndef ERTS_RBT_FLAGS_T
+# error Missing definition of ERTS_RBT_FLAGS_T
+#endif
+#ifndef ERTS_RBT_INIT_EMPTY_TNODE
+# error Missing definition of ERTS_RBT_INIT_EMPTY_TNODE
+#endif
+#ifndef ERTS_RBT_IS_RED
+# error Missing definition of ERTS_RBT_IS_RED
+#endif
+#ifndef ERTS_RBT_SET_RED
+# error Missing definition of ERTS_RBT_SET_RED
+#endif
+#ifndef ERTS_RBT_IS_BLACK
+# error Missing definition of ERTS_RBT_IS_BLACK
+#endif
+#ifndef ERTS_RBT_SET_BLACK
+# error Missing definition of ERTS_RBT_SET_BLACK
+#endif
+#ifndef ERTS_RBT_GET_FLAGS
+# error Missing definition of ERTS_RBT_GET_FLAGS
+#endif
+#ifndef ERTS_RBT_SET_FLAGS
+# error Missing definition of ERTS_RBT_SET_FLAGS
+#endif
+#ifndef ERTS_RBT_GET_PARENT
+# error Missing definition of ERTS_RBT_GET_PARENT
+#endif
+#ifndef ERTS_RBT_SET_PARENT
+# error Missing definition of ERTS_RBT_SET_PARENT
+#endif
+#ifndef ERTS_RBT_GET_RIGHT
+# error Missing definition of ERTS_RBT_GET_RIGHT
+#endif
+#ifndef ERTS_RBT_GET_LEFT
+# error Missing definition of ERTS_RBT_GET_LEFT
+#endif
+#ifndef ERTS_RBT_IS_LT
+# error Missing definition of ERTS_RBT_IS_LT
+#endif
+#ifndef ERTS_RBT_GET_KEY
+# error Missing definition of ERTS_RBT_GET_KEY
+#endif
+#ifndef ERTS_RBT_IS_EQ
+# error Missing definition of ERTS_RBT_IS_EQ
+#endif
+
+#if defined(ERTS_RBT_HARD_DEBUG) || defined(DEBUG)
+# ifndef ERTS_RBT_DEBUG
+# define ERTS_RBT_DEBUG 1
+# endif
+#endif
+
+#if defined(ERTS_RBT_HARD_DEBUG) && defined(__GNUC__)
+#warning "* * * * * * * * * * * * * * * * * *"
+#warning "* ERTS_RBT_HARD_DEBUG IS ENABLED! *"
+#warning "* * * * * * * * * * * * * * * * * *"
+#endif
+
+#undef ERTS_RBT_ASSERT
+#if defined(ERTS_RBT_DEBUG)
+#define ERTS_RBT_ASSERT(E) ERTS_ASSERT(E)
+#else
+#define ERTS_RBT_ASSERT(E) ((void) 1)
+#endif
+
+#undef ERTS_RBT_API_INLINE__
+#if defined(ERTS_RBT_NO_API_INLINE) || defined(ERTS_RBT_DEBUG)
+# define ERTS_RBT_API_INLINE__
+#else
+# define ERTS_RBT_API_INLINE__ ERTS_INLINE
+#endif
+
+#ifndef ERTS_RBT_YIELD_STAT_INITER
+# define ERTS_RBT_YIELD_STAT_INITER {NULL, 0}
+#endif
+
+#define ERTS_RBT_CONCAT_MACRO_VALUES___(X, Y) \
+ X ## Y
+#define ERTS_RBT_CONCAT_MACRO_VALUES__(X, Y) \
+ ERTS_RBT_CONCAT_MACRO_VALUES___(X, Y)
+
+#undef ERTS_RBT_YIELD_STATE_T__
+#define ERTS_RBT_YIELD_STATE_T__ \
+ ERTS_RBT_CONCAT_MACRO_VALUES__(ERTS_RBT_PREFIX, _rbt_yield_state_t)
+
+typedef struct {
+ ERTS_RBT_T *x;
+ int up;
+} ERTS_RBT_YIELD_STATE_T__;
+
+#define ERTS_RBT_FUNC__(Name) \
+ ERTS_RBT_CONCAT_MACRO_VALUES__(ERTS_RBT_PREFIX, _rbt_ ## Name)
+
+#undef ERTS_RBT_NEED_REPLACE__
+#undef ERTS_RBT_NEED_INSERT__
+#undef ERTS_RBT_NEED_ROTATE__
+#undef ERTS_RBT_NEED_FOREACH_UNORDERED__
+#undef ERTS_RBT_NEED_FOREACH_ORDERED__
+#undef ERTS_RBT_NEED_HDBG_CHECK_TREE__
+#undef ERTS_RBT_HDBG_CHECK_TREE__
+
+#if defined(ERTS_RBT_WANT_REPLACE) || defined(ERTS_RBT_WANT_DELETE)
+# define ERTS_RBT_NEED_REPLACE__
+#endif
+#if defined(ERTS_RBT_WANT_INSERT) || defined(ERTS_RBT_WANT_LOOKUP_INSERT)
+# define ERTS_RBT_NEED_INSERT__
+#endif
+#if defined(ERTS_RBT_WANT_DELETE) || defined(ERTS_RBT_NEED_INSERT__)
+# define ERTS_RBT_NEED_ROTATE__
+#endif
+#if defined(ERTS_RBT_WANT_FOREACH) \
+ || defined(ERTS_RBT_WANT_FOREACH_YIELDING) \
+ || defined(ERTS_RBT_WANT_FOREACH_DESTROY) \
+ || defined(ERTS_RBT_WANT_FOREACH_DESTROY_YIELDING)
+# define ERTS_RBT_NEED_FOREACH_UNORDERED__
+#endif
+#if defined(ERTS_RBT_WANT_FOREACH_SMALL) \
+ || defined(ERTS_RBT_WANT_FOREACH_LARGE) \
+ || defined(ERTS_RBT_WANT_FOREACH_SMALL_YIELDING) \
+ || defined(ERTS_RBT_WANT_FOREACH_LARGE_YIELDING) \
+ || defined(ERTS_RBT_WANT_FOREACH_SMALL_DESTROY) \
+ || defined(ERTS_RBT_WANT_FOREACH_LARGE_DESTROY) \
+ || defined(ERTS_RBT_WANT_FOREACH_SMALL_DESTROY_YIELDING) \
+ || defined(ERTS_RBT_WANT_FOREACH_LARGE_DESTROY_YIELDING)
+# define ERTS_RBT_NEED_FOREACH_ORDERED__
+#endif
+#if defined(ERTS_RBT_HARD_DEBUG) \
+ && (defined(ERTS_RBT_WANT_DELETE) \
+ || defined(ERTS_RBT_NEED_INSERT__))
+static void ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root);
+# define ERTS_RBT_NEED_HDBG_CHECK_TREE__
+# define ERTS_RBT_HDBG_CHECK_TREE__(R) \
+ ERTS_RBT_FUNC__(hdbg_check_tree)((R))
+#else
+# define ERTS_RBT_HDBG_CHECK_TREE__(R) ((void) 1)
+#endif
+
+#ifdef ERTS_RBT_NEED_ROTATE__
+
+static ERTS_INLINE void
+ERTS_RBT_FUNC__(left_rotate__)(ERTS_RBT_T **root, ERTS_RBT_T *x)
+{
+ ERTS_RBT_T *y, *l, *p;
+
+ y = ERTS_RBT_GET_RIGHT(x);
+ l = ERTS_RBT_GET_LEFT(y);
+ ERTS_RBT_SET_RIGHT(x, l);
+
+ if (l)
+ ERTS_RBT_SET_PARENT(l, x);
+
+ p = ERTS_RBT_GET_PARENT(x);
+ ERTS_RBT_SET_PARENT(y, p);
+
+ if (!p) {
+ ERTS_RBT_ASSERT(*root == x);
+ *root = y;
+#ifdef ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT
+ ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT(x, y);
+#endif
+ }
+ else if (x == ERTS_RBT_GET_LEFT(p))
+ ERTS_RBT_SET_LEFT(p, y);
+ else {
+ ERTS_RBT_ASSERT(x == ERTS_RBT_GET_RIGHT(p));
+ ERTS_RBT_SET_RIGHT(p, y);
+ }
+ ERTS_RBT_SET_LEFT(y, x);
+ ERTS_RBT_SET_PARENT(x, y);
+
+#ifdef ERTS_RBT_UPDATE_ATTACHED_DATA_ROTATE
+ ERTS_RBT_UPDATE_ATTACHED_DATA_ROTATE(!0, x, y);
+#endif
+
+}
+
+static ERTS_INLINE void
+ERTS_RBT_FUNC__(right_rotate__)(ERTS_RBT_T **root, ERTS_RBT_T *x)
+{
+ ERTS_RBT_T *y, *r, *p;
+
+ y = ERTS_RBT_GET_LEFT(x);
+ r = ERTS_RBT_GET_RIGHT(y);
+ ERTS_RBT_SET_LEFT(x, r);
+
+ if (r)
+ ERTS_RBT_SET_PARENT(r, x);
+
+ p = ERTS_RBT_GET_PARENT(x);
+ ERTS_RBT_SET_PARENT(y, p);
+
+ if (!p) {
+ ERTS_RBT_ASSERT(*root == x);
+ *root = y;
+#ifdef ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT
+ ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT(x, y);
+#endif
+ }
+ else if (x == ERTS_RBT_GET_RIGHT(p))
+ ERTS_RBT_SET_RIGHT(p, y);
+ else {
+ ERTS_RBT_ASSERT(x == ERTS_RBT_GET_LEFT(p));
+ ERTS_RBT_SET_LEFT(p, y);
+ }
+
+ ERTS_RBT_SET_RIGHT(y, x);
+ ERTS_RBT_SET_PARENT(x, y);
+
+#ifdef ERTS_RBT_UPDATE_ATTACHED_DATA_ROTATE
+ ERTS_RBT_UPDATE_ATTACHED_DATA_ROTATE(0, x, y);
+#endif
+
+}
+
+#endif /* ERTS_RBT_NEED_ROTATE__ */
+
+#ifdef ERTS_RBT_NEED_REPLACE__
+
+/*
+ * Replace node x with node y
+ */
+static ERTS_INLINE void
+ERTS_RBT_FUNC__(replace__)(ERTS_RBT_T **root, ERTS_RBT_T *x, ERTS_RBT_T *y)
+{
+ ERTS_RBT_T *p, *r, *l;
+ ERTS_RBT_FLAGS_T f;
+
+ p = ERTS_RBT_GET_PARENT(x);
+ if (!p) {
+ ERTS_RBT_ASSERT(*root == x);
+ *root = y;
+#ifdef ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT
+ ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT(x, y);
+#endif
+ }
+ else if (x == ERTS_RBT_GET_LEFT(p))
+ ERTS_RBT_SET_LEFT(p, y);
+ else {
+ ERTS_RBT_ASSERT(x == ERTS_RBT_GET_RIGHT(p));
+ ERTS_RBT_SET_RIGHT(p, y);
+ }
+ l = ERTS_RBT_GET_LEFT(x);
+ if (l) {
+ ERTS_RBT_ASSERT(ERTS_RBT_GET_PARENT(l) == x);
+ ERTS_RBT_SET_PARENT(l, y);
+ }
+ r = ERTS_RBT_GET_RIGHT(x);
+ if (r) {
+ ERTS_RBT_ASSERT(ERTS_RBT_GET_PARENT(r) == x);
+ ERTS_RBT_SET_PARENT(r, y);
+ }
+
+ f = ERTS_RBT_GET_FLAGS(x);
+ ERTS_RBT_SET_FLAGS(y, f);
+ ERTS_RBT_SET_PARENT(y, p);
+ ERTS_RBT_SET_RIGHT(y, r);
+ ERTS_RBT_SET_LEFT(y, l);
+}
+
+#endif /* ERTS_RBT_NEED_REPLACE__ */
+
+#ifdef ERTS_RBT_WANT_REPLACE
+
+static ERTS_RBT_API_INLINE__ void
+ERTS_RBT_FUNC__(replace)(ERTS_RBT_T **root, ERTS_RBT_T *x, ERTS_RBT_T *y)
+{
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_EQ(ERTS_RBT_GET_KEY(x),
+ ERTS_RBT_GET_KEY(y)));
+
+ ERTS_RBT_FUNC__(replace__)(root, x, y);
+}
+
+#endif /* ERTS_RBT_WANT_REPLACE */
+
+#ifdef ERTS_RBT_WANT_DELETE
+
+/*
+ * Delete a node.
+ */
+static ERTS_RBT_API_INLINE__ void
+ERTS_RBT_FUNC__(delete)(ERTS_RBT_T **root, ERTS_RBT_T *n)
+{
+ int spliced_is_black;
+ ERTS_RBT_T *p, *x, *y, *z = n;
+ ERTS_RBT_T null_x; /* null_x is used to get the fixup started when we
+ splice out a node without children. */
+
+ ERTS_RBT_HDBG_CHECK_TREE__(*root);
+
+ ERTS_RBT_INIT_EMPTY_TNODE(&null_x);
+
+ /* Remove node from tree... */
+
+ /* Find node to splice out */
+ if (!ERTS_RBT_GET_LEFT(z) || !ERTS_RBT_GET_RIGHT(z))
+ y = z;
+ else {
+ /* Set y to z:s successor */
+ y = ERTS_RBT_GET_RIGHT(z);
+ while (1) {
+ ERTS_RBT_T *t = ERTS_RBT_GET_LEFT(y);
+ if (!t)
+ break;
+ y = t;
+ }
+ }
+ /* splice out y */
+ x = ERTS_RBT_GET_LEFT(y);
+ if (!x)
+ x = ERTS_RBT_GET_RIGHT(y);
+ spliced_is_black = ERTS_RBT_IS_BLACK(y);
+ p = ERTS_RBT_GET_PARENT(y);
+ if (x)
+ ERTS_RBT_SET_PARENT(x, p);
+ else if (spliced_is_black) {
+ x = &null_x;
+ ERTS_RBT_SET_BLACK(x);
+ ERTS_RBT_SET_PARENT(x, p);
+ ERTS_RBT_SET_LEFT(y, x);
+ }
+
+ if (!p) {
+ ERTS_RBT_ASSERT(*root == y);
+ *root = x;
+#ifdef ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT
+ ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT(y, x);
+#endif
+ }
+ else {
+ if (y == ERTS_RBT_GET_LEFT(p))
+ ERTS_RBT_SET_LEFT(p, x);
+ else {
+ ERTS_RBT_ASSERT(y == ERTS_RBT_GET_RIGHT(p));
+ ERTS_RBT_SET_RIGHT(p, x);
+ }
+#ifdef ERTS_RBT_UPDATE_ATTACHED_DATA_DMOD
+ if (p != z)
+ ERTS_RBT_UPDATE_ATTACHED_DATA_DMOD(p, y == z ? NULL : z);
+#endif
+ }
+ if (y != z) {
+ /* We spliced out the successor of z; replace z by the successor */
+ ERTS_RBT_FUNC__(replace__)(root, z, y);
+#ifdef ERTS_RBT_UPDATE_ATTACHED_DATA_DMOD
+ ERTS_RBT_UPDATE_ATTACHED_DATA_DMOD(y, NULL);
+#endif
+ }
+
+ if (spliced_is_black) {
+ /* We removed a black node which makes the resulting tree
+ violate the Red-Black Tree properties. Fixup tree... */
+
+ p = ERTS_RBT_GET_PARENT(x);
+ while (ERTS_RBT_IS_BLACK(x) && p) {
+ ERTS_RBT_T *r, *l;
+
+ /*
+ * x has an "extra black" which we move up the tree
+ * until we reach the root or until we can get rid of it.
+ *
+ * y is the sibbling of x, and p is their parent
+ */
+
+ if (x == ERTS_RBT_GET_LEFT(p)) {
+ y = ERTS_RBT_GET_RIGHT(p);
+
+ ERTS_RBT_ASSERT(y);
+
+ if (ERTS_RBT_IS_RED(y)) {
+ ERTS_RBT_ASSERT(ERTS_RBT_GET_RIGHT(y));
+ ERTS_RBT_ASSERT(ERTS_RBT_GET_LEFT(y));
+
+ ERTS_RBT_SET_BLACK(y);
+
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_BLACK(p));
+
+ ERTS_RBT_SET_RED(p);
+ ERTS_RBT_FUNC__(left_rotate__)(root, p);
+ p = ERTS_RBT_GET_PARENT(x);
+ y = ERTS_RBT_GET_RIGHT(p);
+ }
+
+ ERTS_RBT_ASSERT(y);
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_BLACK(y));
+
+ l = ERTS_RBT_GET_LEFT(y);
+ r = ERTS_RBT_GET_RIGHT(y);
+ if ((!l || ERTS_RBT_IS_BLACK(l))
+ && (!r || ERTS_RBT_IS_BLACK(r))) {
+ ERTS_RBT_SET_RED(y);
+ x = p;
+ p = ERTS_RBT_GET_PARENT(x);
+ }
+ else {
+ if (!r || ERTS_RBT_IS_BLACK(r)) {
+ ERTS_RBT_SET_BLACK(l);
+ ERTS_RBT_SET_RED(y);
+ ERTS_RBT_FUNC__(right_rotate__)(root, y);
+ p = ERTS_RBT_GET_PARENT(x);
+ y = ERTS_RBT_GET_RIGHT(p);
+ }
+
+ ERTS_RBT_ASSERT(y);
+
+ if (p && ERTS_RBT_IS_RED(p)) {
+
+ ERTS_RBT_SET_BLACK(p);
+ ERTS_RBT_SET_RED(y);
+ }
+
+ ERTS_RBT_ASSERT(ERTS_RBT_GET_RIGHT(y));
+
+ ERTS_RBT_SET_BLACK(ERTS_RBT_GET_RIGHT(y));
+ ERTS_RBT_FUNC__(left_rotate__)(root, p);
+ x = *root;
+ break;
+ }
+ }
+ else {
+ ERTS_RBT_ASSERT(x == ERTS_RBT_GET_RIGHT(p));
+
+ y = ERTS_RBT_GET_LEFT(p);
+
+ ERTS_RBT_ASSERT(y);
+
+ if (ERTS_RBT_IS_RED(y)) {
+ ERTS_RBT_ASSERT(ERTS_RBT_GET_RIGHT(y));
+ ERTS_RBT_ASSERT(ERTS_RBT_GET_LEFT(y));
+
+ ERTS_RBT_SET_BLACK(y);
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_BLACK(p));
+ ERTS_RBT_SET_RED(p);
+ ERTS_RBT_FUNC__(right_rotate__)(root, p);
+
+ p = ERTS_RBT_GET_PARENT(x);
+ y = ERTS_RBT_GET_LEFT(p);
+ }
+
+ ERTS_RBT_ASSERT(y);
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_BLACK(y));
+
+ l = ERTS_RBT_GET_LEFT(y);
+ r = ERTS_RBT_GET_RIGHT(y);
+
+ if ((!r || ERTS_RBT_IS_BLACK(r))
+ && (!l || ERTS_RBT_IS_BLACK(l))) {
+ ERTS_RBT_SET_RED(y);
+ x = p;
+ p = ERTS_RBT_GET_PARENT(x);
+ }
+ else {
+ if (!l || ERTS_RBT_IS_BLACK(l)) {
+ ERTS_RBT_SET_BLACK(r);
+ ERTS_RBT_SET_RED(y);
+ ERTS_RBT_FUNC__(left_rotate__)(root, y);
+
+ p = ERTS_RBT_GET_PARENT(x);
+ y = ERTS_RBT_GET_LEFT(p);
+ }
+
+ ERTS_RBT_ASSERT(y);
+
+ if (p && ERTS_RBT_IS_RED(p)) {
+ ERTS_RBT_SET_BLACK(p);
+ ERTS_RBT_SET_RED(y);
+ }
+
+ ERTS_RBT_ASSERT(ERTS_RBT_GET_LEFT(y));
+
+ ERTS_RBT_SET_BLACK(ERTS_RBT_GET_LEFT(y));
+ ERTS_RBT_FUNC__(right_rotate__)(root, p);
+ x = *root;
+ break;
+ }
+ }
+ }
+
+ ERTS_RBT_SET_BLACK(x);
+
+ x = &null_x;
+ p = ERTS_RBT_GET_PARENT(x);
+
+ if (p) {
+ if (ERTS_RBT_GET_LEFT(p) == x)
+ ERTS_RBT_SET_LEFT(p, NULL);
+ else {
+ ERTS_RBT_ASSERT(ERTS_RBT_GET_RIGHT(p) == x);
+ ERTS_RBT_SET_RIGHT(p, NULL);
+ }
+
+ ERTS_RBT_ASSERT(!ERTS_RBT_GET_LEFT(x));
+ ERTS_RBT_ASSERT(!ERTS_RBT_GET_RIGHT(x));
+ }
+ else if (*root == x) {
+ *root = NULL;
+
+#ifdef ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT
+ ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT(x, NULL);
+#endif
+
+ ERTS_RBT_ASSERT(!ERTS_RBT_GET_LEFT(x));
+ ERTS_RBT_ASSERT(!ERTS_RBT_GET_RIGHT(x));
+ }
+ }
+
+ ERTS_RBT_HDBG_CHECK_TREE__(*root);
+
+}
+
+#endif /* ERTS_RBT_WANT_DELETE */
+
+#ifdef ERTS_RBT_NEED_INSERT__
+
+static void
+ERTS_RBT_FUNC__(insert_fixup__)(ERTS_RBT_T **root, ERTS_RBT_T *n)
+{
+ ERTS_RBT_T *x, *y;
+
+ x = n;
+
+ /*
+ * Rearrange the tree so that it satisfies the Red-Black Tree properties
+ */
+
+ ERTS_RBT_ASSERT(x != *root && ERTS_RBT_IS_RED(ERTS_RBT_GET_PARENT(x)));
+ do {
+ ERTS_RBT_T *p, *pp;
+
+ /*
+ * x and its parent are both red. Move the red pair up the tree
+ * until we get to the root or until we can separate them.
+ */
+
+ p = ERTS_RBT_GET_PARENT(x);
+ pp = ERTS_RBT_GET_PARENT(p);
+
+ ERTS_RBT_ASSERT(p && pp);
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_RED(x));
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_BLACK(pp));
+
+ if (p == ERTS_RBT_GET_LEFT(pp)) {
+ y = ERTS_RBT_GET_RIGHT(pp);
+ if (y && ERTS_RBT_IS_RED(y)) {
+ ERTS_RBT_SET_BLACK(y);
+ ERTS_RBT_SET_BLACK(p);
+ ERTS_RBT_SET_RED(pp);
+ x = pp;
+ }
+ else {
+
+ if (x == ERTS_RBT_GET_RIGHT(p)) {
+ x = p;
+ ERTS_RBT_FUNC__(left_rotate__)(root, x);
+ p = ERTS_RBT_GET_PARENT(x);
+ pp = ERTS_RBT_GET_PARENT(p);
+
+ ERTS_RBT_ASSERT(p && pp);
+ }
+
+ ERTS_RBT_ASSERT(x == ERTS_RBT_GET_LEFT(ERTS_RBT_GET_LEFT(pp)));
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_RED(x));
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_RED(p));
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_BLACK(pp));
+ ERTS_RBT_ASSERT(!y || ERTS_RBT_IS_BLACK(y));
+
+
+ ERTS_RBT_SET_BLACK(p);
+ ERTS_RBT_SET_RED(pp);
+ ERTS_RBT_FUNC__(right_rotate__)(root, pp);
+
+
+ ERTS_RBT_ASSERT(ERTS_RBT_GET_LEFT(ERTS_RBT_GET_PARENT(x)) == x);
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_RED(x));
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_RED(
+ ERTS_RBT_GET_RIGHT(
+ ERTS_RBT_GET_PARENT(x))));
+ ERTS_RBT_ASSERT(!ERTS_RBT_GET_PARENT(x)
+ || ERTS_RBT_IS_BLACK(ERTS_RBT_GET_PARENT(x)));
+ break;
+ }
+ }
+ else {
+ ERTS_RBT_ASSERT(p == ERTS_RBT_GET_RIGHT(pp));
+
+ y = ERTS_RBT_GET_LEFT(pp);
+ if (y && ERTS_RBT_IS_RED(y)) {
+ ERTS_RBT_SET_BLACK(y);
+ ERTS_RBT_SET_BLACK(p);
+ ERTS_RBT_SET_RED(pp);
+ x = pp;
+ }
+ else {
+
+ if (x == ERTS_RBT_GET_LEFT(p)) {
+ x = p;
+ ERTS_RBT_FUNC__(right_rotate__)(root, x);
+ p = ERTS_RBT_GET_PARENT(x);
+ pp = ERTS_RBT_GET_PARENT(p);
+
+ ERTS_RBT_ASSERT(p && pp);
+ }
+
+ ERTS_RBT_ASSERT(x == ERTS_RBT_GET_RIGHT(ERTS_RBT_GET_RIGHT(pp)));
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_RED(x));
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_RED(p));
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_BLACK(pp));
+ ERTS_RBT_ASSERT(!y || ERTS_RBT_IS_BLACK(y));
+
+
+ ERTS_RBT_SET_BLACK(p);
+ ERTS_RBT_SET_RED(pp);
+ ERTS_RBT_FUNC__(left_rotate__)(root, pp);
+
+
+ ERTS_RBT_ASSERT(ERTS_RBT_GET_RIGHT(ERTS_RBT_GET_PARENT(x)) == x);
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_RED(x));
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_RED(
+ ERTS_RBT_GET_LEFT(
+ ERTS_RBT_GET_PARENT(x))));
+ ERTS_RBT_ASSERT(!ERTS_RBT_GET_PARENT(x)
+ || ERTS_RBT_IS_BLACK(ERTS_RBT_GET_PARENT(x)));
+ break;
+ }
+ }
+ } while (x != *root && ERTS_RBT_IS_RED(ERTS_RBT_GET_PARENT(x)));
+
+ ERTS_RBT_SET_BLACK(*root);
+
+}
+
+static ERTS_INLINE ERTS_RBT_T *
+ERTS_RBT_FUNC__(insert_aux__)(ERTS_RBT_T **root, ERTS_RBT_T *n, int lookup)
+{
+ ERTS_RBT_KEY_T kn = ERTS_RBT_GET_KEY(n);
+
+ ERTS_RBT_HDBG_CHECK_TREE__(*root);
+
+ ERTS_RBT_INIT_EMPTY_TNODE(n);
+
+ if (!*root) {
+ ERTS_RBT_SET_BLACK(n);
+ *root = n;
+#ifdef ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT
+ ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT(NULL, n);
+#endif
+ }
+ else {
+ ERTS_RBT_T *p, *x = *root;
+
+ while (1) {
+ ERTS_RBT_KEY_T kx;
+ ERTS_RBT_T *c;
+
+ kx = ERTS_RBT_GET_KEY(x);
+
+ if (lookup && ERTS_RBT_IS_EQ(kn, kx)) {
+
+ ERTS_RBT_HDBG_CHECK_TREE__(*root);
+
+ return x;
+ }
+
+ if (ERTS_RBT_IS_LT(kn, kx)) {
+ c = ERTS_RBT_GET_LEFT(x);
+ if (!c) {
+ ERTS_RBT_SET_PARENT(n, x);
+ ERTS_RBT_SET_LEFT(x, n);
+ p = x;
+ break;
+ }
+ }
+ else {
+ c = ERTS_RBT_GET_RIGHT(x);
+ if (!c) {
+ ERTS_RBT_SET_PARENT(n, x);
+ ERTS_RBT_SET_RIGHT(x, n);
+ p = x;
+ break;
+ }
+ }
+
+ x = c;
+ }
+
+ ERTS_RBT_ASSERT(p);
+
+ ERTS_RBT_SET_RED(n);
+ if (ERTS_RBT_IS_RED(p))
+ ERTS_RBT_FUNC__(insert_fixup__)(root, n);
+ }
+
+ ERTS_RBT_HDBG_CHECK_TREE__(*root);
+
+ return NULL;
+}
+
+#endif /* ERTS_RBT_NEED_INSERT__ */
+
+#ifdef ERTS_RBT_WANT_LOOKUP_INSERT
+
+static ERTS_RBT_API_INLINE__ ERTS_RBT_T *
+ERTS_RBT_FUNC__(lookup_insert)(ERTS_RBT_T **root, ERTS_RBT_T *n)
+{
+ return ERTS_RBT_FUNC__(insert_aux__)(root, n, !0);
+}
+
+#endif /* ERTS_RBT_WANT_LOOKUP_INSERT */
+
+#ifdef ERTS_RBT_WANT_INSERT
+
+static ERTS_RBT_API_INLINE__ void
+ERTS_RBT_FUNC__(insert)(ERTS_RBT_T **root, ERTS_RBT_T *n)
+{
+ (void) ERTS_RBT_FUNC__(insert_aux__)(root, n, 0);
+}
+
+#endif /* ERTS_RBT_WANT_INSERT */
+
+#ifdef ERTS_RBT_WANT_LOOKUP
+
+static ERTS_RBT_API_INLINE__ ERTS_RBT_T *
+ERTS_RBT_FUNC__(lookup)(ERTS_RBT_T *root, ERTS_RBT_KEY_T key)
+{
+ ERTS_RBT_T *x = root;
+
+ if (!x)
+ return NULL;
+
+ while (1) {
+ ERTS_RBT_KEY_T kx = ERTS_RBT_GET_KEY(x);
+ ERTS_RBT_T *c;
+
+ if (ERTS_RBT_IS_EQ(key, kx))
+ return x;
+
+ if (ERTS_RBT_IS_LT(key, kx)) {
+ c = ERTS_RBT_GET_LEFT(x);
+ if (!c)
+ return NULL;
+ }
+ else {
+ c = ERTS_RBT_GET_RIGHT(x);
+ if (!c)
+ return NULL;
+ }
+
+ x = c;
+ }
+}
+
+#endif /* ERTS_RBT_WANT_LOOKUP */
+
+#ifdef ERTS_RBT_WANT_SMALLEST
+
+static ERTS_RBT_API_INLINE__ ERTS_RBT_T *
+ERTS_RBT_FUNC__(smallest)(ERTS_RBT_T *root)
+{
+ ERTS_RBT_T *x = root;
+
+ if (!x)
+ return NULL;
+
+ while (1) {
+ ERTS_RBT_T *c = ERTS_RBT_GET_LEFT(x);
+ if (!c)
+ break;
+ x = c;
+ }
+
+ return x;
+}
+
+#endif /* ERTS_RBT_WANT_SMALLEST */
+
+#ifdef ERTS_RBT_WANT_LARGEST
+
+static ERTS_RBT_API_INLINE__ ERTS_RBT_T *
+ERTS_RBT_FUNC__(largest)(ERTS_RBT_T *root)
+{
+ ERTS_RBT_T *x = root;
+
+ if (!x)
+ return NULL;
+
+ while (1) {
+ ERTS_RBT_T *c = ERTS_RBT_GET_RIGHT(x);
+ if (!c)
+ break;
+ x = c;
+ }
+
+ return x;
+}
+
+#endif /* ERTS_RBT_WANT_LARGEST */
+
+#ifdef ERTS_RBT_NEED_FOREACH_UNORDERED__
+
+static ERTS_INLINE int
+ERTS_RBT_FUNC__(foreach_unordered__)(ERTS_RBT_T **root,
+ int destroying,
+ void (*op)(ERTS_RBT_T *, void *),
+ void *arg,
+ int yielding,
+ ERTS_RBT_YIELD_STATE_T__ *ystate,
+ Sint ylimit)
+{
+ ERTS_RBT_T *c, *p, *x;
+
+ ERTS_RBT_ASSERT(!yielding || ystate);
+
+ if (yielding && ystate->x) {
+ x = ystate->x;
+ ERTS_RBT_ASSERT(ystate->up);
+ goto restart_up;
+ }
+ else {
+ x = *root;
+ if (!x)
+ return 0;
+ if (destroying)
+ *root = NULL;
+ }
+
+ while (1) {
+
+ while (1) {
+
+ while (1) {
+ c = ERTS_RBT_GET_LEFT(x);
+ if (!c)
+ break;
+ x = c;
+ }
+
+ c = ERTS_RBT_GET_RIGHT(x);
+ if (!c)
+ break;
+ x = c;
+ }
+
+ while (1) {
+#ifdef ERTS_RBT_DEBUG
+ int cdir;
+#endif
+ if (yielding && ylimit-- <= 0) {
+ ystate->x = x;
+ ystate->up = 1;
+ return 1;
+ }
+
+ restart_up:
+
+ p = ERTS_RBT_GET_PARENT(x);
+
+#ifdef ERTS_RBT_DEBUG
+ ERTS_RBT_ASSERT(!destroying || !ERTS_RBT_GET_LEFT(x));
+ ERTS_RBT_ASSERT(!destroying || !ERTS_RBT_GET_RIGHT(x));
+
+ if (p) {
+ if (x == ERTS_RBT_GET_LEFT(p)) {
+ cdir = -1;
+ if (destroying)
+ ERTS_RBT_SET_LEFT(p, NULL);
+ }
+ else {
+ ERTS_RBT_ASSERT(x == ERTS_RBT_GET_RIGHT(p));
+ cdir = 1;
+ if (destroying)
+ ERTS_RBT_SET_RIGHT(p, NULL);
+ }
+ }
+#endif
+
+ (*op)(x, arg);
+
+ if (!p) {
+ if (yielding) {
+ ystate->x = NULL;
+ ystate->up = 0;
+ }
+ return 0; /* Done */
+ }
+
+ c = ERTS_RBT_GET_RIGHT(p);
+ if (c && c != x) {
+ ERTS_RBT_ASSERT(cdir < 0);
+
+ /* Go down tree of x's sibling... */
+ x = c;
+ break;
+ }
+
+ x = p;
+ }
+ }
+}
+
+#endif /* ERTS_RBT_NEED_FOREACH_UNORDERED__ */
+
+#ifdef ERTS_RBT_NEED_FOREACH_ORDERED__
+
+static ERTS_INLINE int
+ERTS_RBT_FUNC__(foreach_ordered__)(ERTS_RBT_T **root,
+ int from_small,
+ int destroying,
+ void (*op)(ERTS_RBT_T *, void *),
+ void (*destroy)(ERTS_RBT_T *, void *),
+ void *arg,
+ int yielding,
+ ERTS_RBT_YIELD_STATE_T__ *ystate,
+ Sint ylimit)
+{
+ ERTS_RBT_T *c, *p, *x;
+
+ ERTS_RBT_ASSERT(!yielding || ystate);
+ ERTS_RBT_ASSERT(!destroying || destroy);
+
+ if (yielding && ystate->x) {
+ x = ystate->x;
+ if (ystate->up)
+ goto restart_up;
+ else
+ goto restart_down;
+ }
+ else {
+ x = *root;
+ if (!x)
+ return 0;
+ if (destroying)
+ *root = NULL;
+ }
+
+ while (1) {
+
+ while (1) {
+
+ while (1) {
+ c = from_small ? ERTS_RBT_GET_LEFT(x) : ERTS_RBT_GET_RIGHT(x);
+ if (!c)
+ break;
+ x = c;
+ }
+
+ (*op)(x, arg);
+
+ if (yielding && --ylimit <= 0) {
+ ystate->x = x;
+ ystate->up = 0;
+ return 1;
+ }
+
+ restart_down:
+
+ c = from_small ? ERTS_RBT_GET_RIGHT(x) : ERTS_RBT_GET_LEFT(x);
+ if (!c)
+ break;
+ x = c;
+ }
+
+ while (1) {
+ p = ERTS_RBT_GET_PARENT(x);
+
+ if (p) {
+
+ c = from_small ? ERTS_RBT_GET_RIGHT(p) : ERTS_RBT_GET_LEFT(p);
+ if (!c || c != x) {
+ ERTS_RBT_ASSERT((from_small
+ ? ERTS_RBT_GET_LEFT(p)
+ : ERTS_RBT_GET_RIGHT(p)) == x);
+
+ (*op)(p, arg);
+
+ if (yielding && --ylimit <= 0) {
+ ystate->x = x;
+ ystate->up = 1;
+ return 1;
+ restart_up:
+ p = ERTS_RBT_GET_PARENT(x);
+ }
+ }
+
+ if (c && c != x) {
+ ERTS_RBT_ASSERT((from_small
+ ? ERTS_RBT_GET_LEFT(p)
+ : ERTS_RBT_GET_RIGHT(p)) == x);
+
+ /* Go down tree of x's sibling... */
+ x = c;
+ break;
+ }
+ }
+
+ if (destroying) {
+
+#ifdef ERTS_RBT_DEBUG
+ ERTS_RBT_ASSERT(!ERTS_RBT_GET_LEFT(x)
+ && !ERTS_RBT_GET_RIGHT(x));
+
+ if (p) {
+ if (x == ERTS_RBT_GET_LEFT(p))
+ ERTS_RBT_SET_LEFT(p, NULL);
+ else {
+ ERTS_RBT_ASSERT(x == ERTS_RBT_GET_RIGHT(p));
+ ERTS_RBT_SET_RIGHT(p, NULL);
+ }
+ }
+#endif
+
+ (*destroy)(x, arg);
+ }
+
+ if (!p) {
+ if (yielding) {
+ ystate->x = NULL;
+ ystate->up = 0;
+ }
+ return 1; /* Done */
+ }
+ x = p;
+ }
+ }
+}
+
+#endif /* ERTS_RBT_NEED_FOREACH_ORDERED__ */
+
+#ifdef ERTS_RBT_WANT_FOREACH
+
+static ERTS_RBT_API_INLINE__ void
+ERTS_RBT_FUNC__(foreach)(ERTS_RBT_T *root,
+ void (*op)(ERTS_RBT_T *, void *),
+ void *arg)
+{
+ (void) ERTS_RBT_FUNC__(foreach_unordered__)(&root, 0, op, arg,
+ 0, NULL, 0);
+}
+
+#endif /* ERTS_RBT_WANT_FOREACH */
+
+#ifdef ERTS_RBT_WANT_FOREACH_SMALL
+
+static ERTS_RBT_API_INLINE__ void
+ERTS_RBT_FUNC__(foreach_small)(ERTS_RBT_T *root,
+ void (*op)(ERTS_RBT_T *, void *),
+ void *arg)
+{
+ (void) ERTS_RBT_FUNC__(foreach_ordered__)(&root, 1, 0,
+ op, NULL, arg,
+ 0, NULL, 0);
+}
+
+#endif /* ERTS_RBT_WANT_FOREACH_SMALL */
+
+#ifdef ERTS_RBT_WANT_FOREACH_LARGE
+
+static ERTS_RBT_API_INLINE__ void
+ERTS_RBT_FUNC__(foreach_large)(ERTS_RBT_T *root,
+ void (*op)(ERTS_RBT_T *, void *),
+ void *arg)
+{
+ (void) ERTS_RBT_FUNC__(foreach_ordered__)(&root, 0, 0,
+ op, NULL, arg,
+ 0, NULL, 0);
+}
+
+#endif /* ERTS_RBT_WANT_FOREACH_LARGE */
+
+#ifdef ERTS_RBT_WANT_FOREACH_YIELDING
+
+static ERTS_RBT_API_INLINE__ void
+ERTS_RBT_FUNC__(foreach_yielding)(ERTS_RBT_T *root,
+ void (*op)(ERTS_RBT_T *, void *),
+ void *arg,
+ ERTS_RBT_YIELD_STATE_T__ *ystate,
+ Sint ylimit)
+{
+ (void) ERTS_RBT_FUNC__(foreach_unordered__)(*root, 0, op, arg,
+ 1, ystate, ylimit);
+}
+
+#endif /* ERTS_RBT_WANT_FOREACH_YIELDING */
+
+#ifdef ERTS_RBT_WANT_FOREACH_SMALL_YIELDING
+
+static ERTS_RBT_API_INLINE__ int
+ERTS_RBT_FUNC__(foreach_small_yielding)(ERTS_RBT_T *root,
+ void (*op)(ERTS_RBT_T *, void *),
+ void *arg,
+ ERTS_RBT_YIELD_STATE_T__ *ystate,
+ Sint ylimit)
+{
+ return ERTS_RBT_FUNC__(foreach_ordered__)(&root, 1, 0,
+ op, NULL, arg,
+ 1, ystate, ylimit);
+}
+
+#endif /* ERTS_RBT_WANT_FOREACH_SMALL_YIELDING */
+
+#ifdef ERTS_RBT_WANT_FOREACH_LARGE_YIELDING
+
+static ERTS_RBT_API_INLINE__ int
+ERTS_RBT_FUNC__(foreach_large_yielding)(ERTS_RBT_T *root,
+ void (*op)(ERTS_RBT_T *, void *),
+ void *arg,
+ ERTS_RBT_YIELD_STATE_T__ *ystate,
+ Sint ylimit)
+{
+ return ERTS_RBT_FUNC__(foreach_ordered__)(&root, 0, 0,
+ op, NULL, arg,
+ 1, ystate, ylimit);
+}
+
+#endif /* ERTS_RBT_WANT_FOREACH_LARGE_YIELDING */
+
+#ifdef ERTS_RBT_WANT_FOREACH_DESTROY
+
+static ERTS_RBT_API_INLINE__ void
+ERTS_RBT_FUNC__(foreach_destroy)(ERTS_RBT_T **root,
+ void (*op)(ERTS_RBT_T *, void *),
+ void *arg)
+{
+ (void) ERTS_RBT_FUNC__(foreach_unordered__)(root, 1, op, arg,
+ 0, NULL, 0);
+}
+
+#endif /* ERTS_RBT_WANT_FOREACH_DESTROY */
+
+#ifdef ERTS_RBT_WANT_FOREACH_SMALL_DESTROY
+
+static ERTS_RBT_API_INLINE__ void
+ERTS_RBT_FUNC__(foreach_small_destroy)(ERTS_RBT_T **root,
+ void (*op)(ERTS_RBT_T *, void *),
+ void (*destr)(ERTS_RBT_T *, void *),
+ void *arg)
+{
+ (void) ERTS_RBT_FUNC__(foreach_ordered__)(root, 1, 1,
+ op, destr, arg,
+ 0, NULL, 0);
+}
+
+#endif /* ERTS_RBT_WANT_FOREACH_SMALL_DESTROY */
+
+#ifdef ERTS_RBT_WANT_FOREACH_LARGE_DESTROY
+
+static ERTS_RBT_API_INLINE__ void
+ERTS_RBT_FUNC__(foreach_large_destroy)(ERTS_RBT_T **root,
+ void (*op)(ERTS_RBT_T *, void *),
+ void (*destr)(ERTS_RBT_T *, void *),
+ void *arg)
+{
+ (void) ERTS_RBT_FUNC__(foreach_ordered__)(root, 0, 1,
+ op, destr, arg,
+ 0, NULL, 0);
+}
+
+#endif /* ERTS_RBT_WANT_FOREACH_LARGE_DESTROY */
+
+#ifdef ERTS_RBT_WANT_FOREACH_DESTROY_YIELDING
+
+static ERTS_RBT_API_INLINE__ int
+ERTS_RBT_FUNC__(foreach_destroy_yielding)(ERTS_RBT_T **root,
+ void (*op)(ERTS_RBT_T *, void *),
+ void *arg,
+ ERTS_RBT_YIELD_STATE_T__ *ystate,
+ Sint ylimit)
+{
+ return ERTS_RBT_FUNC__(foreach_unordered__)(root, 1, op, arg,
+ 1, ystate, ylimit);
+}
+
+#endif /* ERTS_RBT_WANT_FOREACH_DESTROY_YIELDING */
+
+#ifdef ERTS_RBT_WANT_FOREACH_SMALL_DESTROY_YIELDING
+
+static ERTS_RBT_API_INLINE__ int
+ERTS_RBT_FUNC__(foreach_small_destroy_yielding)(ERTS_RBT_T **root,
+ void (*op)(ERTS_RBT_T *, void *),
+ void (*destr)(ERTS_RBT_T *, void *),
+ void *arg,
+ ERTS_RBT_YIELD_STATE_T__ *ystate,
+ Sint ylimit)
+{
+ return ERTS_RBT_FUNC__(foreach_ordered__)(root, 1, 1,
+ op, destr, arg,
+ 1, ystate, ylimit);
+}
+
+#endif /* ERTS_RBT_WANT_FOREACH_SMALL_DESTROY_YIELDING */
+
+#ifdef ERTS_RBT_WANT_FOREACH_LARGE_DESTROY_YIELDING
+
+static ERTS_RBT_API_INLINE__ int
+ERTS_RBT_FUNC__(foreach_large_destroy_yielding)(ERTS_RBT_T **root,
+ void (*op)(ERTS_RBT_T *, void *),
+ void (*destr)(ERTS_RBT_T *, void *),
+ void *arg,
+ ERTS_RBT_YIELD_STATE_T__ *ystate,
+ Sint ylimit)
+{
+ return ERTS_RBT_FUNC__(foreach_ordered__)(root, 0, 1,
+ op, destr, arg,
+ 1, ystate, ylimit);
+}
+
+#endif /* ERTS_RBT_WANT_FOREACH_LARGE_DESTROY_YIELDING */
+
+#ifdef ERTS_RBT_WANT_DEBUG_PRINT
+
+static void
+ERTS_RBT_FUNC__(debug_print)(FILE *filep, ERTS_RBT_T *x, int indent,
+ void (*print_node)(ERTS_RBT_T *))
+{
+ if (x) {
+ ERTS_RBT_FUNC__(debug_print)(filep, ERTS_RBT_GET_RIGHT(x),
+ indent+2, print_node);
+ erts_fprintf(filep,
+ "%*s[%s:%p:",
+ indent, "",
+ ERTS_RBT_IS_BLACK(x) ? "Black" : "Red",
+ x);
+ (*print_node)(x);
+ erts_fprintf(filep, "]\n");
+ ERTS_RBT_FUNC__(debug_print)(filep, ERTS_RBT_GET_LEFT(x),
+ indent+2, print_node);
+ }
+}
+
+#endif /* ERTS_RBT_WANT_DEBUG_PRINT */
+
+#ifdef ERTS_RBT_NEED_HDBG_CHECK_TREE__
+
+static void
+ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root)
+{
+ int black_depth = -1, no_black = 0;
+ ERTS_RBT_T *c, *p, *x = root;
+ ERTS_RBT_KEY_T kx;
+ ERTS_RBT_KEY_T kc;
+
+ if (!x)
+ return;
+
+ ERTS_RBT_ASSERT(!ERTS_RBT_GET_PARENT(x));
+
+ while (1) {
+
+ while (1) {
+
+ while (1) {
+
+ if (ERTS_RBT_IS_BLACK(x))
+ no_black++;
+ else {
+ c = ERTS_RBT_GET_RIGHT(x);
+ ERTS_RBT_ASSERT(!c || ERTS_RBT_IS_BLACK(c));
+ c = ERTS_RBT_GET_LEFT(x);
+ ERTS_RBT_ASSERT(!c || ERTS_RBT_IS_BLACK(c));
+ }
+
+ c = ERTS_RBT_GET_LEFT(x);
+ if (!c)
+ break;
+
+ ERTS_RBT_ASSERT(x == ERTS_RBT_GET_PARENT(c));
+
+ kx = ERTS_RBT_GET_KEY(x);
+ kc = ERTS_RBT_GET_KEY(c);
+
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_LT(kc, kx)
+ || ERTS_RBT_IS_EQ(kc, kx));
+
+ x = c;
+ }
+
+ c = ERTS_RBT_GET_RIGHT(x);
+ if (!c) {
+ if (black_depth < 0)
+ black_depth = no_black;
+ ERTS_RBT_ASSERT(black_depth == no_black);
+ break;
+ }
+
+ ERTS_RBT_ASSERT(x == ERTS_RBT_GET_PARENT(c));
+
+ kx = ERTS_RBT_GET_KEY(x);
+ kc = ERTS_RBT_GET_KEY(c);
+
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_LT(kx, kc)
+ || ERTS_RBT_IS_EQ(kx, kc));
+ x = c;
+ }
+
+ while (1) {
+ p = ERTS_RBT_GET_PARENT(x);
+
+ if (ERTS_RBT_IS_BLACK(x))
+ no_black--;
+
+ if (p) {
+
+ ERTS_RBT_ASSERT(x == ERTS_RBT_GET_LEFT(p)
+ || x == ERTS_RBT_GET_RIGHT(p));
+
+ c = ERTS_RBT_GET_RIGHT(p);
+ if (c && c != x) {
+ ERTS_RBT_ASSERT(ERTS_RBT_GET_LEFT(p) == x);
+
+ kx = ERTS_RBT_GET_KEY(x);
+ kc = ERTS_RBT_GET_KEY(c);
+
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_LT(kx, kc)
+ || ERTS_RBT_IS_EQ(kx, kc));
+ /* Go down tree of x's sibling... */
+ x = c;
+ break;
+ }
+ }
+
+ if (!p) {
+ ERTS_RBT_ASSERT(root == x);
+ ERTS_RBT_ASSERT(no_black == 0);
+ return; /* Done */
+ }
+
+ x = p;
+ }
+ }
+}
+
+#undef ERTS_RBT_PRINT_TREE__
+
+#endif /* ERTS_RBT_NEED_HDBG_CHECK_TREE__ */
+
+#undef ERTS_RBT_ASSERT
+#undef ERTS_RBT_DEBUG
+#undef ERTS_RBT_API_INLINE__
+#undef ERTS_RBT_YIELD_STATE_T__
+#undef ERTS_RBT_NEED_REPLACE__
+#undef ERTS_RBT_NEED_INSERT__
+#undef ERTS_RBT_NEED_ROTATE__
+#undef ERTS_RBT_NEED_FOREACH_UNORDERED__
+#undef ERTS_RBT_NEED_FOREACH_ORDERED__
+#undef ERTS_RBT_NEED_HDBG_CHECK_TREE__
+#undef ERTS_RBT_HDBG_CHECK_TREE__
+
+#ifdef ERTS_RBT_UNDEF
+# undef ERTS_RBT_PREFIX
+# undef ERTS_RBT_T
+# undef ERTS_RBT_KEY_T
+# undef ERTS_RBT_FLAGS_T
+# undef ERTS_RBT_INIT_EMPTY_TNODE
+# undef ERTS_RBT_IS_RED
+# undef ERTS_RBT_SET_RED
+# undef ERTS_RBT_IS_BLACK
+# undef ERTS_RBT_SET_BLACK
+# undef ERTS_RBT_GET_FLAGS
+# undef ERTS_RBT_SET_FLAGS
+# undef ERTS_RBT_GET_PARENT
+# undef ERTS_RBT_SET_PARENT
+# undef ERTS_RBT_GET_RIGHT
+# undef ERTS_RBT_SET_RIGHT
+# undef ERTS_RBT_GET_LEFT
+# undef ERTS_RBT_SET_LEFT
+# undef ERTS_RBT_GET_KEY
+# undef ERTS_RBT_IS_LT
+# undef ERTS_RBT_IS_EQ
+# undef ERTS_RBT_UNDEF
+# undef ERTS_RBT_NO_API_INLINE
+# undef ERTS_RBT_UPDATE_ATTACHED_DATA_ROTATE
+# undef ERTS_RBT_UPDATE_ATTACHED_DATA_DMOD
+# undef ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT
+# undef ERTS_RBT_WANT_DELETE
+# undef ERTS_RBT_WANT_INSERT
+# undef ERTS_RBT_WANT_LOOKUP_INSERT
+# undef ERTS_RBT_WANT_REPLACE
+# undef ERTS_RBT_WANT_LOOKUP
+# undef ERTS_RBT_WANT_SMALLEST
+# undef ERTS_RBT_WANT_LARGEST
+# undef ERTS_RBT_WANT_FOREACH
+# undef ERTS_RBT_WANT_FOREACH_DESTROY
+# undef ERTS_RBT_WANT_FOREACH_YIELDING
+# undef ERTS_RBT_WANT_FOREACH_DESTROY_YIELDING
+# undef ERTS_RBT_WANT_FOREACH_SMALL
+# undef ERTS_RBT_WANT_FOREACH_LARGE
+# undef ERTS_RBT_WANT_FOREACH_SMALL_DESTROY
+# undef ERTS_RBT_WANT_FOREACH_LARGE_DESTROY
+# undef ERTS_RBT_WANT_FOREACH_SMALL_YIELDING
+# undef ERTS_RBT_WANT_FOREACH_LARGE_YIELDING
+# undef ERTS_RBT_WANT_FOREACH_SMALL_DESTROY_YIELDING
+# undef ERTS_RBT_WANT_FOREACH_LARGE_DESTROY_YIELDING
+# undef ERTS_RBT_WANT_DEBUG_PRINT
+#endif