Hi, In the interest of little ramdisk kernels which are ever so space constrained, I have this diff that moves the trees into external functions, thereby reducing code duplication that arises from macros.
The functions will only be used by the kernel and only when option EXTERN_TREES is enabled. The small overhead thus will only affect install kernels. I would like this tested on as many machines as possible on many architectures, both with ramdisk and normal kernels and userland. It currently shrinks my amd64 RAMDISK by 5626 bytes. Userland and non-ramdisk kernels will use the inline/macro version of the trees and should not be affected at all. The namei and vnode tree HEADs are moved to the header file, since the PROTOTYPE needs the struct layout of the RB_HEAD in EXTERN_TREES mode. Tests and ok? -- Ariane Index: arch/amd64/conf/RAMDISK =================================================================== RCS file: /cvs/src/sys/arch/amd64/conf/RAMDISK,v retrieving revision 1.52 diff -u -d -p -r1.52 RAMDISK --- arch/amd64/conf/RAMDISK 29 Jun 2011 20:52:08 -0000 1.52 +++ arch/amd64/conf/RAMDISK 22 Sep 2011 12:15:34 -0000 @@ -5,6 +5,7 @@ machine amd64 # architecture, used by option SCSITERSE option SMALL_KERNEL option NO_PROPOLICE +option EXTERN_TREES # non-inline sys/tree.h maxusers 4 # estimated number of users option TIMEZONE=0 # time zone to adjust RTC time by Index: arch/i386/conf/RAMDISK =================================================================== RCS file: /cvs/src/sys/arch/i386/conf/RAMDISK,v retrieving revision 1.177 diff -u -d -p -r1.177 RAMDISK --- arch/i386/conf/RAMDISK 29 Jun 2011 20:52:09 -0000 1.177 +++ arch/i386/conf/RAMDISK 22 Sep 2011 12:16:48 -0000 @@ -6,6 +6,7 @@ option SCSITERSE option SMALL_KERNEL option NO_PROPOLICE +option EXTERN_TREES # non-inline sys/tree.h maxusers 4 # estimated number of users option TIMEZONE=0 # time zone to adjust RTC time by Index: arch/i386/conf/RAMDISKB =================================================================== RCS file: /cvs/src/sys/arch/i386/conf/RAMDISKB,v retrieving revision 1.120 diff -u -d -p -r1.120 RAMDISKB --- arch/i386/conf/RAMDISKB 29 Jun 2011 20:52:09 -0000 1.120 +++ arch/i386/conf/RAMDISKB 22 Sep 2011 12:16:51 -0000 @@ -6,6 +6,7 @@ option SCSITERSE option SMALL_KERNEL option NO_PROPOLICE +option EXTERN_TREES # non-inline sys/tree.h maxusers 4 # estimated number of users option TIMEZONE=0 # time zone to adjust RTC time by Index: arch/i386/conf/RAMDISKC =================================================================== RCS file: /cvs/src/sys/arch/i386/conf/RAMDISKC,v retrieving revision 1.101 diff -u -d -p -r1.101 RAMDISKC --- arch/i386/conf/RAMDISKC 29 Jun 2011 20:52:09 -0000 1.101 +++ arch/i386/conf/RAMDISKC 22 Sep 2011 12:16:54 -0000 @@ -6,6 +6,7 @@ option SCSITERSE option SMALL_KERNEL option NO_PROPOLICE +option EXTERN_TREES # non-inline sys/tree.h maxusers 4 # estimated number of users option TIMEZONE=0 # time zone to adjust RTC time by Index: conf/GENERIC =================================================================== RCS file: /cvs/src/sys/conf/GENERIC,v retrieving revision 1.183 diff -u -d -p -r1.183 GENERIC --- conf/GENERIC 21 Aug 2011 20:19:56 -0000 1.183 +++ conf/GENERIC 22 Sep 2011 12:17:36 -0000 @@ -19,6 +19,7 @@ option PTRACE # ptrace(2) system call #option KVA_GUARDPAGES # slow virtual address recycling (+ guarding) option POOL_DEBUG # pool corruption detection #option VFSLCKDEBUG # VFS locking checks +#option EXTERN_TREES # non-inline sys/tree.h option CRYPTO # Cryptographic framework Index: conf/files =================================================================== RCS file: /cvs/src/sys/conf/files,v retrieving revision 1.527 diff -u -d -p -r1.527 files --- conf/files 3 Sep 2011 20:03:27 -0000 1.527 +++ conf/files 21 Sep 2011 16:44:48 -0000 @@ -731,6 +731,9 @@ file kern/subr_pool.c file kern/dma_alloc.c file kern/subr_prf.c file kern/subr_prof.c +file kern/subr_tree.c extern_trees +file kern/subr_tree_rb.c extern_trees +file kern/subr_tree_splay.c extern_trees file kern/subr_userconf.c boot_config file kern/subr_xxx.c file kern/sys_generic.c Index: kern/subr_tree.c =================================================================== RCS file: kern/subr_tree.c diff -N kern/subr_tree.c --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ kern/subr_tree.c 22 Sep 2011 12:36:56 -0000 @@ -0,0 +1,123 @@ +/* $OpenBSD: tree.h,v 1.12 2009/03/02 09:42:55 mikeb Exp $ */ +/* + * Copyright 2002 Niels Provos <[email protected]> + * Copyright 2011 Ariane van der Steldt <[email protected]> + * 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. + */ + +/* + * Implementation of tree functions common to most types of tree. + */ + +#include <sys/tree.h> + +/* + * Find the first element for which cmp(result, elm) >= 0. + */ +void * +_tree_nfind(const struct _tree_defn *defn, void *root, void *elm, + size_t left_offset, size_t right_offset) +{ + void *found = NULL; + int cmp; + + while (root != NULL) { + cmp = TREE_ENTRY_CMP(defn, elm, root); + if (cmp < 0) { + found = root; + root = *(void**) + (TREE_ENTRY(defn, char, root) + left_offset); + } else if (cmp > 0) { + root = *(void**) + (TREE_ENTRY(defn, char, root) + right_offset); + } else + return root; + } + return found; +} + +/* + * Find the element for which cmp(result, elm) == 0. + */ +void * +_tree_find(const struct _tree_defn *defn, void *root, void *elm, + size_t left_offset, size_t right_offset) +{ + int cmp; + + while (root != NULL) { + cmp = TREE_ENTRY_CMP(defn, elm, root); + if (cmp < 0) { + root = *(void**)(TREE_ENTRY(defn, char, root) + + left_offset); + } else if (cmp > 0) { + root = *(void**)(TREE_ENTRY(defn, char, root) + + right_offset); + } else + return root; + } + return NULL; +} + +/* + * Traverse the tree as far as possible using the ptr_offset in the entry. + */ +void * +_tree_minmax(const struct _tree_defn *defn, void *root, size_t ptr_offset) +{ + void *found = NULL; + + while (root != NULL) { + found = root; + root = *(void**)(TREE_ENTRY(defn, char, root) + ptr_offset); + } + return found; +} + +/* + * Find the next or previous element in a tree. + */ +void * +_tree_nextprev(const struct _tree_defn *defn, void *elm, size_t prev_offset, + size_t next_offset, size_t parent_offset) +{ + void *found; + + found = *(void**)(TREE_ENTRY(defn, char, elm) + next_offset); + if (found != NULL) + return _tree_minmax(defn, found, prev_offset); + + while (1) { + found = *(void**)(TREE_ENTRY(defn, char, elm) + + parent_offset); + if (found == NULL) + return NULL; + if (*(void**)(TREE_ENTRY(defn, char, found) + prev_offset) == + elm) { + /* found->prev = elm, found is the next element */ + return found; + } + /* found->next = elm, redo parent search using found as elm */ + elm = found; + } +} Index: kern/subr_tree_rb.c =================================================================== RCS file: kern/subr_tree_rb.c diff -N kern/subr_tree_rb.c --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ kern/subr_tree_rb.c 22 Sep 2011 12:37:01 -0000 @@ -0,0 +1,383 @@ +/* $OpenBSD: tree.h,v 1.12 2009/03/02 09:42:55 mikeb Exp $ */ +/* + * Copyright 2002 Niels Provos <[email protected]> + * Copyright 2011 Ariane van der Steldt <[email protected]> + * 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. + */ + +/* + * Specialized tree functions for red-black trees. + */ + +#include <sys/tree.h> + +void _rb_set(const struct _tree_defn*, void*, void*); +void _rb_set_blackred(const struct _tree_defn*, void*, void*); +void _rb_insert_color(const struct _tree_defn*, void**, void*); +void _rb_remove_color(const struct _tree_defn*, void**, void*, void*); +void _rb_rotate_left(const struct _tree_defn*, void**, void*); +void _rb_rotate_right(const struct _tree_defn*, void**, void*); + +/* Helper: returns the untyped entry of p. */ +#define RBE(defn, p) TREE_ENTRY(defn, struct _rb_entry_untyped, (p)) + +void +_rb_set(const struct _tree_defn *defn, void *elm, void *parent) +{ + RBE(defn, elm)->rbe_parent = parent; + RBE(defn, elm)->rbe_left = RBE(defn, elm)->rbe_right = NULL; + RBE(defn, elm)->rbe_color = RB_RED; +} + +void +_rb_set_blackred(const struct _tree_defn *defn, void *black, void *red) +{ + RBE(defn, black)->rbe_color = RB_BLACK; + RBE(defn, red)->rbe_color = RB_RED; +} + +void +_rb_rotate_left(const struct _tree_defn *defn, void **head, void *elm) +{ + void *tmp; + + tmp = RBE(defn, elm)->rbe_right; + if ((RBE(defn, elm)->rbe_right = RBE(defn, tmp)->rbe_left) != NULL) + RBE(defn, RBE(defn, tmp)->rbe_left)->rbe_parent = elm; + if (defn->augment) + defn->augment(elm); + if ((RBE(defn, tmp)->rbe_parent = RBE(defn, elm)->rbe_parent) + != NULL) { + if (elm == RBE(defn, RBE(defn, elm)->rbe_parent)->rbe_left) { + RBE(defn, RBE(defn, elm)->rbe_parent)->rbe_left = + tmp; + } else { + RBE(defn, RBE(defn, elm)->rbe_parent)->rbe_right = + tmp; + } + } else + *head = tmp; + + RBE(defn, tmp)->rbe_left = elm; + RBE(defn, elm)->rbe_parent = tmp; + if (defn->augment) { + defn->augment(tmp); + if (RBE(defn, tmp)->rbe_parent != NULL) + defn->augment(RBE(defn, tmp)->rbe_parent); + } +} + +void +_rb_rotate_right(const struct _tree_defn *defn, void **head, void *elm) +{ + void *tmp; + + tmp = RBE(defn, elm)->rbe_left; + if ((RBE(defn, elm)->rbe_left = RBE(defn, tmp)->rbe_right) != NULL) + RBE(defn, RBE(defn, tmp)->rbe_right)->rbe_parent = elm; + if (defn->augment) + defn->augment(elm); + if ((RBE(defn, tmp)->rbe_parent = RBE(defn, elm)->rbe_parent) + != NULL) { + if (elm == RBE(defn, RBE(defn, elm)->rbe_parent)->rbe_left) { + RBE(defn, RBE(defn, elm)->rbe_parent)->rbe_left = + tmp; + } else { + RBE(defn, RBE(defn, elm)->rbe_parent)->rbe_right = + tmp; + } + } else + *head = tmp; + + RBE(defn, tmp)->rbe_right = elm; + RBE(defn, elm)->rbe_parent = tmp; + if (defn->augment) { + defn->augment(tmp); + if (RBE(defn, tmp)->rbe_parent != NULL) + defn->augment(RBE(defn, tmp)->rbe_parent); + } +} + +void +_rb_insert_color(const struct _tree_defn *defn, void **head, void *elm) +{ + void *parent, *gparent, *tmp; + + while ( + (parent = RBE(defn, elm)->rbe_parent) + && RBE(defn, parent)->rbe_color == RB_RED) { + gparent = RBE(defn, parent)->rbe_parent; + if (parent == RBE(defn, gparent)->rbe_left) { + tmp = RBE(defn, gparent)->rbe_right; + if (tmp && RBE(defn, tmp)->rbe_color == RB_RED) { + RBE(defn, tmp)->rbe_color = RB_BLACK; + _rb_set_blackred(defn, parent, gparent); + elm = gparent; + continue; + } + if (RBE(defn, parent)->rbe_right == elm) { + _rb_rotate_left(defn, head, parent); + tmp = parent; + parent = elm; + elm = tmp; + } + _rb_set_blackred(defn, parent, gparent); + _rb_rotate_right(defn, head, gparent); + } else { + tmp = RBE(defn, gparent)->rbe_left; + if (tmp && RBE(defn, tmp)->rbe_color == RB_RED) { + RBE(defn, tmp)->rbe_color = RB_BLACK; + _rb_set_blackred(defn, parent, gparent); + elm = gparent; + continue; + } + if (RBE(defn, parent)->rbe_left == elm) { + _rb_rotate_right(defn, head, parent); + tmp = parent; + parent = elm; + elm = tmp; + } + _rb_set_blackred(defn, parent, gparent); + _rb_rotate_left(defn, head, gparent); + } + } + RBE(defn, *head)->rbe_color = RB_BLACK; +} + +void +_rb_remove_color(const struct _tree_defn *defn, void **head, + void *parent, void *elm) +{ + void *tmp; + + while ( + (elm == NULL || RBE(defn, elm)->rbe_color == RB_BLACK) + && elm != *head) { + if (RBE(defn, parent)->rbe_left == elm) { + tmp = RBE(defn, parent)->rbe_right; + if (RBE(defn, tmp)->rbe_color == RB_RED) { + _rb_set_blackred(defn, tmp, parent); + _rb_rotate_left(defn, head, parent); + tmp = RBE(defn, parent)->rbe_right; + } + if ( + (RBE(defn, tmp)->rbe_left == NULL || + RBE(defn, RBE(defn, tmp)->rbe_left)->rbe_color + == RB_BLACK) + && + (RBE(defn, tmp)->rbe_right == NULL || + RBE(defn, RBE(defn, tmp)->rbe_right)->rbe_color + == RB_BLACK)) { + RBE(defn, tmp)->rbe_color = RB_RED; + elm = parent; + parent = RBE(defn, elm)->rbe_parent; + } else { + if (RBE(defn, tmp)->rbe_right == NULL || + RBE(defn, RBE(defn, tmp)->rbe_right) + ->rbe_color == RB_BLACK) { + void *oleft; + oleft = RBE(defn, tmp)->rbe_left; + if (oleft) { + RBE(defn, oleft)->rbe_color = + RB_BLACK; + } + RBE(defn, tmp)->rbe_color = RB_RED; + _rb_rotate_right(defn, head, tmp); + tmp = RBE(defn, parent)->rbe_right; + } + RBE(defn, tmp)->rbe_color = + RBE(defn, parent)->rbe_color; + RBE(defn, parent)->rbe_color = RB_BLACK; + if (RBE(defn, tmp)->rbe_right) { + RBE(defn, RBE(defn, tmp)->rbe_right) + ->rbe_color = RB_BLACK; + } + _rb_rotate_left(defn, head, parent); + elm = *head; + break; + } + } else { + tmp = RBE(defn, parent)->rbe_left; + if (RBE(defn, tmp)->rbe_color == RB_RED) { + _rb_set_blackred(defn, tmp, parent); + _rb_rotate_right(defn, head, parent); + tmp = RBE(defn, parent)->rbe_left; + } + if ((RBE(defn, tmp)->rbe_left == NULL || + RBE(defn, RBE(defn, tmp)->rbe_left)->rbe_color + == RB_BLACK) + && + (RBE(defn, tmp)->rbe_right == NULL || + RBE(defn, RBE(defn, tmp)->rbe_right)->rbe_color + == RB_BLACK)) { + RBE(defn, tmp)->rbe_color = RB_RED; + elm = parent; + parent = RBE(defn, elm)->rbe_parent; + } else { + if (RBE(defn, tmp)->rbe_left == NULL || + RBE(defn, RBE(defn, tmp)->rbe_left) + ->rbe_color == RB_BLACK) { + void *oright; + oright = RBE(defn, tmp)->rbe_right; + if (oright) { + RBE(defn, oright)->rbe_color = + RB_BLACK; + } + RBE(defn, tmp)->rbe_color = RB_RED; + _rb_rotate_left(defn, head, tmp); + tmp = RBE(defn, parent)->rbe_left; + } + RBE(defn, tmp)->rbe_color = + RBE(defn, parent)->rbe_color; + RBE(defn, parent)->rbe_color = RB_BLACK; + if (RBE(defn, tmp)->rbe_left) { + RBE(defn, RBE(defn, tmp)->rbe_left) + ->rbe_color = RB_BLACK; + } + _rb_rotate_right(defn, head, parent); + elm = *head; + break; + } + } + } + + if (elm) + RBE(defn, elm)->rbe_color = RB_BLACK; +} + +void * +_rb_insert(const struct _tree_defn *defn, void **head, void *elm) +{ + void *tmp; + void *parent = NULL; + int comp = 0; + + tmp = *head; + while (tmp != NULL) { + parent = tmp; + comp = TREE_ENTRY_CMP(defn, elm, parent); + if (comp < 0) { + tmp = RBE(defn, tmp)->rbe_left; + } else if (comp > 0) { + tmp = RBE(defn, tmp)->rbe_right; + } else + return tmp; + } + _rb_set(defn, elm, parent); + if (parent != NULL) { + if (comp < 0) + RBE(defn, parent)->rbe_left = elm; + else + RBE(defn, parent)->rbe_right = elm; + if (defn->augment) + defn->augment(parent); + } else + *head = elm; + _rb_insert_color(defn, head, elm); + return NULL; +} + +void * +_rb_remove(const struct _tree_defn *defn, void **root, void *elm) +{ + void *child, *parent, *old = elm; + int color; + + if (RBE(defn, elm)->rbe_left == NULL) + child = RBE(defn, elm)->rbe_right; + else if (RBE(defn, elm)->rbe_right == NULL) + child = RBE(defn, elm)->rbe_left; + else { + void *left; + + elm = RBE(defn, elm)->rbe_right; + while ((left = RBE(defn, elm)->rbe_left) != NULL) + elm = left; + + child = RBE(defn, elm)->rbe_right; + parent = RBE(defn, elm)->rbe_parent; + color = RBE(defn, elm)->rbe_color; + + if (child) + RBE(defn, child)->rbe_parent = parent; + if (parent) { + if (RBE(defn, parent)->rbe_left == elm) + RBE(defn, parent)->rbe_left = child; + else + RBE(defn, parent)->rbe_right = child; + if (defn->augment) + defn->augment(parent); + } else + *root = child; + + if (RBE(defn, elm)->rbe_parent == old) + parent = elm; + *RBE(defn, elm) = *RBE(defn, old); + if (RBE(defn, old)->rbe_parent != NULL) { + if (RBE(defn, RBE(defn, old)->rbe_parent)->rbe_left + == old) { + RBE(defn, RBE(defn, old)->rbe_parent) + ->rbe_left = elm; + } else { + RBE(defn, RBE(defn, old)->rbe_parent) + ->rbe_right = elm; + } + if (defn->augment) + defn->augment(parent); + } else + *root = elm; + + RBE(defn, RBE(defn, old)->rbe_left)->rbe_parent = elm; + if (RBE(defn, old)->rbe_right != NULL) { + RBE(defn, RBE(defn, old)->rbe_right)->rbe_parent = + elm; + } + if (defn->augment) { + left = parent; + do { + defn->augment(left); + } while ((left = RBE(defn, left)->rbe_parent)); + } + + goto color; + } + + parent = RBE(defn, elm)->rbe_parent; + color = RBE(defn, elm)->rbe_color; + if (child) + RBE(defn, child)->rbe_parent = parent; + if (parent) { + if (RBE(defn, parent)->rbe_left == elm) + RBE(defn, parent)->rbe_left = child; + else + RBE(defn, parent)->rbe_right = child; + if (defn->augment) + defn->augment(parent); + } else + *root = child; + +color: + if (color == RB_BLACK) + _rb_remove_color(defn, root, parent, child); + return old; +} Index: kern/subr_tree_splay.c =================================================================== RCS file: kern/subr_tree_splay.c diff -N kern/subr_tree_splay.c --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ kern/subr_tree_splay.c 22 Sep 2011 12:37:07 -0000 @@ -0,0 +1,201 @@ +/* $OpenBSD: tree.h,v 1.12 2009/03/02 09:42:55 mikeb Exp $ */ +/* + * Copyright 2002 Niels Provos <[email protected]> + * Copyright 2011 Ariane van der Steldt <[email protected]> + * 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. + */ + +/* + * Specialized functions for splay trees. + */ + +#include <sys/tree.h> + +/* Helper: returns the untyped entry of p. */ +#define SPE(defn, p) TREE_ENTRY(defn, struct _splay_entry_untyped, p) + +void _splay_rotate_right(const struct _tree_defn*, void**, void*); +void _splay_rotate_left(const struct _tree_defn*, void**, void*); + +void +_splay_rotate_right(const struct _tree_defn *defn, void **head, void *tmp) +{ + SPE(defn, *head)->spe_left = SPE(defn, tmp)->spe_right; + SPE(defn, tmp)->spe_right = *head; + *head = tmp; +} + +void +_splay_rotate_left(const struct _tree_defn *defn, void **head, void *tmp) +{ + SPE(defn, *head)->spe_right = SPE(defn, tmp)->spe_left; + SPE(defn, tmp)->spe_left = *head; + *head = tmp; +} + +void +_splay_to_root(const struct _tree_defn *defn, void **head, void *elm) +{ + struct _splay_entry_untyped node, *left, *right; + void *tmp; + int comp; + + node.spe_left = node.spe_right = NULL; + left = right = &node; + + while ((comp = TREE_ENTRY_CMP(defn, elm, *head)) != 0) { + if (comp < 0) { + tmp = SPE(defn, *head)->spe_left; + if (tmp == NULL) + break; + if (TREE_ENTRY_CMP(defn, elm, tmp) < 0) { + _splay_rotate_right(defn, head, tmp); + if (SPE(defn, *head)->spe_left == NULL) + break; + } + + right->spe_left = *head; + right = SPE(defn, *head); + *head = SPE(defn, *head)->spe_left; + } else if (comp > 0) { + tmp = SPE(defn, *head)->spe_right; + if (tmp == NULL) + break; + if (TREE_ENTRY_CMP(defn, elm, tmp) > 0) { + _splay_rotate_left(defn, head, tmp); + if (SPE(defn, *head)->spe_right == NULL) + break; + } + + left->spe_right = *head; + left = SPE(defn, *head); + *head = SPE(defn, *head)->spe_right; + } + } + + left->spe_right = SPE(defn, *head)->spe_left; + right->spe_left = SPE(defn, *head)->spe_right; + SPE(defn, *head)->spe_left = node.spe_right; + SPE(defn, *head)->spe_right = node.spe_left; +} + +void * +_splay_minmax(const struct _tree_defn *defn, void **root, int direction) +{ + size_t ptr_offset; + void *result; + + if (*root == NULL) + return NULL; + + switch (direction) { + case TREE_LEFT: + ptr_offset = offsetof(struct _splay_entry_untyped, spe_left); + break; + case TREE_RIGHT: + ptr_offset = offsetof(struct _splay_entry_untyped, spe_right); + break; + } + + result = _tree_minmax(defn, *root, ptr_offset); + if (result != NULL) + _splay_to_root(defn, root, result); + return result; +} + +void * +_splay_nextprev(const struct _tree_defn *defn, void **root, void *elm, + int direction) +{ + size_t ptr_offset; + void *result; + + /* + * No if statements around splay_to_root: tree is guaranteed not + * empty (because elm is in the tree). + */ + _splay_to_root(defn, root, elm); + switch (direction) { + case TREE_LEFT: + result = SPE(defn, elm)->spe_left; + ptr_offset = offsetof(struct _splay_entry_untyped, spe_right); + break; + case TREE_RIGHT: + result = SPE(defn, elm)->spe_right; + ptr_offset = offsetof(struct _splay_entry_untyped, spe_left); + break; + } + + result = _tree_minmax(defn, result, ptr_offset); + return result; +} + +void * +_splay_insert(const struct _tree_defn *defn, void **head, void *elm) +{ + int comp; + + if (*head == NULL) { + SPE(defn, elm)->spe_left = SPE(defn, elm)->spe_right = NULL; + } else { + _splay_to_root(defn, head, elm); + comp = TREE_ENTRY_CMP(defn, elm, *head); + if (comp < 0) { + SPE(defn, elm)->spe_left = + SPE(defn, *head)->spe_left; + SPE(defn, elm)->spe_right = *head; + SPE(defn, *head)->spe_left = NULL; + } else if (comp > 0) { + SPE(defn, elm)->spe_right = + SPE(defn, *head)->spe_right; + SPE(defn, elm)->spe_left = *head; + SPE(defn, *head)->spe_right = NULL; + } else + return *head; + } + *head = elm; + return NULL; +} + +void * +_splay_remove(const struct _tree_defn *defn, void **head, void *elm) +{ + void *tmp; + + if (*head == NULL) + return NULL; + + _splay_to_root(defn, head, elm); + if (TREE_ENTRY_CMP(defn, elm, *head) == 0) { + if (SPE(defn, *head)->spe_left == NULL) + *head = SPE(defn, *head)->spe_right; + else { + tmp = SPE(defn, *head)->spe_right; + *head = SPE(defn, *head)->spe_left; + _splay_to_root(defn, head, elm); + SPE(defn, *head)->spe_right = tmp; + } + return elm; + } + return NULL; +} Index: sys/buf.h =================================================================== RCS file: /cvs/src/sys/sys/buf.h,v retrieving revision 1.78 diff -u -d -p -r1.78 buf.h --- sys/buf.h 4 Jul 2011 04:30:41 -0000 1.78 +++ sys/buf.h 21 Sep 2011 16:44:48 -0000 @@ -49,7 +49,7 @@ struct buf; struct vnode; -struct buf_rb_bufs; +RB_HEAD(buf_rb_bufs, buf); RB_PROTOTYPE(buf_rb_bufs, buf, b_rbbufs, rb_buf_compare); LIST_HEAD(bufhead, buf); Index: sys/namei.h =================================================================== RCS file: /cvs/src/sys/sys/namei.h,v retrieving revision 1.26 diff -u -d -p -r1.26 namei.h --- sys/namei.h 7 Jul 2011 23:45:00 -0000 1.26 +++ sys/namei.h 21 Sep 2011 16:44:48 -0000 @@ -40,7 +40,7 @@ #include <sys/uio.h> struct namecache; -struct namecache_rb_cache; +RB_HEAD(namecache_rb_cache, namecache); RB_PROTOTYPE(namecache_rb_cache, namecache, n_rbcache, namecache_compare); /* Index: sys/tree.h =================================================================== RCS file: /cvs/src/sys/sys/tree.h,v retrieving revision 1.13 diff -u -d -p -r1.13 tree.h --- sys/tree.h 9 Jul 2011 00:19:45 -0000 1.13 +++ sys/tree.h 22 Sep 2011 12:36:52 -0000 @@ -1,6 +1,7 @@ /* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */ /* * Copyright 2002 Niels Provos <[email protected]> + * Copyright 2011 Ariane van der Steldt <[email protected]> * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -52,6 +53,23 @@ * * Every operation on a red-black tree is bounded as O(lg n). * The maximum height of a red-black tree is 2lg (n+1). + * + * + * The implementation for the kernel uses a number of external functions, + * in order to reduce the size of the kernel image. The implementation can + * be found in sys/kern/subr_tree*.c. + * + * Userland, on the other hand, uses the original implementation, that + * uses the inline functions. This minimizes impact on userland and keeps + * tree.h usage independant of library use. + */ + +#ifndef RB_AUGMENT +#define RB_AUGMENT(x) do {} while (0) +#endif + +/* + * Splay code shared between both implementations. */ #define SPLAY_HEAD(name, type) \ @@ -77,6 +95,292 @@ struct { \ #define SPLAY_ROOT(head) (head)->sph_root #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) + +/* + * RB code shared between both implementations. + */ + +#define RB_BLACK (0) +#define RB_RED (1) + +#define RB_HEAD(name, type) \ +struct name { \ + struct type *rbh_root; /* root of the tree */ \ +} + +#define RB_INITIALIZER(root) \ + { NULL } + +#define RB_INIT(root) do { \ + (root)->rbh_root = NULL; \ +} while (0) + +#define RB_ENTRY(type) \ +struct { \ + struct type *rbe_left; /* left element */ \ + struct type *rbe_right; /* right element */ \ + struct type *rbe_parent; /* parent element */ \ + int rbe_color; /* node color */ \ +} + +#define RB_LEFT(elm, field) (elm)->field.rbe_left +#define RB_RIGHT(elm, field) (elm)->field.rbe_right +#define RB_PARENT(elm, field) (elm)->field.rbe_parent +#define RB_COLOR(elm, field) (elm)->field.rbe_color +#define RB_ROOT(head) (head)->rbh_root +#define RB_EMPTY(head) (RB_ROOT(head) == NULL) + + +#ifdef EXTERN_TREES /* Implementation specific for kernel. */ + +#include <sys/param.h> /* Needed for offsetof */ + +/* + * Definition of the entry type of a tree. + */ +struct _tree_defn { + size_t entry_offset; /* Offset of entry in type. */ + int (*cmp_fn) (void *, void *); /* Comparator function. */ + void (*augment) (void *); /* RB augment (bah) */ +}; + +/* Generic tree functions. */ +void *_tree_nfind(const struct _tree_defn*, void*, void*, size_t, size_t); +void *_tree_find(const struct _tree_defn*, void*, void*, size_t, size_t); +void *_tree_minmax(const struct _tree_defn*, void*, size_t); +void *_tree_nextprev(const struct _tree_defn*, void*, size_t, size_t, + size_t); + +/* SPLAY generic functions. */ +void _splay_to_root(const struct _tree_defn*, void**, void*); +void *_splay_minmax(const struct _tree_defn*, void**, int); +void *_splay_nextprev(const struct _tree_defn*, void**, void*, int); +void *_splay_insert(const struct _tree_defn*, void**, void*); +void *_splay_remove(const struct _tree_defn*, void**, void*); + +/* RB generic functions. */ +void *_rb_insert(const struct _tree_defn*, void**, void*); +void *_rb_remove(const struct _tree_defn*, void**, void*); + + +#define TREE_LEFT (-1) +#define TREE_RIGHT ( 1) + +/* Initializer of _tree_defn. */ +#define TREE_DEFN(elem_type, entry, cmp_fn, augment) \ + { offsetof(struct elem_type, entry), \ + (int (*)(void*, void*))cmp_fn, (void (*)(void *))augment } + +/* Find the entry field of the element. */ +#define TREE_ENTRY(defn, entry_type, entry) \ + ((entry_type*)(((char*)(entry)) + (defn)->entry_offset)) + +/* Invoke the comparison function of the tree. */ +#define TREE_ENTRY_CMP(defn, entry0, entry1) \ + ((defn)->cmp_fn((entry0), (entry1))) + + +/* + * Splay trees. + */ +struct _splay_entry_untyped { + void *spe_left; /* left element */ + void *spe_right; /* right element */ +}; + +#define SPLAY_FIND(name, tree, elm) name##_SPLAY_FIND(tree, elm) +#define SPLAY_MIN(name, tree) name##_SPLAY_MINMAX(tree, TREE_LEFT) +#define SPLAY_MAX(name, tree) name##_SPLAY_MINMAX(tree, TREE_RIGHT) +#define SPLAY_NEXT(name, tree, elm) \ + name##_SPLAY_NEXTPREV(tree, elm, TREE_RIGHT) +#define SPLAY_PREV(name, tree, elm) \ + name##_SPLAY_NEXTPREV(tree, elm, TREE_LEFT) +#define SPLAY_INSERT(name, tree, elm) name##_SPLAY_INSERT(tree, elm) +#define SPLAY_REMOVE(name, tree, elm) name##_SPLAY_REMOVE(tree, elm) + +#define SPLAY_PROTOTYPE(name, type, field, cmp) \ +extern const struct _tree_defn name##_splay_defn; \ + \ +static __inline \ +struct type * \ +name##_SPLAY_FIND(struct name *tree, struct type *elm) \ +{ \ + _splay_to_root(&name##_splay_defn, \ + (void**)&SPLAY_ROOT(tree), elm); \ + if (TREE_ENTRY_CMP(&name##_splay_defn, \ + SPLAY_ROOT(tree), elm) == 0) \ + return SPLAY_ROOT(tree); \ + return NULL; \ +} \ + \ +static __inline \ +struct type * \ +name##_SPLAY_MINMAX(struct name *tree, int direction) \ +{ \ + return (struct type*)_splay_minmax(&name##_splay_defn, \ + (void**)&SPLAY_ROOT(tree), direction); \ +} \ + \ +static __inline \ +struct type * \ +name##_SPLAY_NEXTPREV(struct name *tree, struct type *elm, \ + int direction) \ +{ \ + return (struct type*)_splay_nextprev(&name##_splay_defn, \ + (void**)&SPLAY_ROOT(tree), elm, direction); \ +} \ + \ +static __inline \ +struct type * \ +name##_SPLAY_INSERT(struct name *tree, struct type *elm) \ +{ \ + return (struct type*)_splay_insert(&name##_splay_defn, \ + (void**)&SPLAY_ROOT(tree), elm); \ +} \ + \ +static __inline \ +struct type * \ +name##_SPLAY_REMOVE(struct name *tree, struct type *elm) \ +{ \ + return (struct type*)_splay_remove(&name##_splay_defn, \ + (void**)&SPLAY_ROOT(tree), elm); \ +} + +#define SPLAY_GENERATE(name, type, field, cmp) \ +const struct _tree_defn name##_splay_defn = \ + TREE_DEFN(type, field, cmp, NULL); + +/* + * Red-black trees. + */ + +struct _rb_entry_untyped { + void *rbe_left; /* left element */ + void *rbe_right; /* right element */ + void *rbe_parent; /* parent element */ + int rbe_color; /* node color */ +}; + +#define RB_FIND(name, tree, elm) name##_RB_FIND(tree, elm) +#define RB_NFIND(name, tree, elm) name##_RB_NFIND(tree, elm) +#define RB_NEXT(name, tree, elm) name##_RB_NEXTPREV(elm, TREE_RIGHT) +#define RB_PREV(name, tree, elm) name##_RB_NEXTPREV(elm, TREE_LEFT) +#define RB_MIN(name, tree) name##_RB_MINMAX(tree, TREE_LEFT) +#define RB_MAX(name, tree) name##_RB_MINMAX(tree, TREE_RIGHT) +#define RB_INSERT(name, tree, elm) name##_RB_INSERT(tree, elm) +#define RB_REMOVE(name, tree, elm) name##_RB_REMOVE(tree, elm) + +#define RB_PROTOTYPE(name, type, field, cmp) \ +extern const struct _tree_defn name##_rb_defn; \ + \ +static __inline \ +struct type * \ +name##_RB_FIND(struct name *tree, struct type *elm) \ +{ \ + return (struct type*)_tree_find(&name##_rb_defn, \ + RB_ROOT(tree), elm, \ + offsetof(struct _rb_entry_untyped, rbe_left), \ + offsetof(struct _rb_entry_untyped, rbe_right)); \ +} \ + \ +static __inline \ +struct type * \ +name##_RB_NFIND(struct name *tree, struct type *elm) \ +{ \ + return (struct type*)_tree_nfind(&name##_rb_defn, \ + RB_ROOT(tree), elm, \ + offsetof(struct _rb_entry_untyped, rbe_left), \ + offsetof(struct _rb_entry_untyped, rbe_right)); \ +} \ + \ +static __inline \ +struct type * \ +name##_RB_MINMAX(struct name *head, int direction) \ +{ \ + size_t ptr_offset; \ + \ + switch (direction) { \ + case TREE_LEFT: \ + ptr_offset = \ + offsetof(struct _rb_entry_untyped, rbe_left); \ + break; \ + case TREE_RIGHT: \ + ptr_offset = \ + offsetof(struct _rb_entry_untyped, rbe_right); \ + break; \ + } \ + \ + return (struct type*)_tree_minmax(&name##_rb_defn, \ + RB_ROOT(head), ptr_offset); \ +} \ + \ +static __inline \ +struct type * \ +name##_RB_NEXTPREV(struct type *elm, int direction) \ +{ \ + /* \ + * Names here: if direction is TREE_RIGHT: \ + * prev_offset points to the previous element, next_offset \ + * to the next element; \ + * \ + * Otherwise: \ + * prev_offset points to the next element, next_offset to \ + * the previous. \ + * \ + * In other words: prev is using next on a mirrored tree. \ + */ \ + size_t prev_offset; \ + size_t next_offset; \ + size_t parent_offset; \ + \ + switch (direction) { \ + case TREE_LEFT: \ + prev_offset = \ + offsetof(struct _rb_entry_untyped, rbe_right); \ + next_offset = \ + offsetof(struct _rb_entry_untyped, rbe_left); \ + break; \ + case TREE_RIGHT: \ + prev_offset = \ + offsetof(struct _rb_entry_untyped, rbe_left); \ + next_offset = \ + offsetof(struct _rb_entry_untyped, rbe_right); \ + break; \ + } \ + parent_offset = \ + offsetof(struct _rb_entry_untyped, rbe_parent); \ + \ + return (struct type*)_tree_nextprev(&name##_rb_defn, elm, \ + prev_offset, next_offset, parent_offset); \ +} \ + \ +static __inline \ +struct type * \ +name##_RB_INSERT(struct name *tree, struct type *elm) \ +{ \ + return (struct type*)_rb_insert(&name##_rb_defn, \ + (void**)&RB_ROOT(tree), elm); \ +} \ + \ +static __inline \ +struct type * \ +name##_RB_REMOVE(struct name *tree, struct type *elm) \ +{ \ + return (struct type*)_rb_remove(&name##_rb_defn, \ + (void**)&RB_ROOT(tree), elm); \ +} + +#define RB_GENERATE(name, type, field, cmp) \ +static void \ +name##_rb_augment(struct type *elm) \ +{ \ + RB_AUGMENT(elm); \ +} \ +const struct _tree_defn name##_rb_defn = \ + TREE_DEFN(type, field, cmp, name##_rb_augment); + +#else /* EXTERN_TREES; stand-alone implementation for userland. */ + /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ @@ -144,6 +448,20 @@ name##_SPLAY_NEXT(struct name *head, str } \ \ static __inline struct type * \ +name##_SPLAY_PREV(struct name *head, struct type *elm) \ +{ \ + name##_SPLAY(head, elm); \ + if (SPLAY_LEFT(elm, field) != NULL) { \ + elm = SPLAY_LEFT(elm, field); \ + while (SPLAY_RIGHT(elm, field) != NULL) { \ + elm = SPLAY_RIGHT(elm, field); \ + } \ + } else \ + elm = NULL; \ + return (elm); \ +} \ + \ +static __inline struct type * \ name##_SPLAY_MIN_MAX(struct name *head, int val) \ { \ name##_SPLAY_MINMAX(head, val); \ @@ -277,45 +595,13 @@ void name##_SPLAY_MINMAX(struct name *he #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) +#define SPLAY_PREV(name, x, y) name##_SPLAY_PREV(x, y) #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) -#define SPLAY_FOREACH(x, name, head) \ - for ((x) = SPLAY_MIN(name, head); \ - (x) != NULL; \ - (x) = SPLAY_NEXT(name, head, x)) - /* Macros that define a red-black tree */ -#define RB_HEAD(name, type) \ -struct name { \ - struct type *rbh_root; /* root of the tree */ \ -} - -#define RB_INITIALIZER(root) \ - { NULL } - -#define RB_INIT(root) do { \ - (root)->rbh_root = NULL; \ -} while (0) - -#define RB_BLACK 0 -#define RB_RED 1 -#define RB_ENTRY(type) \ -struct { \ - struct type *rbe_left; /* left element */ \ - struct type *rbe_right; /* right element */ \ - struct type *rbe_parent; /* parent element */ \ - int rbe_color; /* node color */ \ -} - -#define RB_LEFT(elm, field) (elm)->field.rbe_left -#define RB_RIGHT(elm, field) (elm)->field.rbe_right -#define RB_PARENT(elm, field) (elm)->field.rbe_parent -#define RB_COLOR(elm, field) (elm)->field.rbe_color -#define RB_ROOT(head) (head)->rbh_root -#define RB_EMPTY(head) (RB_ROOT(head) == NULL) #define RB_SET(elm, parent, field) do { \ RB_PARENT(elm, field) = parent; \ @@ -328,10 +614,6 @@ struct { \ RB_COLOR(red, field) = RB_RED; \ } while (0) -#ifndef RB_AUGMENT -#define RB_AUGMENT(x) do {} while (0) -#endif - #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ (tmp) = RB_RIGHT(elm, field); \ if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ @@ -386,8 +668,7 @@ attr struct type *name##_RB_FIND(struct attr struct type *name##_RB_NFIND(struct name *, struct type *); \ attr struct type *name##_RB_NEXT(struct type *); \ attr struct type *name##_RB_PREV(struct type *); \ -attr struct type *name##_RB_MINMAX(struct name *, int); \ - \ +attr struct type *name##_RB_MINMAX(struct name *, int); /* Main rb operation. * Moves node close to the key of elm to top @@ -413,7 +694,8 @@ name##_RB_INSERT_COLOR(struct name *head continue; \ } \ if (RB_RIGHT(parent, field) == elm) { \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ + RB_ROTATE_LEFT(head, parent, tmp, \ + field); \ tmp = parent; \ parent = elm; \ elm = tmp; \ @@ -429,7 +711,8 @@ name##_RB_INSERT_COLOR(struct name *head continue; \ } \ if (RB_LEFT(parent, field) == elm) { \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ + RB_ROTATE_RIGHT(head, parent, tmp, \ + field); \ tmp = parent; \ parent = elm; \ elm = tmp; \ @@ -451,7 +734,8 @@ name##_RB_REMOVE_COLOR(struct name *head tmp = RB_RIGHT(parent, field); \ if (RB_COLOR(tmp, field) == RB_RED) { \ RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ + RB_ROTATE_LEFT(head, parent, tmp, \ + field); \ tmp = RB_RIGHT(parent, field); \ } \ if ((RB_LEFT(tmp, field) == NULL || \ @@ -468,14 +752,16 @@ name##_RB_REMOVE_COLOR(struct name *head if ((oleft = RB_LEFT(tmp, field)))\ RB_COLOR(oleft, field) = RB_BLACK;\ RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_RIGHT(head, tmp, oleft, field);\ + RB_ROTATE_RIGHT(head, tmp, oleft,\ + field); \ tmp = RB_RIGHT(parent, field); \ } \ RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ RB_COLOR(parent, field) = RB_BLACK; \ if (RB_RIGHT(tmp, field)) \ RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ - RB_ROTATE_LEFT(head, parent, tmp, field);\ + RB_ROTATE_LEFT(head, parent, tmp, \ + field); \ elm = RB_ROOT(head); \ break; \ } \ @@ -483,7 +769,8 @@ name##_RB_REMOVE_COLOR(struct name *head tmp = RB_LEFT(parent, field); \ if (RB_COLOR(tmp, field) == RB_RED) { \ RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ + RB_ROTATE_RIGHT(head, parent, tmp, \ + field); \ tmp = RB_LEFT(parent, field); \ } \ if ((RB_LEFT(tmp, field) == NULL || \ @@ -500,14 +787,16 @@ name##_RB_REMOVE_COLOR(struct name *head if ((oright = RB_RIGHT(tmp, field)))\ RB_COLOR(oright, field) = RB_BLACK;\ RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_LEFT(head, tmp, oright, field);\ + RB_ROTATE_LEFT(head, tmp, oright,\ + field); \ tmp = RB_LEFT(parent, field); \ } \ RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ RB_COLOR(parent, field) = RB_BLACK; \ if (RB_LEFT(tmp, field)) \ RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ + RB_ROTATE_RIGHT(head, parent, tmp, \ + field); \ elm = RB_ROOT(head); \ break; \ } \ @@ -725,24 +1014,41 @@ name##_RB_MINMAX(struct name *head, int #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) +#endif /* EXTERN_TREES */ + + +/* + * Foreach and foreach-reverse for each tree. + */ + +#define SPLAY_FOREACH(x, name, head) \ + for ((x) = SPLAY_MIN(name, head); \ + (x) != NULL; \ + (x) = SPLAY_NEXT(name, head, (x))) + +#define SPLAY_FOREACH_REVERSE(x, name, head) \ + for ((x) = SPLAY_MAX(name, head); \ + (x) != NULL; \ + (x) = SPLAY_PREV(name, head, (x))) + #define RB_FOREACH(x, name, head) \ for ((x) = RB_MIN(name, head); \ (x) != NULL; \ - (x) = name##_RB_NEXT(x)) + (x) = RB_NEXT(name, head, (x))) #define RB_FOREACH_SAFE(x, name, head, y) \ for ((x) = RB_MIN(name, head); \ - ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ + ((x) != NULL) && ((y) = RB_NEXT(name, head, (x)), 1); \ (x) = (y)) #define RB_FOREACH_REVERSE(x, name, head) \ for ((x) = RB_MAX(name, head); \ (x) != NULL; \ - (x) = name##_RB_PREV(x)) + (x) = RB_PREV(name, head, (x))) #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ for ((x) = RB_MAX(name, head); \ - ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ + ((x) != NULL) && ((y) = RB_PREV(name, head, (x)), 1); \ (x) = (y)) #endif /* _SYS_TREE_H_ */ Index: sys/vnode.h =================================================================== RCS file: /cvs/src/sys/sys/vnode.h,v retrieving revision 1.109 diff -u -d -p -r1.109 vnode.h --- sys/vnode.h 5 Apr 2011 14:34:16 -0000 1.109 +++ sys/vnode.h 22 Sep 2011 12:26:05 -0000 @@ -82,9 +82,6 @@ enum vtagtype { */ LIST_HEAD(buflists, buf); -RB_HEAD(buf_rb_bufs, buf); -RB_HEAD(namecache_rb_cache, namecache); - struct vnode { struct uvm_vnode v_uvm; /* uvm data */ struct vops *v_op; /* vnode operations vector */
