augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro

[linux-2.6-microblaze.git] / tools / include / linux / rbtree_augmented.h

diff --git a/tools/include/linux/rbtree_augmented.h b/tools/include/linux/rbtree_augmented.h
index de3a480..4e8c4c7 100644 (file)
--- a/tools/include/linux/rbtree_augmented.h
+++ b/tools/include/linux/rbtree_augmented.h
@@ -63,7 +63,7 @@ rb_insert_augmented_cached(struct rb_node *node,
 }
 
 /*
- * Template for declaring augmented rbtree callbacks
+ * Template for declaring augmented rbtree callbacks (generic case)
  *
  * RBSTATIC:    'static' or empty
  * RBNAME:      name of the rb_augment_callbacks structure
@@ -109,6 +109,40 @@ RBSTATIC const struct rb_augment_callbacks RBNAME = {                      \
        .rotate = RBNAME ## _rotate                                     \
 };
 
+/*
+ * Template for declaring augmented rbtree callbacks,
+ * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
+ *
+ * RBSTATIC:    'static' or empty
+ * RBNAME:      name of the rb_augment_callbacks structure
+ * RBSTRUCT:    struct type of the tree nodes
+ * RBFIELD:     name of struct rb_node field within RBSTRUCT
+ * RBTYPE:      type of the RBAUGMENTED field
+ * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
+ * RBCOMPUTE:   name of function that returns the per-node RBTYPE scalar
+ */
+
+#define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,        \
+                                RBTYPE, RBAUGMENTED, RBCOMPUTE)              \
+static inline RBTYPE RBNAME ## _compute_max(RBSTRUCT *node)                  \
+{                                                                            \
+       RBSTRUCT *child;                                                      \
+       RBTYPE max = RBCOMPUTE(node);                                         \
+       if (node->RBFIELD.rb_left) {                                          \
+               child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD);   \
+               if (child->RBAUGMENTED > max)                                 \
+                       max = child->RBAUGMENTED;                             \
+       }                                                                     \
+       if (node->RBFIELD.rb_right) {                                         \
+               child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD);  \
+               if (child->RBAUGMENTED > max)                                 \
+                       max = child->RBAUGMENTED;                             \
+       }                                                                     \
+       return max;                                                           \
+}                                                                            \
+RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,                    \
+                    RBTYPE, RBAUGMENTED, RBNAME ## _compute_max)
+
 
 #define        RB_RED          0
 #define        RB_BLACK        1