HomeFreeBSD

libalias: Fix splay comparsion bug

Description

libalias: Fix splay comparsion bug

Comparing elements in a tree requires transitiviy. If a < b and b < c
then a must be smaller than c. This way the tree elements are always
pairwise comparable.

Tristate comparsion functions returning values lower, equal, or
greater than zero, are usually implemented by a simple subtraction of
the operands. If the size of the operands are equal to the size of
the result, integer modular arithmetics kick in and violates the
transitivity.

Example:
Working on byte with 0, 120, and 240. Now computing the differences:

120 -   0 = 120
240 - 120 = 120
240 -   0 = -16

MFC after: 3 days

Details

Provenance
donnerAuthored on Jul 2 2021, 9:41 PM
Parents
rGdc3548453689: dumpfs(8): add option to only print superblock information
Branches
Unknown
Tags
Unknown