Paths

Table of Contentst

Differential D36010

rb_tree: allow augmentation update after element change
ClosedPublic
Actions

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

Tags

None

Referenced Files

	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

	Unknown Object (File)
	Aug 17 2024, 10:54 AM

	Unknown Object (File)
	Aug 17 2024, 2:49 AM

	Unknown Object (File)
	Aug 7 2024, 11:28 AM

View All 60 Files

Subscribers

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

Lint

Lint Skipped

Unit

Tests Skipped

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.

Accept all reviewer suggestions.

dougm marked 2 inline comments as done.Aug 2 2022, 4:15 PM

kib accepted this revision.Aug 2 2022, 4:17 PM

kib added inline comments.

share/man/man3/tree.3
610	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

Closed by commit rG35557a0d9169: rb_tree: update augmentation after element change (authored by dougm). · Explain WhyAug 2 2022, 4:23 PM

This revision was automatically updated to reflect the committed changes.

dougm added a commit: rG35557a0d9169: rb_tree: update augmentation after element change.

Herald added a subscriber: imp. · View Herald TranscriptAug 2 2022, 4:23 PM

dougm added a commit: rG7ba58de6b6d0: rb_tree: update augmentation after element change.Aug 22 2022, 9:23 AM

Revision Contents
Changeset List

Path

Size

share/

man/

man3/

14 lines

sys/

sys/

19 lines

Diff 108824

share/man/man3/tree.3

Loading...

sys/sys/tree.h

Loading...