1e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat/* 2e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat Red Black Trees 3e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat (C) 1999 Andrea Arcangeli <andrea@suse.de> 4e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 5e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat This program is free software; you can redistribute it and/or modify 6e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat it under the terms of the GNU General Public License as published by 7e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat the Free Software Foundation; either version 2 of the License, or 8e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat (at your option) any later version. 9e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 10e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat This program is distributed in the hope that it will be useful, 11e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat but WITHOUT ANY WARRANTY; without even the implied warranty of 12e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat GNU General Public License for more details. 14e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 15e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat You should have received a copy of the GNU General Public License 16e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat along with this program; if not, write to the Free Software 17e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 18e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 19e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat linux/include/linux/rbtree.h 20e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 21e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat To use rbtrees you'll have to implement your own insert and search cores. 22e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat This will avoid us to use callbacks and to drop drammatically performances. 23e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat I know it's not the cleaner way, but in C (not in C++) to get 24e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat performances and genericity... 25e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 26e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat Some example of insert and search follows here. The search is a plain 27e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat normal search over an ordered tree. The insert instead must be implemented 28e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat int two steps: as first thing the code must insert the element in 29e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat order as a red leaf in the tree, then the support library function 30e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_insert_color() must be called. Such function will do the 31e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat not trivial work to rebalance the rbtree if necessary. 32e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 33e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat----------------------------------------------------------------------- 34e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstatic inline struct page * rb_search_page_cache(struct inode * inode, 35e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat unsigned long offset) 36e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 37e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node * n = inode->i_rb_page_cache.rb_node; 38e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct page * page; 39e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 40e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat while (n) 41e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 42e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat page = rb_entry(n, struct page, rb_page_cache); 43e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 44e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (offset < page->offset) 45e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat n = n->rb_left; 46e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else if (offset > page->offset) 47e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat n = n->rb_right; 48e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 49e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return page; 50e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 51e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return NULL; 52e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 53e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 54e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstatic inline struct page * __rb_insert_page_cache(struct inode * inode, 55e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat unsigned long offset, 56e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node * node) 57e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 58e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node ** p = &inode->i_rb_page_cache.rb_node; 59e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node * parent = NULL; 60e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct page * page; 61e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 62e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat while (*p) 63e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 64e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent = *p; 65e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat page = rb_entry(parent, struct page, rb_page_cache); 66e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 67e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (offset < page->offset) 68e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat p = &(*p)->rb_left; 69e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else if (offset > page->offset) 70e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat p = &(*p)->rb_right; 71e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 72e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return page; 73e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 74e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 75e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_link_node(node, parent, p); 76e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 77e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return NULL; 78e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 79e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 80e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstatic inline struct page * rb_insert_page_cache(struct inode * inode, 81e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat unsigned long offset, 82e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node * node) 83e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 84e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct page * ret; 85e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if ((ret = __rb_insert_page_cache(inode, offset, node))) 86e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat goto out; 87e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_insert_color(node, &inode->i_rb_page_cache); 88e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat out: 89e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return ret; 90e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 91e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat----------------------------------------------------------------------- 92e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat*/ 93e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 94e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#ifndef _LINUX_RBTREE_H 95e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define _LINUX_RBTREE_H 96e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 97e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#include <stdlib.h> 98e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 99e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstruct rb_node 100e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 101e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat unsigned long rb_parent_color; 102e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define RB_RED 0 103e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define RB_BLACK 1 104e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *rb_right; 105e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *rb_left; 106e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat}; 107e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 108e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstruct rb_root 109e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 110e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *rb_node; 111e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat}; 112e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 113e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#undef offsetof 114e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#ifdef __compiler_offsetof 115e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER) 116e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#else 117e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) 118e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#endif 119e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 120e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define container_of(ptr, type, member) ({ \ 121e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat const typeof( ((type *)0)->member ) *__mptr = (ptr); \ 122e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat (type *)( (char *)__mptr - offsetof(type,member) );}) 123e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 124e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) 125e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define rb_color(r) ((r)->rb_parent_color & 1) 126e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define rb_is_red(r) (!rb_color(r)) 127e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define rb_is_black(r) rb_color(r) 128e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) 129e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0) 130e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 131e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstatic inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) 132e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 133e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; 134e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 135e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstatic inline void rb_set_color(struct rb_node *rb, int color) 136e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 137e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; 138e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 139e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 140e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define RB_ROOT (struct rb_root) { NULL, } 141e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#define rb_entry(ptr, type, member) container_of(ptr, type, member) 142e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 143e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatextern void rb_insert_color(struct rb_node *, struct rb_root *); 144e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatextern void rb_erase(struct rb_node *, struct rb_root *); 145e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 146e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat/* Find logical next and previous nodes in a tree */ 147e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatextern struct rb_node *rb_next(struct rb_node *); 148e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatextern struct rb_node *rb_prev(struct rb_node *); 149e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatextern struct rb_node *rb_first(struct rb_root *); 150e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatextern struct rb_node *rb_last(struct rb_root *); 151e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 152e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat/* Fast replacement of a single node without remove/rebalance/add/rebalance */ 153e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatextern void rb_replace_node(struct rb_node *victim, struct rb_node *new, 154e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_root *root); 155e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 156e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstatic inline void rb_link_node(struct rb_node * node, struct rb_node * parent, 157e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node ** rb_link) 158e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 159e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node->rb_parent_color = (unsigned long )parent; 160e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node->rb_left = node->rb_right = NULL; 161e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 162e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat *rb_link = node; 163e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 164e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 165e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#endif /* _LINUX_RBTREE_H */ 166