← Back to branch summary

~wb-munzinger/+junk/ocfs2-tools

« back to all changes in this revision

Viewing changes to libocfs2/include/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:
libocfs2/include/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 */