update proplib
authorAlex Hornung <ahornung@gmail.com>
Sat, 16 Jul 2011 08:34:41 +0000 (09:34 +0100)
committerAlex Hornung <ahornung@gmail.com>
Sat, 16 Jul 2011 17:36:36 +0000 (18:36 +0100)
 * There are several bugfixes and many cosmetic fixes.

Obtained-from: NetBSD

23 files changed:
lib/libprop/Makefile
lib/libprop/prop_array.3
lib/libprop/prop_array_util.3
lib/libprop/prop_dictionary.3
lib/libprop/prop_dictionary_util.3
lib/libprop/prop_ingest.3
lib/libprop/prop_number.3
lib/libprop/prop_object.3
lib/libprop/prop_send_ioctl.3
lib/libprop/prop_send_syscall.3 [copied from lib/libprop/prop_send_ioctl.3 with 50% similarity]
lib/libprop/proplib.3
share/man/man9/Makefile
share/man/man9/prop_copyin_ioctl.9
sys/libprop/prop_array.h
sys/libprop/prop_array_util.c
sys/libprop/prop_dictionary.c
sys/libprop/prop_dictionary.h
sys/libprop/prop_dictionary_util.c
sys/libprop/prop_kern.c
sys/libprop/prop_number.c
sys/libprop/prop_object.c
sys/libprop/prop_rb.c
sys/libprop/prop_rb_impl.h

index a7c6a59..aaab8ee 100644 (file)
@@ -30,6 +30,7 @@ MLINKS+= prop_send_ioctl.3 prop_dictionary_sendrecv_ioctl.3
 MAN+=  prop_dictionary_util.3
 MLINKS+= prop_dictionary_util.3 prop_dictionary_get_bool.3
 MLINKS+= prop_dictionary_util.3 prop_dictionary_set_bool.3
+MLINKS+= prop_dictionary_util.3        prop_dictionary_get_dict.3
 MLINKS+= prop_dictionary_util.3 prop_dictionary_get_int8.3
 MLINKS+= prop_dictionary_util.3 prop_dictionary_get_uint8.3
 MLINKS+= prop_dictionary_util.3 prop_dictionary_set_int8.3
@@ -50,6 +51,7 @@ MLINKS+= prop_dictionary_util.3 prop_dictionary_get_cstring.3
 MLINKS+= prop_dictionary_util.3 prop_dictionary_set_cstring.3
 MLINKS+= prop_dictionary_util.3 prop_dictionary_get_cstring_nocopy.3
 MLINKS+= prop_dictionary_util.3 prop_dictionary_set_cstring_nocopy.3
+MLINKS+= prop_dictionary_util.3 prop_dictionary_set_and_rel.3
 
 MLINKS+= prop_array.3 prop_array_add.3
 MLINKS+= prop_array.3 prop_array_capacity.3
@@ -103,6 +105,7 @@ MLINKS+= prop_array_util.3 prop_array_get_cstring.3
 MLINKS+= prop_array_util.3 prop_array_set_cstring.3
 MLINKS+= prop_array_util.3 prop_array_get_cstring_nocopy.3
 MLINKS+= prop_array_util.3 prop_array_set_cstring_nocopy.3
+MLINKS+= prop_array_util.3 prop_array_add_and_rel.3
 
 MLINKS+= prop_bool.3 prop_bool_copy.3
 MLINKS+= prop_bool.3 prop_bool_create.3
@@ -184,4 +187,10 @@ MLINKS+= prop_string.3 prop_string_equals_cstring.3
 MLINKS+= prop_string.3 prop_string_mutable.3
 MLINKS+= prop_string.3 prop_string_size.3
 
+MAN+=  prop_send_syscall.3
+MLINKS+= prop_send_syscall.3 prop_array_send_syscall.3
+MLINKS+= prop_send_syscall.3 prop_array_recv_syscall.3
+MLINKS+= prop_send_syscall.3 prop_dictionary_send_syscall.3
+MLINKS+= prop_send_syscall.3 prop_dictionary_recv_syscall.3
+
 .include <bsd.lib.mk>
index d00e4e8..4e7d1a6 100644 (file)
@@ -219,7 +219,7 @@ constant, as defined in
 .Pa libprop/prop_array.c
 file, e.g.
 .Pp
-.Dl "#define   EXPAND_STEP             16"
+.Dl #define    EXPAND_STEP             16
 .It Fn prop_array_remove "prop_array_t array" "unsigned int index"
 Remove the reference to the object stored at array index
 .Fa index .
@@ -266,7 +266,7 @@ Returns
 .Dv NULL
 on failure.
 .It Fn prop_array_externalize_to_pref "prop_array_t array" \
-"struct plistref *pref"
+       "struct plistref *pref"
 Externalizes an array and packs it into the plistref specified by
 .Fa pref .
 Returns
index 394dcc1..6ff6247 100644 (file)
@@ -1,4 +1,4 @@
-.\"    $NetBSD: prop_array_util.3,v 1.3 2008/09/11 13:15:13 haad Exp $
+.\"    $NetBSD: prop_array_util.3,v 1.5 2011/03/24 17:05:39 bouyer Exp $
 .\"
 .\" Copyright (c) 2006 The NetBSD Foundation, Inc.
 .\" All rights reserved.
@@ -27,7 +27,7 @@
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 .\" POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd June 2, 2008
+.Dd March 12, 2011
 .Dt PROP_ARRAY_UTIL 3
 .Os
 .Sh NAME
@@ -61,8 +61,8 @@
 .Nm prop_array_get_cstring ,
 .Nm prop_array_set_cstring ,
 .Nm prop_array_get_cstring_nocopy ,
-.Nm prop_array_set_cstring_nocopy
-.Nd array property collection object utility functions
+.Nm prop_array_set_cstring_nocopy ,
+.Nm prop_array_add_and_rel
 .Sh LIBRARY
 .Lb libprop
 .Sh SYNOPSIS
 .Ft bool
 .Fn prop_array_set_cstring_nocopy "prop_array_t dict" \
     "unsigned int indx" "const char *strp"
+.Ft bool
+.Fn prop_array_add_and_rel "prop_array_t dict" \
+    "prop_object_t obj"
 .Sh DESCRIPTION
 The
 .Nm prop_array_util
@@ -191,6 +194,11 @@ functions do not copy the string that is set or returned.
 See
 .Xr prop_string 3
 for more information.
+.Pp
+The
+.Fn prop_array_add_and_rel
+function adds the object to the end of the array and releases it.
+The object is also released on failure.
 .Sh RETURN VALUES
 The
 .Nm prop_array_util
index bbc052c..3abba64 100644 (file)
@@ -1,4 +1,4 @@
-.\"    $NetBSD: prop_dictionary.3,v 1.15 2009/12/05 10:17:17 wiz Exp $
+.\"    $NetBSD: prop_dictionary.3,v 1.16 2011/02/02 16:37:27 plunky Exp $
 .\"
 .\" Copyright (c) 2006, 2009 The NetBSD Foundation, Inc.
 .\" All rights reserved.
@@ -41,7 +41,7 @@
 .Nm prop_dictionary_iterator ,
 .Nm prop_dictionary_all_keys ,
 .Nm prop_dictionary_make_immutable ,
-.\".Nm prop_dictionary_mutable ,
+.Nm prop_dictionary_mutable ,
 .Nm prop_dictionary_get ,
 .Nm prop_dictionary_set ,
 .Nm prop_dictionary_remove ,
@@ -85,8 +85,8 @@
 .\"
 .Ft void
 .Fn prop_dictionary_make_immutable "prop_dictionary_t dict"
-.\".Ft bool
-.\".Fn prop_dictionary_mutable "prop_dictionary_t dict"
+.Ft bool
+.Fn prop_dictionary_mutable "prop_dictionary_t dict"
 .\"
 .Ft prop_object_t
 .Fn prop_dictionary_get "prop_dictionary_t dict" "const char *key"
@@ -207,10 +207,10 @@ on failure.
 Make
 .Fa dict
 immutable.
-.\".It Fn prop_dictionary_mutable "prop_dictionary_t dict"
-.\"Returns
-.\".Dv true
-.\"if the dictionary is mutable.
+.It Fn prop_dictionary_mutable "prop_dictionary_t dict"
+Returns
+.Dv true
+if the dictionary is mutable.
 .It Fn prop_dictionary_get "prop_dictionary_t dict" "const char *key"
 Return the object stored in the dictionary with the key
 .Fa key .
@@ -313,7 +313,7 @@ if externalizing or writing the dictionary fails for any reason.
 .It Fn prop_dictionary_internalize_from_file "const char *path"
 Reads the XML property list contained in the file specified by
 .Fa path ,
-internalizes it, and returns the corresponding array.
+internalizes it, and returns the corresponding dictionary.
 Returns
 .Dv NULL
 on failure.
index 57d8936..e3b705b 100644 (file)
@@ -1,4 +1,4 @@
-.\"    $NetBSD: prop_dictionary_util.3,v 1.4 2008/06/02 09:27:04 haad Exp $
+.\"    $NetBSD: prop_dictionary_util.3,v 1.5 2011/03/24 17:05:39 bouyer Exp $
 .\"
 .\" Copyright (c) 2006 The NetBSD Foundation, Inc.
 .\" All rights reserved.
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 .\" POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd October 25, 2006
+.Dd March 12, 2011
 .Dt PROP_DICTIONARY_UTIL 3
 .Os
 .Sh NAME
 .Nm prop_dictionary_util ,
+.Nm prop_dictionary_get_dict ,
 .Nm prop_dictionary_get_bool ,
 .Nm prop_dictionary_set_bool ,
 .Nm prop_dictionary_get_int8 ,
 .Nm prop_dictionary_get_cstring ,
 .Nm prop_dictionary_set_cstring ,
 .Nm prop_dictionary_get_cstring_nocopy ,
-.Nm prop_dictionary_set_cstring_nocopy
-.Nd dictionary property collection object utility functions
+.Nm prop_dictionary_set_cstring_nocopy ,
+.Nm prop_dictionary_set_and_rel
 .Sh LIBRARY
 .Lb libprop
 .Sh SYNOPSIS
 .In libprop/proplib.h
 .\"
 .Ft bool
+.Fn prop_dictionary_get_dict "prop_dictionary_t dict" "const char *key" \
+    "bool *dictp"
+.Ft bool
 .Fn prop_dictionary_get_bool "prop_dictionary_t dict" "const char *key" \
     "bool *valp"
 .Ft bool
 .Ft bool
 .Fn prop_dictionary_set_cstring_nocopy "prop_dictionary_t dict" \
     "const char *key" "const char *strp"
+.Ft bool
+.Fn prop_dictionary_set_and_rel "prop_dictionary_t dict" \
+    "const char *key" "prop_object_t obj"
 .Sh DESCRIPTION
 The
 .Nm prop_dictionary_util
@@ -159,6 +166,11 @@ functions do not copy the string that is set or returned.
 See
 .Xr prop_string 3
 for more information.
+.Pp
+The
+.Fn prop_dictionary_set_and_rel
+function adds the object to the dictionary and releases it.
+The object is also released on failure.
 .Sh RETURN VALUES
 The
 .Nm prop_dictionary_util
index bce000f..fc424ef 100644 (file)
@@ -1,4 +1,4 @@
-.\"    $NetBSD: prop_ingest.3,v 1.6 2010/02/18 14:00:39 wiz Exp $
+.\"    $NetBSD: prop_ingest.3,v 1.5 2008/04/30 13:10:46 martin Exp $
 .\"
 .\" Copyright (c) 2006 The NetBSD Foundation, Inc.
 .\" All rights reserved.
@@ -39,8 +39,6 @@
 .Nm prop_ingest_context_private ,
 .Nm prop_dictionary_ingest
 .Nd Ingest a dictionary into an arbitrary binary format
-.Sh LIBRARY
-.Lb libprop
 .Sh SYNOPSIS
 .In libprop/proplib.h
 .Ft prop_ingest_context_t
@@ -83,7 +81,7 @@ The expected property type of the object associated with the key
 to specify that any type is allowed).
 .It
 A callback function of type
-.Vt prop_ingest_handler_t
+.Dv prop_ingest_handler_t
 that will perform the translation for the application.
 .El
 .Pp
index 88b8422..654282e 100644 (file)
@@ -150,14 +150,20 @@ Returns
 if the numeric value object has an unsigned value.
 .It Fn prop_number_integer_value "prop_number_t number"
 Returns the signed integer value of the numeric value object.
-If the supplied object isn't a numeric value, zero is returned. Thus,
-it is not possible to distinguish between ``not a prop_number_t''
-and ``prop_number_t has a value of 0''.
+If the supplied object isn't a numeric value, zero is returned.
+Thus,
+it is not possible to distinguish between
+.Dq not a prop_number_t
+and
+.Dq prop_number_t has a value of 0 .
 .It Fn prop_number_unsigned_integer_value "prop_number_t number"
 Returns the unsigned integer value of the numeric value object.
-If the supplied object isn't a numeric value, zero is returned. Thus,
-it is not possible to distinguish between ``not a prop_number_t''
-and ``prop_number_t has a value of 0''.
+If the supplied object isn't a numeric value, zero is returned.
+Thus,
+it is not possible to distinguish between
+.Dq not a prop_number_t
+and
+.Dq prop_number_t has a value of 0 .
 .It Fn prop_number_equals "prop_number_t num1" "prop_number_t num2"
 Returns
 .Dv true
index bd7fb8e..6e2fd40 100644 (file)
 The
 .Nm prop_object
 family of functions operate on all property container object types.
-.Bl -tag -width 0n
+.Bl -tag -width ""
 .It Fn prop_object_retain "prop_object_t obj"
 Increment the reference count on an object.
 .It Fn prop_object_release "prop_object_t obj"
 Decrement the reference count on an object.
 If the last reference is dropped, the object is freed.
 .It Fn prop_object_type "prop_object_t obj"
-Determine the type of the object.  Objects are one of the following types:
+Determine the type of the object.
+Objects are one of the following types:
 .Pp
 .Bl -tag -width "PROP_TYPE_DICT_KEYSYM" -compact
 .It Dv PROP_TYPE_BOOL
index 7d59b66..6936d4c 100644 (file)
@@ -1,4 +1,4 @@
-.\"    $NetBSD: prop_send_ioctl.3,v 1.5 2008/04/30 13:10:46 martin Exp $
+.\"    $NetBSD: prop_send_ioctl.3,v 1.6 2011/01/20 10:44:42 wiz Exp $
 .\"
 .\" Copyright (c) 2006 The NetBSD Foundation, Inc.
 .\" All rights reserved.
@@ -37,8 +37,6 @@
 .Nm prop_dictionary_recv_ioctl ,
 .Nm prop_dictionary_sendrecv_ioctl
 .Nd Send and receive propertly lists to and from the kernel using ioctl
-.Sh LIBRARY
-.Lb libprop
 .Sh SYNOPSIS
 .In libprop/proplib.h
 .Ft int
@@ -65,33 +63,8 @@ functions implement the user space side of a protocol for sending property
 lists to and from the kernel using
 .Xr ioctl 2 .
 .Sh RETURN VALUES
-If successful, functions return zero. Otherwise, an error number is returned to indicate the error.
-.Sh ERRORS
-.Fn prop_array_send_ioctl
-and
-.Fn prop_dictionary_send_ioctl
-will fail if:
-.Bl -tag -width Er
-.It Bq Er ENOMEM
-Cannot allocate memory
-.It Bq Er ENOTSUP
-Not supported
-.El
-.Pp
-.Fn prop_array_recv_ioctl
-and
-.Fn prop_dictionary_recv_ioctl
-will fail if:
-.Bl -tag -width Er
-.It Bq Er EIO
-Input/output error
-.It Bq Er ENOTSUP
-Not supported
-.El
-.Pp
-In addition to these,
-.Xr ioctl 2
-errors may be returned.
+If successful, functions return zero.
+Otherwise, an error number is returned to indicate the error.
 .Sh EXAMPLES
 The following
 .Pq simplified
@@ -139,6 +112,32 @@ The
 function combines the send and receive functionality, allowing for
 ioctls that require two-way communication
 .Pq for example to specify arguments for the ioctl operation .
+.Sh ERRORS
+.Fn prop_array_send_ioctl
+and
+.Fn prop_dictionary_send_ioctl
+will fail if:
+.Bl -tag -width Er
+.It Bq Er ENOMEM
+Cannot allocate memory
+.It Bq Er ENOTSUP
+Not supported
+.El
+.Pp
+.Fn prop_array_recv_ioctl
+and
+.Fn prop_dictionary_recv_ioctl
+will fail if:
+.Bl -tag -width Er
+.It Bq Er EIO
+Input/output error
+.It Bq Er ENOTSUP
+Not supported
+.El
+.Pp
+In addition to these,
+.Xr ioctl 2
+errors may be returned.
 .Sh SEE ALSO
 .Xr prop_array 3 ,
 .Xr prop_dictionary 3 ,
