15db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner/* 25db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner Red Black Trees 35db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner (C) 1999 Andrea Arcangeli <andrea@suse.de> 45db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 55db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner This program is free software; you can redistribute it and/or modify 65db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner it under the terms of the GNU General Public License as published by 75db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner the Free Software Foundation; either version 2 of the License, or 85db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner (at your option) any later version. 95db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 105db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner This program is distributed in the hope that it will be useful, 115db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner but WITHOUT ANY WARRANTY; without even the implied warranty of 125db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 135db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner GNU General Public License for more details. 145db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 155db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner You should have received a copy of the GNU General Public License 165db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner along with this program; if not, write to the Free Software 175db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 185db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 195db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner linux/include/linux/rbtree.h 205db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 215db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner To use rbtrees you'll have to implement your own insert and search cores. 225db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner This will avoid us to use callbacks and to drop drammatically performances. 235db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner I know it's not the cleaner way, but in C (not in C++) to get 245db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner performances and genericity... 255db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 265db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner Some example of insert and search follows here. The search is a plain 275db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner normal search over an ordered tree. The insert instead must be implemented 285db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner in two steps: First, the code must insert the element in order as a red leaf 295db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner in the tree, and then the support library function rb_insert_color() must 305db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner be called. Such function will do the not trivial work to rebalance the 315db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner rbtree, if necessary. 325db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 335db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner----------------------------------------------------------------------- 345db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerstatic inline struct page * rb_search_page_cache(struct inode * inode, 355db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner unsigned long offset) 365db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner{ 375db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct rb_node * n = inode->i_rb_page_cache.rb_node; 385db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct page * page; 395db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 405db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner while (n) 415db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner { 425db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner page = rb_entry(n, struct page, rb_page_cache); 435db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 445db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner if (offset < page->offset) 455db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner n = n->rb_left; 465db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner else if (offset > page->offset) 475db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner n = n->rb_right; 485db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner else 495db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner return page; 505db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner } 515db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner return NULL; 525db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner} 535db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 545db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerstatic inline struct page * __rb_insert_page_cache(struct inode * inode, 555db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner unsigned long offset, 565db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct rb_node * node) 575db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner{ 585db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct rb_node ** p = &inode->i_rb_page_cache.rb_node; 595db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct rb_node * parent = NULL; 605db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct page * page; 615db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 625db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner while (*p) 635db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner { 645db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner parent = *p; 655db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner page = rb_entry(parent, struct page, rb_page_cache); 665db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 675db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner if (offset < page->offset) 685db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner p = &(*p)->rb_left; 695db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner else if (offset > page->offset) 705db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner p = &(*p)->rb_right; 715db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner else 725db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner return page; 735db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner } 745db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 755db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner rb_link_node(node, parent, p); 765db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 775db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner return NULL; 785db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner} 795db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 805db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerstatic inline struct page * rb_insert_page_cache(struct inode * inode, 815db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner unsigned long offset, 825db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct rb_node * node) 835db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner{ 845db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct page * ret; 855db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner if ((ret = __rb_insert_page_cache(inode, offset, node))) 865db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner goto out; 875db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner rb_insert_color(node, &inode->i_rb_page_cache); 885db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner out: 895db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner return ret; 905db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner} 915db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner----------------------------------------------------------------------- 925db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner*/ 935db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 945db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#ifndef _LINUX_RBTREE_H 955db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define _LINUX_RBTREE_H 965db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 975db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#include <stdlib.h> 98d4e5abfb1bb990a029005c1a801961fc1a0ba866Adrien Schildknecht#include <stdint.h> 995db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1005db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#undef offsetof 1015db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#ifdef __compiler_offsetof 1025db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER) 1035db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#else 1045db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) 1055db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#endif 1065db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1075db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define container_of(ptr, type, member) ({ \ 108e64e6761aa22f31123a91206a5686526f7b9c6c0Theodore Ts'o const __typeof__( ((type *)0)->member ) *__mptr = (ptr); \ 1095db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner (type *)( (char *)__mptr - offsetof(type,member) );}) 1105db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1115db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerstruct rb_node 1125db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner{ 113d4e5abfb1bb990a029005c1a801961fc1a0ba866Adrien Schildknecht uintptr_t rb_parent_color; 1145db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define RB_RED 0 1155db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define RB_BLACK 1 1165db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct rb_node *rb_right; 1175db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct rb_node *rb_left; 1185db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner} __attribute__((aligned(sizeof(long)))); 1195db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner /* The alignment might seem pointless, but allegedly CRIS needs it */ 1205db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1215db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerstruct rb_root 1225db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner{ 1235db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct rb_node *rb_node; 1245db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner}; 1255db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1265db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1275db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define ext2fs_rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) 1285db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define ext2fs_rb_color(r) ((r)->rb_parent_color & 1) 1295db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define ext2fs_rb_is_red(r) (!ext2fs_rb_color(r)) 1305db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define ext2fs_rb_is_black(r) ext2fs_rb_color(r) 1315db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define ext2fs_rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) 1325db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define ext2fs_rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0) 1335db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1345db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerstatic inline void ext2fs_rb_set_parent(struct rb_node *rb, struct rb_node *p) 1355db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner{ 136d4e5abfb1bb990a029005c1a801961fc1a0ba866Adrien Schildknecht rb->rb_parent_color = (rb->rb_parent_color & 3) | (uintptr_t)p; 1375db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner} 1385db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerstatic inline void ext2fs_rb_set_color(struct rb_node *rb, int color) 1395db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner{ 1405db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; 1415db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner} 1425db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1435db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define RB_ROOT (struct rb_root) { NULL, } 1445db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#define ext2fs_rb_entry(ptr, type, member) container_of(ptr, type, member) 1455db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 146539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilgerstatic inline int ext2fs_rb_empty_root(struct rb_root *root) 147539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilger{ 148539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilger return root->rb_node == NULL; 149539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilger} 150539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilger 151539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilgerstatic inline int ext2fs_rb_empty_node(struct rb_node *node) 152539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilger{ 153539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilger return ext2fs_rb_parent(node) == node; 154539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilger} 155539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilger 156539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilgerstatic inline void ext2fs_rb_clear_node(struct rb_node *node) 157539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilger{ 158539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilger ext2fs_rb_set_parent(node, node); 159539d3ae3da75021fe391a68c2714b4bb29ddc199Andreas Dilger} 1605db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1615db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerextern void ext2fs_rb_insert_color(struct rb_node *, struct rb_root *); 1625db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerextern void ext2fs_rb_erase(struct rb_node *, struct rb_root *); 1635db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1645db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernertypedef void (*rb_augment_f)(struct rb_node *node, void *data); 1655db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1665db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerextern void ext2fs_rb_augment_insert(struct rb_node *node, 1675db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner rb_augment_f func, void *data); 1685db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerextern struct rb_node *ext2fs_rb_augment_erase_begin(struct rb_node *node); 1695db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerextern void ext2fs_rb_augment_erase_end(struct rb_node *node, 1705db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner rb_augment_f func, void *data); 1715db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1725db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner/* Find logical next and previous nodes in a tree */ 173e48bf256e99e4923c6193ff78000af18c700d93dTheodore Ts'oextern struct rb_node *ext2fs_rb_next(struct rb_node *); 174e48bf256e99e4923c6193ff78000af18c700d93dTheodore Ts'oextern struct rb_node *ext2fs_rb_prev(struct rb_node *); 1755db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerextern struct rb_node *ext2fs_rb_first(const struct rb_root *); 1765db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerextern struct rb_node *ext2fs_rb_last(const struct rb_root *); 1775db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1785db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner/* Fast replacement of a single node without remove/rebalance/add/rebalance */ 1795db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerextern void ext2fs_rb_replace_node(struct rb_node *victim, struct rb_node *new, 1805db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct rb_root *root); 1815db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1825db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czernerstatic inline void ext2fs_rb_link_node(struct rb_node * node, 1835db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct rb_node * parent, 1845db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner struct rb_node ** rb_link) 1855db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner{ 186d4e5abfb1bb990a029005c1a801961fc1a0ba866Adrien Schildknecht node->rb_parent_color = (uintptr_t)parent; 1875db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner node->rb_left = node->rb_right = NULL; 1885db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1895db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner *rb_link = node; 1905db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner} 1915db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner 1925db745a2836fd480d6be1b7cf388b0aad6b786adLukas Czerner#endif /* _LINUX_RBTREE_H */ 193