[PATCH v5 25/25] rbtree.h: (optional?) Add RB_INSERT_DUPE_RIGHT flag

[Daniel Santos <daniel.santos@pobox.com>]

I'm not sure if this is needed anywhere in the kernel. If not, it will
cause inserts run on older compilers to slow down very slightly.

This flag affects the behavior of inserts in trees where duplicate keys
are allowed.  It's generally assumed that the new node will be added to
the head of a group of nodes with the same key value.  However, this
behavior may not always be desired and this flag offers the option to
choose them to be inserted at the tail of such a group.

Signed-off-by: Daniel Santos <daniel.santos@pobox.com>
---
 include/linux/rbtree.h |   79 ++++++++++++++++++++++++++++++++++++-----------
 1 files changed, 60 insertions(+), 19 deletions(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index f1fbdea..2ca553b 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -264,6 +264,11 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
  * @RB_INSERT_REPLACES:	When set, the rb_insert() will replace a value if it
  * 			matches the supplied one (valid only when
  * 			RB_UNIQUE_KEYS is set).
+ * @RB_INSERT_DUPE_RIGHT: Normally, when inserting a duplicate value into a
+ * 			tree with non-unique keys, the new value is inserted at
+ * 			the the head of the group same-value objects.  This
+ * 			flag causes inserts in such cases to put the new value
+ * 			at the tail of the group.
  * @RB_IS_AUGMENTED:	is an augmented tree
  * @RB_VERIFY_USAGE:	Perform checks upon node insertion for a small run-time
  * 			overhead. This has other usage restrictions, so read
@@ -300,12 +305,14 @@ enum rb_flags {
 	RB_HAS_COUNT		= 0x00000004,
 	RB_UNIQUE_KEYS		= 0x00000008,
 	RB_INSERT_REPLACES	= 0x00000010,
+	RB_INSERT_DUPE_RIGHT	= 0x00000020,
 	RB_IS_AUGMENTED		= 0x00000040,
 	RB_VERIFY_USAGE		= 0x00000080 & __RB_DEBUG_ENABLE_MASK,
 	RB_VERIFY_INTEGRITY	= 0x00000100 & __RB_DEBUG_ENABLE_MASK,
 	RB_ALL_FLAGS		= RB_HAS_LEFTMOST | RB_HAS_RIGHTMOST
 			| RB_HAS_COUNT | RB_UNIQUE_KEYS
 			| RB_INSERT_REPLACES | RB_IS_AUGMENTED
+			| RB_INSERT_DUPE_RIGHT
 			| RB_VERIFY_USAGE | RB_VERIFY_INTEGRITY,
 };
 
@@ -504,15 +511,19 @@ void __rb_assert_good_rel(const struct rb_relationship *rel)
 	/* Due to a bug in versions of gcc prior to 4.6, the following
 	 * expressions are always evalulated at run-time:
 	 *
+	 * ((rel->flags & RB_UNIQUE_KEYS) && (rel->flags & RB_INSERT_DUPE_RIGHT))
 	 * (!(rel->flags & RB_UNIQUE_KEYS) && (rel->flags & RB_INSERT_REPLACES))
 	 *
 	 * The work-around for this bug is separate each bitwise AND test using
 	 * an if/else construct and evaluate only the last test with the
 	 * BUILD_BUG_ON macro.
 	 */
-
-	if (rel->flags & RB_INSERT_REPLACES)
-		BUILD_BUG_ON42(!(rel->flags & RB_UNIQUE_KEYS));
+	if (rel->flags & RB_UNIQUE_KEYS)
+		/* only with non-unique keys */
+		BUILD_BUG_ON42(rel->flags & RB_INSERT_DUPE_RIGHT);
+	else
+		/* only with unique keys */
+		BUILD_BUG_ON42(rel->flags & RB_INSERT_REPLACES);
 }
 
 
@@ -840,6 +851,7 @@ struct rb_node *__rb_find_subtree(
 				 */
 				break;
 			else if (!diff) {
+				/* FIXME: non-unique keys broken here on inserts */
 				/* exact match */
 				*matched = go_left
 					 ? RB_MATCH_LEFT
@@ -1022,16 +1034,34 @@ struct rb_node *rb_insert(
 
 		parent = *p;
 
-		if (diff > 0) {
-			p = &(*p)->rb_right;
-			if (rel->flags & RB_HAS_LEFTMOST)
-				leftmost = 0;
-		} else if (!(rel->flags & RB_UNIQUE_KEYS) || diff < 0) {
-			p = &(*p)->rb_left;
-			if (rel->flags & RB_HAS_RIGHTMOST)
-				rightmost = 0;
-		} else
-			break;
+		/* when using non-unique keys, a new same-key objects is
+		 * inserted at the head of any existing same-key objects unless
+		 * RB_INSERT_DUPE_RIGHT is specified, which causes them to be
+		 * inserted at the tail.
+		 */
+		if (rel->flags & RB_INSERT_DUPE_RIGHT) {
+			if (diff < 0) {
+				p = &(*p)->rb_left;
+				if (rel->flags & RB_HAS_RIGHTMOST)
+					rightmost = 0;
+			} else if (!(rel->flags & RB_UNIQUE_KEYS) || diff > 0) {
+				p = &(*p)->rb_right;
+				if (rel->flags & RB_HAS_LEFTMOST)
+					leftmost = 0;
+			} else
+				break;
+		} else {
+			if (diff > 0) {
+				p = &(*p)->rb_right;
+				if (rel->flags & RB_HAS_LEFTMOST)
+					leftmost = 0;
+			} else if (!(rel->flags & RB_UNIQUE_KEYS) || diff < 0) {
+				p = &(*p)->rb_left;
+				if (rel->flags & RB_HAS_RIGHTMOST)
+					rightmost = 0;
+			} else
+				break;
+		}
 	}
 
 	if ((rel->flags & RB_HAS_LEFTMOST) && leftmost) {
@@ -1087,12 +1117,23 @@ struct rb_node *rb_insert_near(
 			diff   = rel->compare(__rb_node_to_key(*p, rel), key);
 			parent = *p;
 
-			if (diff > 0)
-				p = &(*p)->rb_right;
-			else if (!(rel->flags & RB_UNIQUE_KEYS) || diff < 0)
-				p = &(*p)->rb_left;
-			else
-				break;
+			if (rel->flags & RB_INSERT_REPLACES) {
+				if (diff < 0)
+					p = &(*p)->rb_left;
+				else if (!(rel->flags & RB_UNIQUE_KEYS) ||
+						diff > 0)
+					p = &(*p)->rb_right;
+				else
+					break;
+			} else {
+				if (diff > 0)
+					p = &(*p)->rb_right;
+				else if (!(rel->flags & RB_UNIQUE_KEYS) ||
+						diff < 0)
+					p = &(*p)->rb_left;
+				else
+					break;
+			}
 		}
 		ret = *p;
 	}
-- 
1.7.3.4