similarity index 50%
copy from lib/libprop/prop_send_ioctl.3
copy to lib/libprop/prop_send_syscall.3
index 7d59b66..d41735d 100644 (file)
@@ -1,4 +1,4 @@
-.\"    $NetBSD: prop_send_ioctl.3,v 1.5 2008/04/30 13:10:46 martin Exp $
+.\"    $NetBSD: prop_send_syscall.3,v 1.3 2011/01/20 10:48:37 wiz Exp $
 .\"
 .\" Copyright (c) 2006 The NetBSD Foundation, Inc.
 .\" All rights reserved.
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 .\" POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd January 21, 2008
-.Dt PROP_SEND_IOCTL 3
+.Dd January 17, 2011
+.Dt PROP_SEND_SYCALL 3
 .Os
 .Sh NAME
-.Nm prop_array_send_ioctl ,
-.Nm prop_array_recv_ioctl ,
-.Nm prop_dictionary_send_ioctl ,
-.Nm prop_dictionary_recv_ioctl ,
-.Nm prop_dictionary_sendrecv_ioctl
-.Nd Send and receive propertly lists to and from the kernel using ioctl
-.Sh LIBRARY
-.Lb libprop
+.Nm prop_array_send_syscall ,
+.Nm prop_array_recv_syscall ,
+.Nm prop_dictionary_send_syscall ,
+.Nm prop_dictionary_recv_syscall
+.Nd send and receive property lists to and from the kernel using syscalls
 .Sh SYNOPSIS
 .In libprop/proplib.h
-.Ft int
-.Fn prop_array_send_ioctl "prop_array_t array" "int fd" "unsigned long cmd"
-.Ft int
-.Fn prop_array_recv_ioctl "int fd" "unsigned long cmd" "prop_array_t *arrayp"
-.Ft int
-.Fn prop_dictionary_send_ioctl "prop_dictionary_t dict" "int fd" \
-    "unsigned long cmd"
-.Ft int
-.Fn prop_dictionary_recv_ioctl "int fd" "unsigned long cmd" \
+.Ft bool
+.Fn prop_array_send_syscall "prop_array_t array" "struct plistref *prefp"
+.Ft bool
+.Fn prop_array_recv_syscall "const struct plistref *prefp" \
+    "prop_array_t *arrayp"
+.Ft bool
+.Fn prop_dictionary_send_syscall "prop_dictionary_t dict" \
+    "struct plistref *prefp"
+.Ft bool
+.Fn prop_dictionary_recv_syscall "const struct plistref *prefp" \
     "prop_dictionary_t *dictp"
-.Fn prop_dictionary_sendrecv_ioctl "prop_dictionary_t dict" "int fd" \
-    "unsigned long cmd" "prop_dictionary_t *dictp"
 .Sh DESCRIPTION
 The
-.Nm prop_array_send_ioctl ,
-.Nm prop_array_recv_ioctl ,
-.Nm prop_dictionary_send_ioctl ,
-.Nm prop_dictionary_recv_ioctl ,
+.Nm prop_array_send_syscall ,
+.Nm prop_array_recv_syscall ,
+.Nm prop_dictionary_send_syscall ,
 and
-.Nm prop_dictionary_sendrecv_ioctl
+.Nm prop_dictionary_recv_syscall
 functions implement the user space side of a protocol for sending property
 lists to and from the kernel using
-.Xr ioctl 2 .
+.Xr syscall 2 .
 .Sh RETURN VALUES
-If successful, functions return zero. Otherwise, an error number is returned to indicate the error.
-.Sh ERRORS
-.Fn prop_array_send_ioctl
-and
-.Fn prop_dictionary_send_ioctl
-will fail if:
-.Bl -tag -width Er
-.It Bq Er ENOMEM
-Cannot allocate memory
-.It Bq Er ENOTSUP
-Not supported
-.El
-.Pp
-.Fn prop_array_recv_ioctl
-and
-.Fn prop_dictionary_recv_ioctl
-will fail if:
-.Bl -tag -width Er
-.It Bq Er EIO
-Input/output error
-.It Bq Er ENOTSUP
-Not supported
-.El
-.Pp
-In addition to these,
-.Xr ioctl 2
-errors may be returned.
+If successful, the functions return true, false otherwise.
 .Sh EXAMPLES
 The following
 .Pq simplified
 example demonstrates using
-.Fn prop_dictionary_send_ioctl
+.Fn prop_dictionary_send_syscall
 and
-.Fn prop_dictionary_recv_ioctl
+.Fn prop_dictionary_recv_syscall
 in an application:
 .Bd -literal
 void
 foo_setprops(prop_dictionary_t dict)
 {
-    int fd;
-
-    fd = open("/dev/foo", O_RDWR, 0640);
-    if (fd == -1)
-        return;
+    struct pref pref;
 
-    (void) prop_dictionary_send_ioctl(dict, fd, FOOSETPROPS);
+    (void) prop_dictionary_send_syscall(dict, \*[Am]pref);
+    (void) my_syscall_set(\*[Am]pref);
 
-    (void) close(fd);
 }
 
 prop_dictionary_t
 foo_getprops(void)
 {
     prop_dictionary_t dict;
-    int fd;
+    struct pref pref;
 
-    fd = open("/dev/foo", O_RDONLY, 0640);
-    if (fd == -1)
-       return (NULL);
-
-    if (prop_dictionary_recv_ioctl(fd, FOOGETPROPS, \*[Am]dict) != 0)
+    (void) my_syscall_get(\*[Am]pref);
+    if (!prop_dictionary_recv_syscall(\*[Am]pref, \*[Am]dict))
         return (NULL);
 
-    (void) close(fd);
-
     return (dict);
 }
 .Ed
-.Pp
-The
-.Nm prop_dictionary_sendrecv_ioctl
-function combines the send and receive functionality, allowing for
-ioctls that require two-way communication
-.Pq for example to specify arguments for the ioctl operation .
 .Sh SEE ALSO
 .Xr prop_array 3 ,
 .Xr prop_dictionary 3 ,
index 9ea9a29..481ea5d 100644 (file)
@@ -27,7 +27,7 @@
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 .\" POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd June 21, 2007
+.Dd January 17, 2011
 .Dt PROPLIB 3
 .Os
 .Sh NAME
@@ -94,6 +94,7 @@ released using an iterator-specific release function.
 .Xr prop_number 3 ,
 .Xr prop_object 3 ,
 .Xr prop_send_ioctl 3 ,
+.Xr prop_send_syscall 3 ,
 .Xr prop_string 3
 .Sh HISTORY
 The
index 929e662..514ecff 100644 (file)
@@ -713,9 +713,11 @@ MLINKS+=posix4.9 p1003_1b.9
 MLINKS+=priv.9 priv_check.9 \
        priv.9 priv_check_cred.9
 MLINKS+=prop_copyin_ioctl.9 prop_array_copyin.9 \
+       prop_copyin_ioctl.9 prop_array_copyout.9 \
        prop_copyin_ioctl.9 prop_array_copyin_ioctl.9 \
        prop_copyin_ioctl.9 prop_array_copyout_ioctl.9 \
        prop_copyin_ioctl.9 prop_dictionary_copyin.9 \
+       prop_copyin_ioctl.9 prop_dictionary_copyout.9 \
        prop_copyin_ioctl.9 prop_dictionary_copyin_ioctl.9 \
        prop_copyin_ioctl.9 prop_dictionary_copyout_ioctl.9
 MLINKS+=rman.9 rman_activate_resource.9 \
index b62469c..17935d1 100644 (file)
@@ -1,4 +1,4 @@
-.\"    $NetBSD: prop_copyin_ioctl.9,v 1.7 2009/12/14 05:47:30 dholland Exp $
+.\"    $NetBSD: prop_copyin_ioctl.9,v 1.8 2011/01/19 20:34:23 bouyer Exp $
 .\"
 .\" Copyright (c) 2006, 2009 The NetBSD Foundation, Inc.
 .\" All rights reserved.
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 .\" POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd October 10, 2009
+.Dd January 17, 2011
 .Dt PROP_COPYIN_IOCTL 9
 .Os
 .Sh NAME
 .Nm prop_array_copyin_ioctl ,
 .Nm prop_array_copyout_ioctl ,
 .Nm prop_array_copyin ,
+.Nm prop_array_copyout ,
 .Nm prop_dictionary_copyin_ioctl ,
 .Nm prop_dictionary_copyout_ioctl ,
-.Nm prop_dictionary_copyin
+.Nm prop_dictionary_copyin ,
+.Nm prop_dictionary_copyout
 .Nd Copy property lists to and from kernel space
 .Sh SYNOPSIS
 .In libprop/proplib.h
@@ -50,6 +52,9 @@
 .Fn prop_array_copyout_ioctl "struct plistref *pref" \
     "const u_long cmd" "prop_array_t array"
 .Ft int
+.Fn prop_array_copyout "struct plistref *pref" \
+    "prop_array_t array"
+.Ft int
 .Fn prop_dictionary_copyin_ioctl "const struct plistref *pref" \
     "const u_long cmd" "prop_dictionary_t *dictp"
 .Ft int
@@ -58,6 +63,9 @@
 .Ft int
 .Fn prop_dictionary_copyout_ioctl "struct plistref *pref" \
     "const u_long cmd" "prop_dictionary_t dict"
+.Ft int
+.Fn prop_dictionary_copyout "struct plistref *pref" \
+    "prop_dictionary_t dict"
 .Sh DESCRIPTION
 The
 .Nm prop_array_copyin_ioctl ,
@@ -69,9 +77,11 @@ functions implement the kernel side of a protocol for copying property lists
 to and from the kernel using
 .Xr ioctl 2 .
 The functions
-.Nm prop_array_copyin
+.Nm prop_array_copyin ,
+.Nm prop_array_copyout ,
+.Nm prop_dictionary_copyin ,
 and
-.Nm prop_dictionary_copyin
+.Nm prop_dictionary_copyout
 implement the kernel side of a protocol for copying property lists to the
 kernel as arguments of normal system calls.
 .Pp
@@ -175,6 +185,7 @@ Not supported
 .Xr prop_array 3 ,
 .Xr prop_dictionary 3 ,
 .Xr prop_send_ioctl 3 ,
+.Xr prop_send_syscall 3 ,
 .Xr proplib 3
 .Sh HISTORY
 The
index 7f5c9a3..ff74dac 100644 (file)
@@ -1,4 +1,4 @@
-/*     $NetBSD: prop_array.h,v 1.9 2009/10/10 21:26:16 bad Exp $    */
+/*     $NetBSD: prop_array.h,v 1.11 2011/01/20 11:17:58 bouyer Exp $    */
 
 /*-
  * Copyright (c) 2006, 2009 The NetBSD Foundation, Inc.
@@ -71,8 +71,12 @@ struct plistref;
 bool           prop_array_externalize_to_pref(prop_array_t, struct plistref *);
 int            prop_array_send_ioctl(prop_array_t, int, unsigned long);
 int            prop_array_recv_ioctl(int, unsigned long, prop_array_t *);
+bool           prop_array_send_syscall(prop_array_t, struct plistref *);
+bool           prop_array_recv_syscall(const struct plistref *,
+                                       prop_array_t *);
 #elif defined(_KERNEL)
 int            prop_array_copyin(const struct plistref *, prop_array_t *);
+int            prop_array_copyout(struct plistref *, prop_array_t);
 int            prop_array_copyin_ioctl(const struct plistref *, const u_long,
                                        prop_array_t *);
 int            prop_array_copyout_ioctl(struct plistref *, const u_long,
@@ -148,6 +152,8 @@ bool                prop_array_set_cstring_nocopy(prop_array_t,
                                                   unsigned int,
                                                   const char *);
 
+bool           prop_array_add_and_rel(prop_array_t, prop_object_t);
+
 __END_DECLS
 
 #endif /* _PROPLIB_PROP_ARRAY_H_ */
index 6d5dd61..77a5804 100644 (file)
@@ -51,7 +51,7 @@ prop_array_get_bool(prop_array_t array,
        b = prop_array_get(array, indx);
        if (prop_object_type(b) != PROP_TYPE_BOOL)
                return (false);
-
+       
        *valp = prop_bool_true(b);
 
        return (true);
@@ -238,3 +238,14 @@ TEMPLATE(,)
 TEMPLATE(_nocopy,const)
 
 #undef TEMPLATE
+
+bool
+prop_array_add_and_rel(prop_array_t array, prop_object_t po)
+{
+       bool ret;
+       if (po == NULL)
+               return false;
+       ret = prop_array_add(array, po);
+       prop_object_release(po);
+       return ret;
+}
index 9611e8d..b569886 100644 (file)
@@ -1,4 +1,4 @@
-/*     $NetBSD: prop_dictionary.c,v 1.35 2009/04/14 02:53:41 haad Exp $        */
+/*     $NetBSD: prop_dictionary.c,v 1.36 2010/09/24 22:51:52 rmind Exp $       */
 
 /*-
  * Copyright (c) 2006, 2007 The NetBSD Foundation, Inc.
@@ -62,14 +62,10 @@ struct _prop_dictionary_keysym {
        struct _prop_object             pdk_obj;
        size_t                          pdk_size;
        struct rb_node                  pdk_link;
-       char                            pdk_key[1];
+       char                            pdk_key[1];
        /* actually variable length */
 };
 
-#define        RBNODE_TO_PDK(n)                                                \
-       ((struct _prop_dictionary_keysym *)                             \
-        ((uintptr_t)n - offsetof(struct _prop_dictionary_keysym, pdk_link)))
-
        /* pdk_key[1] takes care of the NUL */
 #define        PDK_SIZE_16             (sizeof(struct _prop_dictionary_keysym) + 16)
 #define        PDK_SIZE_32             (sizeof(struct _prop_dictionary_keysym) + 32)
@@ -135,8 +131,8 @@ static const struct _prop_object_type _prop_object_type_dictionary = {
        .pot_extern             =       _prop_dictionary_externalize,
        .pot_equals             =       _prop_dictionary_equals,
        .pot_equals_finish      =       _prop_dictionary_equals_finish,
-       .pot_lock               =       _prop_dictionary_lock,
-       .pot_unlock             =       _prop_dictionary_unlock,
+       .pot_lock               =       _prop_dictionary_lock,
+       .pot_unlock             =       _prop_dictionary_unlock,                
 };
 
 static _prop_object_free_rv_t
