OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

Compare Revisions

  • This comparison shows the changes necessary to convert path 
    /openrisc/trunk/rtos/ecos-2.0/packages/compat/linux
    from Rev 27 to Rev 174
    ↔ Reverse comparison
  •

Rev 27 → Rev 174

/v2_0/cdl/linux.cdl
0,0 → 1,64
# ====================================================================
#
# linux.cdl
#
# Linux compatibility layer data
#
# ====================================================================
#####ECOSGPLCOPYRIGHTBEGIN####
## -------------------------------------------
## This file is part of eCos, the Embedded Configurable Operating System.
## Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 Red Hat, Inc.
##
## eCos is free software; you can redistribute it and/or modify it under
## the terms of the GNU General Public License as published by the Free
## Software Foundation; either version 2 or (at your option) any later version.
##
## eCos is distributed in the hope that it will be useful, but WITHOUT ANY
## WARRANTY; without even the implied warranty of MERCHANTABILITY or
## FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
## for more details.
##
## You should have received a copy of the GNU General Public License along
## with eCos; if not, write to the Free Software Foundation, Inc.,
## 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
##
## As a special exception, if other files instantiate templates or use macros
## or inline functions from this file, or you compile this file and link it
## with other works to produce a work based on this file, this file does not
## by itself cause the resulting work to be covered by the GNU General Public
## License. However the source code for this file must still be made available
## in accordance with section (3) of the GNU General Public License.
##
## This exception does not invalidate any other reasons why a work based on
## this file might be covered by the GNU General Public License.
##
## Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
## at http://sources.redhat.com/ecos/ecos-license/
## -------------------------------------------
#####ECOSGPLCOPYRIGHTEND####
# ====================================================================
######DESCRIPTIONBEGIN####
#
# Author(s): dwmw2
# Contributors:
# Date: 2003-01-08
#
#####DESCRIPTIONEND####
#
# ====================================================================
 
cdl_package CYGPKG_LINUX_COMPAT {
display "Linux compatibility layer"
include_dir ""
description "
eCos supports a basic Linux compatibility Layer providing various
functions, equivalents or stubs expected by Linux kernel code, for
assistance in porting drivers and file system code from Linux.
Note this does not provide Linux compatibility to applications."
 
compile rbtree.c
 
}
 
# EOF linux.cdl
/v2_0/include/linux/mtd/compatmac.h
0,0 → 1,5
#ifndef __LINUX_MTD_COMPATMAC_H__
#define __LINUX_MTD_COMPATMAC_H__
 
 
#endif /* __LINUX_MTD_COMPATMAC_H__ */
/v2_0/include/linux/mtd/mtd.h
0,0 → 1,5
#ifndef __LINUX_MTD_MTD_H__
#define __LINUX_MTD_MTD_H__
 
 
#endif /* __LINUX_MTD_MTD_H__ */
/v2_0/include/linux/zlib.h
0,0 → 1,14
#ifndef __LINUX_ZLIB_H__
#define __LINUX_ZLIB_H__
 
#include <cyg/compress/zlib.h>
 
#define zlib_deflateInit(x,y) deflateInit(x,y)
#define zlib_deflate(x,y) deflate(x,y)
#define zlib_deflateEnd(x) deflateEnd(x)
#define zlib_inflateInit(x) inflateInit(x)
#define zlib_inflateInit2(x,y) inflateInit2(x,y)
#define zlib_inflate(x,y) inflate(x,y)
#define zlib_inflateEnd(x) inflateEnd(x)
 
#endif /* __LINUX_ZLIB_H__ */
/v2_0/include/linux/wait.h
0,0 → 1,15
#ifndef __LINUX_WAIT_H__
#define __LINUX_WAIT_H__
 
 
typedef struct { } wait_queue_head_t;
 
#define init_waitqueue_head(wait) do{} while (0)
#define add_wait_queue(wait,new_wait) do{} while (0)
#define remove_wait_queue(wait,old_wait) do{} while (0)
#define DECLARE_WAITQUEUE(wait,current) do{} while (0)
 
static inline void wake_up(wait_queue_head_t *erase_wait)
{ /* Only used for waking up threads blocks on erases. Not used in eCos */ }
 
#endif /* __LINUX_WAIT_H__ */
/v2_0/include/linux/types.h
0,0 → 1,12
#ifndef __LINUX_TYPES_H__
#define __LINUX_TYPES_H__
 
