/root/src/xen/xen/include/xen/rbtree.h

Source (jump to first uncovered line)
/*
  Red Black Trees
  (C) 1999  Andrea Arcangeli <andrea@suse.de>
  
  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

  linux/include/linux/rbtree.h

  To use rbtrees you'll have to implement your own insert and search cores.
  This will avoid us to use callbacks and to drop drammatically performances.
  I know it's not the cleaner way,  but in C (not in C++) to get
  performances and genericity...

  Some example of insert and search follows here. The search is a plain
  normal search over an ordered tree. The insert instead must be implemented
  int two steps: as first thing the code must insert the element in
  order as a red leaf in the tree, then the support library function
  rb_insert_color() must be called. Such function will do the
  not trivial work to rebalance the rbtree if necessary.

-----------------------------------------------------------------------
static inline struct page * rb_search_page_cache(struct inode * inode,
             unsigned long offset)
{
  struct rb_node * n = inode->i_rb_page_cache.rb_node;
  struct page * page;

  while (n)
  {
    page = rb_entry(n, struct page, rb_page_cache);

    if (offset < page->offset)
      n = n->rb_left;
    else if (offset > page->offset)
      n = n->rb_right;
    else
      return page;
  }
  return NULL;
}

static inline struct page * __rb_insert_page_cache(struct inode * inode,
               unsigned long offset,
               struct rb_node * node)
{
  struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
  struct rb_node * parent = NULL;
  struct page * page;

  while (*p)
  {
    parent = *p;
    page = rb_entry(parent, struct page, rb_page_cache);

    if (offset < page->offset)
      p = &(*p)->rb_left;
    else if (offset > page->offset)
      p = &(*p)->rb_right;
    else
      return page;
  }

  rb_link_node(node, parent, p);

  return NULL;
}

static inline struct page * rb_insert_page_cache(struct inode * inode,
             unsigned long offset,
             struct rb_node * node)
{
  struct page * ret;
  if ((ret = __rb_insert_page_cache(inode, offset, node)))
    goto out;
  rb_insert_color(node, &inode->i_rb_page_cache);
 out:
  return ret;
}
-----------------------------------------------------------------------
*/

#ifndef __RBTREE_H__
#define __RBTREE_H__

struct rb_node
{
  unsigned long  rb_parent_color;
#define RB_RED    0
#define RB_BLACK  1
  struct rb_node *rb_right;
  struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root
{
  struct rb_node *rb_node;
};

#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
#define rb_color(r)   ((r)->rb_parent_color & 1)
#define rb_is_red(r)   (!rb_color(r))
#define rb_is_black(r) rb_color(r)
#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)

static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
  rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
}
static inline void rb_set_color(struct rb_node *rb, int color)
{
  rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}

#define RB_ROOT (struct rb_root) { NULL, }
#define rb_entry(ptr, type, member) container_of(ptr, type, member)

#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))

extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);

/* Find logical next and previous nodes in a tree */
extern struct rb_node *rb_next(const struct rb_node *);
extern struct rb_node *rb_prev(const struct rb_node *);
extern struct rb_node *rb_first(const struct rb_root *);
extern struct rb_node *rb_last(const struct rb_root *);

/* Fast replacement of a single node without remove/rebalance/add/rebalance */
extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, 
          struct rb_root *root);

static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
        struct rb_node ** rb_link)
{
  node->rb_parent_color = (unsigned long )parent;
  node->rb_left = node->rb_right = NULL;

  *rb_link = node;
}

#endif /* __RBTREE_H__ */

Line	Count	Source (jump to first uncovered line)
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		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 __RBTREE_H__
95		#define __RBTREE_H__
96
97		struct rb_node
98		{
99		unsigned long rb_parent_color;
100		#define RB_RED 0
101	0	#define RB_BLACK 1
102		struct rb_node *rb_right;
103		struct rb_node *rb_left;
104		} __attribute__((aligned(sizeof(long))));
105		/* The alignment might seem pointless, but allegedly CRIS needs it */
106
107		struct rb_root
108		{
109		struct rb_node *rb_node;
110		};
111
112	0	#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
113	0	#define rb_color(r) ((r)->rb_parent_color & 1)
114	0	#define rb_is_red(r) (!rb_color(r))
115	0	#define rb_is_black(r) rb_color(r)
116	0	#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
117	0	#define rb_set_black(r) do { (r)->rb_parent_color \|= 1; } while (0)
118
119		static inline void rb_set_parent(struct rb_node rb, struct rb_node p)
120	0	{
121	0	rb->rb_parent_color = (rb->rb_parent_color & 3) \| (unsigned long)p;
122	0	} Unexecuted instantiation: tmem.c:rb_set_parent Unexecuted instantiation: setup.c:rb_set_parent Unexecuted instantiation: tmem_control.c:rb_set_parent Unexecuted instantiation: tmem_xen.c:rb_set_parent Unexecuted instantiation: rbtree.c:rb_set_parent Unexecuted instantiation: page_alloc.c:rb_set_parent Unexecuted instantiation: memory.c:rb_set_parent
123		static inline void rb_set_color(struct rb_node *rb, int color)
124	0	{
125	0	rb->rb_parent_color = (rb->rb_parent_color & ~1) \| color;
126	0	} Unexecuted instantiation: setup.c:rb_set_color Unexecuted instantiation: memory.c:rb_set_color Unexecuted instantiation: tmem_control.c:rb_set_color Unexecuted instantiation: tmem_xen.c:rb_set_color Unexecuted instantiation: tmem.c:rb_set_color Unexecuted instantiation: rbtree.c:rb_set_color Unexecuted instantiation: page_alloc.c:rb_set_color
127
128	0	#define RB_ROOT (struct rb_root) { NULL, }
129		#define rb_entry(ptr, type, member) container_of(ptr, type, member)
130
131		#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
132		#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
133		#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
134
135		extern void rb_insert_color(struct rb_node , struct rb_root );
136		extern void rb_erase(struct rb_node , struct rb_root );
137
138		/* Find logical next and previous nodes in a tree */
139		extern struct rb_node rb_next(const struct rb_node );
140		extern struct rb_node rb_prev(const struct rb_node );
141		extern struct rb_node rb_first(const struct rb_root );
142		extern struct rb_node rb_last(const struct rb_root );
143
144		/* Fast replacement of a single node without remove/rebalance/add/rebalance */
145		extern void rb_replace_node(struct rb_node victim, struct rb_node new,
146		struct rb_root *root);
147
148		static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
149		struct rb_node ** rb_link)
150	0	{
151	0	node->rb_parent_color = (unsigned long )parent;
152	0	node->rb_left = node->rb_right = NULL;
153	0
154	0	*rb_link = node;
155	0	} Unexecuted instantiation: tmem_control.c:rb_link_node Unexecuted instantiation: page_alloc.c:rb_link_node Unexecuted instantiation: rbtree.c:rb_link_node Unexecuted instantiation: tmem.c:rb_link_node Unexecuted instantiation: setup.c:rb_link_node Unexecuted instantiation: tmem_xen.c:rb_link_node Unexecuted instantiation: memory.c:rb_link_node
156
157		#endif /* __RBTREE_H__ */

Coverage Report

Created: 2017-10-25 09:10