Fix a "copy-and-paste" error that Coverity picked up in the augment code

This brings it back in line with the macros.

via Paco A. and the FRRouting project.

ok deraadt@ visa@ guenther@ tb@

make rb_n2e return a struct rb_entry *, not void *

maybe this will help prevent misassignment in the future.

use unsigned long instead of caddr_t to move between nodes and entries.

this removes the need for sys/param.h. this code can be built with
only sys/tree.h, which in turn only needs sys/_null.h.

add RBT_SET_LEFT, RBT_SET_RIGHT, and RBT_SET_PARENT

this are provided so an RBT and it's topology can be copied without
having to reinsert the copied nodes into a new tree.

there are two reasons RB

add RBT_SET_LEFT, RBT_SET_RIGHT, and RBT_SET_PARENT

this are provided so an RBT and it's topology can be copied without
having to reinsert the copied nodes into a new tree.

there are two reasons RBT_LEFT/RIGHT/PARENT macros cant be used like
RB_LEFT/RIGHT/PARENT for this. firstly, RBT_LEFT and co are functions that
return a pointer value, they dont provide access to the pointer
itself for use as an lvalue that you can assign to. secondly, RBT
entries dont store pointers to other nodes, they point to the
RBT_ENTRY structures inside other nodes. this means that RBT_SET_LEFT
and co have to get an offset from the node to the RBT_ENTRY and
store that.

show more ...

whitespace fixes, no functional change

remove a trailing \

i mustnt have cleaned this up properly when i copied the tree.h code

from Ilya Kaliman

add RBT_POISON and RBT_CHECK so you can poison the pointers in RBT_ENTRYs

this seems like a better way forward than simply removing the
poisoning that uvm does.

fix $OpenBSD$ tag

rename the members of rb_entry so they dont keep working with RB macros

provide an implementation of red black trees using functions

the main goal of this change is to reduce the amount of code that
is generated as a result of using the macro implementation (RB_FOO)
of

provide an implementation of red black trees using functions

the main goal of this change is to reduce the amount of code that
is generated as a result of using the macro implementation (RB_FOO)
of red black trees. on amd64 we should get a few dozen kilobytes
of code space back, and make red black trees more icache friendly
at the same time.

the new (RBT_FOO) implementation is modelled on the existing one,
but has some minor api variations. generally you can replace RB_
with RBT_ and get most of the way to converting code.

internally the red black tree functions all take an rb_type struct
that describes the layout of the object wired into a tree (ie, the
offset of the RBT_ENTRY inside a node), the comparison function,
and an optional augment function. because the functions are supposed
to be used for all types, they end up taking void * for the node
pointers instead of specific types. the tree is operated on as
pointers between the RBT_ENTRY structs instead of the nodes, which
gave me some type safety when implementing the code (cos casts
to/from void * dont ever fail, and continually calculating the
offset of the rb entry is annoying). RBT_ENTRYs are turned into
node pointers by prepending the offset stored in the rb_type struct
before theyre given to the comparison function or returned to the
caller.

to provide type safety on top of this, RBT_PROTOTYPE generates static
inline function wrappers that only take arguments of the right type,
and implicitly provide the rb_type struct argument to the actual
RBT functions. therefore the actual functions should never be called
directly, all calls should go through the RBT_ wrappers.

RBT_GENERATE is responsible for creating the rb_type struct used
by these wrappers. notably it also generates a wrapper around the
compare function so the user provided one must take the right types
instead of void *.

in terms of speed, this code is comparable to the macro implementation.
eg, insertion is very slightly slower in microbenchmarks, but
deletion appears to be significantly faster. this is possibly because
of the aggressive inlining ive done inside the delete codepaths.

the code is not yet wired into the kernel build.

it also needs to be said that there have been several attempts
before this to provide functions for at least some parts of the
kernels red black trees. that work made this a lot easier.

ok deraadt@ jung@ tedu@

show more ...