HomeFreeBSD

rb_tree: update augmentation after element change

Description

rb_tree: update augmentation after element change

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.

Reviewed by: kib
MFC after: 1 week
Differential Revision: https://reviews.freebsd.org/D36010

(cherry picked from commit 35557a0d9169172b90df903b0daf389c2839b749)

Details

Provenance
dougmAuthored on Aug 2 2022, 4:19 PM
Reviewer
kib
Differential Revision
D36010: rb_tree: allow augmentation update after element change
Parents
rGd86e51e9956c: Adjust function definition in subr_devmap.c to avoid clang 15 warning
Branches
Unknown
Tags
Unknown