source: rtems/cpukit/libfs/src/jffs2/src/compat-rbtree.c @ 78b85286

4.11
Last change on this file since 78b85286 was 78b85286, checked in by Sebastian Huber <sebastian.huber@…>, on Sep 12, 2013 at 2:53:41 PM

JFFS2: Update Linux compatibility layer

Modify compatbility layer for RTEMS. Add support for Linux 3.11 based
JFFS2.

  • Property mode set to 100644
File size: 12.3 KB
Line 
1/*========================================================================
2//
3//      rbtree.c
4//
5//      Red Black tree implementation
6//
7//========================================================================
8// ####ECOSGPLCOPYRIGHTBEGIN####                                           
9// -------------------------------------------                             
10// This file is part of eCos, the Embedded Configurable Operating System.   
11// Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
12//
13// eCos is free software; you can redistribute it and/or modify it under   
14// the terms of the GNU General Public License as published by the Free     
15// Software Foundation; either version 2 or (at your option) any later     
16// version.                                                                 
17//
18// eCos is distributed in the hope that it will be useful, but WITHOUT     
19// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or   
20// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License   
21// for more details.                                                       
22//
23// You should have received a copy of the GNU General Public License       
24// along with eCos; if not, write to the Free Software Foundation, Inc.,   
25// 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.           
26//
27// As a special exception, if other files instantiate templates or use     
28// macros or inline functions from this file, or you compile this file     
29// and link it with other works to produce a work based on this file,       
30// this file does not by itself cause the resulting work to be covered by   
31// the GNU General Public License. However the source code for this file   
32// must still be made available in accordance with section (3) of the GNU   
33// General Public License v2.                                               
34//
35// This exception does not invalidate any other reasons why a work based   
36// on this file might be covered by the GNU General Public License.         
37// -------------------------------------------                             
38// ####ECOSGPLCOPYRIGHTEND####                                             
39//========================================================================
40//#####DESCRIPTIONBEGIN####
41//
42// Author(s):     Niels Provos/OpenBSD
43// Contributors:  dwmw2
44// Date:          2003-01-21
45// Purpose:       This file provides an implementation of red-black trees.
46// Description:   Derived from OpenBSD src/sys/sys/tree.h
47// Usage:         
48//
49//####DESCRIPTIONEND####
50//
51//======================================================================
52*/
53
54/*      $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
55/*
56 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
57 * All rights reserved.
58 *
59 * Redistribution and use in source and binary forms, with or without
60 * modification, are permitted provided that the following conditions
61 * are met:
62 * 1. Redistributions of source code must retain the above copyright
63 *    notice, this list of conditions and the following disclaimer.
64 * 2. Redistributions in binary form must reproduce the above copyright
65 *    notice, this list of conditions and the following disclaimer in the
66 *    documentation and/or other materials provided with the distribution.
67 *
68 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
69 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
70 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
71 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
72 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
73 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
74 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
75 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
76 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
77 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
78 */
79
80/* Fields renamed to match Linux ones. */
81#include <linux/rbtree.h>
82
83
84#define RB_HEAD(head)           (head)->rb_node
85#define RB_LEFT(elm)            (elm)->rb_left
86#define RB_RIGHT(elm)           (elm)->rb_right
87#define RB_PARENT(elm)          (elm)->rb_parent
88#define RB_COLOR(elm)           (elm)->rb_color
89
90
91#define RB_SET(elm, parent) do {                                \
92        RB_PARENT(elm) = parent;                                \
93        RB_LEFT(elm) = RB_RIGHT(elm) = NULL;    \
94        RB_COLOR(elm) = RB_RED;                         \
95} while (0)
96
97#define RB_SET_BLACKRED(black, red) do {                        \
98        RB_COLOR(black) = RB_BLACK;                             \
99        RB_COLOR(red) = RB_RED;                                 \
100} while (0)
101
102#ifndef RB_AUGMENT
103#define RB_AUGMENT(x)
104#endif
105
106#define RB_ROTATE_LEFT(head, elm, tmp) do {                     \
107        (tmp) = RB_RIGHT(elm);                                  \
108        if ((RB_RIGHT(elm) = RB_LEFT(tmp))) {                   \
109                RB_PARENT(RB_LEFT(tmp)) = (elm);                \
110        }                                                       \
111        RB_AUGMENT(elm);                                        \
112        if ((RB_PARENT(tmp) = RB_PARENT(elm))) {                \
113                if ((elm) == RB_LEFT(RB_PARENT(elm)))           \
114                        RB_LEFT(RB_PARENT(elm)) = (tmp);        \
115                else                                            \
116                        RB_RIGHT(RB_PARENT(elm)) = (tmp);       \
117        } else                                                  \
118                (head)->rb_node = (tmp);                        \
119        RB_LEFT(tmp) = (elm);                                   \
120        RB_PARENT(elm) = (tmp);                                 \
121        RB_AUGMENT(tmp);                                        \
122        if ((RB_PARENT(tmp))) {                                 \
123                RB_AUGMENT(RB_PARENT(tmp));                     \
124        }                                                       \
125} while (0)
126
127#define RB_ROTATE_RIGHT(head, elm, tmp) do {                    \
128        (tmp) = RB_LEFT(elm);                                   \
129        if ((RB_LEFT(elm) = RB_RIGHT(tmp))) {                   \
130                RB_PARENT(RB_RIGHT(tmp)) = (elm);               \
131        }                                                       \
132        RB_AUGMENT(elm);                                        \
133        if ((RB_PARENT(tmp) = RB_PARENT(elm))) {                \
134                if ((elm) == RB_LEFT(RB_PARENT(elm)))           \
135                        RB_LEFT(RB_PARENT(elm)) = (tmp);        \
136                else                                            \
137                        RB_RIGHT(RB_PARENT(elm)) = (tmp);       \
138        } else                                                  \
139                (head)->rb_node = (tmp);                        \
140        RB_RIGHT(tmp) = (elm);                                  \
141        RB_PARENT(elm) = (tmp);                                 \
142        RB_AUGMENT(tmp);                                        \
143        if ((RB_PARENT(tmp))) {                                 \
144                RB_AUGMENT(RB_PARENT(tmp));                     \
145        }                                                       \
146} while(0)
147
148/* Note args swapped to match Linux */
149void rb_insert_color(struct rb_node *elm, struct rb_root *head)
150{
151        struct rb_node *parent, *gparent, *tmp;
152        while ((parent = RB_PARENT(elm)) &&
153            RB_COLOR(parent) == RB_RED) {
154                gparent = RB_PARENT(parent);
155                if (parent == RB_LEFT(gparent)) {
156                        tmp = RB_RIGHT(gparent);
157                        if (tmp && RB_COLOR(tmp) == RB_RED) {
158                                RB_COLOR(tmp) = RB_BLACK;
159                                RB_SET_BLACKRED(parent, gparent);
160                                elm = gparent;
161                                continue;
162                        }
163                        if (RB_RIGHT(parent) == elm) {
164                                RB_ROTATE_LEFT(head, parent, tmp);
165                                tmp = parent;
166                                parent = elm;
167                                elm = tmp;
168                        }
169                        RB_SET_BLACKRED(parent, gparent);
170                        RB_ROTATE_RIGHT(head, gparent, tmp);
171                } else {
172                        tmp = RB_LEFT(gparent);
173                        if (tmp && RB_COLOR(tmp) == RB_RED) {
174                                RB_COLOR(tmp) = RB_BLACK;
175                                RB_SET_BLACKRED(parent, gparent);
176                                elm = gparent;
177                                continue;
178                        }
179                        if (RB_LEFT(parent) == elm) {
180                                RB_ROTATE_RIGHT(head, parent, tmp);
181                                tmp = parent;
182                                parent = elm;
183                                elm = tmp;
184                        }
185                        RB_SET_BLACKRED(parent, gparent);
186                        RB_ROTATE_LEFT(head, gparent, tmp);
187                }
188        }
189        RB_COLOR(head->rb_node) = RB_BLACK;
190}
191
192
193static void rb_remove_color(struct rb_root *head, struct rb_node *parent,
194                            struct rb_node *elm)
195{
196        struct rb_node *tmp;
197        while ((elm == NULL || RB_COLOR(elm) == RB_BLACK) &&
198            elm != RB_HEAD(head)) {
199                if (RB_LEFT(parent) == elm) {
200                        tmp = RB_RIGHT(parent);
201                        if (RB_COLOR(tmp) == RB_RED) {
202                                RB_SET_BLACKRED(tmp, parent);
203                                RB_ROTATE_LEFT(head, parent, tmp);
204                                tmp = RB_RIGHT(parent);
205                        }
206                        if ((RB_LEFT(tmp) == NULL ||
207                            RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
208                            (RB_RIGHT(tmp) == NULL ||
209                            RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
210                                RB_COLOR(tmp) = RB_RED;
211                                elm = parent;
212                                parent = RB_PARENT(elm);
213                        } else {
214                                if (RB_RIGHT(tmp) == NULL ||
215                                    RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK) {
216                                        struct rb_node *oleft;
217                                        if ((oleft = RB_LEFT(tmp)))
218                                                RB_COLOR(oleft) = RB_BLACK;
219                                        RB_COLOR(tmp) = RB_RED;
220                                        RB_ROTATE_RIGHT(head, tmp, oleft);
221                                        tmp = RB_RIGHT(parent);
222                                }
223                                RB_COLOR(tmp) = RB_COLOR(parent);
224                                RB_COLOR(parent) = RB_BLACK;
225                                if (RB_RIGHT(tmp))
226                                        RB_COLOR(RB_RIGHT(tmp)) = RB_BLACK;
227                                RB_ROTATE_LEFT(head, parent, tmp);
228                                elm = RB_HEAD(head);
229                                break;
230                        }
231                } else {
232                        tmp = RB_LEFT(parent);
233                        if (RB_COLOR(tmp) == RB_RED) {
234                                RB_SET_BLACKRED(tmp, parent);
235                                RB_ROTATE_RIGHT(head, parent, tmp);
236                                tmp = RB_LEFT(parent);
237                        }
238                        if ((RB_LEFT(tmp) == NULL ||
239                            RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
240                            (RB_RIGHT(tmp) == NULL ||
241                            RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
242                                RB_COLOR(tmp) = RB_RED;
243                                elm = parent;
244                                parent = RB_PARENT(elm);
245                        } else {
246                                if (RB_LEFT(tmp) == NULL ||
247                                    RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) {
248                                        struct rb_node *oright;
249                                        if ((oright = RB_RIGHT(tmp)))
250                                                RB_COLOR(oright) = RB_BLACK;
251                                        RB_COLOR(tmp) = RB_RED;
252                                        RB_ROTATE_LEFT(head, tmp, oright);
253                                        tmp = RB_LEFT(parent);
254                                }
255                                RB_COLOR(tmp) = RB_COLOR(parent);
256                                RB_COLOR(parent) = RB_BLACK;
257                                if (RB_LEFT(tmp))
258                                        RB_COLOR(RB_LEFT(tmp)) = RB_BLACK;
259                                RB_ROTATE_RIGHT(head, parent, tmp);
260                                elm = RB_HEAD(head);
261                                break;
262                        }
263                }
264        }
265        if (elm)
266                RB_COLOR(elm) = RB_BLACK;
267}
268
269/* Note name changed. Guess why :) */
270void rb_erase(struct rb_node *elm, struct rb_root *head)
271{
272        struct rb_node *child, *parent, *old = elm;
273        int color;
274        if (RB_LEFT(elm) == NULL)
275                child = RB_RIGHT(elm);
276        else if (RB_RIGHT(elm) == NULL)
277                child = RB_LEFT(elm);
278        else {
279                struct rb_node *left;
280                elm = RB_RIGHT(elm);
281                while ((left = RB_LEFT(elm)))
282                        elm = left;
283                child = RB_RIGHT(elm);
284                parent = RB_PARENT(elm);
285                color = RB_COLOR(elm);
286                if (child)
287                        RB_PARENT(child) = parent;
288                if (parent) {
289                        if (RB_LEFT(parent) == elm)
290                                RB_LEFT(parent) = child;
291                        else
292                                RB_RIGHT(parent) = child;
293                        RB_AUGMENT(parent);
294                } else
295                        RB_HEAD(head) = child;
296                if (RB_PARENT(elm) == old)
297                        parent = elm;
298                *(elm) = *(old);
299                if (RB_PARENT(old)) {
300                        if (RB_LEFT(RB_PARENT(old)) == old)
301                                RB_LEFT(RB_PARENT(old)) = elm;
302                        else
303                                RB_RIGHT(RB_PARENT(old)) = elm;
304                        RB_AUGMENT(RB_PARENT(old));
305                } else
306                        RB_HEAD(head) = elm;
307                RB_PARENT(RB_LEFT(old)) = elm;
308                if (RB_RIGHT(old))
309                        RB_PARENT(RB_RIGHT(old)) = elm;
310                if (parent) {
311                        left = parent;
312                        do {
313                                RB_AUGMENT(left);
314                        } while ((left = RB_PARENT(left)));
315                }
316                goto color;
317        }
318        parent = RB_PARENT(elm);
319        color = RB_COLOR(elm);
320        if (child)
321                RB_PARENT(child) = parent;
322        if (parent) {
323                if (RB_LEFT(parent) == elm)
324                        RB_LEFT(parent) = child;
325                else
326                        RB_RIGHT(parent) = child;
327                RB_AUGMENT(parent);
328        } else
329                RB_HEAD(head) = child;
330color:
331        if (color == RB_BLACK)
332                rb_remove_color(head, parent, child);
333}
334
335struct rb_node *rb_next(struct rb_node *elm)
336{
337        if (RB_RIGHT(elm)) {
338                elm = RB_RIGHT(elm);
339                while (RB_LEFT(elm))
340                        elm = RB_LEFT(elm);
341        } else {
342                if (RB_PARENT(elm) &&
343                    (elm == RB_LEFT(RB_PARENT(elm))))
344                        elm = RB_PARENT(elm);
345                else {
346                        while (RB_PARENT(elm) &&
347                            (elm == RB_RIGHT(RB_PARENT(elm))))
348                                elm = RB_PARENT(elm);
349                        elm = RB_PARENT(elm);
350                }
351        }
352        return (elm);
353}
354
355struct rb_node *rb_prev(struct rb_node *elm)
356{
357        if (RB_LEFT(elm)) {
358                elm = RB_LEFT(elm);
359                while (RB_RIGHT(elm))
360                        elm = RB_RIGHT(elm);
361        } else {
362                if (RB_PARENT(elm) &&
363                    (elm == RB_RIGHT(RB_PARENT(elm))))
364                        elm = RB_PARENT(elm);
365                else {
366                        while (RB_PARENT(elm) &&
367                            (elm == RB_LEFT(RB_PARENT(elm))))
368                                elm = RB_PARENT(elm);
369                        elm = RB_PARENT(elm);
370                }
371        }
372        return (elm);
373}
374
375/* These ones are lifted from Linux -- but that's OK because I
376   wrote them. dwmw2. */
377struct rb_node *rb_first(struct rb_root *root)
378{
379        struct rb_node  *n;
380
381        n = root->rb_node;
382        if (!n)
383                return 0;
384        while (n->rb_left)
385                n = n->rb_left;
386        return n;
387}
388
389struct rb_node *rb_last(struct rb_root *root)
390{
391        struct rb_node  *n;
392
393        n = root->rb_node;
394        if (!n)
395                return 0;
396        while (n->rb_right)
397                n = n->rb_right;
398        return n;
399}
400
401void rb_replace_node(struct rb_node *victim, struct rb_node *new,
402                     struct rb_root *root)
403{
404        struct rb_node *parent = victim->rb_parent;
405
406        /* Set the surrounding nodes to point to the replacement */
407        if (parent) {
408                if (victim == parent->rb_left)
409                        parent->rb_left = new;
410                else
411                        parent->rb_right = new;
412        } else {
413                root->rb_node = new;
414        }
415        if (victim->rb_left)
416                victim->rb_left->rb_parent = new;
417        if (victim->rb_right)
418                victim->rb_right->rb_parent = new;
419
420        /* Copy the pointers/colour from the victim to the replacement */
421        *new = *victim;
422}
Note: See TracBrowser for help on using the repository browser.