#include "cyg/infra/cyg_type.h"
 
#define uint8_t cyg_uint8
#define uint16_t cyg_uint16
#define uint32_t cyg_uint32
#define loff_t off_t
 
#endif /* __LINUX_TYPES_H__ */
 
/v2_0/include/linux/config.h
0,0 → 1,5
#ifndef __LINUX_CONFIG_H__
#define __LINUX_CONFIG_H__
 
 
#endif /* __LINUX_CONFIG_H__ */
/v2_0/include/linux/string.h
0,0 → 1,6
#ifndef __LINUX_STRING_H__
#define __LINUX_STRING_H__
 
#include <string.h>
 
#endif /* __LINUX_STRING_H__ */
/v2_0/include/linux/zutil.h
0,0 → 1,6
#ifndef __LINUX_ZUTIL_H__
#define __LINUX_ZUTIL_H__
 
#define PRESET_DICT 0x20 /* preset dictionary flag in zlib header */
 
#endif /* __LINUX_ZUTIL_H__ */
/v2_0/include/linux/fs.h
0,0 → 1,13
#ifndef __LINUX_FS_H__
#define __LINUX_FS_H__
 
#include <linux/stat.h>
/*
* File types
*/
#define DT_UNKNOWN 0
#define DT_DIR 4
#define DT_REG 8
 
 
#endif /* __LINUX_FS_H__ */
/v2_0/include/linux/completion.h
0,0 → 1,7
#ifndef __LINUX_COMPLETION_H__
#define __LINUX_COMPLETION_H__
 
struct completion { } ;
 
#endif /* __LINUX_COMPLETION_H__ */
 
/v2_0/include/linux/compiler.h
0,0 → 1,7
#ifndef __LINUX_COMPILER_H__
#define __LINUX_COMPILER_H__
 
#define likely(x) (x)
#define unlikely(x) (x)
 
#endif /* __LINUX_COMPILER_H__ */
/v2_0/include/linux/pagemap.h
0,0 → 1,19
#ifndef __LINUX_PAGEMAP_H__
#define __LINUX_PAGEMAP_H__
 
#include <asm/bug.h>
#include <asm/page.h>
 
#define PAGE_CACHE_SHIFT PAGE_SHIFT
#define PAGE_CACHE_SIZE PAGE_SIZE
 
#define PageLocked(pg) 1
#define Page_Uptodate(pg) 0
#define UnlockPage(pg)
#define PAGE_BUG(pg) BUG()
#define ClearPageUptodate(pg)
#define SetPageError(pg)
#define ClearPageError(pg)
#define SetPageUptodate(pg)
 
#endif /* __LINUX_PAGEMAP_H__ */
/v2_0/include/linux/list.h
0,0 → 1,127
/*
* JFFS2 -- Journalling Flash File System, Version 2.
*
* Copyright (C) 2002 Red Hat, Inc.
*
* Created by Jonathan Larmour <jlarmour@redhat.com>
*
*===========================================================================
*####ECOSGPLCOPYRIGHTBEGIN####
* -------------------------------------------
* This file is part of eCos, the Embedded Configurable Operating System.
* Copyright (C) 2003 Red Hat.
*
* eCos is free software; you can redistribute it and/or modify it under
* the terms of the GNU General Public License as published by the Free
* Software Foundation; either version 2 or (at your option) any later version.
*
* eCos is distributed in the hope that it will be useful, but WITHOUT ANY
* WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* for more details.
*
* You should have received a copy of the GNU General Public License along
* with eCos; if not, write to the Free Software Foundation, Inc.,
* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
*
* As a special exception, if other files instantiate templates or use macros
* or inline functions from this file, or you compile this file and link it
* with other works to produce a work based on this file, this file does not
* by itself cause the resulting work to be covered by the GNU General Public
* License. However the source code for this file must still be made available
* in accordance with section (3) of the GNU General Public License.
*
* This exception does not invalidate any other reasons why a work based on
* this file might be covered by the GNU General Public License.
*
* Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
* at http://sources.redhat.com/ecos/ecos-license/
* -------------------------------------------
*####ECOSGPLCOPYRIGHTEND####
*===========================================================================
*
*/
 
#ifndef CYGONCE_FS_JFFS2_LIST_H
#define CYGONCE_FS_JFFS2_LIST_H
 
 
/* -----------------------------------------------------------------------*/
 