@@ -176,28 +172,32 @@ struct _prop_dictionary_iterator {
  */
 
 static int
-_prop_dict_keysym_rb_compare_nodes(const struct rb_node *n1,
-                                  const struct rb_node *n2)
+/*ARGSUSED*/
+_prop_dict_keysym_rb_compare_nodes(void *ctx __unused,
+                                  const void *n1, const void *n2)
 {
-       const prop_dictionary_keysym_t pdk1 = RBNODE_TO_PDK(n1);
-       const prop_dictionary_keysym_t pdk2 = RBNODE_TO_PDK(n2);
+       const struct _prop_dictionary_keysym *pdk1 = n1;
+       const struct _prop_dictionary_keysym *pdk2 = n2;
 
-       return (strcmp(pdk1->pdk_key, pdk2->pdk_key));
+       return strcmp(pdk1->pdk_key, pdk2->pdk_key);
 }
 
 static int
-_prop_dict_keysym_rb_compare_key(const struct rb_node *n,
-                                const void *v)
+/*ARGSUSED*/
+_prop_dict_keysym_rb_compare_key(void *ctx __unused,
+                                const void *n, const void *v)
 {
-       const prop_dictionary_keysym_t pdk = RBNODE_TO_PDK(n);
+       const struct _prop_dictionary_keysym *pdk = n;
        const char *cp = v;
 
-       return (strcmp(pdk->pdk_key, cp));
+       return strcmp(pdk->pdk_key, cp);
 }
 
-static const struct rb_tree_ops _prop_dict_keysym_rb_tree_ops = {
+static const rb_tree_ops_t _prop_dict_keysym_rb_tree_ops = {
        .rbto_compare_nodes = _prop_dict_keysym_rb_compare_nodes,
-       .rbto_compare_key   = _prop_dict_keysym_rb_compare_key,
+       .rbto_compare_key = _prop_dict_keysym_rb_compare_key,
+       .rbto_node_offset = offsetof(struct _prop_dictionary_keysym, pdk_link),
+       .rbto_context = NULL
 };
 
 static struct rb_tree _prop_dict_keysym_tree;
@@ -235,7 +235,7 @@ _prop_dict_keysym_free(prop_stack_t stack, prop_object_t *obj)
 {
        prop_dictionary_keysym_t pdk = *obj;
 
-       _prop_rb_tree_remove_node(&_prop_dict_keysym_tree, &pdk->pdk_link);
+       _prop_rb_tree_remove_node(&_prop_dict_keysym_tree, pdk);
        _prop_dict_keysym_put(pdk);
 
        return _PROP_OBJECT_FREE_DONE;
@@ -256,7 +256,7 @@ _prop_dict_keysym_externalize(struct _prop_object_externalize_context *ctx,
                                                pdk->pdk_key) == false ||
            _prop_object_externalize_end_tag(ctx, "string") == false)
                return (false);
-
+       
        return (true);
 }
 
@@ -282,10 +282,8 @@ _prop_dict_keysym_equals(prop_object_t v1, prop_object_t v2,
 static prop_dictionary_keysym_t
 _prop_dict_keysym_alloc(const char *key)
 {
-       prop_dictionary_keysym_t opdk, pdk;
-       const struct rb_node *n;
+       prop_dictionary_keysym_t opdk, pdk, rpdk;
        size_t size;
-       bool rv;
 
        _PROP_ONCE_RUN(_prop_dict_init_once, _prop_dict_init);
 
@@ -294,9 +292,8 @@ _prop_dict_keysym_alloc(const char *key)
         * we just retain it and return it.
         */
        _PROP_MUTEX_LOCK(_prop_dict_keysym_tree_mutex);
-       n = _prop_rb_tree_find(&_prop_dict_keysym_tree, key);
-       if (n != NULL) {
-               opdk = RBNODE_TO_PDK(n);
+       opdk = _prop_rb_tree_find(&_prop_dict_keysym_tree, key);
+       if (opdk != NULL) {
                prop_object_retain(opdk);
                _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex);
                return (opdk);
@@ -331,16 +328,15 @@ _prop_dict_keysym_alloc(const char *key)
         * we have to check again if it is in the tree.
         */
        _PROP_MUTEX_LOCK(_prop_dict_keysym_tree_mutex);
-       n = _prop_rb_tree_find(&_prop_dict_keysym_tree, key);
-       if (n != NULL) {
-               opdk = RBNODE_TO_PDK(n);
+       opdk = _prop_rb_tree_find(&_prop_dict_keysym_tree, key);
+       if (opdk != NULL) {
                prop_object_retain(opdk);
                _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex);
                _prop_dict_keysym_put(pdk);
                return (opdk);
        }
-       rv = _prop_rb_tree_insert_node(&_prop_dict_keysym_tree, &pdk->pdk_link);
-       _PROP_ASSERT(rv == true);
+       rpdk = _prop_rb_tree_insert_node(&_prop_dict_keysym_tree, pdk);
+       _PROP_ASSERT(rpdk == pdk);
        _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex);
        return (pdk);
 }
@@ -451,7 +447,7 @@ _prop_dictionary_externalize(struct _prop_object_externalize_context *ctx,
        pi = _prop_dictionary_iterator_locked(pd);
        if (pi == NULL)
                goto out;
-
+       
        ctx->poec_depth++;
        _PROP_ASSERT(ctx->poec_depth != 0);
 
@@ -478,7 +474,7 @@ _prop_dictionary_externalize(struct _prop_object_externalize_context *ctx,
        }
        if (_prop_object_externalize_end_tag(ctx, "dict") == false)
                goto out;
-
+       
        rv = true;
 
  out:
@@ -527,8 +523,8 @@ _prop_dictionary_equals(prop_object_t v1, prop_object_t v2,
        *stored_pointer1 = (void *)(idx + 1);
        *stored_pointer2 = (void *)(idx + 1);
 
-       *next_obj1 = &dict1->pd_array[idx].pde_objref;
-       *next_obj2 = &dict2->pd_array[idx].pde_objref;
+       *next_obj1 = dict1->pd_array[idx].pde_objref;
+       *next_obj2 = dict2->pd_array[idx].pde_objref;
 
        if (!prop_dictionary_keysym_equals(dict1->pd_array[idx].pde_key,
                                           dict2->pd_array[idx].pde_key))
@@ -537,7 +533,7 @@ _prop_dictionary_equals(prop_object_t v1, prop_object_t v2,
        return (_PROP_OBJECT_EQUALS_RECURSE);
 
  out:
-       _PROP_RWLOCK_UNLOCK(dict1->pd_rwlock);
+       _PROP_RWLOCK_UNLOCK(dict1->pd_rwlock);
        _PROP_RWLOCK_UNLOCK(dict2->pd_rwlock);
        return (rv);
 }
@@ -545,8 +541,8 @@ _prop_dictionary_equals(prop_object_t v1, prop_object_t v2,
 static void
 _prop_dictionary_equals_finish(prop_object_t v1, prop_object_t v2)
 {
-       _PROP_RWLOCK_UNLOCK(((prop_dictionary_t)v1)->pd_rwlock);
-       _PROP_RWLOCK_UNLOCK(((prop_dictionary_t)v2)->pd_rwlock);
+       _PROP_RWLOCK_UNLOCK(((prop_dictionary_t)v1)->pd_rwlock);
+       _PROP_RWLOCK_UNLOCK(((prop_dictionary_t)v2)->pd_rwlock);
 }
 
 static prop_dictionary_t
@@ -600,7 +596,7 @@ _prop_dictionary_expand(prop_dictionary_t pd, unsigned int capacity)
 
        if (oarray != NULL)
                _PROP_FREE(oarray, M_PROP_DICT);
-
+       
        return (true);
 }
 
@@ -1009,9 +1005,9 @@ prop_dictionary_set(prop_dictionary_t pd, const char *key, prop_object_t po)
 
        if (pd->pd_count == pd->pd_capacity &&
            _prop_dictionary_expand(pd,
-                                   pd->pd_capacity + EXPAND_STEP) == false) {
+                                   pd->pd_capacity + EXPAND_STEP) == false) {
                prop_object_release(pdk);
-               goto out;
+               goto out;
        }
 
        /* At this point, the store will succeed. */
@@ -1333,7 +1329,7 @@ _prop_dictionary_internalize_body(prop_stack_t stack, prop_object_t *obj,
        if (!_PROP_TAG_MATCH(ctx, "key") ||
            ctx->poic_tag_type != _PROP_TAG_TYPE_START ||
            ctx->poic_is_empty_element)
-               goto bad;
+               goto bad;
 
        if (_prop_object_internalize_decode_string(ctx,
                                        tmpkey, PDK_MAXKEY, &keylen,
@@ -1346,7 +1342,7 @@ _prop_dictionary_internalize_body(prop_stack_t stack, prop_object_t *obj,
        if (_prop_object_internalize_find_tag(ctx, "key",
                                _PROP_TAG_TYPE_END) == false)
                goto bad;
-
+   
        /* ..and now the beginning of the value. */
        if (_prop_object_internalize_find_tag(ctx, NULL,
                                _PROP_TAG_TYPE_START) == false)
index 1305302..03556dc 100644 (file)
@@ -1,4 +1,4 @@
-/*     $NetBSD: prop_dictionary.h,v 1.10 2009/10/10 21:26:16 bad Exp $ */
+/*     $NetBSD: prop_dictionary.h,v 1.12 2011/01/20 11:17:58 bouyer Exp $      */
 
 /*-
  * Copyright (c) 2006, 2009 The NetBSD Foundation, Inc.
@@ -92,9 +92,15 @@ int          prop_dictionary_recv_ioctl(int, unsigned long,
 int            prop_dictionary_sendrecv_ioctl(prop_dictionary_t,
                                               int, unsigned long,
                                               prop_dictionary_t *);
+bool           prop_dictionary_send_syscall(prop_dictionary_t,
+                    struct plistref *);
+bool           prop_dictionary_recv_syscall(const struct plistref *,
+                                          prop_dictionary_t *);
 #elif defined(_KERNEL)
 int            prop_dictionary_copyin(const struct plistref *,
                                       prop_dictionary_t *);
+int            prop_dictionary_copyout(struct plistref *,
+                                      prop_dictionary_t);
 int            prop_dictionary_copyin_ioctl(const struct plistref *,
                                             const u_long,
                                             prop_dictionary_t *);
@@ -107,6 +113,8 @@ int         prop_dictionary_copyout_ioctl(struct plistref *,
  * Utility routines to make it more convenient to work with values
  * stored in dictionaries.
  */
+bool           prop_dictionary_get_dict(prop_dictionary_t, const char *,
+                                        prop_dictionary_t *);
 bool           prop_dictionary_get_bool(prop_dictionary_t, const char *,
                                         bool *);
 bool           prop_dictionary_set_bool(prop_dictionary_t, const char *,
@@ -160,6 +168,10 @@ bool               prop_dictionary_set_cstring_nocopy(prop_dictionary_t,
                                                   const char *,
                                                   const char *);
 
+bool           prop_dictionary_set_and_rel(prop_dictionary_t,
+                                                  const char *,
+                                                  prop_object_t);
+
 __END_DECLS
 
 #endif /* _PROPLIB_PROP_DICTIONARY_H_ */
index 681a925..f7af66d 100644 (file)
 #include <libprop/proplib.h>
 #include "prop_object_impl.h"  /* only to hide kernel vs. not-kernel */
 
+bool
+prop_dictionary_get_dict(prop_dictionary_t dict, const char *key, prop_dictionary_t *dp)
+{
+       prop_object_t o;
+       o = prop_dictionary_get(dict, key);
+       if (o == NULL || prop_object_type(o) != PROP_TYPE_DICTIONARY)
+               return false;
+       *dp = o;
+       return true;
+
+}
+
 bool
 prop_dictionary_get_bool(prop_dictionary_t dict,
                         const char *key,
@@ -51,7 +63,7 @@ prop_dictionary_get_bool(prop_dictionary_t dict,
        b = prop_dictionary_get(dict, key);
        if (prop_object_type(b) != PROP_TYPE_BOOL)
                return (false);
-
+       
        *valp = prop_bool_true(b);
 
        return (true);
@@ -206,3 +218,15 @@ TEMPLATE(,)
 TEMPLATE(_nocopy,const)
 
 #undef TEMPLATE
+
+bool
+prop_dictionary_set_and_rel(prop_dictionary_t dict, const char *key,
+    prop_object_t po)
+{
+       bool ret;
+       if (po == NULL)
+               return false;
+       ret = prop_dictionary_set(dict, key, po);
+       prop_object_release(po);
+       return ret;
+}
index 9387c5d..d35964a 100644 (file)
@@ -1,4 +1,4 @@
-/*     $NetBSD: prop_kern.c,v 1.13 2009/10/11 12:13:45 bad Exp $       */
+/*     $NetBSD: prop_kern.c,v 1.15 2011/01/19 20:34:23 bouyer Exp $    */
 
 /*-
  * Copyright (c) 2006, 2009 The NetBSD Foundation, Inc.
@@ -83,6 +83,7 @@ prop_array_externalize_to_pref(prop_array_t array, struct plistref *prefp)
                errno = rv;     /* pass up error value in errno */
        return (rv == 0);
 }
+__strong_reference(prop_array_externalize_to_pref, prop_array_send_syscall)
 
 /*
  * prop_dictionary_externalize_to_pref --
@@ -99,6 +100,8 @@ prop_dictionary_externalize_to_pref(prop_dictionary_t dict, struct plistref *pre
                errno = rv;     /* pass up error value in errno */
        return (rv == 0);
 }
+__strong_reference(prop_dictionary_externalize_to_pref,
+    prop_dictionary_send_syscall)
 
 static int
 _prop_object_send_ioctl(prop_object_t obj, int fd, unsigned long cmd)
@@ -115,7 +118,7 @@ _prop_object_send_ioctl(prop_object_t obj, int fd, unsigned long cmd)
                error = errno;
        else
                error = 0;
-
+       
        free(buf);
 
        return (error);
@@ -193,7 +196,7 @@ prop_array_recv_ioctl(int fd, unsigned long cmd, prop_array_t *arrayp)
 
        if (ioctl(fd, cmd, &pref) == -1)
                return (errno);
-
+       
        return (_prop_object_internalize_from_pref(&pref, PROP_TYPE_ARRAY,
                                         (prop_object_t *)arrayp));
 }
@@ -214,6 +217,31 @@ prop_dictionary_recv_ioctl(int fd, unsigned long cmd, prop_dictionary_t *dictp)
                                         (prop_object_t *)dictp));
 }
 
+/*
+ * prop_array_recv_syscall --
+ *     Receive an array from the kernel as pref.
+ *     Pref's buf is freed on exit
+ */
+bool
+prop_array_recv_syscall(const struct plistref *pref, prop_array_t *arrayp)
+{
+       return (_prop_object_internalize_from_pref(pref, PROP_TYPE_ARRAY,
+                                        (prop_object_t *)arrayp));
+}
+
+/*
+ * prop_dictionary_recv_syscall --
+ *     Receive a dictionary from the kernel as pref.
+ *     Pref's buf is freed on exit
+ */
+bool
+prop_dictionary_recv_syscall(const struct plistref *pref,
+    prop_dictionary_t *dictp)
+{
+       return (_prop_object_internalize_from_pref(pref, PROP_TYPE_DICTIONARY,
+                                        (prop_object_t *)dictp));
+}
+
 /*
  * prop_dictionary_sendrecv_ioctl --
  *     Combination send/receive a dictionary to/from the kernel using
@@ -235,7 +263,7 @@ prop_dictionary_sendrecv_ioctl(prop_dictionary_t dict, int fd,
                error = errno;
        else
                error = 0;
-
+       
        free(buf);
 
        if (error)
@@ -368,8 +396,7 @@ prop_dictionary_copyin_ioctl(const struct plistref *pref, const u_long cmd,
 }
 
 static int
-_prop_object_copyout_ioctl(struct plistref *pref, const u_long cmd,
-                          prop_object_t obj)
+_prop_object_copyout(struct plistref *pref, prop_object_t obj)
 {
        struct proc *p = curproc;
        char *buf;
@@ -377,9 +404,6 @@ _prop_object_copyout_ioctl(struct plistref *pref, const u_long cmd,
        int error = 0;
        vm_offset_t uaddr;
 
-       if ((cmd & IOC_OUT) == 0)
-               return (EFAULT);
-
        switch (prop_object_type(obj)) {
        case PROP_TYPE_ARRAY:
                buf = prop_array_externalize(obj);
@@ -425,6 +449,36 @@ _prop_object_copyout_ioctl(struct plistref *pref, const u_long cmd,
        return (error);
 }
 
+/*
+ * prop_array_copyout --
+ *     Copy out an array to a syscall arg.
+ */
+int
+prop_array_copyout(struct plistref *pref, prop_array_t array)
+{
+       return (_prop_object_copyout(pref, array));
+}
+
+/*
+ * prop_dictionary_copyout --
+ *     Copy out a dictionary to a syscall arg.
+ */
+int
+prop_dictionary_copyout(struct plistref *pref, prop_dictionary_t dict)
+{
+       return (_prop_object_copyout(pref, dict));
+}
+
+static int
+_prop_object_copyout_ioctl(struct plistref *pref, const u_long cmd,
+                          prop_object_t obj)
+{
+       if ((cmd & IOC_OUT) == 0)
+               return (EFAULT);
+       return _prop_object_copyout(pref, obj);
+}
+
+
 /*
  * prop_array_copyout_ioctl --
  *     Copy out an array being received with an ioctl.
@@ -444,6 +498,7 @@ int
 prop_dictionary_copyout_ioctl(struct plistref *pref, const u_long cmd,
                              prop_dictionary_t dict)
 {
-       return (_prop_object_copyout_ioctl(pref, cmd, dict));
+       return (
+           _prop_object_copyout_ioctl(pref, cmd, dict));
 }
 #endif /* _KERNEL */
index 4bd715a..616e1aa 100644 (file)
@@ -61,10 +61,6 @@ struct _prop_number {
        } pn_value;
 };
 
-#define        RBNODE_TO_PN(n)                                                 \
-       ((struct _prop_number *)                                        \
-        ((uintptr_t)n - offsetof(struct _prop_number, pn_link)))
-
 _PROP_POOL_INIT(_prop_number_pool, sizeof(struct _prop_number), "propnmbr")
 
 static _prop_object_free_rv_t
@@ -85,8 +81,8 @@ static const struct _prop_object_type _prop_object_type_number = {
        .pot_free       =       _prop_number_free,
        .pot_extern     =       _prop_number_externalize,
        .pot_equals     =       _prop_number_equals,
-       .pot_lock       =       _prop_number_lock,
-       .pot_unlock     =       _prop_number_unlock,
+       .pot_lock       =       _prop_number_lock,
+       .pot_unlock     =       _prop_number_unlock,
 };
 
 #define        prop_object_is_number(x)        \
@@ -125,28 +121,31 @@ _prop_number_compare_values(const struct _prop_number_value *pnv1,
 }
 
 static int
-_prop_number_rb_compare_nodes(const struct rb_node *n1,
-                             const struct rb_node *n2)
+/*ARGSUSED*/
+_prop_number_rb_compare_nodes(void *ctx __unused,
+                             const void *n1, const void *n2)
 {
-       const prop_number_t pn1 = RBNODE_TO_PN(n1);
-       const prop_number_t pn2 = RBNODE_TO_PN(n2);
+       const struct _prop_number *pn1 = n1;
+       const struct _prop_number *pn2 = n2;
 
-       return (_prop_number_compare_values(&pn1->pn_value, &pn2->pn_value));
+       return _prop_number_compare_values(&pn1->pn_value, &pn2->pn_value);
 }
 
 static int
-_prop_number_rb_compare_key(const struct rb_node *n,
-                           const void *v)
+/*ARGSUSED*/
+_prop_number_rb_compare_key(void *ctx __unused, const void *n, const void *v)
 {
-       const prop_number_t pn = RBNODE_TO_PN(n);
+       const struct _prop_number *pn = n;
        const struct _prop_number_value *pnv = v;
 
-       return (_prop_number_compare_values(&pn->pn_value, pnv));
+       return _prop_number_compare_values(&pn->pn_value, pnv);
 }
 
-static const struct rb_tree_ops _prop_number_rb_tree_ops = {
+static const rb_tree_ops_t _prop_number_rb_tree_ops = {
        .rbto_compare_nodes = _prop_number_rb_compare_nodes,
-       .rbto_compare_key   = _prop_number_rb_compare_key,
+       .rbto_compare_key = _prop_number_rb_compare_key,
+       .rbto_node_offset = offsetof(struct _prop_number, pn_link),
+       .rbto_context = NULL
 };
 
 static struct rb_tree _prop_number_tree;
@@ -158,7 +157,7 @@ _prop_number_free(prop_stack_t stack, prop_object_t *obj)
 {
        prop_number_t pn = *obj;
 
-       _prop_rb_tree_remove_node(&_prop_number_tree, &pn->pn_link);
+       _prop_rb_tree_remove_node(&_prop_number_tree, pn);
 
        _PROP_POOL_PUT(_prop_number_pool, pn);
 
@@ -172,12 +171,11 @@ _prop_number_init(void)
 {
 
        _PROP_MUTEX_INIT(_prop_number_tree_mutex);
-       _prop_rb_tree_init(&_prop_number_tree,
-           &_prop_number_rb_tree_ops);
+       _prop_rb_tree_init(&_prop_number_tree, &_prop_number_rb_tree_ops);
        return 0;
 }
 
-static void
+static void 
 _prop_number_lock(void)
 {
        /* XXX: init necessary? */
@@ -190,7 +188,7 @@ _prop_number_unlock(void)
 {
        _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
 }
-
+       
 static bool
 _prop_number_externalize(struct _prop_object_externalize_context *ctx,
                         void *v)
@@ -211,7 +209,7 @@ _prop_number_externalize(struct _prop_object_externalize_context *ctx,
            _prop_object_externalize_append_cstring(ctx, tmpstr) == false ||
            _prop_object_externalize_end_tag(ctx, "integer") == false)
                return (false);
-
+       
        return (true);
 }
 
@@ -274,9 +272,7 @@ _prop_number_equals(prop_object_t v1, prop_object_t v2,
 static prop_number_t
 _prop_number_alloc(const struct _prop_number_value *pnv)
 {
-       prop_number_t opn, pn;
-       struct rb_node *n;
-       bool rv;
+       prop_number_t opn, pn, rpn;
 
        _PROP_ONCE_RUN(_prop_number_init_once, _prop_number_init);
 
@@ -285,9 +281,8 @@ _prop_number_alloc(const struct _prop_number_value *pnv)
         * we just retain it and return it.
         */
        _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
-       n = _prop_rb_tree_find(&_prop_number_tree, pnv);
-       if (n != NULL) {
-               opn = RBNODE_TO_PN(n);
+       opn = _prop_rb_tree_find(&_prop_number_tree, pnv);
+       if (opn != NULL) {
                prop_object_retain(opn);
                _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
                return (opn);
@@ -311,16 +306,15 @@ _prop_number_alloc(const struct _prop_number_value *pnv)
         * we have to check again if it is in the tree.
         */
        _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
-       n = _prop_rb_tree_find(&_prop_number_tree, pnv);
-       if (n != NULL) {
-               opn = RBNODE_TO_PN(n);
+       opn = _prop_rb_tree_find(&_prop_number_tree, pnv);
+       if (opn != NULL) {
                prop_object_retain(opn);
                _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
                _PROP_POOL_PUT(_prop_number_pool, pn);
                return (opn);
        }
-       rv = _prop_rb_tree_insert_node(&_prop_number_tree, &pn->pn_link);
-       _PROP_ASSERT(rv == true);
+       rpn = _prop_rb_tree_insert_node(&_prop_number_tree, pn);
+       _PROP_ASSERT(rpn == pn);
        _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
        return (pn);
 }
@@ -415,7 +409,7 @@ prop_number_size(prop_number_t pn)
        }
 
        if (pnv->pnv_signed > INT32_MAX || pnv->pnv_signed < INT32_MIN)
-               return (64);
+               return (64);
        if (pnv->pnv_signed > INT16_MAX || pnv->pnv_signed < INT16_MIN)
                return (32);
        if (pnv->pnv_signed > INT8_MAX  || pnv->pnv_signed < INT8_MIN)
@@ -486,7 +480,7 @@ prop_number_equals_integer(prop_number_t pn, int64_t val)
        if (pn->pn_value.pnv_is_unsigned &&
            (pn->pn_value.pnv_unsigned > INT64_MAX || val < 0))
                return (false);
-
+       
        return (pn->pn_value.pnv_signed == val);
 }
 
@@ -501,11 +495,11 @@ prop_number_equals_unsigned_integer(prop_number_t pn, uint64_t val)
 
        if (! prop_object_is_number(pn))
                return (false);
-
+       
        if (! pn->pn_value.pnv_is_unsigned &&
            (pn->pn_value.pnv_signed < 0 || val > INT64_MAX))
                return (false);
-
+       
        return (pn->pn_value.pnv_unsigned == val);
 }
 
@@ -547,7 +541,7 @@ _prop_number_internalize_signed(struct _prop_object_internalize_context *ctx,
 #ifndef _KERNEL                /* XXX can't check for ERANGE in the kernel */
        if ((pnv->pnv_signed == INT64_MAX || pnv->pnv_signed == INT64_MIN) &&
            errno == ERANGE)
-               return (false);
+               return (false);
 #endif
        pnv->pnv_is_unsigned = false;
        ctx->poic_cp = cp;
@@ -589,7 +583,7 @@ _prop_number_internalize(prop_stack_t stack, prop_object_t *obj,
        } else {
                if (_prop_number_internalize_signed(ctx, &pnv) == false &&
                    _prop_number_internalize_unsigned(ctx, &pnv) == false)
-                       return (true);
+                       return (true);
        }
 
        if (_prop_object_internalize_find_tag(ctx, "integer",
index dbdde97..b8ec0b4 100644 (file)
@@ -72,7 +72,7 @@ _prop_standalone_realloc(void *v, size_t size)
                memcpy(rv, v, size);    /* XXX */
                dealloc(v, 0);          /* XXX */
        }
-
+       
        return (rv);
 }
 #endif /* _STANDALONE */
@@ -120,7 +120,7 @@ _prop_object_externalize_start_tag(
            _prop_object_externalize_append_cstring(ctx, tag) == false ||
            _prop_object_externalize_append_char(ctx, '>') == false)
                return (false);
-
+       
        return (true);
 }
 
@@ -163,8 +163,8 @@ _prop_object_externalize_empty_tag(
            _prop_object_externalize_append_char(ctx, '/') == false ||
            _prop_object_externalize_append_char(ctx, '>') == false ||
            _prop_object_externalize_append_char(ctx, '\n') == false)
-               return (false);
-
+               return (false);
+       
        return (true);
 }
 
@@ -432,7 +432,7 @@ _prop_object_internalize_find_tag(struct _prop_object_internalize_context *ctx,
            (taglen != ctx->poic_tagname_len ||
             memcmp(tag, ctx->poic_tagname, taglen) != 0))
                return (false);
-
+       
        /* Check for empty tag. */
        if (*cp == '/') {
                if (ctx->poic_tag_type != _PROP_TAG_TYPE_START)
@@ -472,21 +472,21 @@ _prop_object_internalize_find_tag(struct _prop_object_internalize_context *ctx,
                return (false);
 
        ctx->poic_tagattr_len = cp - ctx->poic_tagattr;
-
+       
        cp++;
        if (*cp != '\"')
                return (false);
        cp++;
        if (_PROP_EOF(*cp))
                return (false);
-
+       
        ctx->poic_tagattrval = cp;
        while (*cp != '\"')
                cp++;
        if (_PROP_EOF(*cp))
                return (false);
        ctx->poic_tagattrval_len = cp - ctx->poic_tagattrval;
-
+       
        cp++;
        if (*cp != '>')
                return (false);
@@ -508,7 +508,7 @@ _prop_object_internalize_decode_string(
        const char *src;
        size_t tarindex;
        char c;
-
+       
        tarindex = 0;
        src = ctx->poic_cp;
 
@@ -524,7 +524,7 @@ _prop_object_internalize_decode_string(
                            src[2] == 'm' &&
                            src[3] == 'p' &&
                            src[4] == ';') {
-                               c = '&';
+                               c = '&';
                                src += 5;
                        } else if (src[1] == 'l' &&
                                   src[2] == 't' &&
@@ -567,7 +567,7 @@ _prop_object_internalize_decode_string(
                *sizep = tarindex;
        if (cpp != NULL)
                *cpp = src;
-
+       
        return (true);
 }
 
@@ -706,7 +706,7 @@ _prop_generic_internalize(const char *xml, const char *master_tag)
        }
 
  out:
-       _prop_object_internalize_context_free(ctx);
+       _prop_object_internalize_context_free(ctx);
        return (obj);
 }
 
@@ -723,7 +723,7 @@ _prop_object_internalize_context_alloc(const char *xml)
                           M_TEMP);
        if (ctx == NULL)
                return (NULL);
-
+       
        ctx->poic_xml = ctx->poic_cp = xml;
 
        /*
@@ -806,12 +806,12 @@ _prop_object_externalize_file_dirname(const char *path, char *result)
         */
        if (path == NULL || *path == '\0')
                goto singledot;
-
+       
        /* String trailing slashes, if any. */
        lastp = path + strlen(path) - 1;
        while (lastp != path && *lastp == '/')
                lastp--;
-
+       
        /* Terminate path at the last occurrence of '/'. */
        do {
                if (*lastp == '/') {
@@ -830,7 +830,7 @@ _prop_object_externalize_file_dirname(const char *path, char *result)
                }
        } while (--lastp >= path);
 
-       /* No /'s found, return ".". */
+       /* No /'s found, return ".". */
  singledot:
        strcpy(result, ".");
 }
@@ -912,7 +912,7 @@ _prop_object_internalize_map_file(const char *fname)
        mf = _PROP_MALLOC(sizeof(*mf), M_TEMP);
        if (mf == NULL)
                return (NULL);
-
+       
        fd = open(fname, O_RDONLY, 0400);
        if (fd == -1) {
                _PROP_FREE(mf, M_TEMP);
@@ -940,7 +940,7 @@ _prop_object_internalize_map_file(const char *fname)
                need_guard = true;
 
        mf->poimf_xml = mmap(NULL, need_guard ? mf->poimf_mapsize + pgsize
-                                             : mf->poimf_mapsize,
+                                             : mf->poimf_mapsize,
                            PROT_READ, MAP_FILE|MAP_SHARED, fd, (off_t)0);
        (void) close(fd);
        if (mf->poimf_xml == MAP_FAILED) {
@@ -1019,7 +1019,7 @@ prop_object_release_emergency(prop_object_t obj)
 
                /* Save pointerto unlock function */
                unlock = po->po_type->pot_unlock;
-
+               
                /* Dance a bit to make sure we always get the non-racy ocnt */
                ocnt = atomic_dec_32_nv(&po->po_refcnt);
                ocnt++;
@@ -1030,8 +1030,8 @@ prop_object_release_emergency(prop_object_t obj)
                                unlock();
                        break;
                }
-
-               _PROP_ASSERT(po->po_type);
+               
+               _PROP_ASSERT(po->po_type);              
                if ((po->po_type->pot_free)(NULL, &obj) ==
                    _PROP_OBJECT_FREE_DONE) {
                        if (unlock != NULL)
@@ -1041,7 +1041,7 @@ prop_object_release_emergency(prop_object_t obj)
 
                if (unlock != NULL)
                        unlock();
-
+               
                parent = po;
                atomic_inc_32(&po->po_refcnt);
        }
@@ -1063,7 +1063,7 @@ prop_object_release(prop_object_t obj)
 {
        struct _prop_object *po;
        struct _prop_stack stack;
-       void (*unlock)(void);
+       void (*unlock)(void); 
        int ret;
        uint32_t ocnt;
 
@@ -1079,7 +1079,7 @@ prop_object_release(prop_object_t obj)
 
                        /* Save pointer to object unlock function */
                        unlock = po->po_type->pot_unlock;
-
+                       
                        ocnt = atomic_dec_32_nv(&po->po_refcnt);
                        ocnt++;
                        _PROP_ASSERT(ocnt != 0);
@@ -1090,7 +1090,7 @@ prop_object_release(prop_object_t obj)
                                        unlock();
                                break;
                        }
-
+                       
                        ret = (po->po_type->pot_free)(&stack, &obj);
 
                        if (unlock != NULL)
@@ -1098,7 +1098,7 @@ prop_object_release(prop_object_t obj)
 
                        if (ret == _PROP_OBJECT_FREE_DONE)
                                break;
-
+                       
                        atomic_inc_32(&po->po_refcnt);
                } while (ret == _PROP_OBJECT_FREE_RECURSE);
                if (ret == _PROP_OBJECT_FREE_FAILED)
@@ -1154,7 +1154,7 @@ prop_object_equals_with_error(prop_object_t obj1, prop_object_t obj2,
 
        if (po1->po_type != po2->po_type)
                return (false);
-
+    
  continue_subtree:
        ret = (*po1->po_type->pot_equals)(obj1, obj2,
                                          &stored_pointer1, &stored_pointer2,
@@ -1165,6 +1165,8 @@ prop_object_equals_with_error(prop_object_t obj1, prop_object_t obj2,
                if (!_prop_stack_pop(&stack, &obj1, &obj2,
                                     &stored_pointer1, &stored_pointer2))
                        return true;
+               po1 = obj1;
+               po2 = obj2;
                goto continue_subtree;
        }
        _PROP_ASSERT(ret == _PROP_OBJECT_EQUALS_RECURSE);
@@ -1184,7 +1186,7 @@ finish:
                po1 = obj1;
                (*po1->po_type->pot_equals_finish)(obj1, obj2);
        }
-       return (false);
+       return (false);         
 }
 
 /*
index f907f28..f2f2494 100644 (file)
 #define        __predict_false(x)      (x)
 #endif
 
-static void rb_tree_reparent_nodes(struct rb_tree *, struct rb_node *,
-                                  unsigned int);
 static void rb_tree_insert_rebalance(struct rb_tree *, struct rb_node *);
 static void rb_tree_removal_rebalance(struct rb_tree *, struct rb_node *,
        unsigned int);
 #ifdef RBDEBUG
 static const struct rb_node *rb_tree_iterate_const(const struct rb_tree *,
-       const struct rb_node *, unsigned int);
+       const struct rb_node *, const unsigned int);
 static bool rb_tree_check_node(const struct rb_tree *, const struct rb_node *,
        const struct rb_node *, bool);
+#else
+#define        rb_tree_check_node(a, b, c, d)  true
 #endif
 
 #ifdef RBDEBUG
@@ -67,128 +67,81 @@ static bool rb_tree_check_node(const struct rb_tree *, const struct rb_node *,
 
 #define        RBUNCONST(a)    ((void *)(unsigned long)(const void *)(a))
 
-/*
- * Rather than testing for the NULL everywhere, all terminal leaves are
- * pointed to this node (and that includes itself).  Note that by setting
- * it to be const, that on some architectures trying to write to it will
- * cause a fault.
- */
-static const struct rb_node sentinel_node = {
-       .rb_nodes = { RBUNCONST(&sentinel_node),
-                     RBUNCONST(&sentinel_node),
-                     NULL },
-       .rb_u = { .u_s = { .s_sentinel = 1 } },
-};
+#define        RB_NODETOITEM(rbto, rbn)        \
+    ((void *)((uintptr_t)(rbn) - (rbto)->rbto_node_offset))
+#define        RB_ITEMTONODE(rbto, rbn)        \
+    ((rb_node_t *)((uintptr_t)(rbn) + (rbto)->rbto_node_offset))
+
+#define        RB_SENTINEL_NODE        NULL
 
 void
-_prop_rb_tree_init(struct rb_tree *rbt, const struct rb_tree_ops *ops)
+_prop_rb_tree_init(struct rb_tree *rbt, const rb_tree_ops_t *ops)
 {
        RB_TAILQ_INIT(&rbt->rbt_nodes);
 #ifdef RBDEBUG
        rbt->rbt_count = 0;
 #endif
        rbt->rbt_ops = ops;
-       *((const struct rb_node **)&rbt->rbt_root) = &sentinel_node;
+       rbt->rbt_root = RB_SENTINEL_NODE;
 }
 
-/*
- * Swap the location and colors of 'self' and its child @ which.  The child
- * can not be a sentinel node.
- */
-/*ARGSUSED*/
-static void
-rb_tree_reparent_nodes(struct rb_tree *rbt _PROP_ARG_UNUSED,
-    struct rb_node *old_father, unsigned int which)
-{
-       const unsigned int other = which ^ RB_NODE_OTHER;
-       struct rb_node * const grandpa = old_father->rb_parent;
-       struct rb_node * const old_child = old_father->rb_nodes[which];
-       struct rb_node * const new_father = old_child;
-       struct rb_node * const new_child = old_father;
-       unsigned int properties;
-
-       KASSERT(which == RB_NODE_LEFT || which == RB_NODE_RIGHT);
 
-       KASSERT(!RB_SENTINEL_P(old_child));
-       KASSERT(old_child->rb_parent == old_father);
-
-       KASSERT(rb_tree_check_node(rbt, old_father, NULL, false));
-       KASSERT(rb_tree_check_node(rbt, old_child, NULL, false));
-       KASSERT(RB_ROOT_P(old_father) || rb_tree_check_node(rbt, grandpa, NULL, false));
-
-       /*
-        * Exchange descendant linkages.
-        */
-       grandpa->rb_nodes[old_father->rb_position] = new_father;
-       new_child->rb_nodes[which] = old_child->rb_nodes[other];
-       new_father->rb_nodes[other] = new_child;
-
-       /*
-        * Update ancestor linkages
-        */
-       new_father->rb_parent = grandpa;
-       new_child->rb_parent = new_father;
-
-       /*
-        * Exchange properties between new_father and new_child.  The only
-        * change is that new_child's position is now on the other side.
-        */
-       properties = old_child->rb_properties;
-       new_father->rb_properties = old_father->rb_properties;
-       new_child->rb_properties = properties;
-       new_child->rb_position = other;
+void *
+_prop_rb_tree_find(struct rb_tree *rbt, const void *key)
+{
+       const rb_tree_ops_t *rbto = rbt->rbt_ops;
+       rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
+       struct rb_node *parent = rbt->rbt_root;
 
-       /*
-        * Make sure to reparent the new child to ourself.
-        */
-       if (!RB_SENTINEL_P(new_child->rb_nodes[which])) {
-               new_child->rb_nodes[which]->rb_parent = new_child;
-               new_child->rb_nodes[which]->rb_position = which;
+       while (!RB_SENTINEL_P(parent)) {
+               void *pobj = RB_NODETOITEM(rbto, parent);
+               const signed int diff = (*compare_key)(rbto->rbto_context,
+                   pobj, key);
+               if (diff == 0)
+                       return pobj;
+               parent = parent->rb_nodes[diff < 0];
        }
 
-       KASSERT(rb_tree_check_node(rbt, new_father, NULL, false));
-       KASSERT(rb_tree_check_node(rbt, new_child, NULL, false));
-       KASSERT(RB_ROOT_P(new_father) || rb_tree_check_node(rbt, grandpa, NULL, false));
+       return NULL;
 }
 
-bool
-_prop_rb_tree_insert_node(struct rb_tree *rbt, struct rb_node *self)
+void *
+_prop_rb_tree_insert_node(struct rb_tree *rbt, void *object)
 {
-       struct rb_node *parent, *tmp;
-       rb_compare_nodes_fn compare_nodes = rbt->rbt_ops->rbto_compare_nodes;
+       const rb_tree_ops_t *rbto = rbt->rbt_ops;
+       rbto_compare_nodes_fn compare_nodes = rbto->rbto_compare_nodes;
+       struct rb_node *parent, *tmp, *self = RB_ITEMTONODE(rbto, object);
        unsigned int position;
+       bool rebalance;
+
+       RBSTAT_INC(rbt->rbt_insertions);
 
-       self->rb_properties = 0;
        tmp = rbt->rbt_root;
        /*
         * This is a hack.  Because rbt->rbt_root is just a struct rb_node *,
-        * just like rb_node->rb_nodes[RB_NODE_LEFT], we can use this fact to
+        * just like rb_node->rb_nodes[RB_DIR_LEFT], we can use this fact to
         * avoid a lot of tests for root and know that even at root,
-        * updating rb_node->rb_parent->rb_nodes[rb_node->rb_position] will
-        * rbt->rbt_root.
+        * updating RB_FATHER(rb_node)->rb_nodes[RB_POSITION(rb_node)] will
+        * update rbt->rbt_root.
         */
-       /* LINTED: see above */
-       parent = (struct rb_node *)&rbt->rbt_root;
-       position = RB_NODE_LEFT;
+       parent = (struct rb_node *)(void *)&rbt->rbt_root;
+       position = RB_DIR_LEFT;
 
        /*
         * Find out where to place this new leaf.
         */
        while (!RB_SENTINEL_P(tmp)) {
-               const int diff = (*compare_nodes)(tmp, self);
+               void *tobj = RB_NODETOITEM(rbto, tmp);
+               const signed int diff = (*compare_nodes)(rbto->rbto_context,
+                   tobj, object);
                if (__predict_false(diff == 0)) {
                        /*
-                        * Node already exists; don't insert.
+                        * Node already exists; return it.
                         */
-                       return false;
+                       return tobj;
                }
                parent = tmp;
-               KASSERT(diff != 0);
-               if (diff < 0) {
-                       position = RB_NODE_LEFT;
-               } else {
-                       position = RB_NODE_RIGHT;
-               }
+               position = (diff < 0);
                tmp = parent->rb_nodes[position];
        }
 
@@ -196,7 +149,7 @@ _prop_rb_tree_insert_node(struct rb_tree *rbt, struct rb_node *self)
        {
                struct rb_node *prev = NULL, *next = NULL;
 
-               if (position == RB_NODE_RIGHT)
+               if (position == RB_DIR_RIGHT)
                        prev = parent;
                else if (tmp != rbt->rbt_root)
                        next = parent;
@@ -212,212 +165,337 @@ _prop_rb_tree_insert_node(struct rb_tree *rbt, struct rb_node *self)
                        prev = TAILQ_PREV(next, rb_node_qh, rb_link);
                KASSERT(prev == NULL || !RB_SENTINEL_P(prev));
                KASSERT(next == NULL || !RB_SENTINEL_P(next));
-               KASSERT(prev == NULL
-                       || (*compare_nodes)(prev, self) > 0);
-               KASSERT(next == NULL
-                       || (*compare_nodes)(self, next) > 0);
+               KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
+                   RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
+               KASSERT(next == NULL || (*compare_nodes)(rbto->rbto_context,
+                   RB_NODETOITEM(rbto, self), RB_NODETOITEM(rbto, next)) < 0);
        }
 #endif
 
        /*
         * Initialize the node and insert as a leaf into the tree.
         */
-       self->rb_parent = parent;
-       self->rb_position = position;
-       /* LINTED: rbt_root hack */
-       if (__predict_false(parent == (struct rb_node *) &rbt->rbt_root)) {
-               RB_MARK_ROOT(self);
+       RB_SET_FATHER(self, parent);
+       RB_SET_POSITION(self, position);
+       if (__predict_false(parent == (struct rb_node *)(void *)&rbt->rbt_root)) {
+               RB_MARK_BLACK(self);            /* root is always black */
+#ifndef RBSMALL
+               rbt->rbt_minmax[RB_DIR_LEFT] = self;
+               rbt->rbt_minmax[RB_DIR_RIGHT] = self;
+#endif
+               rebalance = false;
        } else {
-               KASSERT(position == RB_NODE_LEFT || position == RB_NODE_RIGHT);
-               KASSERT(!RB_ROOT_P(self));      /* Already done */
+               KASSERT(position == RB_DIR_LEFT || position == RB_DIR_RIGHT);
+#ifndef RBSMALL
+               /*
+                * Keep track of the minimum and maximum nodes.  If our
+                * parent is a minmax node and we on their min/max side,
+                * we must be the new min/max node.
+                */
+               if (parent == rbt->rbt_minmax[position])
+                       rbt->rbt_minmax[position] = self;
+#endif /* !RBSMALL */
+               /*
+                * All new nodes are colored red.  We only need to rebalance
+                * if our parent is also red.
+                */
+               RB_MARK_RED(self);
+               rebalance = RB_RED_P(parent);
        }
        KASSERT(RB_SENTINEL_P(parent->rb_nodes[position]));
        self->rb_left = parent->rb_nodes[position];
        self->rb_right = parent->rb_nodes[position];
        parent->rb_nodes[position] = self;
-       KASSERT(self->rb_left == &sentinel_node &&
-           self->rb_right == &sentinel_node);
+       KASSERT(RB_CHILDLESS_P(self));
 
        /*
         * Insert the new node into a sorted list for easy sequential access
         */
-       RBT_COUNT_INCR(rbt);
+       RBSTAT_INC(rbt->rbt_count);
 #ifdef RBDEBUG
-       if (RB_ROOT_P(self)) {
+       if (RB_ROOT_P(rbt, self)) {
                RB_TAILQ_INSERT_HEAD(&rbt->rbt_nodes, self, rb_link);
-       } else if (position == RB_NODE_LEFT) {
-               KASSERT((*compare_nodes)(self, self->rb_parent) > 0);
-               RB_TAILQ_INSERT_BEFORE(self->rb_parent, self, rb_link);
+       } else if (position == RB_DIR_LEFT) {
+               KASSERT((*compare_nodes)(rbto->rbto_context,
+                   RB_NODETOITEM(rbto, self),
+                   RB_NODETOITEM(rbto, RB_FATHER(self))) < 0);
+               RB_TAILQ_INSERT_BEFORE(RB_FATHER(self), self, rb_link);
        } else {
-               KASSERT((*compare_nodes)(self->rb_parent, self) > 0);
-               RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, self->rb_parent,
+               KASSERT((*compare_nodes)(rbto->rbto_context,
+                   RB_NODETOITEM(rbto, RB_FATHER(self)),
+                   RB_NODETOITEM(rbto, self)) < 0);
+               RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, RB_FATHER(self),
                    self, rb_link);
        }
 #endif
+       KASSERT(rb_tree_check_node(rbt, self, NULL, !rebalance));
 
-#if 0
        /*
-        * Validate the tree before we rebalance
+        * Rebalance tree after insertion
         */
-       _prop_rb_tree_check(rbt, false);
-#endif
+       if (rebalance) {
+               rb_tree_insert_rebalance(rbt, self);
+               KASSERT(rb_tree_check_node(rbt, self, NULL, true));
+       }
+
+       /* Succesfully inserted, return our node pointer. */
+       return object;
+}
+
+/*
+ * Swap the location and colors of 'self' and its child @ which.  The child
+ * can not be a sentinel node.  This is our rotation function.  However,
+ * since it preserves coloring, it great simplifies both insertion and
+ * removal since rotation almost always involves the exchanging of colors
+ * as a separate step.
+ */
+/*ARGSUSED*/
+static void
+rb_tree_reparent_nodes(struct rb_tree *rbt, struct rb_node *old_father,
+       const unsigned int which)
+{
+       const unsigned int other = which ^ RB_DIR_OTHER;
+       struct rb_node * const grandpa = RB_FATHER(old_father);
+       struct rb_node * const old_child = old_father->rb_nodes[which];
+       struct rb_node * const new_father = old_child;
+       struct rb_node * const new_child = old_father;
+
+       KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
+
+       KASSERT(!RB_SENTINEL_P(old_child));
+       KASSERT(RB_FATHER(old_child) == old_father);
+
+       KASSERT(rb_tree_check_node(rbt, old_father, NULL, false));
+       KASSERT(rb_tree_check_node(rbt, old_child, NULL, false));
+       KASSERT(RB_ROOT_P(rbt, old_father) ||
+           rb_tree_check_node(rbt, grandpa, NULL, false));
 
        /*
-        * Rebalance tree after insertion
+        * Exchange descendant linkages.
         */
-       rb_tree_insert_rebalance(rbt, self);
+       grandpa->rb_nodes[RB_POSITION(old_father)] = new_father;
+       new_child->rb_nodes[which] = old_child->rb_nodes[other];
+       new_father->rb_nodes[other] = new_child;
 
-#if 0
        /*
-        * Validate the tree after we rebalanced
+        * Update ancestor linkages
+        */
+       RB_SET_FATHER(new_father, grandpa);
+       RB_SET_FATHER(new_child, new_father);
+
+       /*
+        * Exchange properties between new_father and new_child.  The only
+        * change is that new_child's position is now on the other side.
         */
-       _prop_rb_tree_check(rbt, true);
+#if 0
+       {
+               struct rb_node tmp;
+               tmp.rb_info = 0;
+               RB_COPY_PROPERTIES(&tmp, old_child);
+               RB_COPY_PROPERTIES(new_father, old_father);
+               RB_COPY_PROPERTIES(new_child, &tmp);
+       }
+#else
+       RB_SWAP_PROPERTIES(new_father, new_child);
 #endif
+       RB_SET_POSITION(new_child, other);
 
-       return true;
+       /*
+        * Make sure to reparent the new child to ourself.
+        */
+       if (!RB_SENTINEL_P(new_child->rb_nodes[which])) {
+               RB_SET_FATHER(new_child->rb_nodes[which], new_child);
+               RB_SET_POSITION(new_child->rb_nodes[which], which);
+       }
+
+       KASSERT(rb_tree_check_node(rbt, new_father, NULL, false));
+       KASSERT(rb_tree_check_node(rbt, new_child, NULL, false));
+       KASSERT(RB_ROOT_P(rbt, new_father) ||
+           rb_tree_check_node(rbt, grandpa, NULL, false));
 }
-\f
+
 static void
 rb_tree_insert_rebalance(struct rb_tree *rbt, struct rb_node *self)
 {
-       RB_MARK_RED(self);
-
-       while (!RB_ROOT_P(self) && RB_RED_P(self->rb_parent)) {
-               const unsigned int which =
-                    (self->rb_parent == self->rb_parent->rb_parent->rb_left
-                       ? RB_NODE_LEFT
-                       : RB_NODE_RIGHT);
-               const unsigned int other = which ^ RB_NODE_OTHER;
-               struct rb_node * father = self->rb_parent;
-               struct rb_node * grandpa = father->rb_parent;
-               struct rb_node * const uncle = grandpa->rb_nodes[other];
+       struct rb_node * father = RB_FATHER(self);
+       struct rb_node * grandpa = RB_FATHER(father);
+       struct rb_node * uncle;
+       unsigned int which;
+       unsigned int other;
 
+       KASSERT(!RB_ROOT_P(rbt, self));
+       KASSERT(RB_RED_P(self));
+       KASSERT(RB_RED_P(father));
+       RBSTAT_INC(rbt->rbt_insertion_rebalance_calls);
+
+       for (;;) {
                KASSERT(!RB_SENTINEL_P(self));
+
+               KASSERT(RB_RED_P(self));
+               KASSERT(RB_RED_P(father));
                /*
                 * We are red and our parent is red, therefore we must have a
                 * grandfather and he must be black.
                 */
-               KASSERT(RB_RED_P(self)
-                       && RB_RED_P(father)
-                       && RB_BLACK_P(grandpa));
+               grandpa = RB_FATHER(father);
+               KASSERT(RB_BLACK_P(grandpa));
+               KASSERT(RB_DIR_RIGHT == 1 && RB_DIR_LEFT == 0);
+               which = (father == grandpa->rb_right);
+               other = which ^ RB_DIR_OTHER;
+               uncle = grandpa->rb_nodes[other];
+
+               if (RB_BLACK_P(uncle))
+                       break;
 
-               if (RB_RED_P(uncle)) {
+               RBSTAT_INC(rbt->rbt_insertion_rebalance_passes);
+               /*
+                * Case 1: our uncle is red
+                *   Simply invert the colors of our parent and
+                *   uncle and make our grandparent red.  And
+                *   then solve the problem up at his level.
+                */
+               RB_MARK_BLACK(uncle);
+               RB_MARK_BLACK(father);
+               if (__predict_false(RB_ROOT_P(rbt, grandpa))) {
                        /*
-                        * Case 1: our uncle is red
-                        *   Simply invert the colors of our parent and
-                        *   uncle and make our grandparent red.  And
-                        *   then solve the problem up at his level.
+                        * If our grandpa is root, don't bother
+                        * setting him to red, just return.
                         */
-                       RB_MARK_BLACK(uncle);
-                       RB_MARK_BLACK(father);
-                       RB_MARK_RED(grandpa);
-                       self = grandpa;
-                       continue;
+                       KASSERT(RB_BLACK_P(grandpa));
+                       return;
                }
-               /*
-                * Case 2&3: our uncle is black.
-                */
-               if (self == father->rb_nodes[other]) {
+               RB_MARK_RED(grandpa);
+               self = grandpa;
+               father = RB_FATHER(self);
+               KASSERT(RB_RED_P(self));
+               if (RB_BLACK_P(father)) {
                        /*
-                        * Case 2: we are on the same side as our uncle
-                        *   Swap ourselves with our parent so this case
-                        *   becomes case 3.  Basically our parent becomes our
-                        *   child.
+                        * If our greatgrandpa is black, we're done.
                         */
-                       rb_tree_reparent_nodes(rbt, father, other);
-                       KASSERT(father->rb_parent == self);
-                       KASSERT(self->rb_nodes[which] == father);
-                       KASSERT(self->rb_parent == grandpa);
-                       self = father;
-                       father = self->rb_parent;
+                       KASSERT(RB_BLACK_P(rbt->rbt_root));
+                       return;
                }
-               KASSERT(RB_RED_P(self) && RB_RED_P(father));
-               KASSERT(grandpa->rb_nodes[which] == father);
+       }
+
+       KASSERT(!RB_ROOT_P(rbt, self));
+       KASSERT(RB_RED_P(self));
+       KASSERT(RB_RED_P(father));
+       KASSERT(RB_BLACK_P(uncle));
+       KASSERT(RB_BLACK_P(grandpa));
+       /*
+        * Case 2&3: our uncle is black.
+        */
+       if (self == father->rb_nodes[other]) {
                /*
-                * Case 3: we are opposite a child of a black uncle.
-                *   Swap our parent and grandparent.  Since our grandfather
-                *   is black, our father will become black and our new sibling
-                *   (former grandparent) will become red.
+                * Case 2: we are on the same side as our uncle
+                *   Swap ourselves with our parent so this case
+                *   becomes case 3.  Basically our parent becomes our
+                *   child.
                 */
-               rb_tree_reparent_nodes(rbt, grandpa, which);
-               KASSERT(self->rb_parent == father);
-               KASSERT(self->rb_parent->rb_nodes[self->rb_position ^ RB_NODE_OTHER] == grandpa);
-               KASSERT(RB_RED_P(self));
-               KASSERT(RB_BLACK_P(father));
-               KASSERT(RB_RED_P(grandpa));
-               break;
+               rb_tree_reparent_nodes(rbt, father, other);
+               KASSERT(RB_FATHER(father) == self);
+               KASSERT(self->rb_nodes[which] == father);
+               KASSERT(RB_FATHER(self) == grandpa);
+               self = father;
+               father = RB_FATHER(self);
        }
+       KASSERT(RB_RED_P(self) && RB_RED_P(father));
+       KASSERT(grandpa->rb_nodes[which] == father);
+       /*
+        * Case 3: we are opposite a child of a black uncle.
+        *   Swap our parent and grandparent.  Since our grandfather
+        *   is black, our father will become black and our new sibling
+        *   (former grandparent) will become red.
+        */
+       rb_tree_reparent_nodes(rbt, grandpa, which);
+       KASSERT(RB_FATHER(self) == father);
+       KASSERT(RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER] == grandpa);
+       KASSERT(RB_RED_P(self));
+       KASSERT(RB_BLACK_P(father));
+       KASSERT(RB_RED_P(grandpa));
 
        /*
         * Final step: Set the root to black.
         */
        RB_MARK_BLACK(rbt->rbt_root);
 }
-\f
-struct rb_node *
-_prop_rb_tree_find(struct rb_tree *rbt, const void *key)
-{
-       struct rb_node *parent = rbt->rbt_root;
-       rb_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
 
-       while (!RB_SENTINEL_P(parent)) {
-               const int diff = (*compare_key)(parent, key);
-               if (diff == 0)
-                       return parent;
-               parent = parent->rb_nodes[diff > 0];
-       }
-
-       return NULL;
-}
-\f
 static void
-rb_tree_prune_node(struct rb_tree *rbt, struct rb_node *self, int rebalance)
+rb_tree_prune_node(struct rb_tree *rbt, struct rb_node *self, bool rebalance)
 {
-       const unsigned int which = self->rb_position;
-       struct rb_node *father = self->rb_parent;
+       const unsigned int which = RB_POSITION(self);
+       struct rb_node *father = RB_FATHER(self);
+#ifndef RBSMALL
+       const bool was_root = RB_ROOT_P(rbt, self);
+#endif
 
-       KASSERT(rebalance || (RB_ROOT_P(self) || RB_RED_P(self)));
+       KASSERT(rebalance || (RB_ROOT_P(rbt, self) || RB_RED_P(self)));
        KASSERT(!rebalance || RB_BLACK_P(self));
        KASSERT(RB_CHILDLESS_P(self));
        KASSERT(rb_tree_check_node(rbt, self, NULL, false));
 
+       /*
+        * Since we are childless, we know that self->rb_left is pointing
+        * to the sentinel node.
+        */
        father->rb_nodes[which] = self->rb_left;
 
        /*
-        * Remove ourselves from the node list and decrement the count.
+        * Remove ourselves from the node list, decrement the count,
+        * and update min/max.
         */
        RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
-       RBT_COUNT_DECR(rbt);
+       RBSTAT_DEC(rbt->rbt_count);
+#ifndef RBSMALL
+       if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self)) {
+               rbt->rbt_minmax[RB_POSITION(self)] = father;
+               /*
+                * When removing the root, rbt->rbt_minmax[RB_DIR_LEFT] is
+                * updated automatically, but we also need to update 
+                * rbt->rbt_minmax[RB_DIR_RIGHT];
+                */
+               if (__predict_false(was_root)) {
+                       rbt->rbt_minmax[RB_DIR_RIGHT] = father;
+               }
+       }
+       RB_SET_FATHER(self, NULL);
+#endif
 
+       /*
+        * Rebalance if requested.
+        */
        if (rebalance)
                rb_tree_removal_rebalance(rbt, father, which);
-       KASSERT(RB_ROOT_P(self) || rb_tree_check_node(rbt, father, NULL, true));
+       KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
 }
 
+/*
+ * When deleting an interior node
+ */
 static void
 rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,
        struct rb_node *standin)
 {
-       unsigned int standin_which = standin->rb_position;
-       unsigned int standin_other = standin_which ^ RB_NODE_OTHER;
-       struct rb_node *standin_child;
-       struct rb_node *standin_father;
+       const unsigned int standin_which = RB_POSITION(standin);
+       unsigned int standin_other = standin_which ^ RB_DIR_OTHER;
+       struct rb_node *standin_son;
+       struct rb_node *standin_father = RB_FATHER(standin);
        bool rebalance = RB_BLACK_P(standin);
 
-       if (standin->rb_parent == self) {
+       if (standin_father == self) {
                /*
                 * As a child of self, any childen would be opposite of
-                * our parent (self).
+                * our parent.
                 */
                KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_other]));
-               standin_child = standin->rb_nodes[standin_which];
+               standin_son = standin->rb_nodes[standin_which];
        } else {
                /*
                 * Since we aren't a child of self, any childen would be
-                * on the same side as our parent (self).
+                * on the same side as our parent.
                 */
                KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_which]));
-               standin_child = standin->rb_nodes[standin_other];
+               standin_son = standin->rb_nodes[standin_other];
        }
 
        /*
@@ -427,7 +505,7 @@ rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,
        /*
         * If standin has a child, it must be red.
         */
-       KASSERT(RB_SENTINEL_P(standin_child) || RB_RED_P(standin_child));
+       KASSERT(RB_SENTINEL_P(standin_son) || RB_RED_P(standin_son));
 
        /*
         * Verify things are sane.
@@ -435,83 +513,103 @@ rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,
        KASSERT(rb_tree_check_node(rbt, self, NULL, false));
        KASSERT(rb_tree_check_node(rbt, standin, NULL, false));
 
-       if (!RB_SENTINEL_P(standin_child)) {
-               /*
-                * We know we have a red child so if we swap them we can
-                * void flipping standin's child to black afterwards.
-                */
-               KASSERT(rb_tree_check_node(rbt, standin_child, NULL, true));
-               rb_tree_reparent_nodes(rbt, standin,
-                   standin_child->rb_position);
-               KASSERT(rb_tree_check_node(rbt, standin, NULL, true));
-               KASSERT(rb_tree_check_node(rbt, standin_child, NULL, true));
+       if (__predict_false(RB_RED_P(standin_son))) {
                /*
-                * Since we are removing a red leaf, no need to rebalance.
+                * We know we have a red child so if we flip it to black
+                * we don't have to rebalance.
                 */
+               KASSERT(rb_tree_check_node(rbt, standin_son, NULL, true));
+               RB_MARK_BLACK(standin_son);
                rebalance = false;
-               /*
-                * We know that standin can not be a child of self, so
-                * update before of that.
-                */
-               KASSERT(standin->rb_parent != self);
-               standin_which = standin->rb_position;
-               standin_other = standin_which ^ RB_NODE_OTHER;
+
+               if (standin_father == self) {
+                       KASSERT(RB_POSITION(standin_son) == standin_which);
+               } else {
+                       KASSERT(RB_POSITION(standin_son) == standin_other);
+                       /*
+                        * Change the son's parentage to point to his grandpa.
+                        */
+                       RB_SET_FATHER(standin_son, standin_father);
+                       RB_SET_POSITION(standin_son, standin_which);
+               }
        }
-       KASSERT(RB_CHILDLESS_P(standin));
 
-       /*
-        * If we are about to delete the standin's father, then when we call
-        * rebalance, we need to use ourselves as our father.  Otherwise
-        * remember our original father.  Also, if we are our standin's father
-        * we only need to reparent the standin's brother.
-        */
-       if (standin->rb_parent == self) {
+       if (standin_father == self) {
                /*
-                * |   R   -->   S   |
-                * | Q   S --> Q   * |
-                * |       -->       |
+                * If we are about to delete the standin's father, then when
+                * we call rebalance, we need to use ourselves as our father.
+                * Otherwise remember our original father.  Also, sincef we are
+                * our standin's father we only need to reparent the standin's
+                * brother.
+                *
+                * |    R      -->     S    |
+                * |  Q   S    -->   Q   T  |
+                * |        t  -->          |
                 */
-               standin_father = standin;
                KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_other]));
                KASSERT(!RB_SENTINEL_P(self->rb_nodes[standin_other]));
                KASSERT(self->rb_nodes[standin_which] == standin);
                /*
-                * Make our brother our son.
+                * Have our son/standin adopt his brother as his new son.
                 */
-               standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
-               standin->rb_nodes[standin_other]->rb_parent = standin;
-               KASSERT(standin->rb_nodes[standin_other]->rb_position == standin_other);
+               standin_father = standin;
        } else {
                /*
-                * |  P      -->  P    |
-                * |      S  -->    Q  |
-                * |    Q    -->       |
+                * |    R          -->    S       .  |
+                * |   / \  |   T  -->   / \  |  /   |
+                * |  ..... | S    -->  ..... | T    |
+                *
+                * Sever standin's connection to his father.
+                */
+               standin_father->rb_nodes[standin_which] = standin_son;
+               /*
+                * Adopt the far son.
                 */
-               standin_father = standin->rb_parent;
-               standin_father->rb_nodes[standin_which] =
-                   standin->rb_nodes[standin_which];
-               standin->rb_left = self->rb_left;
-               standin->rb_right = self->rb_right;
-               standin->rb_left->rb_parent = standin;
-               standin->rb_right->rb_parent = standin;
+               standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
+               RB_SET_FATHER(standin->rb_nodes[standin_other], standin);
+               KASSERT(RB_POSITION(self->rb_nodes[standin_other]) == standin_other);
+               /*
+                * Use standin_other because we need to preserve standin_which
+                * for the removal_rebalance.
+                */
+               standin_other = standin_which;
        }
 
+       /*
+        * Move the only remaining son to our standin.  If our standin is our
+        * son, this will be the only son needed to be moved.
+        */
+       KASSERT(standin->rb_nodes[standin_other] != self->rb_nodes[standin_other]);
+       standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
+       RB_SET_FATHER(standin->rb_nodes[standin_other], standin);
+
        /*
         * Now copy the result of self to standin and then replace
         * self with standin in the tree.
         */
-       standin->rb_parent = self->rb_parent;
-       standin->rb_properties = self->rb_properties;
-       standin->rb_parent->rb_nodes[standin->rb_position] = standin;
+       RB_COPY_PROPERTIES(standin, self);
+       RB_SET_FATHER(standin, RB_FATHER(self));
+       RB_FATHER(standin)->rb_nodes[RB_POSITION(standin)] = standin;
 
        /*
-        * Remove ourselves from the node list and decrement the count.
+        * Remove ourselves from the node list, decrement the count,
+        * and update min/max.
         */
        RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
-       RBT_COUNT_DECR(rbt);
+       RBSTAT_DEC(rbt->rbt_count);
+#ifndef RBSMALL
+       if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self))
+               rbt->rbt_minmax[RB_POSITION(self)] = RB_FATHER(self);
+       RB_SET_FATHER(self, NULL);
+#endif
 
        KASSERT(rb_tree_check_node(rbt, standin, NULL, false));
