Copy stable/9 to releng/9.3 as part of the 9.3-RELEASE cycle.

Approved by: re (implicit)
Sponsored by: The FreeBSD Foundation

Copy head to stable/9 as part of 9.0-RELEASE release cycle.

Approved by: re (implicit)

In sys/tree.h:
* Add RB_FOREACH_FROM() which continues traversal *at*
the y-node provided. There is no pre-increment.
* Nuke RB_FOREACH_SAFE as it was buggy; it would omit the final node.
* Replace RB_FOREACH_SAFE() with a working implementation
derived from RB_FOREACH_FROM().
The key observation is that we now only check the loop-control
variable, but still cache the next member pointer.
* Add RB_FOREACH_REVERSE_FROM() which continues backwards
traversal *at* the y-node provided. There is no pre-increment.
Typically this is used to back out of allocations made
whilst walking an RB-tree.
* Add RB_FOREACH_REVERSE_SAFE() which performs insertion and
deletion safe backwards traversal.

Add macro RB_FOREACH_SAFE(), which accepts an additional argument
specifying a temporary tree node pointer. It may be used in a
similar way to the *_SAFE() macros in <sys/queue.h>.

Implement RB_PREV() AND RB_FOREACH_REVERSE().

Simplify/optimize RB_NFIND().

Submitted by: Andriy Gapon <avg@icyb.net.ua>

Add the RB_PROTOTYPE_STATIC and RB_GENERATE_STATIC macros.

Approved by: markm (mentor)

Add the RB_NFIND() macro, which is useful for red-black tree searches
for which there may not be an exact match.

Reviewed by: glebius, julian
Approved by: markm (mentor)

Make the default RB_AUGMENT() produce a 'do {} while (0)' instead
of nothing. This prevents the compiler from complaining about empty
if statements when compiled with higher WARN levels.

Add FreeBSD tag

This commit was generated by cvs2svn to compensate for changes in r127563,
which included commits to RCS files with non-trunk default branches.

Synch with NetBSD: avoid "unused parameter" warning.

Import the original directly from NetBSD instead of via OpenBSD.

Sync with OpenBSD (two-year old bug fix)

Import OpenBSD's <sys/tree.h>, needed by OpenSSH.

Obtained from: OpenBSD