/* Doubly linked list implementation to replace the GPL'd one used in
the Linux kernel. */
 
#include <stddef.h>
#include <cyg/infra/cyg_type.h>
 
/* TYPES */
 
struct list_head {
struct list_head *next;
struct list_head *prev;
};
 
/* MACROS */
 
#define INIT_LIST_HEAD( _list_ ) \
CYG_MACRO_START \
(_list_)->next = (_list_)->prev = (_list_); \
CYG_MACRO_END
 
/* FUNCTIONS */
 
/* Insert an entry _after_ the specified entry */
static __inline__ void
list_add( struct list_head *newent, struct list_head *afterthisent )
{
struct list_head *next = afterthisent->next;
newent->next = next;
newent->prev = afterthisent;
afterthisent->next = newent;
next->prev = newent;
} /* list_add() */
 
/* Insert an entry _before_ the specified entry */
static __inline__ void
list_add_tail( struct list_head *newent, struct list_head *beforethisent )
{
struct list_head *prev = beforethisent->prev;
newent->prev = prev;
newent->next = beforethisent;
beforethisent->prev = newent;
prev->next = newent;
} /* list_add_tail() */
 
/* Delete the specified entry */
static __inline__ void
list_del( struct list_head *ent )
{
ent->prev->next = ent->next;
ent->next->prev = ent->prev;
} /* list_del() */
 
/* Is this list empty? */
static __inline__ int
list_empty( struct list_head *list )
{
return ( list->next == list );
} /* list_empty() */
 
/* list_entry - Assuming you have a struct of type _type_ that contains a
list which has the name _member_ in that struct type, then given the
address of that list in the struct, _list_, this returns the address
of the container structure */
 
#define list_entry( _list_, _type_, _member_ ) \
((_type_ *)((char *)(_list_)-(char *)(offsetof(_type_,_member_))))
 
/* list_for_each - using _ent_, iterate through list _list_ */
 
#define list_for_each( _ent_, _list_ ) \
for ( (_ent_) = (_list_)->next; \
(_ent_) != (_list_); \
(_ent_) = (_ent_)->next )
 
/* -----------------------------------------------------------------------*/
#endif /* #ifndef CYGONCE_FS_JFFS2_LIST_H */
/* EOF list.h */
/v2_0/include/linux/stat.h
0,0 → 1,34
#ifndef __LINUX_STAT_H__
#define __LINUX_STAT_H__
 
 
#include <sys/stat.h>
 
/* FIXME: eCos doesn't define bits for symlinks or sockets. In fact,
since the inode types are mutually exclusive, it's a bit of a waste
of space to have separate bits for each type. */
#ifndef __stat_mode_LNK
#define __stat_mode_LNK (1<<19)
#define S_ISLNK(__mode) ((__mode) & __stat_mode_LNK)
#endif
#ifndef __stat_mode_SOCK
#define __stat_mode_SOCK (1<<20)
#define S_ISSOCK(__mode) ((__mode) & __stat_mode_SOCK)
#endif
 
#define S_IFMT 0x18001F
 
#define S_IFDIR __stat_mode_DIR
#define S_IFREG __stat_mode_REG
#define S_IFBLK __stat_mode_BLK
#define S_IFCHR __stat_mode_CHR
#define S_IFLNK __stat_mode_LNK
#define S_IFSOCK __stat_mode_SOCK
#define S_IFIFO __stat_mode_FIFO
 
#define S_IRUGO (S_IRUSR|S_IRGRP|S_IROTH)
#define S_IWUGO (S_IWUSR|S_IWGRP|S_IWOTH)
#define S_IXUGO (S_IXUSR|S_IXGRP|S_IXOTH)
#define S_IRWXUGO (S_IRWXU|S_IRWXG|S_IRWXO)
 
#endif /* __LINUX_STAT_H__ */
/v2_0/include/linux/crc32.h
0,0 → 1,8
#ifndef CRC32_H
#define CRC32_H
 
#include <cyg/crc/crc.h>
 
#define crc32(val, s, len) cyg_crc32_accumulate(val, (unsigned char *)s, len)
 
#endif
/v2_0/include/linux/TODO
0,0 → 1,11
 
This contains a very limited set of Linux-compatibility headers, initially
just for getting JFFS2 to build.
 
