Page MenuHomeFreeBSD

rb_tree: allow augmentation update after element change
ClosedPublic

Authored by dougm on Aug 2 2022, 3:27 AM.
Tags
None
Referenced Files
F105100346: D36010.diff
Thu, Dec 12, 9:48 AM
Unknown Object (File)
Thu, Dec 5, 3:14 PM
Unknown Object (File)
Sun, Dec 1, 1:38 AM
Unknown Object (File)
Oct 3 2024, 6:35 AM
Unknown Object (File)
Sep 8 2024, 4:33 AM
Unknown Object (File)
Sep 8 2024, 3:48 AM
Unknown Object (File)
Sep 2 2024, 6:12 PM
Unknown Object (File)
Aug 18 2024, 4:37 PM
Subscribers

Details

Summary

For an augmented rb_tree, allow a faster alternative to removing an element from the tree, tweaking it slightly, and inserting it back into the tree, knowing that its relative position in the tree is unchanged. Instead, just change the element and invoke RB_UPDATE_AUGMENT to fix the augmentation data for all the nodes in the tree.

Diff Detail

Repository
rG FreeBSD src repository
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

dougm requested review of this revision.Aug 2 2022, 3:27 AM
dougm created this revision.
sys/sys/tree.h
378

Don't we need the block ({}) around RB_AUGMENT() there, for macro expansion safety?

380

I believe CONSTCOND was the annotation for lint, which we removed quite long time ago. I do not see a need to insert it into the new code.

Accept all reviewer suggestions.

dougm marked 2 inline comments as done.Aug 2 2022, 4:15 PM
kib added inline comments.
share/man/man3/tree.3
612

If
.Fn RB_AUGMENT
is defined

sys/sys/tree.h
375

I suspect this line has inconsistent indentation

This revision is now accepted and ready to land.Aug 2 2022, 4:17 PM