path: root/sys/sys/lock.h
diff options
authorDoug Moore <dougm@FreeBSD.org>2020-07-23 17:16:20 +0000
committerDoug Moore <dougm@FreeBSD.org>2020-07-23 17:16:20 +0000
commite605dcc939848312a201b4aa53bd7bb67d862b18 (patch)
tree6c800f06b56aa8da98656aafdd79fcc3afab41af /sys/sys/lock.h
parent7df88b9ddd2e7db27ab71d38db8d0d6b4ad31e51 (diff)
Rank balanced (RB) trees are a class of balanced trees that includes
AVL trees, red-black trees, and others. Weak AVL (wavl) trees are a recently discovered member of that class. This change replaces red-black rebalancing with weak AVL rebalancing in the RB tree macros. Wavl trees sit between AVL and red-black trees in terms of how strictly balance is enforced. They have the stricter balance of AVL trees as the tree is built - a wavl tree is an AVL tree until the first deletion. Once removals start, wavl trees are lazier about rebalancing than AVL trees, so that removals can be fast, but the balance of the tree can decay to that of a red-black tree. Subsequent insertions can push balance back toward the stricter AVL conditions. Removing a node from a wavl tree never requires more than two rotations, which is better than either red-black or AVL trees. Inserting a node into a wavl tree never requires more than two rotations, which matches red-black and AVL trees. The only disadvantage of wavl trees to red-black trees is that more insertions are likely to adjust the tree a bit. That's the cost of keeping the tree more balanced. Testing has shown that for the cases where red-black trees do worst, wavl trees better balance leads to faster lookups, so that if lookups outnumber insertions by a nontrivial amount, lookup time saved exceeds the extra cost of balancing. Reviewed by: alc, gbe, markj Tested by: pho Discussed with: emaste Differential Revision: https://reviews.freebsd.org/D25480
Notes: svn path=/head/; revision=363450
Diffstat (limited to 'sys/sys/lock.h')
0 files changed, 0 insertions, 0 deletions