source: rtems/cpukit/libfs/src/jffs2/src/compat-rbtree.c @ 672038b

4.11
Last change on this file since 672038b was 672038b, checked in by Sebastian Huber <sebastian.huber@…>, on Sep 12, 2013 at 2:46:51 PM

JFFS2: Import from eCos

Import of Linux compatibility layer and JFFS2 file system support from
eCos.

The files are imported from eCos CVS on 2013-09-16.

cvs -d :pserver:anoncvs@ecos.sourceware.org:/cvs/ecos login
cvs -z3 -d :pserver:anoncvs@ecos.sourceware.org:/cvs/ecos co -P ecos

The files

"ecos/packages/compat/linux/current/asm/atomic.h",
"ecos/packages/compat/linux/current/asm/bug.h",
"ecos/packages/compat/linux/current/asm/page.h",
"ecos/packages/compat/linux/current/cyg/crc/crc.h",
"ecos/packages/compat/linux/current/cyg/infra/cyg_type.h",
"ecos/packages/compat/linux/current/linux/compiler.h",
"ecos/packages/compat/linux/current/linux/completion.h",
"ecos/packages/compat/linux/current/linux/config.h",
"ecos/packages/compat/linux/current/linux/crc32.h",
"ecos/packages/compat/linux/current/linux/errno.h",
"ecos/packages/compat/linux/current/linux/fs.h",
"ecos/packages/compat/linux/current/linux/kernel.h",
"ecos/packages/compat/linux/current/linux/list.h",
"ecos/packages/compat/linux/current/linux/mtd/compatmac.h",
"ecos/packages/compat/linux/current/linux/mtd/mtd.h",
"ecos/packages/compat/linux/current/linux/pagemap.h",
"ecos/packages/compat/linux/current/linux/rbtree.h",
"ecos/packages/compat/linux/current/linux/rwsem.h",
"ecos/packages/compat/linux/current/linux/sched.h",
"ecos/packages/compat/linux/current/linux/slab.h",
"ecos/packages/compat/linux/current/linux/spinlock.h",
"ecos/packages/compat/linux/current/linux/stat.h",
"ecos/packages/compat/linux/current/linux/string.h",
"ecos/packages/compat/linux/current/linux/timer.h",
"ecos/packages/compat/linux/current/linux/types.h",
"ecos/packages/compat/linux/current/linux/version.h",
"ecos/packages/compat/linux/current/linux/vmalloc.h",
"ecos/packages/compat/linux/current/linux/wait.h",
"ecos/packages/compat/linux/current/linux/workqueue.h", and
"ecos/packages/compat/linux/current/linux/zlib.h"
"ecos/packages/compat/linux/current/linux/zutil.h"

are copied to "cpukit/libfs/src/jffs2/include".

The file "ecos/packages/services/crc/current/src/crc32.c" is copied to
"cpukit/libfs/src/jffs2/src/compat-crc32.c".

The file "ecos/packages/compat/linux/current/src/rbtree.c" is copied to
"cpukit/libfs/src/jffs2/src/compat-rbtree.c".

The file "ecos/packages/fs/jffs2/current/src/dir-ecos.c" is copied to
"cpukit/libfs/src/jffs2/src/dir-rtems.c".

The file "ecos/packages/fs/jffs2/current/src/flashio.c" is copied to
"cpukit/libfs/src/jffs2/src/flashio.c".

The file "ecos/packages/fs/jffs2/current/src/fs-ecos.c" is copied to
"cpukit/libfs/src/jffs2/src/fs-rtems.c".

The file "ecos/packages/fs/jffs2/current/src/malloc-ecos.c" is copied to
"cpukit/libfs/src/jffs2/src/malloc-rtems.c".

The file "ecos/packages/fs/jffs2/current/src/os-ecos.h" is copied to
"cpukit/libfs/src/jffs2/src/os-rtems.h".

The LICENSE file referenced in some files of this patch set is part of a
previous patch set imported from Linux.

  • Property mode set to 100644
