Integrate rbtrees into Akaros
authorBarret Rhoden <brho@cs.berkeley.edu>
Thu, 13 Oct 2016 15:24:29 +0000 (11:24 -0400)
committerBarret Rhoden <brho@cs.berkeley.edu>
Tue, 29 Nov 2016 16:27:40 +0000 (11:27 -0500)
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
kern/include/linux/compat_todo.h
kern/include/linux_compat.h
kern/include/rbtree.h
kern/include/rbtree_augmented.h
kern/lib/Kbuild
kern/lib/rbtree.c

index d1a107b..38686d9 100644 (file)
@@ -19,6 +19,7 @@
 #include <stddef.h>
 #include <string.h>
 #include <taskqueue.h>
+#include <rbtree.h>
 
 #define ETH_ALEN       6               /* Octets in one ethernet addr   */
 #define ETH_ZLEN       60              /* Min. octets in frame sans FCS */
@@ -115,27 +116,6 @@ extern int ____ilog2_NaN;
        LOG2_UP(n)                              \
  )
 
-struct rb_node {
-       unsigned long  __rb_parent_color;
-       struct rb_node *rb_right;
-       struct rb_node *rb_left;
-};
-
-struct rb_root {
-       struct rb_node *rb_node;
-};
-
-#define RB_ROOT        (struct rb_root) { NULL, }
-
-static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
-                               struct rb_node ** rb_link)
-{
-       node->__rb_parent_color = (unsigned long)parent;
-       node->rb_left = node->rb_right = NULL;
-
-       *rb_link = node;
-}
-
 #define __printf(...)
 
 #define sprintf(s, fmt, ...) ({ \
index 014ac3c..7f321bb 100644 (file)
@@ -41,7 +41,9 @@
 #define rcu_read_unlock()
 #define rcu_dereference(x) (x)
 #define rcu_dereference_protected(x, y) (x)
+#ifndef rcu_assign_pointer
 #define rcu_assign_pointer(dst, src) (dst) = (src)
+#endif
 #define RCU_INIT_POINTER(dst, src) rcu_assign_pointer(dst, src)
 #define synchronize_rcu()
 
index e585018..04b9ddc 100644 (file)
   See Documentation/rbtree.txt for documentation and samples.
 */
 
-#ifndef        _LINUX_RBTREE_H
-#define        _LINUX_RBTREE_H
+#pragma once
 
-#include <linux/kernel.h>
-#include <linux/stddef.h>
-#include <linux/rcupdate.h>
+/* TODO: eventually we'll support some form of RCU and concurrent rb-tree
+ * usage.  When we do that, we'll need to grab these functions from Linux. */
+#ifndef WRITE_ONCE
+#define WRITE_ONCE(d, s) (d) = (s)
+#endif
+#ifndef rcu_assign_pointer
+#define rcu_assign_pointer(d, s) (d) = (s)
+#endif
 
 struct rb_node {
        unsigned long  __rb_parent_color;
@@ -124,5 +128,3 @@ static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent
             pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
                        typeof(*pos), field); 1; }); \
             pos = n)
-
-#endif /* _LINUX_RBTREE_H */
index d076183..7feba41 100644 (file)
   linux/include/linux/rbtree_augmented.h
 */
 
-#ifndef _LINUX_RBTREE_AUGMENTED_H
-#define _LINUX_RBTREE_AUGMENTED_H
+#pragma once
 
-#include <linux/compiler.h>
-#include <linux/rbtree.h>
+#include <compiler.h>
+#include <rbtree.h>
 
 /*
  * Please note - only struct rb_augment_callbacks and the prototypes for
@@ -258,5 +257,3 @@ rb_erase_augmented(struct rb_node *node, struct rb_root *root,
        if (rebalance)
                __rb_erase_color(rebalance, root, augment->rotate);
 }
-
-#endif /* _LINUX_RBTREE_AUGMENTED_H */
index a526703..0b0df9b 100644 (file)
@@ -1,5 +1,6 @@
 obj-y                                          += address_range.o
 obj-y                                          += circular_buffer.o
+obj-y                                          += rbtree.o
 obj-y                                          += slice.o
 obj-y                                          += sort.o
 obj-y                                          += crypto/
index eb8a19f..66d9ec7 100644 (file)
@@ -21,8 +21,7 @@
   linux/lib/rbtree.c
 */
 
-#include <linux/rbtree_augmented.h>
-#include <linux/export.h>
+#include <rbtree_augmented.h>
 
 /*
  * red-black trees properties:  http://en.wikipedia.org/wiki/Rbtree
@@ -398,7 +397,6 @@ void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
 {
        ____rb_erase_color(parent, root, augment_rotate);
 }
-EXPORT_SYMBOL(__rb_erase_color);
 
 /*
  * Non-augmented rbtree manipulation functions.
@@ -419,7 +417,6 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
        __rb_insert(node, root, dummy_rotate);
 }
-EXPORT_SYMBOL(rb_insert_color);
 
 void rb_erase(struct rb_node *node, struct rb_root *root)
 {
@@ -428,7 +425,6 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
        if (rebalance)
                ____rb_erase_color(rebalance, root, dummy_rotate);
 }
-EXPORT_SYMBOL(rb_erase);
 
 /*
  * Augmented rbtree manipulation functions.
@@ -442,7 +438,6 @@ void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
 {
        __rb_insert(node, root, augment_rotate);
 }
-EXPORT_SYMBOL(__rb_insert_augmented);
 
 /*
  * This function returns the first node (in sort order) of the tree.
@@ -458,7 +453,6 @@ struct rb_node *rb_first(const struct rb_root *root)
                n = n->rb_left;
        return n;
 }
-EXPORT_SYMBOL(rb_first);
 
 struct rb_node *rb_last(const struct rb_root *root)
 {
@@ -471,7 +465,6 @@ struct rb_node *rb_last(const struct rb_root *root)
                n = n->rb_right;
        return n;
 }
-EXPORT_SYMBOL(rb_last);
 
 struct rb_node *rb_next(const struct rb_node *node)
 {
@@ -503,7 +496,6 @@ struct rb_node *rb_next(const struct rb_node *node)
 
        return parent;
 }
-EXPORT_SYMBOL(rb_next);
 
 struct rb_node *rb_prev(const struct rb_node *node)
 {
@@ -532,7 +524,6 @@ struct rb_node *rb_prev(const struct rb_node *node)
 
        return parent;
 }
-EXPORT_SYMBOL(rb_prev);
 
 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
                     struct rb_root *root)
@@ -549,7 +540,6 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
                rb_set_parent(victim->rb_right, new);
        __rb_change_child(victim, new, parent, root);
 }
-EXPORT_SYMBOL(rb_replace_node);
 
 void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
                         struct rb_root *root)
@@ -571,7 +561,6 @@ void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
         */
        __rb_change_child_rcu(victim, new, parent, root);
 }
-EXPORT_SYMBOL(rb_replace_node_rcu);
 
 static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
 {
@@ -602,7 +591,6 @@ struct rb_node *rb_next_postorder(const struct rb_node *node)
                 * should be next */
                return (struct rb_node *)parent;
 }
-EXPORT_SYMBOL(rb_next_postorder);
 
 struct rb_node *rb_first_postorder(const struct rb_root *root)
 {
@@ -611,4 +599,3 @@ struct rb_node *rb_first_postorder(const struct rb_root *root)
 
        return rb_left_deepest_node(root->rb_node);
 }
-EXPORT_SYMBOL(rb_first_postorder);