pctrie: change for vm_radix compatibility

[dougm]

Summary

Restructure parts of pctrie code to make it more compatible with the needs of vm_radix code.

1. End passing function pointers for memory management.

By breaking insertion into two functions, the call for allocating memory can happen at the top level and be inlined, rather than happening via an function pointer to a memory allocator.

By changing the remove function slightly, freeing of memory, when necessary, can happen at the top level and be inlined.

By turning the reclamation code into two functions, one for starting iteration over to-be-freed nodes and the other continuing it, all the freeing can happen at the top level and be inlined.

2. Offer a version of remove that does not panic and returns the freed value (or NULL).
3. Offer a 'replace' operation, to replace one leaf with another that has the same key.

These are three of the roadblocks that prevent code sharing between pctrie and vm_radix code.

Test Plan

I have booted a kernel with these changes in place.

[dougm]

Rename 'rtree' to 'ptree' in a few places to keep consistent with pctrie naming conventions.

[markj]

sys/kern/subr_pctrie.c

263–264

The function also inserts the value in some cases.

568

This line looks to be too long.

[dougm]

Expose PCTRIE_PAD in the header file, since it exists only to remind users of pctries not to allocate nodes at odd addresses.

[dougm]

Correct a typo in a comment.

[dougm]

Rewrite some comments.

[dougm]

Is there any more feedback to offer on this change?