-       KASSERT(rb_tree_check_node(rbt, standin_father, NULL, false));
+       KASSERT(RB_FATHER_SENTINEL_P(standin)
+               || rb_tree_check_node(rbt, standin_father, NULL, false));
+       KASSERT(RB_LEFT_SENTINEL_P(standin)
+               || rb_tree_check_node(rbt, standin->rb_left, NULL, false));
+       KASSERT(RB_RIGHT_SENTINEL_P(standin)
+               || rb_tree_check_node(rbt, standin->rb_right, NULL, false));
 
        if (!rebalance)
                return;
@@ -527,46 +625,61 @@ rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,
  *
  * But it's more efficient to just evalate and recolor the child.
  */
-/*ARGSUSED*/
 static void
-rb_tree_prune_blackred_branch(struct rb_tree *rbt _PROP_ARG_UNUSED,
-    struct rb_node *self, unsigned int which)
+rb_tree_prune_blackred_branch(struct rb_tree *rbt, struct rb_node *self,
+       unsigned int which)
 {
-       struct rb_node *parent = self->rb_parent;
-       struct rb_node *child = self->rb_nodes[which];
+       struct rb_node *father = RB_FATHER(self);
+       struct rb_node *son = self->rb_nodes[which];
+#ifndef RBSMALL
+       const bool was_root = RB_ROOT_P(rbt, self);
+#endif
 
-       KASSERT(which == RB_NODE_LEFT || which == RB_NODE_RIGHT);
-       KASSERT(RB_BLACK_P(self) && RB_RED_P(child));
-       KASSERT(!RB_TWOCHILDREN_P(child));
-       KASSERT(RB_CHILDLESS_P(child));
+       KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
+       KASSERT(RB_BLACK_P(self) && RB_RED_P(son));
+       KASSERT(!RB_TWOCHILDREN_P(son));
+       KASSERT(RB_CHILDLESS_P(son));
        KASSERT(rb_tree_check_node(rbt, self, NULL, false));
-       KASSERT(rb_tree_check_node(rbt, child, NULL, false));
+       KASSERT(rb_tree_check_node(rbt, son, NULL, false));
 
        /*
         * Remove ourselves from the tree and give our former child our
         * properties (position, color, root).
         */
-       parent->rb_nodes[self->rb_position] = child;
-       child->rb_parent = parent;
-       child->rb_properties = self->rb_properties;
+       RB_COPY_PROPERTIES(son, self);
+       father->rb_nodes[RB_POSITION(son)] = son;
+       RB_SET_FATHER(son, father);
 
        /*
-        * Remove ourselves from the node list and decrement the count.
+        * Remove ourselves from the node list, decrement the count,
+        * and update minmax.
         */
        RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
-       RBT_COUNT_DECR(rbt);
+       RBSTAT_DEC(rbt->rbt_count);
+#ifndef RBSMALL
+       if (__predict_false(was_root)) {
+               KASSERT(rbt->rbt_minmax[which] == son);
+               rbt->rbt_minmax[which ^ RB_DIR_OTHER] = son;
+       } else if (rbt->rbt_minmax[RB_POSITION(self)] == self) {
+               rbt->rbt_minmax[RB_POSITION(self)] = son;
+       }
+       RB_SET_FATHER(self, NULL);
+#endif
 
-       KASSERT(RB_ROOT_P(self) || rb_tree_check_node(rbt, parent, NULL, true));
-       KASSERT(rb_tree_check_node(rbt, child, NULL, true));
+       KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
+       KASSERT(rb_tree_check_node(rbt, son, NULL, true));
 }
