Page MenuHomeFreeBSD

rb_tree: allow augmentation update after element change
ClosedPublic

Authored by dougm on Tue, Aug 2, 3:27 AM.

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
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

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

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

379

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.Tue, Aug 2, 4:15 PM
kib added inline comments.
share/man/man3/tree.3
611

If
.Fn RB_AUGMENT
is defined

sys/sys/tree.h
374

I suspect this line has inconsistent indentation

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