Some things are simply stubs which don't _work_, to allow the JFFS2 code
to compile. Note that you may need to implement these _properly_ in order
to use these for making other Linux code work, or indeed for making the
JFFS2 NAND support work.
 
The non-working parts include, but are not limited to:
workqueue.h, wait.h, timer.h, spinlock.h, sched.h, compiler.h
/v2_0/include/linux/kernel.h
0,0 → 1,28
#ifndef __LINUX_KERNEL_H__
#define __LINUX_KERNEL_H__
#include <cyg/infra/diag.h>
 
#define jiffies 100
 
#define ERR_PTR(err) (void*)(err)
#define PTR_ERR(err) (cyg_int32)(err)
#define IS_ERR(err) (err==NULL)
 
#define CURRENT_TIME cyg_timestamp()
 
#define KERN_EMERG "<0>" // system is unusable
#define KERN_ALERT "<1>" // action must be taken immediately
#define KERN_CRIT "<2>" // critical conditions
#define KERN_ERR "<3>" // error conditions
#define KERN_WARNING "<4>" // warning conditions
#define KERN_NOTICE "<5>" // normal but significant condition
#define KERN_INFO "<6>" // informational
#define KERN_DEBUG "<7>" // debug-level messages
#define printk diag_printf
 
#define min(x,y) (x<y?x:y)
#define max(x,y) (x<y?y:x)
#define min_t(t, x,y) ((t)x<(t)y?(t)x:(t)y)
 
 
#endif /* __LINUX_KERNEL_H__ */
/v2_0/include/linux/timer.h
0,0 → 1,10
#ifndef __LINUX_TIMER_H__
#define __LINUX_TIMER_H__
 
/* Not yet */
 
struct timer_list { } ;
 
 
#endif /* __LINUX_TIMER_H__ */
 
/v2_0/include/linux/slab.h
0,0 → 1,12
#ifndef __LINUX_SLAB_H__
#define __LINUX_SLAB_H__
 
#include <stdlib.h>
 
#include <asm/page.h> /* Don't ask. Linux headers are a mess. */
 
#define kmalloc(x, y) malloc(x)
#define kfree(x) free(x)
 
#endif /* __LINUX_SLAB_H__ */
 
/v2_0/include/linux/spinlock.h
0,0 → 1,13
#ifndef __LINUX_SPINLOCK_H__
#define __LINUX_SPINLOCK_H__
 
 
typedef struct { } spinlock_t;
#define SPIN_LOCK_UNLOCKED (spinlock_t) { }
#define spin_lock_init(lock) do{} while (0)
#define spin_lock(lock) do{} while (0)
#define spin_unlock(lock) do{} while (0)
#define spin_lock_bh(lock) do{} while (0)
#define spin_unlock_bh(lock) do{} while (0)
 
#endif /* __LINUX_SPINLOCK_H__ */
/v2_0/include/linux/rbtree.h
0,0 → 1,46
#ifndef _LINUX_RBTREE_H
#define _LINUX_RBTREE_H
 
 
struct rb_node {
struct rb_node *rb_left; /* left element */
struct rb_node *rb_right; /* right element */
struct rb_node *rb_parent; /* parent element */
int rb_color; /* node color */
};
 
struct rb_root {
struct rb_node *rb_node; /* root of the tree */
};
#define NULL ((void *)0)
#define RB_ROOT ((struct rb_root){NULL})
#define rb_entry(p, container, field) \
((container *) ((void *)p - ((void *)&(((container *)0)->field))))
 
#define RB_BLACK 0
#define RB_RED 1
 
 
extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);
 
/* Find logical next and previous nodes in a tree */
extern struct rb_node *rb_next(struct rb_node *);
extern struct rb_node *rb_prev(struct rb_node *);
extern struct rb_node *rb_first(struct rb_root *);
 
/* Fast replacement of a single node without remove/rebalance/add/rebalance */
extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
struct rb_root *root);
 
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
struct rb_node ** rb_link)
{
node->rb_parent = parent;
node->rb_color = RB_RED;
node->rb_left = node->rb_right = NULL;
 
*rb_link = node;
}
 