-/*
- *
- */
+
 void
-_prop_rb_tree_remove_node(struct rb_tree *rbt, struct rb_node *self)
+_prop_rb_tree_remove_node(struct rb_tree *rbt, void *object)
 {
-       struct rb_node *standin;
+       const rb_tree_ops_t *rbto = rbt->rbt_ops;
+       struct rb_node *standin, *self = RB_ITEMTONODE(rbto, object);
        unsigned int which;
+
+       KASSERT(!RB_SENTINEL_P(self));
+       RBSTAT_INC(rbt->rbt_removals);
+
        /*
         * In the following diagrams, we (the node to be removed) are S.  Red
         * nodes are lowercase.  T could be either red or black.
@@ -585,11 +698,8 @@ _prop_rb_tree_remove_node(struct rb_tree *rbt, struct rb_node *self)
         * |  s    -->  *    |
         */
        if (RB_CHILDLESS_P(self)) {
-               if (RB_RED_P(self) || RB_ROOT_P(self)) {
-                       rb_tree_prune_node(rbt, self, false);
-                       return;
-               }
-               rb_tree_prune_node(rbt, self, true);
+               const bool rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self);
+               rb_tree_prune_node(rbt, self, rebalance);
                return;
        }
        KASSERT(!RB_CHILDLESS_P(self));
