URL
https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk
Subversion Repositories openrisc_me
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/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/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/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/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/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/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/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/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/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/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; |
} |
/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#### |
//=========================================================================== |