#endif /* _LINUX_RBTREE_H */
/v2_0/include/linux/errno.h
0,0 → 1,46
#include <errno.h>
/v2_0/include/linux/version.h
0,0 → 1,5
#ifndef __LINUX_VERSION_H__
#define __LINUX_VERSION_H__
 
 
#endif /* __LINUX_VERSION_H__ */
/v2_0/include/linux/sched.h
0,0 → 1,7
#ifndef __LINUX_SCHED_H__
#define __LINUX_SCHED_H__
 
#define cond_resched() do { } while(0)
#define signal_pending(x) (0)
 
#endif /* __LINUX_SCHED_H__ */
/v2_0/include/linux/workqueue.h
0,0 → 1,11
#ifndef __LINUX_WORKQUEUE_H__
#define __LINUX_WORKQUEUE_H__
 
/* We don't do this yet */
struct work_struct { } ;
 
#define INIT_WORK(x,y,z) /* */
#define schedule_work(x) do { } while(0)
#define flush_scheduled_work() do { } while(0)
 
#endif /* __LINUX_WORKQUEUE_H__ */
/v2_0/include/asm/atomic.h
0,0 → 1,10
#ifndef __ASM_ATOMIC_H__
#define __ASM_ATOMIC_H__
 
#define atomic_t int
#define atomic_inc(atom) (*atom)++
#define atomic_dec(atom) (*atom)--
#define atomic_read(atom) (*atom)
 
 
#endif /* __ASM_ATOMIC_H__ */
/v2_0/include/asm/page.h
0,0 → 1,10
#ifndef __ASM_PAGE_H__
#define __ASM_PAGE_H__
 
/* These aren't used by much yet. If that changes, you might want
to make them actually correct :) */
#define PAGE_SHIFT 0xC
#define PAGE_SIZE (0x1 << PAGE_SHIFT)
 
 
#endif /* __ASM_PAGE_H__ */
/v2_0/include/asm/bug.h
0,0 → 1,6
#ifndef __ASM_BUG_H__
#define __ASM_BUG_H__
 
#define BUG() do { diag_printf("BUG() at %s %d\n", __FILE__, __LINE__); *(int *)0=0; } while (0)
 
#endif /* __ASM_BUG_H__ */
/v2_0/include/asm/semaphore.h
0,0 → 1,20
#ifndef __ASM_SEMAPHORE_H__
#define __ASM_SEMAPHORE_H__
 
#include <cyg/hal/drv_api.h>
 
struct semaphore {
cyg_drv_mutex_t x;
};
 
#define DECLARE_MUTEX(x) struct semaphore x = { { 0 } };
#define DECLARE_MUTEX_LOCKED(x) struct semaphore x = { { 1 } };
 
#define init_MUTEX(sem) cyg_drv_mutex_init((cyg_drv_mutex_t *)sem)
#define init_MUTEX_LOCKED(sem) do { cyg_drv_mutex_init((cyg_drv_mutex_t *)sem); cyg_drv_mutex_lock((cyg_drv_mutex_t *)sem); } while(0)
#define down(sem) cyg_drv_mutex_lock((cyg_drv_mutex_t *)sem)
#define down_interruptible(sem) ({ cyg_drv_mutex_lock((cyg_drv_mutex_t *)sem), 0; })
#define down_trylock(sem) cyg_drv_mutex_trylock((cyg_drv_mutex_t *)sem)
#define up(sem) cyg_drv_mutex_unlock((cyg_drv_mutex_t *)sem)
 
#endif /* __ASM_SEMAPHORE_H__ */
/v2_0/ChangeLog
0,0 → 1,38
2003-01-21 David Woodhouse <dwmw2@infradead.org>
 
* New package.
 
