Line data    Source code

       1             : /*
       2             :   Red Black Trees
       3             :   (C) 1999  Andrea Arcangeli <andrea@suse.de>
       4             :   
       5             :   This program is free software; you can redistribute it and/or modify
       6             :   it under the terms of the GNU General Public License as published by
       7             :   the Free Software Foundation; either version 2 of the License, or
       8             :   (at your option) any later version.
       9             : 
      10             :   This program is distributed in the hope that it will be useful,
      11             :   but WITHOUT ANY WARRANTY; without even the implied warranty of
      12             :   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      13             :   GNU General Public License for more details.
      14             : 
      15             :   You should have received a copy of the GNU General Public License
      16             :   along with this program; if not, write to the Free Software
      17             :   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
      18             : 
      19             :   linux/include/linux/rbtree.h
      20             : 
      21             :   To use rbtrees you'll have to implement your own insert and search cores.
      22             :   This will avoid us to use callbacks and to drop drammatically performances.
      23             :   I know it's not the cleaner way,  but in C (not in C++) to get
      24             :   performances and genericity...
      25             : 
      26             :   See Documentation/rbtree.txt for documentation and samples.
      27             : */
      28             : 
      29             : #ifndef _LINUX_RBTREE_H
      30             : #define _LINUX_RBTREE_H
      31             : 
      32             : #include <linux/kernel.h>
      33             : #include <linux/stddef.h>
      34             : 
      35             : struct rb_node {
      36             :         unsigned long  __rb_parent_color;
      37             :         struct rb_node *rb_right;
      38             :         struct rb_node *rb_left;
      39             : } __attribute__((aligned(sizeof(long))));
      40             :     /* The alignment might seem pointless, but allegedly CRIS needs it */
      41             : 
      42             : struct rb_root {
      43             :         struct rb_node *rb_node;
      44             : };
      45             : 
      46             : 
      47             : #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
      48             : 
      49             : #define RB_ROOT (struct rb_root) { NULL, }
      50             : #define rb_entry(ptr, type, member) container_of(ptr, type, member)
      51             : 
      52             : #define RB_EMPTY_ROOT(root)  ((root)->rb_node == NULL)
      53             : 
      54             : /* 'empty' nodes are nodes that are known not to be inserted in an rbree */
      55             : #define RB_EMPTY_NODE(node)  \
      56             :         ((node)->__rb_parent_color == (unsigned long)(node))
      57             : #define RB_CLEAR_NODE(node)  \
      58             :         ((node)->__rb_parent_color = (unsigned long)(node))
      59             : 
      60             : 
      61             : extern void rb_insert_color(struct rb_node *, struct rb_root *);
      62             : extern void rb_erase(struct rb_node *, struct rb_root *);
      63             : 
      64             : 
      65             : /* Find logical next and previous nodes in a tree */
      66             : extern struct rb_node *rb_next(const struct rb_node *);
      67             : extern struct rb_node *rb_prev(const struct rb_node *);
      68             : extern struct rb_node *rb_first(const struct rb_root *);
      69             : extern struct rb_node *rb_last(const struct rb_root *);
      70             : 
      71             : /* Postorder iteration - always visit the parent after its children */
      72             : extern struct rb_node *rb_first_postorder(const struct rb_root *);
      73             : extern struct rb_node *rb_next_postorder(const struct rb_node *);
      74             : 
      75             : /* Fast replacement of a single node without remove/rebalance/add/rebalance */
      76             : extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, 
      77             :                             struct rb_root *root);
      78             : 
      79             : static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
      80             :                                 struct rb_node ** rb_link)
      81             : {
      82     3533947 :         node->__rb_parent_color = (unsigned long)parent;
      83     3533947 :         node->rb_left = node->rb_right = NULL;
      84             : 
      85     3533947 :         *rb_link = node;
      86             : }
      87             : 
      88             : #define rb_entry_safe(ptr, type, member) \
      89             :         ({ typeof(ptr) ____ptr = (ptr); \
      90             :            ____ptr ? rb_entry(____ptr, type, member) : NULL; \
      91             :         })
      92             : 
      93             : /**
      94             :  * rbtree_postorder_for_each_entry_safe - iterate over rb_root in post order of
      95             :  * given type safe against removal of rb_node entry
      96             :  *
      97             :  * @pos:        the 'type *' to use as a loop cursor.
      98             :  * @n:          another 'type *' to use as temporary storage
      99             :  * @root:       'rb_root *' of the rbtree.
     100             :  * @field:      the name of the rb_node field within 'type'.
     101             :  */
     102             : #define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
     103             :         for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
     104             :              pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
     105             :                         typeof(*pos), field); 1; }); \
     106             :              pos = n)
     107             : 
     108             : #endif  /* _LINUX_RBTREE_H */