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
Unknown Object (File)
Dec 20 2023, 12:25 AM
Unknown Object (File)
Dec 12 2023, 4:46 AM
Unknown Object (File)
Nov 28 2023, 8:06 PM
Unknown Object (File)
Nov 25 2023, 4:30 PM
Unknown Object (File)
Nov 6 2023, 5:10 PM
Unknown Object (File)
Nov 6 2023, 3:00 PM
Unknown Object (File)
Nov 6 2023, 1:17 PM
Unknown Object (File)
Oct 27 2023, 7:01 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