]> git.pld-linux.org Git - packages/kernel.git/blame - rbtree-2.2.21-1.diff
projects / packages / kernel.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
- added description of djurban's branch
[packages/kernel.git] / rbtree-2.2.21-1.diff
CommitLineData
b362acf5
KT		 1diff -urN v2.2.21/linux/Makefile linux/Makefile
2--- v2.2.21/linux/Makefile Tue May 21 23:26:01 2002
3+++ linux/Makefile Sat Aug 10 20:52:16 2002
4@@ -222,6 +222,10 @@
5 DRIVERS := $(DRIVERS) drivers/telephony/telephony.a
6 endif
7
8+ifeq ($(CONFIG_NET_SCHED),y)
9+LIBS := $(TOPDIR)/lib/lib_extra_objs.o $(LIBS)
10+endif
11+
12 include arch/$(ARCH)/Makefile
13
14 .S.s:
15diff -urN v2.2.21/linux/include/linux/rbtree.h linux/include/linux/rbtree.h
16--- v2.2.21/linux/include/linux/rbtree.h Thu Jan 1 00:00:00 1970
17+++ linux/include/linux/rbtree.h Sat Aug 10 20:39:46 2002
18@@ -0,0 +1,133 @@
19+/*
20+ Red Black Trees
21+ (C) 1999 Andrea Arcangeli <andrea@suse.de>
22+
23+ This program is free software; you can redistribute it and/or modify
24+ it under the terms of the GNU General Public License as published by
25+ the Free Software Foundation; either version 2 of the License, or
26+ (at your option) any later version.
27+
28+ This program is distributed in the hope that it will be useful,
29+ but WITHOUT ANY WARRANTY; without even the implied warranty of
30+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31+ GNU General Public License for more details.
32+
33+ You should have received a copy of the GNU General Public License
34+ along with this program; if not, write to the Free Software
35+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
36+
37+ linux/include/linux/rbtree.h
38+
39+ To use rbtrees you'll have to implement your own insert and search cores.
40+ This will avoid us to use callbacks and to drop drammatically performances.
41+ I know it's not the cleaner way, but in C (not in C++) to get
42+ performances and genericity...
43+
44+ Some example of insert and search follows here. The search is a plain
45+ normal search over an ordered tree. The insert instead must be implemented
46+ int two steps: as first thing the code must insert the element in
47+ order as a red leaf in the tree, then the support library function
48+ rb_insert_color() must be called. Such function will do the
49+ not trivial work to rebalance the rbtree if necessary.
50+
51+-----------------------------------------------------------------------
52+static inline struct page * rb_search_page_cache(struct inode * inode,
53+ unsigned long offset)
54+{
55+ rb_node_t * n = inode->i_rb_page_cache.rb_node;
56+ struct page * page;
57+
58+ while (n)
59+ {
60+ page = rb_entry(n, struct page, rb_page_cache);
61+
62+ if (offset < page->offset)
63+ n = n->rb_left;
64+ else if (offset > page->offset)
65+ n = n->rb_right;
66+ else
67+ return page;
68+ }
69+ return NULL;
70+}
71+
72+static inline struct page * __rb_insert_page_cache(struct inode * inode,
73+ unsigned long offset,
74+ rb_node_t * node)
75+{
76+ rb_node_t ** p = &inode->i_rb_page_cache.rb_node;
77+ rb_node_t * parent = NULL;
78+ struct page * page;
79+
80+ while (*p)
81+ {
82+ parent = *p;
83+ page = rb_entry(parent, struct page, rb_page_cache);
84+
85+ if (offset < page->offset)
86+ p = &(*p)->rb_left;
87+ else if (offset > page->offset)
88+ p = &(*p)->rb_right;
89+ else
90+ return page;
91+ }
92+
93+ rb_link_node(node, parent, p);
94+
95+ return NULL;
96+}
97+
98+static inline struct page * rb_insert_page_cache(struct inode * inode,
99+ unsigned long offset,
100+ rb_node_t * node)
101+{
102+ struct page * ret;
103+ if ((ret = __rb_insert_page_cache(inode, offset, node)))
104+ goto out;
105+ rb_insert_color(node, &inode->i_rb_page_cache);
106+ out:
107+ return ret;
108+}
109+-----------------------------------------------------------------------
110+*/
111+
112+#ifndef _LINUX_RBTREE_H
113+#define _LINUX_RBTREE_H
114+
115+#include <linux/kernel.h>
116+#include <linux/stddef.h>
117+
118+typedef struct rb_node_s
119+{
120+ struct rb_node_s * rb_parent;
121+ int rb_color;
122+#define RB_RED 0
123+#define RB_BLACK 1
124+ struct rb_node_s * rb_right;
125+ struct rb_node_s * rb_left;
126+}
127+rb_node_t;
128+
129+typedef struct rb_root_s
130+{
131+ struct rb_node_s * rb_node;
132+}
133+rb_root_t;
134+
135+#define RB_ROOT (rb_root_t) { NULL, }
136+#define rb_entry(ptr, type, member) \
137+ ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
138+
139+extern void rb_insert_color(rb_node_t *, rb_root_t *);
140+extern void rb_erase(rb_node_t *, rb_root_t *);
141+
142+static inline void rb_link_node(rb_node_t * node, rb_node_t * parent, rb_node_t ** rb_link)
143+{
144+ node->rb_parent = parent;
145+ node->rb_color = RB_RED;
146+ node->rb_left = node->rb_right = NULL;
147+
148+ *rb_link = node;
149+}
150+
151+#endif /* _LINUX_RBTREE_H */
152diff -urN v2.2.21/linux/lib/Makefile linux/lib/Makefile
153--- v2.2.21/linux/lib/Makefile Mon Nov 27 13:54:00 1995
154+++ linux/lib/Makefile Sat Aug 10 20:43:42 2002
155@@ -6,6 +6,12 @@
156 # unless it's something special (ie not a .c file).
157 #
158
159+# Currently, rbtree.o is used only from net/sched/sch_htb.c
160+ifeq ($(CONFIG_NET_SCHED),y)
161+O_TARGET := lib_extra_objs.o
162+OX_OBJS := rbtree.o
163+endif
164+
165 L_TARGET := lib.a
166 L_OBJS := errno.o ctype.o string.o vsprintf.o
167
168diff -urN v2.2.21/linux/lib/rbtree.c linux/lib/rbtree.c
169--- v2.2.21/linux/lib/rbtree.c Thu Jan 1 00:00:00 1970
170+++ linux/lib/rbtree.c Sat Aug 10 20:39:46 2002
171@@ -0,0 +1,296 @@
172+/*
173+ Red Black Trees
174+ (C) 1999 Andrea Arcangeli <andrea@suse.de>
175+
176+ This program is free software; you can redistribute it and/or modify
177+ it under the terms of the GNU General Public License as published by
178+ the Free Software Foundation; either version 2 of the License, or
179+ (at your option) any later version.
180+
181+ This program is distributed in the hope that it will be useful,
182+ but WITHOUT ANY WARRANTY; without even the implied warranty of
183+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
184+ GNU General Public License for more details.
185+
186+ You should have received a copy of the GNU General Public License
187+ along with this program; if not, write to the Free Software
188+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
189+
190+ linux/lib/rbtree.c
191+*/
192+
193+#include <linux/rbtree.h>
194+#include <linux/module.h>
195+
196+static void __rb_rotate_left(rb_node_t * node, rb_root_t * root)
197+{
198+ rb_node_t * right = node->rb_right;
199+
200+ if ((node->rb_right = right->rb_left))
201+ right->rb_left->rb_parent = node;
202+ right->rb_left = node;
203+
204+ if ((right->rb_parent = node->rb_parent))
205+ {
206+ if (node == node->rb_parent->rb_left)
207+ node->rb_parent->rb_left = right;
208+ else
209+ node->rb_parent->rb_right = right;
210+ }
211+ else
212+ root->rb_node = right;
213+ node->rb_parent = right;
214+}
215+
216+static void __rb_rotate_right(rb_node_t * node, rb_root_t * root)
217+{
218+ rb_node_t * left = node->rb_left;
219+
220+ if ((node->rb_left = left->rb_right))
221+ left->rb_right->rb_parent = node;
222+ left->rb_right = node;
223+
224+ if ((left->rb_parent = node->rb_parent))
225+ {
226+ if (node == node->rb_parent->rb_right)
227+ node->rb_parent->rb_right = left;
228+ else
229+ node->rb_parent->rb_left = left;
230+ }
231+ else
232+ root->rb_node = left;
233+ node->rb_parent = left;
234+}
235+
236+void rb_insert_color(rb_node_t * node, rb_root_t * root)
237+{
238+ rb_node_t * parent, * gparent;
239+
240+ while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
241+ {
242+ gparent = parent->rb_parent;
243+
244+ if (parent == gparent->rb_left)
245+ {
246+ {
247+ register rb_node_t * uncle = gparent->rb_right;
248+ if (uncle && uncle->rb_color == RB_RED)
249+ {
250+ uncle->rb_color = RB_BLACK;
251+ parent->rb_color = RB_BLACK;
252+ gparent->rb_color = RB_RED;
253+ node = gparent;
254+ continue;
255+ }
256+ }
257+
258+ if (parent->rb_right == node)
259+ {
260+ register rb_node_t * tmp;
261+ __rb_rotate_left(parent, root);
262+ tmp = parent;
263+ parent = node;
264+ node = tmp;
265+ }
266+
267+ parent->rb_color = RB_BLACK;
268+ gparent->rb_color = RB_RED;
269+ __rb_rotate_right(gparent, root);
270+ } else {
271+ {
272+ register rb_node_t * uncle = gparent->rb_left;
273+ if (uncle && uncle->rb_color == RB_RED)
274+ {
275+ uncle->rb_color = RB_BLACK;
276+ parent->rb_color = RB_BLACK;
277+ gparent->rb_color = RB_RED;
278+ node = gparent;
279+ continue;
280+ }
281+ }
282+
283+ if (parent->rb_left == node)
284+ {
285+ register rb_node_t * tmp;
286+ __rb_rotate_right(parent, root);
287+ tmp = parent;
288+ parent = node;
289+ node = tmp;
290+ }
291+
292+ parent->rb_color = RB_BLACK;
293+ gparent->rb_color = RB_RED;
294+ __rb_rotate_left(gparent, root);
295+ }
296+ }
297+
298+ root->rb_node->rb_color = RB_BLACK;
299+}
300+EXPORT_SYMBOL(rb_insert_color);
301+
302+static void __rb_erase_color(rb_node_t * node, rb_node_t * parent,
303+ rb_root_t * root)
304+{
305+ rb_node_t * other;
306+
307+ while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
308+ {
309+ if (parent->rb_left == node)
310+ {
311+ other = parent->rb_right;
312+ if (other->rb_color == RB_RED)
313+ {
314+ other->rb_color = RB_BLACK;
315+ parent->rb_color = RB_RED;
316+ __rb_rotate_left(parent, root);
317+ other = parent->rb_right;
318+ }
319+ if ((!other->rb_left ||
320+ other->rb_left->rb_color == RB_BLACK)
321+ && (!other->rb_right ||
322+ other->rb_right->rb_color == RB_BLACK))
323+ {
324+ other->rb_color = RB_RED;
325+ node = parent;
326+ parent = node->rb_parent;
327+ }
328+ else
329+ {
330+ if (!other->rb_right ||
331+ other->rb_right->rb_color == RB_BLACK)
332+ {
333+ register rb_node_t * o_left;
334+ if ((o_left = other->rb_left))
335+ o_left->rb_color = RB_BLACK;
336+ other->rb_color = RB_RED;
337+ __rb_rotate_right(other, root);
338+ other = parent->rb_right;
339+ }
340+ other->rb_color = parent->rb_color;
341+ parent->rb_color = RB_BLACK;
342+ if (other->rb_right)
343+ other->rb_right->rb_color = RB_BLACK;
344+ __rb_rotate_left(parent, root);
345+ node = root->rb_node;
346+ break;
347+ }
348+ }
349+ else
350+ {
351+ other = parent->rb_left;
352+ if (other->rb_color == RB_RED)
353+ {
354+ other->rb_color = RB_BLACK;
355+ parent->rb_color = RB_RED;
356+ __rb_rotate_right(parent, root);
357+ other = parent->rb_left;
358+ }
359+ if ((!other->rb_left ||
360+ other->rb_left->rb_color == RB_BLACK)
361+ && (!other->rb_right ||
362+ other->rb_right->rb_color == RB_BLACK))
363+ {
364+ other->rb_color = RB_RED;
365+ node = parent;
366+ parent = node->rb_parent;
367+ }
368+ else
369+ {
370+ if (!other->rb_left ||
371+ other->rb_left->rb_color == RB_BLACK)
372+ {
373+ register rb_node_t * o_right;
374+ if ((o_right = other->rb_right))
375+ o_right->rb_color = RB_BLACK;
376+ other->rb_color = RB_RED;
377+ __rb_rotate_left(other, root);
378+ other = parent->rb_left;
379+ }
380+ other->rb_color = parent->rb_color;
381+ parent->rb_color = RB_BLACK;
382+ if (other->rb_left)
383+ other->rb_left->rb_color = RB_BLACK;
384+ __rb_rotate_right(parent, root);
385+ node = root->rb_node;
386+ break;
387+ }
388+ }
389+ }
390+ if (node)
391+ node->rb_color = RB_BLACK;
392+}
393+
394+void rb_erase(rb_node_t * node, rb_root_t * root)
395+{
396+ rb_node_t * child, * parent;
397+ int color;
398+
399+ if (!node->rb_left)
400+ child = node->rb_right;
401+ else if (!node->rb_right)
402+ child = node->rb_left;
403+ else
404+ {
405+ rb_node_t * old = node, * left;
406+
407+ node = node->rb_right;
408+ while ((left = node->rb_left))
409+ node = left;
410+ child = node->rb_right;
411+ parent = node->rb_parent;
412+ color = node->rb_color;
413+
414+ if (child)
415+ child->rb_parent = parent;
416+ if (parent)
417+ {
418+ if (parent->rb_left == node)
419+ parent->rb_left = child;
420+ else
421+ parent->rb_right = child;
422+ }
423+ else
424+ root->rb_node = child;
425+
426+ if (node->rb_parent == old)
427+ parent = node;
428+ node->rb_parent = old->rb_parent;
429+ node->rb_color = old->rb_color;
430+ node->rb_right = old->rb_right;
431+ node->rb_left = old->rb_left;
432+
433+ if (old->rb_parent)
434+ {
435+ if (old->rb_parent->rb_left == old)
436+ old->rb_parent->rb_left = node;
437+ else
438+ old->rb_parent->rb_right = node;
439+ } else
440+ root->rb_node = node;
441+
442+ old->rb_left->rb_parent = node;
443+ if (old->rb_right)
444+ old->rb_right->rb_parent = node;
445+ goto color;
446+ }
447+
448+ parent = node->rb_parent;
449+ color = node->rb_color;
450+
451+ if (child)
452+ child->rb_parent = parent;
453+ if (parent)
454+ {
455+ if (parent->rb_left == node)
456+ parent->rb_left = child;
457+ else
458+ parent->rb_right = child;
459+ }
460+ else
461+ root->rb_node = child;
462+
463+ color:
464+ if (color == RB_BLACK)
465+ __rb_erase_color(child, parent, root);
466+}
467+EXPORT_SYMBOL(rb_erase);
The Linux kernel (the core of the Linux operating system)
This page took 7.193168 seconds and 4 git commands to generate.