File size: 12.1 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} while (0)
125
126#define RB_ROTATE_RIGHT(head, elm, tmp) do {                    \
127        (tmp) = RB_LEFT(elm);                                   \
128        if ((RB_LEFT(elm) = RB_RIGHT(tmp))) {                   \
129                RB_PARENT(RB_RIGHT(tmp)) = (elm);               \
130        }                                                       \
131        RB_AUGMENT(elm);                                        \
132        if ((RB_PARENT(tmp) = RB_PARENT(elm))) {                \
133                if ((elm) == RB_LEFT(RB_PARENT(elm)))           \
134                        RB_LEFT(RB_PARENT(elm)) = (tmp);        \
135                else                                            \
136                        RB_RIGHT(RB_PARENT(elm)) = (tmp);       \
137        } else                                                  \
138                (head)->rb_node = (tmp);                        \
139        RB_RIGHT(tmp) = (elm);                                  \
140        RB_PARENT(elm) = (tmp);                                 \
141        RB_AUGMENT(tmp);                                        \
142        if ((RB_PARENT(tmp)))                                   \
143                RB_AUGMENT(RB_PARENT(tmp));                     \
144} while(0)
145
146/* Note args swapped to match Linux */
147void rb_insert_color(struct rb_node *elm, struct rb_root *head)
148{
149        struct rb_node *parent, *gparent, *tmp;
150        while ((parent = RB_PARENT(elm)) &&
151            RB_COLOR(parent) == RB_RED) {
152                gparent = RB_PARENT(parent);
153                if (parent == RB_LEFT(gparent)) {
154                        tmp = RB_RIGHT(gparent);
155                        if (tmp && RB_COLOR(tmp) == RB_RED) {
156                                RB_COLOR(tmp) = RB_BLACK;
157                                RB_SET_BLACKRED(parent, gparent);
158                                elm = gparent;
159                                continue;
160                        }
161                        if (RB_RIGHT(parent) == elm) {
162                                RB_ROTATE_LEFT(head, parent, tmp);
163                                tmp = parent;
164                                parent = elm;
165                                elm = tmp;
166                        }
167                        RB_SET_BLACKRED(parent, gparent);
168                        RB_ROTATE_RIGHT(head, gparent, tmp);
169                } else {
170                        tmp = RB_LEFT(gparent);
171                        if (tmp && RB_COLOR(tmp) == RB_RED) {
172                                RB_COLOR(tmp) = RB_BLACK;
173                                RB_SET_BLACKRED(parent, gparent);
174                                elm = gparent;
175                                continue;
176                        }
177                        if (RB_LEFT(parent) == elm) {
178                                RB_ROTATE_RIGHT(head, parent, tmp);
179                                tmp = parent;
180                                parent = elm;
181                                elm = tmp;
182                        }
183                        RB_SET_BLACKRED(parent, gparent);
184                        RB_ROTATE_LEFT(head, gparent, tmp);
185                }
186        }
187        RB_COLOR(head->rb_node) = RB_BLACK;
188}
189
190
191static void rb_remove_color(struct rb_root *head, struct rb_node *parent,
192                            struct rb_node *elm)
193{
194        struct rb_node *tmp;
195        while ((elm == NULL || RB_COLOR(elm) == RB_BLACK) &&
196            elm != RB_HEAD(head)) {
197                if (RB_LEFT(parent) == elm) {
198                        tmp = RB_RIGHT(parent);
199                        if (RB_COLOR(tmp) == RB_RED) {
200                                RB_SET_BLACKRED(tmp, parent);
201                                RB_ROTATE_LEFT(head, parent, tmp);
202                                tmp = RB_RIGHT(parent);
203                        }
204                        if ((RB_LEFT(tmp) == NULL ||
205                            RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
206                            (RB_RIGHT(tmp) == NULL ||
207                            RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
208                                RB_COLOR(tmp) = RB_RED;
209                                elm = parent;
210                                parent = RB_PARENT(elm);
211                        } else {
212                                if (RB_RIGHT(tmp) == NULL ||
213                                    RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK) {
214                                        struct rb_node *oleft;
215                                        if ((oleft = RB_LEFT(tmp)))
216                                                RB_COLOR(oleft) = RB_BLACK;
217                                        RB_COLOR(tmp) = RB_RED;
218                                        RB_ROTATE_RIGHT(head, tmp, oleft);
219                                        tmp = RB_RIGHT(parent);
220                                }
221                                RB_COLOR(tmp) = RB_COLOR(parent);
222                                RB_COLOR(parent) = RB_BLACK;
223                                if (RB_RIGHT(tmp))
224                                        RB_COLOR(RB_RIGHT(tmp)) = RB_BLACK;
225                                RB_ROTATE_LEFT(head, parent, tmp);
226                                elm = RB_HEAD(head);
227                                break;
228                        }
229                } else {
230                        tmp = RB_LEFT(parent);
231                        if (RB_COLOR(tmp) == RB_RED) {
232                                RB_SET_BLACKRED(tmp, parent);
233                                RB_ROTATE_RIGHT(head, parent, tmp);
234                                tmp = RB_LEFT(parent);
235                        }
236                        if ((RB_LEFT(tmp) == NULL ||
237                            RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
238                            (RB_RIGHT(tmp) == NULL ||
239                            RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
240                                RB_COLOR(tmp) = RB_RED;
241                                elm = parent;
242                                parent = RB_PARENT(elm);
243                        } else {
244                                if (RB_LEFT(tmp) == NULL ||
245                                    RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) {
246                                        struct rb_node *oright;
247                                        if ((oright = RB_RIGHT(tmp)))
248                                                RB_COLOR(oright) = RB_BLACK;
249                                        RB_COLOR(tmp) = RB_RED;
250                                        RB_ROTATE_LEFT(head, tmp, oright);
251                                        tmp = RB_LEFT(parent);
252                                }
253                                RB_COLOR(tmp) = RB_COLOR(parent);
254                                RB_COLOR(parent) = RB_BLACK;
255                                if (RB_LEFT(tmp))
256                                        RB_COLOR(RB_LEFT(tmp)) = RB_BLACK;
257                                RB_ROTATE_RIGHT(head, parent, tmp);
258                                elm = RB_HEAD(head);
259                                break;
260                        }
261                }
262        }
263        if (elm)
264                RB_COLOR(elm) = RB_BLACK;
265}
266
267/* Note name changed. Guess why :) */
268void rb_erase(struct rb_node *elm, struct rb_root *head)
269{
270        struct rb_node *child, *parent, *old = elm;
271        int color;
272        if (RB_LEFT(elm) == NULL)
273                child = RB_RIGHT(elm);
274        else if (RB_RIGHT(elm) == NULL)
275                child = RB_LEFT(elm);
276        else {
277                struct rb_node *left;
278                elm = RB_RIGHT(elm);
279                while ((left = RB_LEFT(elm)))
280                        elm = left;
281                child = RB_RIGHT(elm);
282                parent = RB_PARENT(elm);
283                color = RB_COLOR(elm);
284                if (child)
285                        RB_PARENT(child) = parent;
286                if (parent) {
287                        if (RB_LEFT(parent) == elm)
288                                RB_LEFT(parent) = child;
289                        else
290                                RB_RIGHT(parent) = child;
291                        RB_AUGMENT(parent);
292                } else
293                        RB_HEAD(head) = child;
294                if (RB_PARENT(elm) == old)
295                        parent = elm;
296                *(elm) = *(old);
297                if (RB_PARENT(old)) {
298                        if (RB_LEFT(RB_PARENT(old)) == old)
299                                RB_LEFT(RB_PARENT(old)) = elm;
300                        else
301                                RB_RIGHT(RB_PARENT(old)) = elm;
302                        RB_AUGMENT(RB_PARENT(old));
303                } else
304                        RB_HEAD(head) = elm;
305                RB_PARENT(RB_LEFT(old)) = elm;
306                if (RB_RIGHT(old))
307                        RB_PARENT(RB_RIGHT(old)) = elm;
308                if (parent) {
309                        left = parent;
310                        do {
311                                RB_AUGMENT(left);
312                        } while ((left = RB_PARENT(left)));
313                }
314                goto color;
315        }
316        parent = RB_PARENT(elm);
317        color = RB_COLOR(elm);
318        if (child)
319                RB_PARENT(child) = parent;
320        if (parent) {
321                if (RB_LEFT(parent) == elm)
322                        RB_LEFT(parent) = child;
323                else
324                        RB_RIGHT(parent) = child;
325                RB_AUGMENT(parent);
326        } else
327                RB_HEAD(head) = child;
328color:
329        if (color == RB_BLACK)
330                rb_remove_color(head, parent, child);
331}
332
333struct rb_node *rb_next(struct rb_node *elm)
334{
335        if (RB_RIGHT(elm)) {
336                elm = RB_RIGHT(elm);
337                while (RB_LEFT(elm))
338                        elm = RB_LEFT(elm);
339        } else {
340                if (RB_PARENT(elm) &&
341                    (elm == RB_LEFT(RB_PARENT(elm))))
342                        elm = RB_PARENT(elm);
343                else {
344                        while (RB_PARENT(elm) &&
345                            (elm == RB_RIGHT(RB_PARENT(elm))))
346                                elm = RB_PARENT(elm);
347                        elm = RB_PARENT(elm);
348                }
349        }
350        return (elm);
351}
352
353struct rb_node *rb_prev(struct rb_node *elm)
354{
355        if (RB_LEFT(elm)) {
356                elm = RB_LEFT(elm);
357                while (RB_RIGHT(elm))
358                        elm = RB_RIGHT(elm);
359        } else {
360                if (RB_PARENT(elm) &&
361                    (elm == RB_RIGHT(RB_PARENT(elm))))
362                        elm = RB_PARENT(elm);
363                else {
364                        while (RB_PARENT(elm) &&
365                            (elm == RB_LEFT(RB_PARENT(elm))))
366                                elm = RB_PARENT(elm);
367                        elm = RB_PARENT(elm);
368                }
369        }
370        return (elm);
371}
372
373/* These ones are lifted from Linux -- but that's OK because I
374   wrote them. dwmw2. */
375struct rb_node *rb_first(struct rb_root *root)
376{
377        struct rb_node  *n;
378
379        n = root->rb_node;
380        if (!n)
381                return 0;
382        while (n->rb_left)
383                n = n->rb_left;
384        return n;
385}
386
387void rb_replace_node(struct rb_node *victim, struct rb_node *new,
388                     struct rb_root *root)
389{
390        struct rb_node *parent = victim->rb_parent;
391
392        /* Set the surrounding nodes to point to the replacement */
393        if (parent) {
394                if (victim == parent->rb_left)
395                        parent->rb_left = new;
396                else
397                        parent->rb_right = new;
398        } else {
399                root->rb_node = new;
400        }
401        if (victim->rb_left)
402                victim->rb_left->rb_parent = new;
403        if (victim->rb_right)
404                victim->rb_right->rb_parent = new;
405
406        /* Copy the pointers/colour from the victim to the replacement */
407        *new = *victim;
408}
Note: See TracBrowser for help on using the repository browser.