rbtree-2.2.21-1.diff

   1 diff -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:
  15 diff -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 */
 152 diff -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
 168 diff -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);