This is the mail archive of the
ecos-patches@sources.redhat.com
mailing list for the eCos project.
Basic linux kernel compatibility package
- From: Jonathan Larmour <jifl at eCosCentric dot com>
- To: eCos Patches List <ecos-patches at sources dot redhat dot com>
- Date: Wed, 22 Jan 2003 01:09:46 +0000
- Subject: Basic linux kernel compatibility package
This adds a basic linux kernel compatibility package. This isn't
compatibility for Linux applications, but Linux kernel drivers and
filesystems. In fact, this is entirely geared towards JFFS2 :). From dwmw2
with some embellishments by me.
Jifl
--
eCosCentric http://www.eCosCentric.com/ <info@eCosCentric.com>
--[ "You can complain because roses have thorns, or you ]--
--[ can rejoice because thorns have roses." -Lincoln ]-- Opinions==mine
Index: ChangeLog
===================================================================
RCS file: /cvs/ecos/ecos/packages/ChangeLog,v
retrieving revision 1.91
diff -u -5 -p -r1.91 ChangeLog
--- ChangeLog 4 Jan 2003 03:42:26 -0000 1.91
+++ ChangeLog 22 Jan 2003 01:07:44 -0000
@@ -1,5 +1,11 @@
+2003-01-22 Jonathan Larmour <jifl@eCosCentric.com>
+
+ * ecos.db: Add CYGPKG_LINUX_COMPAT. Not a compatibility layer
+ for Linux applications, but Linux drivers and filesystems.
+ Intended for an updated JFFS2.
+
2002-12-24 Gary Thomas <gary@mlbassoc.com>
* ecos.db: Add port to Cogent CSB281 (PowerPC 8245)
2002-12-22 Nick Garnett <nickg@ecoscentric.com>
Index: ecos.db
===================================================================
RCS file: /cvs/ecos/ecos/packages/ecos.db,v
retrieving revision 1.84
diff -u -5 -p -r1.84 ecos.db
--- ecos.db 24 Dec 2002 16:00:44 -0000 1.84
+++ ecos.db 22 Jan 2003 01:07:46 -0000
@@ -992,10 +992,21 @@ package CYGPKG_FS_JFFS2 {
script jffs2.cdl
description "
This package contains the JFFS2 filesystem."
}
+package CYGPKG_LINUX_COMPAT {
+ alias { "Linux compatibility" linux_compat linuxcompat }
+ directory compat/linux
+ script linux.cdl
+ 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."
+}
+
package CYGPKG_IO_ETH_DRIVERS {
alias { "Common ethernet support" net_drivers eth_drivers CYGPKG_NET_ETH_DRIVERS }
directory io/eth
script eth_drivers.cdl
description "Platform independent ethernet support."
Index: compat/linux/current/ChangeLog
===================================================================
RCS file: compat/linux/current/ChangeLog
diff -N compat/linux/current/ChangeLog
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/ChangeLog 22 Jan 2003 01:07:46 -0000
@@ -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####
+//===========================================================================
Index: compat/linux/current/cdl/linux.cdl
===================================================================
RCS file: compat/linux/current/cdl/linux.cdl
diff -N compat/linux/current/cdl/linux.cdl
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/cdl/linux.cdl 22 Jan 2003 01:07:46 -0000
@@ -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
Index: compat/linux/current/include/asm/atomic.h
===================================================================
RCS file: compat/linux/current/include/asm/atomic.h
diff -N compat/linux/current/include/asm/atomic.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/asm/atomic.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/asm/bug.h
===================================================================
RCS file: compat/linux/current/include/asm/bug.h
diff -N compat/linux/current/include/asm/bug.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/asm/bug.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/asm/page.h
===================================================================
RCS file: compat/linux/current/include/asm/page.h
diff -N compat/linux/current/include/asm/page.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/asm/page.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/asm/semaphore.h
===================================================================
RCS file: compat/linux/current/include/asm/semaphore.h
diff -N compat/linux/current/include/asm/semaphore.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/asm/semaphore.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/linux/TODO
===================================================================
RCS file: compat/linux/current/include/linux/TODO
diff -N compat/linux/current/include/linux/TODO
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/TODO 22 Jan 2003 01:07:46 -0000
@@ -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
Index: compat/linux/current/include/linux/compiler.h
===================================================================
RCS file: compat/linux/current/include/linux/compiler.h
diff -N compat/linux/current/include/linux/compiler.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/compiler.h 22 Jan 2003 01:07:46 -0000
@@ -0,0 +1,7 @@
+#ifndef __LINUX_COMPILER_H__
+#define __LINUX_COMPILER_H__
+
+#define likely(x) (x)
+#define unlikely(x) (x)
+
+#endif /* __LINUX_COMPILER_H__ */
Index: compat/linux/current/include/linux/completion.h
===================================================================
RCS file: compat/linux/current/include/linux/completion.h
diff -N compat/linux/current/include/linux/completion.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/completion.h 22 Jan 2003 01:07:46 -0000
@@ -0,0 +1,7 @@
+#ifndef __LINUX_COMPLETION_H__
+#define __LINUX_COMPLETION_H__
+
+struct completion { } ;
+
+#endif /* __LINUX_COMPLETION_H__ */
+
Index: compat/linux/current/include/linux/config.h
===================================================================
RCS file: compat/linux/current/include/linux/config.h
diff -N compat/linux/current/include/linux/config.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/config.h 22 Jan 2003 01:07:46 -0000
@@ -0,0 +1,5 @@
+#ifndef __LINUX_CONFIG_H__
+#define __LINUX_CONFIG_H__
+
+
+#endif /* __LINUX_CONFIG_H__ */
Index: compat/linux/current/include/linux/crc32.h
===================================================================
RCS file: compat/linux/current/include/linux/crc32.h
diff -N compat/linux/current/include/linux/crc32.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/crc32.h 22 Jan 2003 01:07:46 -0000
@@ -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
Index: compat/linux/current/include/linux/errno.h
===================================================================
RCS file: compat/linux/current/include/linux/errno.h
diff -N compat/linux/current/include/linux/errno.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/errno.h 22 Jan 2003 01:07:46 -0000
@@ -0,0 +1 @@
+#include <errno.h>
Index: compat/linux/current/include/linux/fs.h
===================================================================
RCS file: compat/linux/current/include/linux/fs.h
diff -N compat/linux/current/include/linux/fs.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/fs.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/linux/kernel.h
===================================================================
RCS file: compat/linux/current/include/linux/kernel.h
diff -N compat/linux/current/include/linux/kernel.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/kernel.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/linux/list.h
===================================================================
RCS file: compat/linux/current/include/linux/list.h
diff -N compat/linux/current/include/linux/list.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/list.h 22 Jan 2003 01:07:46 -0000
@@ -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 */
Index: compat/linux/current/include/linux/pagemap.h
===================================================================
RCS file: compat/linux/current/include/linux/pagemap.h
diff -N compat/linux/current/include/linux/pagemap.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/pagemap.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/linux/rbtree.h
===================================================================
RCS file: compat/linux/current/include/linux/rbtree.h
diff -N compat/linux/current/include/linux/rbtree.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/rbtree.h 22 Jan 2003 01:07:46 -0000
@@ -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 */
Index: compat/linux/current/include/linux/sched.h
===================================================================
RCS file: compat/linux/current/include/linux/sched.h
diff -N compat/linux/current/include/linux/sched.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/sched.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/linux/slab.h
===================================================================
RCS file: compat/linux/current/include/linux/slab.h
diff -N compat/linux/current/include/linux/slab.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/slab.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
+
Index: compat/linux/current/include/linux/spinlock.h
===================================================================
RCS file: compat/linux/current/include/linux/spinlock.h
diff -N compat/linux/current/include/linux/spinlock.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/spinlock.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/linux/stat.h
===================================================================
RCS file: compat/linux/current/include/linux/stat.h
diff -N compat/linux/current/include/linux/stat.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/stat.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/linux/string.h
===================================================================
RCS file: compat/linux/current/include/linux/string.h
diff -N compat/linux/current/include/linux/string.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/string.h 22 Jan 2003 01:07:46 -0000
@@ -0,0 +1,6 @@
+#ifndef __LINUX_STRING_H__
+#define __LINUX_STRING_H__
+
+#include <string.h>
+
+#endif /* __LINUX_STRING_H__ */
Index: compat/linux/current/include/linux/timer.h
===================================================================
RCS file: compat/linux/current/include/linux/timer.h
diff -N compat/linux/current/include/linux/timer.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/timer.h 22 Jan 2003 01:07:46 -0000
@@ -0,0 +1,10 @@
+#ifndef __LINUX_TIMER_H__
+#define __LINUX_TIMER_H__
+
+/* Not yet */
+
+struct timer_list { } ;
+
+
+#endif /* __LINUX_TIMER_H__ */
+
Index: compat/linux/current/include/linux/types.h
===================================================================
RCS file: compat/linux/current/include/linux/types.h
diff -N compat/linux/current/include/linux/types.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/types.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
+
Index: compat/linux/current/include/linux/version.h
===================================================================
RCS file: compat/linux/current/include/linux/version.h
diff -N compat/linux/current/include/linux/version.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/version.h 22 Jan 2003 01:07:46 -0000
@@ -0,0 +1,5 @@
+#ifndef __LINUX_VERSION_H__
+#define __LINUX_VERSION_H__
+
+
+#endif /* __LINUX_VERSION_H__ */
Index: compat/linux/current/include/linux/wait.h
===================================================================
RCS file: compat/linux/current/include/linux/wait.h
diff -N compat/linux/current/include/linux/wait.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/wait.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/linux/workqueue.h
===================================================================
RCS file: compat/linux/current/include/linux/workqueue.h
diff -N compat/linux/current/include/linux/workqueue.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/workqueue.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/linux/zlib.h
===================================================================
RCS file: compat/linux/current/include/linux/zlib.h
diff -N compat/linux/current/include/linux/zlib.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/zlib.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/linux/zutil.h
===================================================================
RCS file: compat/linux/current/include/linux/zutil.h
diff -N compat/linux/current/include/linux/zutil.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/zutil.h 22 Jan 2003 01:07:46 -0000
@@ -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__ */
Index: compat/linux/current/include/linux/mtd/compatmac.h
===================================================================
RCS file: compat/linux/current/include/linux/mtd/compatmac.h
diff -N compat/linux/current/include/linux/mtd/compatmac.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/mtd/compatmac.h 22 Jan 2003 01:07:46 -0000
@@ -0,0 +1,5 @@
+#ifndef __LINUX_MTD_COMPATMAC_H__
+#define __LINUX_MTD_COMPATMAC_H__
+
+
+#endif /* __LINUX_MTD_COMPATMAC_H__ */
Index: compat/linux/current/include/linux/mtd/mtd.h
===================================================================
RCS file: compat/linux/current/include/linux/mtd/mtd.h
diff -N compat/linux/current/include/linux/mtd/mtd.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/include/linux/mtd/mtd.h 22 Jan 2003 01:07:46 -0000
@@ -0,0 +1,5 @@
+#ifndef __LINUX_MTD_MTD_H__
+#define __LINUX_MTD_MTD_H__
+
+
+#endif /* __LINUX_MTD_MTD_H__ */
Index: compat/linux/current/src/rbtree.c
===================================================================
RCS file: compat/linux/current/src/rbtree.c
diff -N compat/linux/current/src/rbtree.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compat/linux/current/src/rbtree.c 22 Jan 2003 01:07:47 -0000
@@ -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;
+}