@@ -602,7 +712,7 @@ _prop_rb_tree_remove_node(struct rb_tree *rbt, struct rb_node *self)
                 * |    S    -->  R      -->  R      |
                 * |  r      -->    s    -->    *    |
                 */
-               which = RB_LEFT_SENTINEL_P(self) ? RB_NODE_RIGHT : RB_NODE_LEFT;
+               which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT;
                KASSERT(RB_BLACK_P(self));
                KASSERT(RB_RED_P(self->rb_nodes[which]));
                KASSERT(RB_CHILDLESS_P(self->rb_nodes[which]));
@@ -615,13 +725,13 @@ _prop_rb_tree_remove_node(struct rb_tree *rbt, struct rb_node *self)
         * We invert these because we prefer to remove from the inside of
         * the tree.
         */
-       which = self->rb_position ^ RB_NODE_OTHER;
+       which = RB_POSITION(self) ^ RB_DIR_OTHER;
 
        /*
         * Let's find the node closes to us opposite of our parent
         * Now swap it with ourself, "prune" it, and rebalance, if needed.
         */
-       standin = _prop_rb_tree_iterate(rbt, self, which);
+       standin = RB_ITEMTONODE(rbto, _prop_rb_tree_iterate(rbt, object, which));
        rb_tree_swap_prune_and_rebalance(rbt, self, standin);
 }
 
