aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_rbtree.h
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator/beam/erl_rbtree.h')
-rw-r--r--erts/emulator/beam/erl_rbtree.h181
1 files changed, 163 insertions, 18 deletions
diff --git a/erts/emulator/beam/erl_rbtree.h b/erts/emulator/beam/erl_rbtree.h
index e59d6900b0..e50abf5cec 100644
--- a/erts/emulator/beam/erl_rbtree.h
+++ b/erts/emulator/beam/erl_rbtree.h
@@ -1,7 +1,7 @@
/*
* %CopyrightBegin%
*
- * Copyright Ericsson AB 2015-2017. All Rights Reserved.
+ * Copyright Ericsson AB 2015-2018. All Rights Reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
@@ -50,8 +50,14 @@
* - 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?
+ * Either:
+ * - ERTS_RBT_CMP_KEYS(KX, KY) - Compare keys...
+ * or:
+ * - 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?
+ *
+ * If ERTS_RBT_CMP_KEYS is defined ERTS_RBT_IS_LT and
+ * ERTS_RBT_IS_EQ will be redefined using ERTS_RBT_CMP_KEYS
*
* Optional defines:
*
@@ -337,6 +343,15 @@
* Should only be used for debuging.
*/
+#ifdef ERTS_RBT_CMP_KEYS
+
+# undef ERTS_RBT_IS_LT
+# define ERTS_RBT_IS_LT(KX, KY) (ERTS_RBT_CMP_KEYS((KX), (KY)) < 0)
+
+# undef ERTS_RBT_IS_EQ
+# define ERTS_RBT_IS_EQ(KX, KY) (ERTS_RBT_CMP_KEYS((KX), (KY)) == 0)
+
+#endif
/*
* Check that we have all mandatory defines
@@ -396,6 +411,16 @@
# error Missing definition of ERTS_RBT_IS_EQ
#endif
+#undef ERTS_RBT_IS_GT__
+#ifdef ERTS_RBT_CMP_KEYS
+# define ERTS_RBT_IS_GT__(KX, KY) \
+ (ERTS_RBT_CMP_KEYS((KX), (KY)) > 0)
+#else
+# define ERTS_RBT_IS_GT__(KX, KY) \
+ (!ERTS_RBT_IS_LT((KX), (KY)) && !ERTS_RBT_IS_EQ((KX), (KY)))
+
+#endif
+
#if defined(ERTS_RBT_HARD_DEBUG) || defined(DEBUG)
# ifndef ERTS_RBT_DEBUG
# define ERTS_RBT_DEBUG 1
@@ -1007,19 +1032,30 @@ ERTS_RBT_FUNC__(insert_aux__)(ERTS_RBT_T **root, ERTS_RBT_T *n, int lookup)
ERTS_RBT_T *p, *x = *root;
while (1) {
- ERTS_RBT_KEY_T kx;
+ ERTS_RBT_KEY_T kx = ERTS_RBT_GET_KEY(x);
ERTS_RBT_T *c;
+ int kres;
+#ifdef ERTS_RBT_CMP_KEYS
+ int kcmp = ERTS_RBT_CMP_KEYS(kn, kx);
+ kres = kcmp == 0;
+#else
+ kres = ERTS_RBT_IS_EQ(kn, kx);
+#endif
- kx = ERTS_RBT_GET_KEY(x);
-
- if (lookup && ERTS_RBT_IS_EQ(kn, kx)) {
+ if (lookup && kres) {
ERTS_RBT_HDBG_CHECK_TREE__(*root, NULL);
return x;
}
- if (ERTS_RBT_IS_LT(kn, kx)) {
+#ifdef ERTS_RBT_CMP_KEYS
+ kres = kcmp < 0;
+#else
+ kres = ERTS_RBT_IS_LT(kn, kx);
+#endif
+
+ if (kres) {
c = ERTS_RBT_GET_LEFT(x);
if (!c) {
ERTS_RBT_SET_PARENT(n, x);
@@ -1075,6 +1111,101 @@ ERTS_RBT_FUNC__(insert)(ERTS_RBT_T **root, ERTS_RBT_T *n)
#endif /* ERTS_RBT_WANT_INSERT */
+#ifdef ERTS_RBT_WANT_LOOKUP_CREATE
+static ERTS_INLINE ERTS_RBT_T *
+ERTS_RBT_FUNC__(lookup_create)(ERTS_RBT_T **root,
+ ERTS_RBT_KEY_T kn,
+ ERTS_RBT_T *(*create)(ERTS_RBT_KEY_T, void *),
+ void *arg,
+ int *created)
+{
+ ERTS_RBT_T *n;
+ ERTS_RBT_HDBG_CHECK_TREE__(*root, NULL);
+
+ if (!*root) {
+ n = (*create)(kn, arg);
+ ERTS_RBT_INIT_EMPTY_TNODE(n);
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_EQ(ERTS_RBT_GET_KEY(n), kn));
+ ERTS_RBT_SET_BLACK(n);
+ *root = n;
+ *created = !0;
+#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_GET_KEY(x);
+ ERTS_RBT_T *c;
+ int kres;
+#ifdef ERTS_RBT_CMP_KEYS
+ int kcmp = ERTS_RBT_CMP_KEYS(kn, kx);
+ kres = kcmp == 0;
+#else
+ kres = ERTS_RBT_IS_EQ(kn, kx);
+#endif
+
+ if (kres) {
+
+ ERTS_RBT_HDBG_CHECK_TREE__(*root, NULL);
+
+ *created = 0;
+ return x;
+ }
+
+#ifdef ERTS_RBT_CMP_KEYS
+ kres = kcmp < 0;
+#else
+ kres = ERTS_RBT_IS_LT(kn, kx);
+#endif
+
+ if (kres) {
+ c = ERTS_RBT_GET_LEFT(x);
+ if (!c) {
+ n = (*create)(kn, arg);
+ ERTS_RBT_INIT_EMPTY_TNODE(n);
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_EQ(ERTS_RBT_GET_KEY(n), kn));
+ *created = !0;
+ ERTS_RBT_SET_PARENT(n, x);
+ ERTS_RBT_SET_LEFT(x, n);
+ p = x;
+ break;
+ }
+ }
+ else {
+ c = ERTS_RBT_GET_RIGHT(x);
+ if (!c) {
+ n = (*create)(kn, arg);
+ ERTS_RBT_INIT_EMPTY_TNODE(n);
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_EQ(ERTS_RBT_GET_KEY(n), kn));
+ *created = !0;
+ ERTS_RBT_SET_PARENT(n, x);
+ ERTS_RBT_SET_RIGHT(x, n);
+ p = x;
+ break;
+ }
+ }
+
+ x = c;
+ }
+
+ ERTS_RBT_ASSERT(ERTS_RBT_IS_EQ(ERTS_RBT_GET_KEY(n), kn));
+ 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, n);
+
+ return n;
+}
+
+#endif /* ERTS_RBT_WANT_LOOKUP_CREATE */
+
#ifdef ERTS_RBT_WANT_LOOKUP
static ERTS_RBT_API_INLINE__ ERTS_RBT_T *
@@ -1088,11 +1219,24 @@ ERTS_RBT_FUNC__(lookup)(ERTS_RBT_T *root, ERTS_RBT_KEY_T key)
while (1) {
ERTS_RBT_KEY_T kx = ERTS_RBT_GET_KEY(x);
ERTS_RBT_T *c;
+ int kres;
+#ifdef ERTS_RBT_CMP_KEYS
+ int kcmp = ERTS_RBT_CMP_KEYS(key, kx);
+ kres = kcmp == 0;
+#else
+ kres = ERTS_RBT_IS_EQ(key, kx);
+#endif
- if (ERTS_RBT_IS_EQ(key, kx))
+ if (kres)
return x;
- if (ERTS_RBT_IS_LT(key, kx)) {
+#ifdef ERTS_RBT_CMP_KEYS
+ kres = kcmp < 0;
+#else
+ kres = ERTS_RBT_IS_LT(key, kx);
+#endif
+
+ if (kres) {
c = ERTS_RBT_GET_LEFT(x);
if (!c)
return NULL;
@@ -1426,14 +1570,14 @@ ERTS_RBT_FUNC__(foreach_large)(ERTS_RBT_T *root,
#ifdef ERTS_RBT_WANT_FOREACH_YIELDING
-static ERTS_RBT_API_INLINE__ void
+static ERTS_RBT_API_INLINE__ int
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,
+ return ERTS_RBT_FUNC__(foreach_unordered__)(&root, 0, op, arg,
1, ystate, ylimit);
}
@@ -1630,8 +1774,7 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n)
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));
+ ERTS_RBT_ASSERT(!ERTS_RBT_IS_GT__(kc, kx));
x = c;
}
@@ -1649,8 +1792,8 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n)
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));
+ ERTS_RBT_ASSERT(!ERTS_RBT_IS_GT__(kx, kc));
+
x = c;
}
@@ -1672,8 +1815,8 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n)
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));
+ ERTS_RBT_ASSERT(!ERTS_RBT_IS_GT__(kx, kc));
+
/* Go down tree of x's sibling... */
x = c;
break;
@@ -1707,6 +1850,7 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n)
#undef ERTS_RBT_NEED_FOREACH_ORDERED__
#undef ERTS_RBT_NEED_HDBG_CHECK_TREE__
#undef ERTS_RBT_HDBG_CHECK_TREE__
+#undef ERTS_RBT_IS_GT__
#ifdef ERTS_RBT_UNDEF
# undef ERTS_RBT_PREFIX
@@ -1727,6 +1871,7 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n)
# undef ERTS_RBT_GET_LEFT
# undef ERTS_RBT_SET_LEFT
# undef ERTS_RBT_GET_KEY
+# undef ERTS_RBT_CMP_KEYS
# undef ERTS_RBT_IS_LT
# undef ERTS_RBT_IS_EQ
# undef ERTS_RBT_UNDEF
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-07 11:35:13 +0000