Merge pull request #1740 from rickard-green/rickard/signals/OTP-14589

Implementation of true asynchronous signaling between processes

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