@@ -631,12 +741,15 @@ rb_tree_removal_rebalance(struct rb_tree *rbt, struct rb_node *parent,
 {
        KASSERT(!RB_SENTINEL_P(parent));
        KASSERT(RB_SENTINEL_P(parent->rb_nodes[which]));
-       KASSERT(which == RB_NODE_LEFT || which == RB_NODE_RIGHT);
+       KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
+       RBSTAT_INC(rbt->rbt_removal_rebalance_calls);
 
        while (RB_BLACK_P(parent->rb_nodes[which])) {
-               unsigned int other = which ^ RB_NODE_OTHER;
+               unsigned int other = which ^ RB_DIR_OTHER;
                struct rb_node *brother = parent->rb_nodes[other];
 
+               RBSTAT_INC(rbt->rbt_removal_rebalance_passes);
+
                KASSERT(!RB_SENTINEL_P(brother));
                /*
                 * For cases 1, 2a, and 2b, our brother's children must
@@ -645,21 +758,24 @@ rb_tree_removal_rebalance(struct rb_tree *rbt, struct rb_node *parent,
                if (RB_BLACK_P(parent)
                    && RB_BLACK_P(brother->rb_left)
                    && RB_BLACK_P(brother->rb_right)) {
-                       /*
-                        * Case 1: Our brother is red, swap its position
-                        * (and colors) with our parent.  This is now case 2b.
-                        *
-                        *    B         ->        D
-                        *  x     d     ->    b     E
-                        *      C   E   ->  x   C
-                        */
                        if (RB_RED_P(brother)) {
+                               /*
+                                * Case 1: Our brother is red, swap its
+                                * position (and colors) with our parent. 
+                                * This should now be case 2b (unless C or E
+                                * has a red child which is case 3; thus no
+                                * explicit branch to case 2b).
+                                *
+                                *    B         ->        D
+                                *  A     d     ->    b     E
+                                *      C   E   ->  A   C
+                                */
                                KASSERT(RB_BLACK_P(parent));
                                rb_tree_reparent_nodes(rbt, parent, other);
                                brother = parent->rb_nodes[other];
                                KASSERT(!RB_SENTINEL_P(brother));
-                               KASSERT(RB_BLACK_P(brother));
                                KASSERT(RB_RED_P(parent));
+                               KASSERT(RB_BLACK_P(brother));
                                KASSERT(rb_tree_check_node(rbt, brother, NULL, false));
                                KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
                        } else {
@@ -668,63 +784,100 @@ rb_tree_removal_rebalance(struct rb_tree *rbt, struct rb_node *parent,
                                 * Change our brother to red, advance up rank
                                 * and go through the loop again.
                                 *
-                                *    B         ->    B
-                                *  A     D     ->  A     d
+                                *    B         ->   *B
+                                * *A     D     ->  A     d
                                 *      C   E   ->      C   E
                                 */
                                RB_MARK_RED(brother);
                                KASSERT(RB_BLACK_P(brother->rb_left));
                                KASSERT(RB_BLACK_P(brother->rb_right));
-                               if (RB_ROOT_P(parent))
-                                       return;
+                               if (RB_ROOT_P(rbt, parent))
+                                       return; /* root == parent == black */
                                KASSERT(rb_tree_check_node(rbt, brother, NULL, false));
                                KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
-                               which = parent->rb_position;
-                               parent = parent->rb_parent;
+                               which = RB_POSITION(parent);
+                               parent = RB_FATHER(parent);
+                               continue;
                        }
-               } else if (RB_RED_P(parent)
+               }
+               /*
+                * Avoid an else here so that case 2a above can hit either
+                * case 2b, 3, or 4.
+                */
+               if (RB_RED_P(parent)
                    && RB_BLACK_P(brother)
                    && RB_BLACK_P(brother->rb_left)
                    && RB_BLACK_P(brother->rb_right)) {
+                       KASSERT(RB_RED_P(parent));
                        KASSERT(RB_BLACK_P(brother));
                        KASSERT(RB_BLACK_P(brother->rb_left));
                        KASSERT(RB_BLACK_P(brother->rb_right));
+                       /*
+                        * We are black, our father is red, our brother and
+                        * both nephews are black.  Simply invert/exchange the
+                        * colors of our father and brother (to black and red
+                        * respectively).
+                        *
+                        *      |    f        -->    F        |
+                        *      |  *     B    -->  *     b    |
+                        *      |      N   N  -->      N   N  |
+                        */
                        RB_MARK_BLACK(parent);
                        RB_MARK_RED(brother);
                        KASSERT(rb_tree_check_node(rbt, brother, NULL, true));
                        break;          /* We're done! */
                } else {
-                       KASSERT(RB_BLACK_P(brother));
-                       KASSERT(!RB_CHILDLESS_P(brother));
                        /*
-                        * Case 3: our brother is black, our left nephew is
-                        * red, and our right nephew is black.  Swap our
-                        * brother with our left nephew.   This result in a
-                        * tree that matches case 4.
-                        *
-                        *     B         ->       D
-                        * A       D     ->   B     E
-                        *       c   e   -> A   C
+                        * Our brother must be black and have at least one
+                        * red child (it may have two).
                         */
+                       KASSERT(RB_BLACK_P(brother));
+                       KASSERT(RB_RED_P(brother->rb_nodes[which]) ||
+                               RB_RED_P(brother->rb_nodes[other]));
                        if (RB_BLACK_P(brother->rb_nodes[other])) {
+                               /*
+                                * Case 3: our brother is black, our near
+                                * nephew is red, and our far nephew is black.
+                                * Swap our brother with our near nephew.  
+                                * This result in a tree that matches case 4.
+                                * (Our father could be red or black).
+                                *
+                                *      |    F      -->    F      |
+                                *      |  x     B  -->  x   B    |
+                                *      |      n    -->        n  |
+                                */
                                KASSERT(RB_RED_P(brother->rb_nodes[which]));
                                rb_tree_reparent_nodes(rbt, brother, which);
-                               KASSERT(brother->rb_parent == parent->rb_nodes[other]);
+                               KASSERT(RB_FATHER(brother) == parent->rb_nodes[other]);
                                brother = parent->rb_nodes[other];
                                KASSERT(RB_RED_P(brother->rb_nodes[other]));
                        }
                        /*
-                        * Case 4: our brother is black and our right nephew
-                        * is red.  Swap our parent and brother locations and
-                        * change our right nephew to black.  (these can be
+                        * Case 4: our brother is black and our far nephew
+                        * is red.  Swap our father and brother locations and
+                        * change our far nephew to black.  (these can be
                         * done in either order so we change the color first).
                         * The result is a valid red-black tree and is a
-                        * terminal case.
+                        * terminal case.  (again we don't care about the
+                        * father's color)
+                        *
+                        * If the father is red, we will get a red-black-black
+                        * tree:
+                        *      |  f      ->  f      -->    b    |
+                        *      |    B    ->    B    -->  F   N  |
+                        *      |      n  ->      N  -->         |
+                        *
+                        * If the father is black, we will get an all black
+                        * tree:
+                        *      |  F      ->  F      -->    B    |
+                        *      |    B    ->    B    -->  F   N  |
+                        *      |      n  ->      N  -->         |
                         *
-                        *     B         ->       D
-                        * A       D     ->   B     E
-                        *       c   e   -> A   C
+                        * If we had two red nephews, then after the swap,
+                        * our former father would have a red grandson. 
                         */
+                       KASSERT(RB_BLACK_P(brother));
+                       KASSERT(RB_RED_P(brother->rb_nodes[other]));
                        RB_MARK_BLACK(brother->rb_nodes[other]);
                        rb_tree_reparent_nodes(rbt, parent, other);
                        break;          /* We're done! */
@@ -733,31 +886,40 @@ rb_tree_removal_rebalance(struct rb_tree *rbt, struct rb_node *parent,
        KASSERT(rb_tree_check_node(rbt, parent, NULL, true));
 }
 
-struct rb_node *
-_prop_rb_tree_iterate(struct rb_tree *rbt, struct rb_node *self,
-       unsigned int direction)
+void *
+_prop_rb_tree_iterate(struct rb_tree *rbt, void *object, const unsigned int direction)
 {
-       const unsigned int other = direction ^ RB_NODE_OTHER;
-       KASSERT(direction == RB_NODE_LEFT || direction == RB_NODE_RIGHT);
+       const rb_tree_ops_t *rbto = rbt->rbt_ops;
+       const unsigned int other = direction ^ RB_DIR_OTHER;
+       struct rb_node *self;
 
-       if (self == NULL) {
+       KASSERT(direction == RB_DIR_LEFT || direction == RB_DIR_RIGHT);
+
+       if (object == NULL) {
+#ifndef RBSMALL
+               if (RB_SENTINEL_P(rbt->rbt_root))
+                       return NULL;
+               return RB_NODETOITEM(rbto, rbt->rbt_minmax[direction]);
+#else
                self = rbt->rbt_root;
                if (RB_SENTINEL_P(self))
                        return NULL;
-               while (!RB_SENTINEL_P(self->rb_nodes[other]))
-                       self = self->rb_nodes[other];
-               return self;
+               while (!RB_SENTINEL_P(self->rb_nodes[direction]))
+                       self = self->rb_nodes[direction];
+               return RB_NODETOITEM(rbto, self);
+#endif /* !RBSMALL */
        }
+       self = RB_ITEMTONODE(rbto, object);
        KASSERT(!RB_SENTINEL_P(self));
        /*
         * We can't go any further in this direction.  We proceed up in the
         * opposite direction until our parent is in direction we want to go.
         */
        if (RB_SENTINEL_P(self->rb_nodes[direction])) {
-               while (!RB_ROOT_P(self)) {
-                       if (other == self->rb_position)
-                               return self->rb_parent;
-                       self = self->rb_parent;
+               while (!RB_ROOT_P(rbt, self)) {
+                       if (other == RB_POSITION(self))
+                               return RB_NODETOITEM(rbto, RB_FATHER(self));
+                       self = RB_FATHER(self);
                }
                return NULL;
        }
@@ -770,24 +932,30 @@ _prop_rb_tree_iterate(struct rb_tree *rbt, struct rb_node *self,
        KASSERT(!RB_SENTINEL_P(self));
        while (!RB_SENTINEL_P(self->rb_nodes[other]))
                self = self->rb_nodes[other];
-       return self;
+       return RB_NODETOITEM(rbto, self);
 }
 
 #ifdef RBDEBUG
 static const struct rb_node *
 rb_tree_iterate_const(const struct rb_tree *rbt, const struct rb_node *self,
-       unsigned int direction)
+       const unsigned int direction)
 {
-       const unsigned int other = direction ^ RB_NODE_OTHER;
-       KASSERT(direction == RB_NODE_LEFT || direction == RB_NODE_RIGHT);
+       const unsigned int other = direction ^ RB_DIR_OTHER;
+       KASSERT(direction == RB_DIR_LEFT || direction == RB_DIR_RIGHT);
 
        if (self == NULL) {
+#ifndef RBSMALL
+               if (RB_SENTINEL_P(rbt->rbt_root))
+                       return NULL;
+               return rbt->rbt_minmax[direction];
+#else
                self = rbt->rbt_root;
                if (RB_SENTINEL_P(self))
                        return NULL;
-               while (!RB_SENTINEL_P(self->rb_nodes[other]))
-                       self = self->rb_nodes[other];
+               while (!RB_SENTINEL_P(self->rb_nodes[direction]))
+                       self = self->rb_nodes[direction];
                return self;
+#endif /* !RBSMALL */
        }
        KASSERT(!RB_SENTINEL_P(self));
        /*
@@ -795,10 +963,10 @@ rb_tree_iterate_const(const struct rb_tree *rbt, const struct rb_node *self,
         * opposite direction until our parent is in direction we want to go.
         */
        if (RB_SENTINEL_P(self->rb_nodes[direction])) {
-               while (!RB_ROOT_P(self)) {
-                       if (other == self->rb_position)
-                               return self->rb_parent;
-                       self = self->rb_parent;
+               while (!RB_ROOT_P(rbt, self)) {
+                       if (other == RB_POSITION(self))
+                               return RB_FATHER(self);
+                       self = RB_FATHER(self);
                }
                return NULL;
        }
@@ -814,33 +982,54 @@ rb_tree_iterate_const(const struct rb_tree *rbt, const struct rb_node *self,
        return self;
 }
 
+static unsigned int
+rb_tree_count_black(const struct rb_node *self)
+{
+       unsigned int left, right;
+
+       if (RB_SENTINEL_P(self))
+               return 0;
+
+       left = rb_tree_count_black(self->rb_left);
+       right = rb_tree_count_black(self->rb_right);
+
+       KASSERT(left == right);
+
+       return left + RB_BLACK_P(self);
+}
+
 static bool
 rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
        const struct rb_node *prev, bool red_check)
 {
-       KASSERT(!self->rb_sentinel);
-       KASSERT(self->rb_left);
-       KASSERT(self->rb_right);
-       KASSERT(prev == NULL ||
-               (*rbt->rbt_ops->rbto_compare_nodes)(prev, self) > 0);
+       const rb_tree_ops_t *rbto = rbt->rbt_ops;
+       rbto_compare_nodes_fn compare_nodes = rbto->rbto_compare_nodes;
+
+       KASSERT(!RB_SENTINEL_P(self));
+       KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
+           RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
 
        /*
         * Verify our relationship to our parent.
         */
-       if (RB_ROOT_P(self)) {
+       if (RB_ROOT_P(rbt, self)) {
                KASSERT(self == rbt->rbt_root);
-               KASSERT(self->rb_position == RB_NODE_LEFT);
-               KASSERT(self->rb_parent->rb_nodes[RB_NODE_LEFT] == self);
-               KASSERT(self->rb_parent == (const struct rb_node *) &rbt->rbt_root);
+               KASSERT(RB_POSITION(self) == RB_DIR_LEFT);
+               KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
+               KASSERT(RB_FATHER(self) == (const struct rb_node *) &rbt->rbt_root);
        } else {
+               int diff = (*compare_nodes)(rbto->rbto_context,
+                   RB_NODETOITEM(rbto, self),
+                   RB_NODETOITEM(rbto, RB_FATHER(self)));
+
                KASSERT(self != rbt->rbt_root);
-               KASSERT(!RB_PARENT_SENTINEL_P(self));
-               if (self->rb_position == RB_NODE_LEFT) {
-                       KASSERT((*rbt->rbt_ops->rbto_compare_nodes)(self, self->rb_parent) > 0);
-                       KASSERT(self->rb_parent->rb_nodes[RB_NODE_LEFT] == self);
+               KASSERT(!RB_FATHER_SENTINEL_P(self));
+               if (RB_POSITION(self) == RB_DIR_LEFT) {
+                       KASSERT(diff < 0);
+                       KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
                } else {
-                       KASSERT((*rbt->rbt_ops->rbto_compare_nodes)(self, self->rb_parent) < 0);
-                       KASSERT(self->rb_parent->rb_nodes[RB_NODE_RIGHT] == self);
+                       KASSERT(diff > 0);
+                       KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_RIGHT] == self);
                }
        }
 
@@ -848,26 +1037,29 @@ rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
         * Verify our position in the linked list against the tree itself.
         */
        {
-               const struct rb_node *prev0 = rb_tree_iterate_const(rbt, self, RB_NODE_LEFT);
-               const struct rb_node *next0 = rb_tree_iterate_const(rbt, self, RB_NODE_RIGHT);
+               const struct rb_node *prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
+               const struct rb_node *next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
                KASSERT(prev0 == TAILQ_PREV(self, rb_node_qh, rb_link));
-               if (next0 != TAILQ_NEXT(self, rb_link))
-                       next0 = rb_tree_iterate_const(rbt, self, RB_NODE_RIGHT);
                KASSERT(next0 == TAILQ_NEXT(self, rb_link));
+#ifndef RBSMALL
+               KASSERT(prev0 != NULL || self == rbt->rbt_minmax[RB_DIR_LEFT]);
+               KASSERT(next0 != NULL || self == rbt->rbt_minmax[RB_DIR_RIGHT]);
+#endif
        }
 
        /*
         * The root must be black.
-        * There can never be two adjacent red nodes.
+        * There can never be two adjacent red nodes. 
         */
        if (red_check) {
-               KASSERT(!RB_ROOT_P(self) || RB_BLACK_P(self));
+               KASSERT(!RB_ROOT_P(rbt, self) || RB_BLACK_P(self));
+               (void) rb_tree_count_black(self);
                if (RB_RED_P(self)) {
                        const struct rb_node *brother;
-                       KASSERT(!RB_ROOT_P(self));
-                       brother = self->rb_parent->rb_nodes[self->rb_position ^ RB_NODE_OTHER];
-                       KASSERT(RB_BLACK_P(self->rb_parent));
-                       /*
+                       KASSERT(!RB_ROOT_P(rbt, self));
+                       brother = RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER];
+                       KASSERT(RB_BLACK_P(RB_FATHER(self)));
+                       /* 
                         * I'm red and have no children, then I must either
                         * have no brother or my brother also be red and
                         * also have no children.  (black count == 0)
@@ -915,11 +1107,11 @@ rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
                         * black, my 2nd closet relative away from my parent
                         * is either red or has a red parent or red children.
                         */
-                       if (!RB_ROOT_P(self)
+                       if (!RB_ROOT_P(rbt, self)
                            && RB_CHILDLESS_P(self)
-                           && RB_BLACK_P(self->rb_parent)) {
-                               const unsigned int which = self->rb_position;
-                               const unsigned int other = which ^ RB_NODE_OTHER;
+                           && RB_BLACK_P(RB_FATHER(self))) {
+                               const unsigned int which = RB_POSITION(self);
+                               const unsigned int other = which ^ RB_DIR_OTHER;
                                const struct rb_node *relative0, *relative;
 
                                relative0 = rb_tree_iterate_const(rbt,
@@ -933,7 +1125,7 @@ rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
                                KASSERT(RB_RED_P(relative)
                                        || RB_RED_P(relative->rb_left)
                                        || RB_RED_P(relative->rb_right)
-                                       || RB_RED_P(relative->rb_parent));
+                                       || RB_RED_P(RB_FATHER(relative)));
 #endif
                        }
                }
@@ -941,9 +1133,9 @@ rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
                 * A grandparent's children must be real nodes and not
                 * sentinels.  First check out grandparent.
                 */
-               KASSERT(RB_ROOT_P(self)
-                       || RB_ROOT_P(self->rb_parent)
-                       || RB_TWOCHILDREN_P(self->rb_parent->rb_parent));
+               KASSERT(RB_ROOT_P(rbt, self)
+                       || RB_ROOT_P(rbt, RB_FATHER(self))
+                       || RB_TWOCHILDREN_P(RB_FATHER(RB_FATHER(self))));
                /*
                 * If we are have grandchildren on our left, then
                 * we must have a child on our right.
@@ -995,11 +1187,11 @@ rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
                        const struct rb_node *prev0;
                        const struct rb_node *next0;
 
-                       prev0 = rb_tree_iterate_const(rbt, self, RB_NODE_LEFT);
+                       prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
                        KASSERT(prev0 != NULL);
                        KASSERT(RB_RIGHT_SENTINEL_P(prev0));
 
-                       next0 = rb_tree_iterate_const(rbt, self, RB_NODE_RIGHT);
+                       next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
                        KASSERT(next0 != NULL);
                        KASSERT(RB_LEFT_SENTINEL_P(next0));
                }
@@ -1008,50 +1200,74 @@ rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
        return true;
 }
 
-static unsigned int
-rb_tree_count_black(const struct rb_node *self)
-{
-       unsigned int left, right;
-
-       if (RB_SENTINEL_P(self))
-               return 0;
-
-       left = rb_tree_count_black(self->rb_left);
-       right = rb_tree_count_black(self->rb_right);
-
-       KASSERT(left == right);
-
-       return left + RB_BLACK_P(self);
-}
-
 void
-_prop_rb_tree_check(const struct rb_tree *rbt, bool red_check)
+rb_tree_check(const struct rb_tree *rbt, bool red_check)
 {
        const struct rb_node *self;
        const struct rb_node *prev;
-       unsigned int count;
+#ifdef RBSTATS
+       unsigned int count = 0;
+#endif
 
-       KASSERT(rbt->rbt_root == NULL || rbt->rbt_root->rb_position == RB_NODE_LEFT);
+       KASSERT(rbt->rbt_root != NULL);
+       KASSERT(RB_LEFT_P(rbt->rbt_root));
+
+#if defined(RBSTATS) && !defined(RBSMALL)
+       KASSERT(rbt->rbt_count > 1
+           || rbt->rbt_minmax[RB_DIR_LEFT] == rbt->rbt_minmax[RB_DIR_RIGHT]);
+#endif
 
        prev = NULL;
-       count = 0;
        TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
                rb_tree_check_node(rbt, self, prev, false);
+#ifdef RBSTATS
                count++;
+#endif
        }
+#ifdef RBSTATS
        KASSERT(rbt->rbt_count == count);
-       KASSERT(RB_SENTINEL_P(rbt->rbt_root)
-               || rb_tree_count_black(rbt->rbt_root));
-
-       /*
-        * The root must be black.
-        * There can never be two adjacent red nodes.
-        */
+#endif
        if (red_check) {
-               KASSERT(rbt->rbt_root == NULL || RB_BLACK_P(rbt->rbt_root));
+               KASSERT(RB_BLACK_P(rbt->rbt_root));
+               KASSERT(RB_SENTINEL_P(rbt->rbt_root)
+                       || rb_tree_count_black(rbt->rbt_root));
+
+               /*
+                * The root must be black.
+                * There can never be two adjacent red nodes. 
+                */
                TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
                        rb_tree_check_node(rbt, self, NULL, true);
                }
        }
 }
 #endif /* RBDEBUG */
+
+#ifdef RBSTATS
+static void
+rb_tree_mark_depth(const struct rb_tree *rbt, const struct rb_node *self,
+       size_t *depths, size_t depth)
+{
+       if (RB_SENTINEL_P(self))
+               return;
+
+       if (RB_TWOCHILDREN_P(self)) {
+               rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
+               rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
+               return;
+       }
+       depths[depth]++;
+       if (!RB_LEFT_SENTINEL_P(self)) {
+               rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
+       }
+       if (!RB_RIGHT_SENTINEL_P(self)) {
+               rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
+       }
+}
+
+void
+rb_tree_depths(const struct rb_tree *rbt, size_t *depths)
+{
+       rb_tree_mark_depth(rbt, rbt->rbt_root, depths, 1);
+}
+#endif /* RBSTATS */
index 7a2b9f3..814ba7d 100644 (file)
 #include <sys/queue.h>
 #include <machine/endian.h>
 
-struct rb_node {
-       struct rb_node *rb_nodes[3];
-#define        RB_NODE_LEFT            0
-#define        RB_NODE_RIGHT           1
-#define        RB_NODE_OTHER           1
-#define        RB_NODE_PARENT          2
-#define        rb_left         rb_nodes[RB_NODE_LEFT]
-#define        rb_right        rb_nodes[RB_NODE_RIGHT]
-#define        rb_parent       rb_nodes[RB_NODE_PARENT]
-       union {
-               struct {
-#if BYTE_ORDER == LITTLE_ENDIAN
-                       unsigned int : 28;
-                       unsigned int s_root : 1;
-                       unsigned int s_position : 1;
-                       unsigned int s_color : 1;
-                       unsigned int s_sentinel : 1;
-#endif
-#if BYTE_ORDER == BIG_ENDIAN
-                       unsigned int s_sentinel : 1;
-                       unsigned int s_color : 1;
-                       unsigned int s_position : 1;
-                       unsigned int s_root : 1;
-                       unsigned int : 28;
-#endif
-               } u_s;
-               unsigned int u_i;
-       } rb_u;
-#define        rb_root                         rb_u.u_s.s_root
-#define        rb_position                     rb_u.u_s.s_position
-#define        rb_color                        rb_u.u_s.s_color
-#define        rb_sentinel                     rb_u.u_s.s_sentinel
-#define        rb_properties                   rb_u.u_i
-#define        RB_SENTINEL_P(rb)               ((rb)->rb_sentinel + 0)
-#define        RB_LEFT_SENTINEL_P(rb)          ((rb)->rb_left->rb_sentinel + 0)
-#define        RB_RIGHT_SENTINEL_P(rb)         ((rb)->rb_right->rb_sentinel + 0)
-#define        RB_PARENT_SENTINEL_P(rb)        ((rb)->rb_parent->rb_sentinel + 0)
-#define        RB_CHILDLESS_P(rb)              (RB_LEFT_SENTINEL_P(rb) \
-                                        && RB_RIGHT_SENTINEL_P(rb))
-#define        RB_TWOCHILDREN_P(rb)            (!RB_LEFT_SENTINEL_P(rb) \
-                                        && !RB_RIGHT_SENTINEL_P(rb))
-#define        RB_ROOT_P(rb)                   ((rb)->rb_root != false)
-#define        RB_RED_P(rb)                    ((rb)->rb_color + 0)
-#define        RB_BLACK_P(rb)                  (!(rb)->rb_color)
-#define        RB_MARK_RED(rb)                 ((void)((rb)->rb_color = 1))
-#define        RB_MARK_BLACK(rb)               ((void)((rb)->rb_color = 0))
-#define        RB_MARK_ROOT(rb)                ((void)((rb)->rb_root = 1))
+
+typedef struct rb_node {
+       struct rb_node *rb_nodes[2];
+#define        RB_DIR_LEFT             0
+#define        RB_DIR_RIGHT            1
+#define        RB_DIR_OTHER            1
+#define        rb_left                 rb_nodes[RB_DIR_LEFT]
+#define        rb_right                rb_nodes[RB_DIR_RIGHT]
+
+       /*
+        * rb_info contains the two flags and the parent back pointer.
+        * We put the two flags in the low two bits since we know that
+        * rb_node will have an alignment of 4 or 8 bytes.
+        */
+       uintptr_t rb_info;
+#define        RB_FLAG_POSITION        0x2
+#define        RB_FLAG_RED             0x1
+#define        RB_FLAG_MASK            (RB_FLAG_POSITION|RB_FLAG_RED)
+#define        RB_FATHER(rb) \
+    ((struct rb_node *)((rb)->rb_info & ~RB_FLAG_MASK))
+#define        RB_SET_FATHER(rb, father) \
+    ((void)((rb)->rb_info = (uintptr_t)(father)|((rb)->rb_info & RB_FLAG_MASK)))
+
+#define        RB_SENTINEL_P(rb)       ((rb) == NULL)
+#define        RB_LEFT_SENTINEL_P(rb)  RB_SENTINEL_P((rb)->rb_left)
+#define        RB_RIGHT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_right)
+#define        RB_FATHER_SENTINEL_P(rb) RB_SENTINEL_P(RB_FATHER((rb)))
+#define        RB_CHILDLESS_P(rb) \
+    (RB_SENTINEL_P(rb) || (RB_LEFT_SENTINEL_P(rb) && RB_RIGHT_SENTINEL_P(rb)))
+#define        RB_TWOCHILDREN_P(rb) \
+    (!RB_SENTINEL_P(rb) && !RB_LEFT_SENTINEL_P(rb) && !RB_RIGHT_SENTINEL_P(rb))
+
+#define        RB_POSITION(rb) \
+    (((rb)->rb_info & RB_FLAG_POSITION) ? RB_DIR_RIGHT : RB_DIR_LEFT)
+#define        RB_RIGHT_P(rb)          (RB_POSITION(rb) == RB_DIR_RIGHT)
+#define        RB_LEFT_P(rb)           (RB_POSITION(rb) == RB_DIR_LEFT)
+#define        RB_RED_P(rb)            (!RB_SENTINEL_P(rb) && ((rb)->rb_info & RB_FLAG_RED) != 0)
+#define        RB_BLACK_P(rb)          (RB_SENTINEL_P(rb) || ((rb)->rb_info & RB_FLAG_RED) == 0)
+#define        RB_MARK_RED(rb)         ((void)((rb)->rb_info |= RB_FLAG_RED))
+#define        RB_MARK_BLACK(rb)       ((void)((rb)->rb_info &= ~RB_FLAG_RED))
+#define        RB_INVERT_COLOR(rb)     ((void)((rb)->rb_info ^= RB_FLAG_RED))
+#define        RB_ROOT_P(rbt, rb)      ((rbt)->rbt_root == (rb))
+#define        RB_SET_POSITION(rb, position) \
+    ((void)((position) ? ((rb)->rb_info |= RB_FLAG_POSITION) : \
+    ((rb)->rb_info &= ~RB_FLAG_POSITION)))
+#define        RB_ZERO_PROPERTIES(rb)  ((void)((rb)->rb_info &= ~RB_FLAG_MASK))
+#define        RB_COPY_PROPERTIES(dst, src) \
+    ((void)((dst)->rb_info ^= ((dst)->rb_info ^ (src)->rb_info) & RB_FLAG_MASK))
+#define RB_SWAP_PROPERTIES(a, b) do { \
+    uintptr_t xorinfo = ((a)->rb_info ^ (b)->rb_info) & RB_FLAG_MASK; \
+    (a)->rb_info ^= xorinfo; \
+    (b)->rb_info ^= xorinfo; \
+  } while (/*CONSTCOND*/ 0)
 #ifdef RBDEBUG
        TAILQ_ENTRY(rb_node) rb_link;
 #endif
-};
+} rb_node_t;
+
+#define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT)
+#define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT)
+#define RB_TREE_FOREACH(N, T) \
+    for ((N) = RB_TREE_MIN(T); (N); \
+       (N) = rb_tree_iterate((T), (N), RB_DIR_RIGHT))
+#define RB_TREE_FOREACH_REVERSE(N, T) \
+    for ((N) = RB_TREE_MAX(T); (N); \
+       (N) = rb_tree_iterate((T), (N), RB_DIR_LEFT))
 
 #ifdef RBDEBUG
 TAILQ_HEAD(rb_node_qh, rb_node);
 
-#define        RB_TAILQ_REMOVE                         TAILQ_REMOVE
-#define        RB_TAILQ_INIT                           TAILQ_INIT
-#define        RB_TAILQ_INSERT_HEAD(a, b, c)           TAILQ_INSERT_HEAD
-#define        RB_TAILQ_INSERT_BEFORE(a, b, c)         TAILQ_INSERT_BEFORE
-#define        RB_TAILQ_INSERT_AFTER(a, b, c, d)       TAILQ_INSERT_AFTER
+#define        RB_TAILQ_REMOVE(a, b, c)                TAILQ_REMOVE(a, b, c)
+#define        RB_TAILQ_INIT(a)                        TAILQ_INIT(a)
+#define        RB_TAILQ_INSERT_HEAD(a, b, c)           TAILQ_INSERT_HEAD(a, b, c)
+#define        RB_TAILQ_INSERT_BEFORE(a, b, c)         TAILQ_INSERT_BEFORE(a, b, c)
+#define        RB_TAILQ_INSERT_AFTER(a, b, c, d)       TAILQ_INSERT_AFTER(a, b, c, d)
 #else
 #define        RB_TAILQ_REMOVE(a, b, c)                do { } while (/*CONSTCOND*/0)
 #define        RB_TAILQ_INIT(a)                        do { } while (/*CONSTCOND*/0)
 #define        RB_TAILQ_INSERT_HEAD(a, b, c)           do { } while (/*CONSTCOND*/0)
 #define        RB_TAILQ_INSERT_BEFORE(a, b, c)         do { } while (/*CONSTCOND*/0)
 #define        RB_TAILQ_INSERT_AFTER(a, b, c, d)       do { } while (/*CONSTCOND*/0)
-#endif
+#endif /* RBDEBUG */
+
+typedef int (*rb_compare_nodes_fn)(void *ctx, const void *, const void *);
+typedef int (*rb_compare_key_fn)(void *ctx, const void *, const void *);
 
-typedef int (*rb_compare_nodes_fn)(const struct rb_node *,
-    const struct rb_node *);
-typedef int (*rb_compare_key_fn)(const struct rb_node *, const void *);
+typedef rb_compare_nodes_fn    rbto_compare_nodes_fn;
+typedef rb_compare_key_fn      rbto_compare_key_fn;
 
-struct rb_tree_ops {
+typedef struct rb_tree_ops {
        rb_compare_nodes_fn     rbto_compare_nodes;
        rb_compare_key_fn       rbto_compare_key;
-};
+       size_t                  rbto_node_offset;
+       void                    *rbto_context;
+} rb_tree_ops_t;
 
-struct rb_tree {
+typedef struct rb_tree {
        struct rb_node *rbt_root;
+       const rb_tree_ops_t *rbt_ops;
+       struct rb_node *rbt_minmax[2];
 #ifdef RBDEBUG
        struct rb_node_qh rbt_nodes;
 #endif
-       const struct rb_tree_ops *rbt_ops;
-#ifdef RBDEBUG
+#ifdef RBSTATS
        unsigned int rbt_count;
+       unsigned int rbt_insertions;
+       unsigned int rbt_removals;
+       unsigned int rbt_insertion_rebalance_calls;
+       unsigned int rbt_insertion_rebalance_passes;
+       unsigned int rbt_removal_rebalance_calls;
+       unsigned int rbt_removal_rebalance_passes;
+#endif
+} rb_tree_t;
+
+
+#ifdef RBSTATS
+#define        RBSTAT_INC(v)   ((void)((v)++))
+#define        RBSTAT_DEC(v)   ((void)((v)--))
+#else
+#define        RBSTAT_INC(v)   do { } while (/*CONSTCOND*/0)
+#define        RBSTAT_DEC(v)   do { } while (/*CONSTCOND*/0)
 #endif
-};
 
-void   _prop_rb_tree_init(struct rb_tree *, const struct rb_tree_ops *);
-bool   _prop_rb_tree_insert_node(struct rb_tree *, struct rb_node *);
-struct rb_node *
+void   _prop_rb_tree_init(struct rb_tree *, const rb_tree_ops_t *);
+void   *
+       _prop_rb_tree_insert_node(struct rb_tree *, void *);
+void   *
        _prop_rb_tree_find(struct rb_tree *, const void *);
-void   _prop_rb_tree_remove_node(struct rb_tree *, struct rb_node *);
+void   _prop_rb_tree_remove_node(struct rb_tree *, void *);
 #ifdef RBDEBUG
 void   _prop_rb_tree_check(const struct rb_tree *, bool);
 #endif
-struct rb_node *
-       _prop_rb_tree_iterate(struct rb_tree *, struct rb_node *, unsigned int);
+void *
+       _prop_rb_tree_iterate(struct rb_tree *, void *, const unsigned int);
 
 #endif /* __NetBSD__ */