//===========================================================================
//####ECOSGPLCOPYRIGHTBEGIN####
// -------------------------------------------
// This file is part of eCos, the Embedded Configurable Operating System.
// Copyright (C) 2003 Red Hat.
//
// eCos is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 2 or (at your option) any later version.
//
// eCos is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
// for more details.
//
// You should have received a copy of the GNU General Public License along
// with eCos; if not, write to the Free Software Foundation, Inc.,
// 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
//
// As a special exception, if other files instantiate templates or use macros
// or inline functions from this file, or you compile this file and link it
// with other works to produce a work based on this file, this file does not
// by itself cause the resulting work to be covered by the GNU General Public
// License. However the source code for this file must still be made available
// in accordance with section (3) of the GNU General Public License.
//
// This exception does not invalidate any other reasons why a work based on
// this file might be covered by the GNU General Public License.
//
// Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
// at http://sources.redhat.com/ecos/ecos-license/
// -------------------------------------------
//####ECOSGPLCOPYRIGHTEND####
//===========================================================================
/v2_0/src/rbtree.c
0,0 → 1,409
/*========================================================================
//
// rbtree.c
//
// Red Black tree implementation
//
//========================================================================
//####ECOSGPLCOPYRIGHTBEGIN####
// -------------------------------------------
// This file is part of eCos, the Embedded Configurable Operating System.
// Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 Red Hat, Inc.
//
// eCos is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 2 or (at your option) any later version.
//
// eCos is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
// for more details.
//
// You should have received a copy of the GNU General Public License along
// with eCos; if not, write to the Free Software Foundation, Inc.,
// 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
//
// As a special exception, if other files instantiate templates or use macros
// or inline functions from this file, or you compile this file and link it
// with other works to produce a work based on this file, this file does not
// by itself cause the resulting work to be covered by the GNU General Public
// License. However the source code for this file must still be made available
// in accordance with section (3) of the GNU General Public License.
//
// This exception does not invalidate any other reasons why a work based on
// this file might be covered by the GNU General Public License.
//
// Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
// at http://sources.redhat.com/ecos/ecos-license/
// -------------------------------------------
//####ECOSGPLCOPYRIGHTEND####
//========================================================================
//#####DESCRIPTIONBEGIN####
//
// Author(s): Niels Provos/OpenBSD
// Contributors: dwmw2
// Date: 2003-01-21
// Purpose: This file provides an implementation of red-black trees.
// Description: Derived from OpenBSD src/sys/sys/tree.h
// Usage:
//
//####DESCRIPTIONEND####
//
//======================================================================
*/
 
/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
/*
* Copyright 2002 Niels Provos <provos@citi.umich.edu>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
/* Fields renamed to match Linux ones. */
#include <linux/rbtree.h>
 
 
#define RB_HEAD(head) (head)->rb_node
#define RB_LEFT(elm) (elm)->rb_left
#define RB_RIGHT(elm) (elm)->rb_right
#define RB_PARENT(elm) (elm)->rb_parent
#define RB_COLOR(elm) (elm)->rb_color
 
 
#define RB_SET(elm, parent) do { \
RB_PARENT(elm) = parent; \
RB_LEFT(elm) = RB_RIGHT(elm) = NULL; \
RB_COLOR(elm) = RB_RED; \
} while (0)
 
#define RB_SET_BLACKRED(black, red) do { \
RB_COLOR(black) = RB_BLACK; \
RB_COLOR(red) = RB_RED; \
} while (0)
 
#ifndef RB_AUGMENT
#define RB_AUGMENT(x)
#endif
 
#define RB_ROTATE_LEFT(head, elm, tmp) do { \
(tmp) = RB_RIGHT(elm); \
if ((RB_RIGHT(elm) = RB_LEFT(tmp))) { \
RB_PARENT(RB_LEFT(tmp)) = (elm); \
} \
RB_AUGMENT(elm); \
if ((RB_PARENT(tmp) = RB_PARENT(elm))) { \
if ((elm) == RB_LEFT(RB_PARENT(elm))) \
RB_LEFT(RB_PARENT(elm)) = (tmp); \
else \
RB_RIGHT(RB_PARENT(elm)) = (tmp); \
} else \
(head)->rb_node = (tmp); \
RB_LEFT(tmp) = (elm); \
RB_PARENT(elm) = (tmp); \
RB_AUGMENT(tmp); \
if ((RB_PARENT(tmp))) \
RB_AUGMENT(RB_PARENT(tmp)); \
} while (0)
 
#define RB_ROTATE_RIGHT(head, elm, tmp) do { \
(tmp) = RB_LEFT(elm); \
if ((RB_LEFT(elm) = RB_RIGHT(tmp))) { \
RB_PARENT(RB_RIGHT(tmp)) = (elm); \
} \
RB_AUGMENT(elm); \
if ((RB_PARENT(tmp) = RB_PARENT(elm))) { \
if ((elm) == RB_LEFT(RB_PARENT(elm))) \
RB_LEFT(RB_PARENT(elm)) = (tmp); \
else \
RB_RIGHT(RB_PARENT(elm)) = (tmp); \
} else \
(head)->rb_node = (tmp); \
RB_RIGHT(tmp) = (elm); \
RB_PARENT(elm) = (tmp); \
RB_AUGMENT(tmp); \
if ((RB_PARENT(tmp))) \
RB_AUGMENT(RB_PARENT(tmp)); \
} while(0)
 
