add_params: Embed inode table and sd_set directly
[wimlib] / src / 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   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 "util.h"
33 #include <stdint.h>
34
35 struct rb_node {
36         uintptr_t  __rb_parent_color;
37         struct rb_node *rb_right;
38         struct rb_node *rb_left;
39 };
40
41 struct rb_root {
42         struct rb_node *rb_node;
43 };
44
45
46 #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
47 #define rb_entry(ptr, type, member) container_of(ptr, type, member)
48
49 extern void rb_insert_color(struct rb_node *, struct rb_root *);
50 extern void rb_erase(struct rb_node *, struct rb_root *);
51
52 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
53                                 struct rb_node ** rb_link)
54 {
55         node->__rb_parent_color = (uintptr_t)parent;
56         node->rb_left = node->rb_right = NULL;
57
58         *rb_link = node;
59 }
60
61 #endif  /* _LINUX_RBTREE_H */