\doxysection{linuxrbtree.\+h}
\label{linuxrbtree_8h_source}\index{include/osmocom/core/linuxrbtree.h@{include/osmocom/core/linuxrbtree.h}}
\textbf{ Go to the documentation of this file.}
\begin{DoxyCode}{0}
\DoxyCodeLine{1 \textcolor{comment}{/*}}
\DoxyCodeLine{2 \textcolor{comment}{  Red Black Trees}}
\DoxyCodeLine{3 \textcolor{comment}{  (C) 1999  Andrea Arcangeli <andrea@suse.de>}}
\DoxyCodeLine{4 \textcolor{comment}{  }}
\DoxyCodeLine{5 \textcolor{comment}{  This program is free software; you can redistribute it and/or modify}}
\DoxyCodeLine{6 \textcolor{comment}{  it under the terms of the GNU General Public License as published by}}
\DoxyCodeLine{7 \textcolor{comment}{  the Free Software Foundation; either version 2 of the License, or}}
\DoxyCodeLine{8 \textcolor{comment}{  (at your option) any later version.}}
\DoxyCodeLine{9 \textcolor{comment}{}}
\DoxyCodeLine{10 \textcolor{comment}{  This program is distributed in the hope that it will be useful,}}
\DoxyCodeLine{11 \textcolor{comment}{  but WITHOUT ANY WARRANTY; without even the implied warranty of}}
\DoxyCodeLine{12 \textcolor{comment}{  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the}}
\DoxyCodeLine{13 \textcolor{comment}{  GNU General Public License for more details.}}
\DoxyCodeLine{14 \textcolor{comment}{}}
\DoxyCodeLine{15 \textcolor{comment}{  linux/include/linux/rbtree.h}}
\DoxyCodeLine{16 \textcolor{comment}{}}
\DoxyCodeLine{17 \textcolor{comment}{  To use rbtrees you'll have to implement your own insert and search cores.}}
\DoxyCodeLine{18 \textcolor{comment}{  This will avoid us to use callbacks and to drop drammatically performances.}}
\DoxyCodeLine{19 \textcolor{comment}{  I know it's not the cleaner way,  but in C (not in C++) to get}}
\DoxyCodeLine{20 \textcolor{comment}{  performances and genericity...}}
\DoxyCodeLine{21 \textcolor{comment}{}}
\DoxyCodeLine{22 \textcolor{comment}{  Some example of insert and search follows here. The search is a plain}}
\DoxyCodeLine{23 \textcolor{comment}{  normal search over an ordered tree. The insert instead must be implemented}}
\DoxyCodeLine{24 \textcolor{comment}{  int two steps: as first thing the code must insert the element in}}
\DoxyCodeLine{25 \textcolor{comment}{  order as a red leaf in the tree, then the support library function}}
\DoxyCodeLine{26 \textcolor{comment}{  rb\_insert\_color() must be called. Such function will do the}}
\DoxyCodeLine{27 \textcolor{comment}{  not trivial work to rebalance the rbtree if necessary.}}
\DoxyCodeLine{28 \textcolor{comment}{}}
\DoxyCodeLine{29 \textcolor{comment}{-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/}}
\DoxyCodeLine{30 \textcolor{comment}{static inline struct page * rb\_search\_page\_cache(struct inode * inode,}}
\DoxyCodeLine{31 \textcolor{comment}{                                                 unsigned long offset)}}
\DoxyCodeLine{32 \textcolor{comment}{\{}}
\DoxyCodeLine{33 \textcolor{comment}{        struct rb\_node * n = inode-\/>i\_rb\_page\_cache.rb\_node;}}
\DoxyCodeLine{34 \textcolor{comment}{        struct page * page;}}
\DoxyCodeLine{35 \textcolor{comment}{}}
\DoxyCodeLine{36 \textcolor{comment}{        while (n)}}
\DoxyCodeLine{37 \textcolor{comment}{        \{}}
\DoxyCodeLine{38 \textcolor{comment}{                page = rb\_entry(n, struct page, rb\_page\_cache);}}
\DoxyCodeLine{39 \textcolor{comment}{}}
\DoxyCodeLine{40 \textcolor{comment}{                if (offset < page-\/>offset)}}
\DoxyCodeLine{41 \textcolor{comment}{                        n = n-\/>rb\_left;}}
\DoxyCodeLine{42 \textcolor{comment}{                else if (offset > page-\/>offset)}}
\DoxyCodeLine{43 \textcolor{comment}{                        n = n-\/>rb\_right;}}
\DoxyCodeLine{44 \textcolor{comment}{                else}}
\DoxyCodeLine{45 \textcolor{comment}{                        return page;}}
\DoxyCodeLine{46 \textcolor{comment}{        \}}}
\DoxyCodeLine{47 \textcolor{comment}{        return NULL;}}
\DoxyCodeLine{48 \textcolor{comment}{\}}}
\DoxyCodeLine{49 \textcolor{comment}{}}
\DoxyCodeLine{50 \textcolor{comment}{static inline struct page * \_\_rb\_insert\_page\_cache(struct inode * inode,}}
\DoxyCodeLine{51 \textcolor{comment}{                                                   unsigned long offset,}}
\DoxyCodeLine{52 \textcolor{comment}{                                                   struct rb\_node * node)}}
\DoxyCodeLine{53 \textcolor{comment}{\{}}
\DoxyCodeLine{54 \textcolor{comment}{        struct rb\_node ** p = \&inode-\/>i\_rb\_page\_cache.rb\_node;}}
\DoxyCodeLine{55 \textcolor{comment}{        struct rb\_node * parent = NULL;}}
\DoxyCodeLine{56 \textcolor{comment}{        struct page * page;}}
\DoxyCodeLine{57 \textcolor{comment}{}}
\DoxyCodeLine{58 \textcolor{comment}{        while (*p)}}
\DoxyCodeLine{59 \textcolor{comment}{        \{}}
\DoxyCodeLine{60 \textcolor{comment}{                parent = *p;}}
\DoxyCodeLine{61 \textcolor{comment}{                page = rb\_entry(parent, struct page, rb\_page\_cache);}}
\DoxyCodeLine{62 \textcolor{comment}{}}
\DoxyCodeLine{63 \textcolor{comment}{                if (offset < page-\/>offset)}}
\DoxyCodeLine{64 \textcolor{comment}{                        p = \&(*p)-\/>rb\_left;}}
\DoxyCodeLine{65 \textcolor{comment}{                else if (offset > page-\/>offset)}}
\DoxyCodeLine{66 \textcolor{comment}{                        p = \&(*p)-\/>rb\_right;}}
\DoxyCodeLine{67 \textcolor{comment}{                else}}
\DoxyCodeLine{68 \textcolor{comment}{                        return page;}}
\DoxyCodeLine{69 \textcolor{comment}{        \}}}
\DoxyCodeLine{70 \textcolor{comment}{}}
\DoxyCodeLine{71 \textcolor{comment}{        rb\_link\_node(node, parent, p);}}
\DoxyCodeLine{72 \textcolor{comment}{}}
\DoxyCodeLine{73 \textcolor{comment}{        return NULL;}}
\DoxyCodeLine{74 \textcolor{comment}{\}}}
\DoxyCodeLine{75 \textcolor{comment}{}}
\DoxyCodeLine{76 \textcolor{comment}{static inline struct page * rb\_insert\_page\_cache(struct inode * inode,}}
\DoxyCodeLine{77 \textcolor{comment}{                                                 unsigned long offset,}}
\DoxyCodeLine{78 \textcolor{comment}{                                                 struct rb\_node * node)}}
\DoxyCodeLine{79 \textcolor{comment}{\{}}
\DoxyCodeLine{80 \textcolor{comment}{        struct page * ret;}}
\DoxyCodeLine{81 \textcolor{comment}{        if ((ret = \_\_rb\_insert\_page\_cache(inode, offset, node)))}}
\DoxyCodeLine{82 \textcolor{comment}{                goto out;}}
\DoxyCodeLine{83 \textcolor{comment}{        rb\_insert\_color(node, \&inode-\/>i\_rb\_page\_cache);}}
\DoxyCodeLine{84 \textcolor{comment}{ out:}}
\DoxyCodeLine{85 \textcolor{comment}{        return ret;}}
\DoxyCodeLine{86 \textcolor{comment}{\}}}
\DoxyCodeLine{87 \textcolor{comment}{-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/-\/}}
\DoxyCodeLine{88 \textcolor{comment}{*/}}
\DoxyCodeLine{89 }
\DoxyCodeLine{90 \textcolor{preprocessor}{\#pragma once}}
\DoxyCodeLine{91 }
\DoxyCodeLine{92 \textcolor{preprocessor}{\#include <stdlib.h>}}
\DoxyCodeLine{93 }
\DoxyCodeLine{94 \textcolor{keyword}{struct }rb\_node}
\DoxyCodeLine{95 \{}
\DoxyCodeLine{96         \textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{long}  rb\_parent\_color;}
\DoxyCodeLine{97 \textcolor{preprocessor}{\#define RB\_RED          0}}
\DoxyCodeLine{98 \textcolor{preprocessor}{\#define RB\_BLACK        1}}
\DoxyCodeLine{99         \textcolor{keyword}{struct }rb\_node *rb\_right;}
\DoxyCodeLine{100         \textcolor{keyword}{struct }rb\_node *rb\_left;}
\DoxyCodeLine{101 \} \_\_attribute\_\_((aligned(\textcolor{keyword}{sizeof}(\textcolor{keywordtype}{long}))));}
\DoxyCodeLine{102     \textcolor{comment}{/* The alignment might seem pointless, but allegedly CRIS needs it */}}
\DoxyCodeLine{103 }
\DoxyCodeLine{104 \textcolor{keyword}{struct }rb\_root}
\DoxyCodeLine{105 \{}
\DoxyCodeLine{106         \textcolor{keyword}{struct }rb\_node *rb\_node;}
\DoxyCodeLine{107 \};}
\DoxyCodeLine{108 }
\DoxyCodeLine{109 }
\DoxyCodeLine{110 \textcolor{preprocessor}{\#define rb\_parent(r)   ((struct rb\_node *)((r)-\/>rb\_parent\_color \& \string~3))}}
\DoxyCodeLine{111 \textcolor{preprocessor}{\#define rb\_color(r)   ((r)-\/>rb\_parent\_color \& 1)}}
\DoxyCodeLine{112 \textcolor{preprocessor}{\#define rb\_is\_red(r)   (!rb\_color(r))}}
\DoxyCodeLine{113 \textcolor{preprocessor}{\#define rb\_is\_black(r) rb\_color(r)}}
\DoxyCodeLine{114 \textcolor{preprocessor}{\#define rb\_set\_red(r)  do \{ (r)-\/>rb\_parent\_color \&= \string~1; \} while (0)}}
\DoxyCodeLine{115 \textcolor{preprocessor}{\#define rb\_set\_black(r)  do \{ (r)-\/>rb\_parent\_color |= 1; \} while (0)}}
\DoxyCodeLine{116 }
\DoxyCodeLine{117 \textcolor{keyword}{static} \textcolor{keyword}{inline} \textcolor{keywordtype}{void} rb\_set\_parent(\textcolor{keyword}{struct} rb\_node *rb, \textcolor{keyword}{struct} rb\_node *p)}
\DoxyCodeLine{118 \{}
\DoxyCodeLine{119         rb-\/>rb\_parent\_color = (rb-\/>rb\_parent\_color \& 3) | (\textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{long})p;}
\DoxyCodeLine{120 \}}
\DoxyCodeLine{121 \textcolor{keyword}{static} \textcolor{keyword}{inline} \textcolor{keywordtype}{void} rb\_set\_color(\textcolor{keyword}{struct} rb\_node *rb, \textcolor{keywordtype}{int} color)}
\DoxyCodeLine{122 \{}
\DoxyCodeLine{123         rb-\/>rb\_parent\_color = (rb-\/>rb\_parent\_color \& \string~1) | color;}
\DoxyCodeLine{124 \}}
\DoxyCodeLine{125 }
\DoxyCodeLine{126 \textcolor{preprocessor}{\#define RB\_ROOT \{ NULL, \}}}
\DoxyCodeLine{127 \textcolor{preprocessor}{\#define rb\_entry(ptr, type, member) container\_of(ptr, type, member)}}
\DoxyCodeLine{128 }
\DoxyCodeLine{129 \textcolor{preprocessor}{\#define RB\_EMPTY\_ROOT(root)     ((root)-\/>rb\_node == NULL)}}
\DoxyCodeLine{130 \textcolor{preprocessor}{\#define RB\_EMPTY\_NODE(node)     (rb\_parent(node) == node)}}
\DoxyCodeLine{131 \textcolor{preprocessor}{\#define RB\_CLEAR\_NODE(node)     (rb\_set\_parent(node, node))}}
\DoxyCodeLine{132 }
\DoxyCodeLine{133 \textcolor{keyword}{extern} \textcolor{keywordtype}{void} rb\_insert\_color(\textcolor{keyword}{struct} rb\_node *, \textcolor{keyword}{struct} rb\_root *);}
\DoxyCodeLine{134 \textcolor{keyword}{extern} \textcolor{keywordtype}{void} rb\_erase(\textcolor{keyword}{struct} rb\_node *, \textcolor{keyword}{struct} rb\_root *);}
\DoxyCodeLine{135 }
\DoxyCodeLine{136 \textcolor{comment}{/* Find logical next and previous nodes in a tree */}}
\DoxyCodeLine{137 \textcolor{keyword}{extern} \textcolor{keyword}{struct }rb\_node *rb\_next(\textcolor{keyword}{const} \textcolor{keyword}{struct} rb\_node *);}
\DoxyCodeLine{138 \textcolor{keyword}{extern} \textcolor{keyword}{struct }rb\_node *rb\_prev(\textcolor{keyword}{const} \textcolor{keyword}{struct} rb\_node *);}
\DoxyCodeLine{139 \textcolor{keyword}{extern} \textcolor{keyword}{struct }rb\_node *rb\_first(\textcolor{keyword}{const} \textcolor{keyword}{struct} rb\_root *);}
\DoxyCodeLine{140 \textcolor{keyword}{extern} \textcolor{keyword}{struct }rb\_node *rb\_last(\textcolor{keyword}{const} \textcolor{keyword}{struct} rb\_root *);}
\DoxyCodeLine{141 }
\DoxyCodeLine{142 \textcolor{comment}{/* Fast replacement of a single node without remove/rebalance/add/rebalance */}}
\DoxyCodeLine{143 \textcolor{keyword}{extern} \textcolor{keywordtype}{void} rb\_replace\_node(\textcolor{keyword}{struct} rb\_node *victim, \textcolor{keyword}{struct} rb\_node *\_new, }
\DoxyCodeLine{144                             \textcolor{keyword}{struct} rb\_root *root);}
\DoxyCodeLine{145 }
\DoxyCodeLine{146 \textcolor{keyword}{static} \textcolor{keyword}{inline} \textcolor{keywordtype}{void} rb\_link\_node(\textcolor{keyword}{struct} rb\_node * node, \textcolor{keyword}{struct} rb\_node * parent,}
\DoxyCodeLine{147                                 \textcolor{keyword}{struct} rb\_node ** rb\_link)}
\DoxyCodeLine{148 \{}
\DoxyCodeLine{149         node-\/>rb\_parent\_color = (\textcolor{keywordtype}{unsigned} long )parent;}
\DoxyCodeLine{150         node-\/>rb\_left = node-\/>rb\_right = NULL;}
\DoxyCodeLine{151 }
\DoxyCodeLine{152         *rb\_link = node;}
\DoxyCodeLine{153 \}}

\end{DoxyCode}
