rb_tree: let insert search start from adjacent node

[dougm]

Summary

When the node to insert in the rb_tree is known to precede or follow a particular node, new methods RB_INSERT_PREV and RB_INSERT_NEXT, defined here, allow the search for where to insert the new node begin with that particular node, rather than at the root, to save a bit of time.

Using those methods, instead of RB_INSERT, in managing a tree in iommu_gas.c, saves a wee bit of time.

[dougm]

Move the left/right path walking code into the insert function.

[dougm]

Correct variable names.

[dougm]

Add a manpage symlink.

[dougm]

Reverse the order of insertion of the boundary entries of the tree. The 'end' entry, with its empty range, won't be considered 'changed' by augmentation, so won't lead to an augmentation update in 'begin', so insert it first.

If empty ranges can be routinely inserted, then the conditions for defining change by augmentation would need to change.

[dougm]

I just updated the wrong review request with an unrelated patch. Ignore for now.

[dougm]

Resolve conflict with recent commit.

[kib]

Should there be some checks, at least in DIAGNOSTICS case, that the position of inserted element is the right one?

[dougm]

With DIAGNOSTIC defined, verify that the user of RB_INSERT_{PREV,NEXT} is using it properly.

[kib]

sys/sys/tree.h

922

#if defined(_KERNEL) && defined(DIAGNOSTIC)