rb_tree: allow augmentation update after element change
ClosedPublic
Actions

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

Details

Reviewers

kib
alc

Commits

rG7ba58de6b6d0: rb_tree: update augmentation after element change
rG35557a0d9169: rb_tree: update augmentation after element change

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.

dougm mentioned this in D36001: iommu_gas: add iommu_gas_remove().Aug 2 2022, 3:45 AM

kib added inline comments.Aug 2 2022, 11:55 AM

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.