Add RB_REINSERT(3), a low overhead alternative to removing a node
and reinserting it back with an updated key.
This is one of dependencies for the upcoming stats(3) code.
Details
Details
- Reviewers
cem - Group Reviewers
manpages - Commits
- rS352837: Add RB_REINSERT(3), a low overhead alternative to removing a node
Diff Detail
Diff Detail
- Repository
- rS FreeBSD src repository - subversion
- Lint
Lint Not Applicable - Unit
Tests Not Applicable
Event Timeline
Comment Actions
Small grammo, nothing major.
| share/man/man3/tree.3 | ||
|---|---|---|
| 582 ↗ | (On Diff #62545) | s/an lower overhead/a lower overhead/ |
Comment Actions
Thanks! Some pretty minor / trivial feedback below. Looks good to me once those are addressed or responded to in some way (I'll be sure to mark it explicitly in Phab).
| share/man/man3/tree.3 | ||
|---|---|---|
| 100–101 ↗ | (On Diff #62545) | alphabetically, the sort here is backwards ("REI" before "REM"). |
| 192–195 ↗ | (On Diff #62545) | Ditto |
| 577 ↗ | (On Diff #62545) | "after ... after" is a little awkward, but not especially bad. I'd prefer "must" over "should," although I guess you could also RB_REMOVE/RB_INSERT if you really wanted. I would probably write this sentence as:
(The RB tree macros act on some arbitrary comparator which must be stable in some way, but don't explicitly have keys.) @bcr, thoughts? |
| 579–581 ↗ | (On Diff #62545) | I'd just drop this sentence, I think. It's a clarification for the name REBALANCE, which has been changed to be less confusing because of the possible confusion implied by this sentence. (And most functions don't need calling most of the time; we don't document that for every single one.) |
| sys/sys/tree.h | ||
| 416 ↗ | (On Diff #62545) | This might just be phabricator fuckiness, but double check the tabs of the trailing \ line up with the preceding lines? |
| 772–774 ↗ | (On Diff #62545) | Fwiw, in other macros cmp is just used without the wrapping parentheses. E.g., cmp(cmpelm, elm) >= 0 Fine as-is, but if you want to change it to be consistent with the other macros that's cool too. |
| share/man/man3/tree.3 | ||
|---|---|---|
| 100–101 ↗ | (On Diff #62545) | Those lists don't seem to be alphabetically sorted, though? |
Comment Actions
Be sure to bump .Dd of tree.3 before you commit. Thanks!
| share/man/man3/tree.3 | ||
|---|---|---|
| 100–101 ↗ | (On Diff #62545) | They're sort of alpha sorted within a bunch of distinct logical groupings, and I'd contend that something like REINSERT is part of the group of {INSERT, REMOVE}, but I could see the argument that it's distinct. So I'm ok either way here, but if it were me, I'd alpha REINSERT between INSERT and REMOVE. Not a big deal to leave as-is. |