Context Navigation

compat-rbtree.c @ 78b85286

4.115

Last change on this file since 78b85286 was 78b85286, checked in by Sebastian Huber <sebastian.huber@…>, on 09/12/13 at 14:53:41

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

Rev	Line
[672038b]	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); \
[78b85286]	122	if ((RB_PARENT(tmp))) { \
[672038b]	123	RB_AUGMENT(RB_PARENT(tmp)); \
[78b85286]	124	} \
[672038b]	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); \
[78b85286]	143	if ((RB_PARENT(tmp))) { \
[672038b]	144	RB_AUGMENT(RB_PARENT(tmp)); \
[78b85286]	145	} \
[672038b]	146	} while(0)
	147
	148	/* Note args swapped to match Linux */
	149	void 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
	193	static 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 :) */
	270	void 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;
	330	color:
	331	if (color == RB_BLACK)
	332	rb_remove_color(head, parent, child);
	333	}
	334
	335	struct 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
	355	struct 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. */
	377	struct 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
[78b85286]	389	struct 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
[672038b]	401	void 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.

Context Navigation

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

Download in other formats: