← Back to branch summary

~wb-munzinger/+junk/ocfs2-tools

« back to all changes in this revision

Viewing changes to include/ocfs2/kernel-rbtree.h

  • Committer: Bazaar Package Importer
  • Author(s): Jeremy Lainé
  • Date: 2009-07-06 07:26:30 UTC
  • mfrom: (1.1.7 upstream) (0.1.5 squeeze)
  • Revision ID: james.westby@ubuntu.com-20090706072630-59335sl51k3rvu74
Tags: 1.4.2-1
http://bugs.debian.org/535471
* New upstream release (Closes: #535471).
* Drop patch for limits.h, included upstream.

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/ocfs2/kernel-rbtree.h
 
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
  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
  Some example of insert and search follows here. The search is a plain
 
27
  normal search over an ordered tree. The insert instead must be implemented
 
28
  int two steps: as first thing the code must insert the element in
 
29
  order as a red leaf in the tree, then the support library function
 
30
  rb_insert_color() must be called. Such function will do the
 
31
  not trivial work to rebalance the rbtree if necessary.
 
32
 
 
33
-----------------------------------------------------------------------
 
34
static inline struct page * rb_search_page_cache(struct inode * inode,
 
35
                                                 unsigned long offset)
 
36
{
 
37
        struct rb_node * n = inode->i_rb_page_cache.rb_node;
 
38
        struct page * page;
 
39
 
 
40
        while (n)
 
41
        {
 
42
                page = rb_entry(n, struct page, rb_page_cache);
 
43
 
 
44
                if (offset < page->offset)
 
45
                        n = n->rb_left;
 
46
                else if (offset > page->offset)
 
47
                        n = n->rb_right;
 
48
                else
 
49
                        return page;
 
50
        }
 
51
        return NULL;
 
52
}
 
53
 
 
54
static inline struct page * __rb_insert_page_cache(struct inode * inode,
 
55
                                                   unsigned long offset,
 
56
                                                   struct rb_node * node)
 
57
{
 
58
        struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
 
59
        struct rb_node * parent = NULL;
 
60
        struct page * page;
 
61
 
 
62
        while (*p)
 
63
        {
 
64
                parent = *p;
 
65
                page = rb_entry(parent, struct page, rb_page_cache);
 
66
 
 
67
                if (offset < page->offset)
 
68
                        p = &(*p)->rb_left;
 
69
                else if (offset > page->offset)
 
70
                        p = &(*p)->rb_right;
 
71
                else
 
72
                        return page;
 
73
        }
 
74
 
 
75
        rb_link_node(node, parent, p);
 
76
 
 
77
        return NULL;
 
78
}
 
79
 
 
80
static inline struct page * rb_insert_page_cache(struct inode * inode,
 
81
                                                 unsigned long offset,
 
82
                                                 struct rb_node * node)
 
83
{
 
84
        struct page * ret;
 
85
        if ((ret = __rb_insert_page_cache(inode, offset, node)))
 
86
                goto out;
 
87
        rb_insert_color(node, &inode->i_rb_page_cache);
 
88
 out:
 
89
        return ret;
 
90
}
 
91
-----------------------------------------------------------------------
 
92
*/
 
93
 
 
94
#ifndef _LINUX_RBTREE_H
 
95
#define _LINUX_RBTREE_H
 
96
 
 
97
#include <stdlib.h>
 
98
 
 
99
struct rb_node
 
100
{
 
101
        struct rb_node *rb_parent;
 
102
        int rb_color;
 
103
#define RB_RED          0
 
104
#define RB_BLACK        1
 
105
        struct rb_node *rb_right;
 
106
        struct rb_node *rb_left;
 
107
};
 
108
 
 
109
struct rb_root
 
110
{
 
111
        struct rb_node *rb_node;
 
112
};
 
113
 
 
114
#define RB_ROOT (struct rb_root) { NULL, }
 
115
#define rb_entry(ptr, type, member)                                     \
 
116
        ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
 
117
 
 
118
extern void rb_insert_color(struct rb_node *, struct rb_root *);
 
119
extern void rb_erase(struct rb_node *, struct rb_root *);
 
120
 
 
121
/* Find logical next and previous nodes in a tree */
 
122
extern struct rb_node *rb_next(struct rb_node *);
 
123
extern struct rb_node *rb_prev(struct rb_node *);
 
124
extern struct rb_node *rb_first(struct rb_root *);
 
125
extern struct rb_node *rb_last(struct rb_root *);
 
126
 
 
127
/* Fast replacement of a single node without remove/rebalance/add/rebalance */
 
128
extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, 
 
129
                            struct rb_root *root);
 
130
 
 
131
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
 
132
                                struct rb_node ** rb_link)
 
133
{
 
134
        node->rb_parent = parent;
 
135
        node->rb_color = RB_RED;
 
136
        node->rb_left = node->rb_right = NULL;
 
137
 
 
138
        *rb_link = node;
 
139
}
 
140
 
 
141
#endif  /* _LINUX_RBTREE_H */