Changeset 651 for GPL/branches/uniaud32-next/include/linux/rbtree.h

Timestamp:

Jan 23, 2021, 10:25:24 PM (5 years ago)

Author:

Paul Smedley

Message:

Update rbtree to linux 5.10.10 code

File:

• GPL/branches/uniaud32-next/include/linux/rbtree.h (modified) (6 diffs)

GPL/branches/uniaud32-next/include/linux/rbtree.h

@@ +1 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
 /*
   Red Black Trees
   (C) 1999  Andrea Arcangeli <andrea@suse.de>
   
-  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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
   linux/include/linux/rbtree.h
@@ -24 +12 @@
   performances and genericity...
 
-  See Documentation/rbtree.txt for documentation and samples.
+  See Documentation/core-api/rbtree.rst for documentation and samples.
 */
-/* from 4.19.163 */
+/* from 5.10.10 */
 
 #ifndef _LINUX_RBTREE_H
@@ -46 +34 @@
 };
 
-/*
- * Leftmost-cached rbtrees.
- *
- * We do not cache the rightmost node based on footprint
- * size vs number of potential users that could benefit
- * from O(1) rb_last(). Just not worth it, users that want
- * this feature can always implement the logic explicitly.
- * Furthermore, users that want to cache both pointers may
- * find it a bit asymmetric, but that's ok.
- */
-struct rb_root_cached {
-        struct rb_root rb_root;
-        struct rb_node *rb_leftmost;
-};
-
 #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
 
 #define RB_ROOT (struct rb_root) { NULL, }
-#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
 #define rb_entry(ptr, type, member) container_of(ptr, type, member)
 
@@ -86 +58 @@
 extern struct rb_node *rb_last(const struct rb_root *);
 
-extern void rb_insert_color_cached(struct rb_node *,
-                                   struct rb_root_cached *, bool);
-extern void rb_erase_cached(struct rb_node *node, struct rb_root_cached *);
-/* Same as rb_first(), but O(1) */
-#define rb_first_cached(root) (root)->rb_leftmost
-
 /* Postorder iteration - always visit the parent after its children */
 extern struct rb_node *rb_first_postorder(const struct rb_root *);
@@ -101 +67 @@
 extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
                                 struct rb_root *root);
-extern void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new,
-                                   struct rb_root_cached *root);
 
 static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
@@ -152 +116 @@
              pos = n)
 
+/*
+ * Leftmost-cached rbtrees.
+ *
+ * We do not cache the rightmost node based on footprint
+ * size vs number of potential users that could benefit
+ * from O(1) rb_last(). Just not worth it, users that want
+ * this feature can always implement the logic explicitly.
+ * Furthermore, users that want to cache both pointers may
+ * find it a bit asymmetric, but that's ok.
+ */
+struct rb_root_cached {
+        struct rb_root rb_root;
+        struct rb_node *rb_leftmost;
+};
+
+#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
+
+/* Same as rb_first(), but O(1) */
+#define rb_first_cached(root) (root)->rb_leftmost
+
+static inline void rb_insert_color_cached(struct rb_node *node,
+                                          struct rb_root_cached *root,
+                                          bool leftmost)
+{
+        if (leftmost)
+                root->rb_leftmost = node;
+        rb_insert_color(node, &root->rb_root);
+}
+
+static inline void rb_erase_cached(struct rb_node *node,
+                                   struct rb_root_cached *root)
+{
+        if (root->rb_leftmost == node)
+                root->rb_leftmost = rb_next(node);
+        rb_erase(node, &root->rb_root);
+}
+
+static inline void rb_replace_node_cached(struct rb_node *victim,
+                                          struct rb_node *new,
+                                          struct rb_root_cached *root)
+{
+        if (root->rb_leftmost == victim)
+                root->rb_leftmost = new;
+        rb_replace_node(victim, new, &root->rb_root);
+}
+
 #endif  /* _LINUX_RBTREE_H */