/* Note args swapped to match Linux */
void rb_insert_color(struct rb_node *elm, struct rb_root *head)
{
struct rb_node *parent, *gparent, *tmp;
while ((parent = RB_PARENT(elm)) &&
RB_COLOR(parent) == RB_RED) {
gparent = RB_PARENT(parent);
if (parent == RB_LEFT(gparent)) {
tmp = RB_RIGHT(gparent);
if (tmp && RB_COLOR(tmp) == RB_RED) {
RB_COLOR(tmp) = RB_BLACK;
RB_SET_BLACKRED(parent, gparent);
elm = gparent;
continue;
}
if (RB_RIGHT(parent) == elm) {
RB_ROTATE_LEFT(head, parent, tmp);
tmp = parent;
parent = elm;
elm = tmp;
}
RB_SET_BLACKRED(parent, gparent);
RB_ROTATE_RIGHT(head, gparent, tmp);
} else {
tmp = RB_LEFT(gparent);
if (tmp && RB_COLOR(tmp) == RB_RED) {
RB_COLOR(tmp) = RB_BLACK;
RB_SET_BLACKRED(parent, gparent);
elm = gparent;
continue;
}
if (RB_LEFT(parent) == elm) {
RB_ROTATE_RIGHT(head, parent, tmp);
tmp = parent;
parent = elm;
elm = tmp;
}
RB_SET_BLACKRED(parent, gparent);
RB_ROTATE_LEFT(head, gparent, tmp);
}
}
RB_COLOR(head->rb_node) = RB_BLACK;
}
 
 
static void rb_remove_color(struct rb_root *head, struct rb_node *parent,
struct rb_node *elm)
{
struct rb_node *tmp;
while ((elm == NULL || RB_COLOR(elm) == RB_BLACK) &&
elm != RB_HEAD(head)) {
if (RB_LEFT(parent) == elm) {
tmp = RB_RIGHT(parent);
if (RB_COLOR(tmp) == RB_RED) {
RB_SET_BLACKRED(tmp, parent);
RB_ROTATE_LEFT(head, parent, tmp);
tmp = RB_RIGHT(parent);
}
if ((RB_LEFT(tmp) == NULL ||
RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
(RB_RIGHT(tmp) == NULL ||
RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
RB_COLOR(tmp) = RB_RED;
elm = parent;
parent = RB_PARENT(elm);
} else {
if (RB_RIGHT(tmp) == NULL ||
RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK) {
struct rb_node *oleft;
if ((oleft = RB_LEFT(tmp)))
RB_COLOR(oleft) = RB_BLACK;
RB_COLOR(tmp) = RB_RED;
RB_ROTATE_RIGHT(head, tmp, oleft);
tmp = RB_RIGHT(parent);
}
RB_COLOR(tmp) = RB_COLOR(parent);
RB_COLOR(parent) = RB_BLACK;
if (RB_RIGHT(tmp))
RB_COLOR(RB_RIGHT(tmp)) = RB_BLACK;
RB_ROTATE_LEFT(head, parent, tmp);
elm = RB_HEAD(head);
break;
}
} else {
tmp = RB_LEFT(parent);
if (RB_COLOR(tmp) == RB_RED) {
RB_SET_BLACKRED(tmp, parent);
RB_ROTATE_RIGHT(head, parent, tmp);
tmp = RB_LEFT(parent);
}
if ((RB_LEFT(tmp) == NULL ||
RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
(RB_RIGHT(tmp) == NULL ||
RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
RB_COLOR(tmp) = RB_RED;
elm = parent;
parent = RB_PARENT(elm);
} else {
if (RB_LEFT(tmp) == NULL ||
RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) {
struct rb_node *oright;
if ((oright = RB_RIGHT(tmp)))
RB_COLOR(oright) = RB_BLACK;
RB_COLOR(tmp) = RB_RED;
RB_ROTATE_LEFT(head, tmp, oright);
tmp = RB_LEFT(parent);
}
RB_COLOR(tmp) = RB_COLOR(parent);
RB_COLOR(parent) = RB_BLACK;
if (RB_LEFT(tmp))
RB_COLOR(RB_LEFT(tmp)) = RB_BLACK;
RB_ROTATE_RIGHT(head, parent, tmp);
elm = RB_HEAD(head);
break;
}
}
}
if (elm)
RB_COLOR(elm) = RB_BLACK;
}
 
/* Note name changed. Guess why :) */
void rb_erase(struct rb_node *elm, struct rb_root *head)
{
struct rb_node *child, *parent, *old = elm;
int color;
if (RB_LEFT(elm) == NULL)
child = RB_RIGHT(elm);
else if (RB_RIGHT(elm) == NULL)
child = RB_LEFT(elm);
else {
struct rb_node *left;
elm = RB_RIGHT(elm);
while ((left = RB_LEFT(elm)))
elm = left;
child = RB_RIGHT(elm);
parent = RB_PARENT(elm);
color = RB_COLOR(elm);
if (child)
RB_PARENT(child) = parent;
if (parent) {
if (RB_LEFT(parent) == elm)
RB_LEFT(parent) = child;
else
RB_RIGHT(parent) = child;
RB_AUGMENT(parent);
} else
RB_HEAD(head) = child;
if (RB_PARENT(elm) == old)
parent = elm;
(elm) = (old);
if (RB_PARENT(old)) {
if (RB_LEFT(RB_PARENT(old)) == old)
RB_LEFT(RB_PARENT(old)) = elm;
else
RB_RIGHT(RB_PARENT(old)) = elm;
RB_AUGMENT(RB_PARENT(old));
} else
RB_HEAD(head) = elm;
RB_PARENT(RB_LEFT(old)) = elm;
if (RB_RIGHT(old))
RB_PARENT(RB_RIGHT(old)) = elm;
if (parent) {
left = parent;
do {
RB_AUGMENT(left);
} while ((left = RB_PARENT(left)));
}
goto color;
}
parent = RB_PARENT(elm);
color = RB_COLOR(elm);
if (child)
RB_PARENT(child) = parent;
if (parent) {
if (RB_LEFT(parent) == elm)
RB_LEFT(parent) = child;
else
RB_RIGHT(parent) = child;
RB_AUGMENT(parent);
} else
RB_HEAD(head) = child;
color:
if (color == RB_BLACK)
rb_remove_color(head, parent, child);
}
 
struct rb_node *rb_next(struct rb_node *elm)
{
if (RB_RIGHT(elm)) {
elm = RB_RIGHT(elm);
while (RB_LEFT(elm))
elm = RB_LEFT(elm);
} else {
if (RB_PARENT(elm) &&
(elm == RB_LEFT(RB_PARENT(elm))))
elm = RB_PARENT(elm);
else {
while (RB_PARENT(elm) &&
(elm == RB_RIGHT(RB_PARENT(elm))))
elm = RB_PARENT(elm);
elm = RB_PARENT(elm);
}
}
return (elm);
}
 
struct rb_node *rb_prev(struct rb_node *elm)
{
if (RB_LEFT(elm)) {
elm = RB_LEFT(elm);
while (RB_RIGHT(elm))
elm = RB_RIGHT(elm);
} else {
if (RB_PARENT(elm) &&
(elm == RB_RIGHT(RB_PARENT(elm))))
elm = RB_PARENT(elm);
else {
while (RB_PARENT(elm) &&
(elm == RB_LEFT(RB_PARENT(elm))))
elm = RB_PARENT(elm);
elm = RB_PARENT(elm);
}
}
return (elm);
}
 
/* These ones are lifted from Linux -- but that's OK because I
wrote them. dwmw2. */
struct rb_node *rb_first(struct rb_root *root)
{
struct rb_node *n;
 
n = root->rb_node;
if (!n)
return 0;
while (n->rb_left)
n = n->rb_left;
return n;
}
 
void rb_replace_node(struct rb_node *victim, struct rb_node *new,
struct rb_root *root)
{
struct rb_node *parent = victim->rb_parent;
 
/* Set the surrounding nodes to point to the replacement */
if (parent) {
if (victim == parent->rb_left)
parent->rb_left = new;
else
parent->rb_right = new;
} else {
root->rb_node = new;
}
if (victim->rb_left)
victim->rb_left->rb_parent = new;
if (victim->rb_right)
victim->rb_right->rb_parent = new;
 
/* Copy the pointers/colour from the victim to the replacement */
*new = *victim;
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.