tree caf7923d87ab340091b59acc40641e8127bf5b1e
parent be50b1426597b7d279d166de5ab60b4daa5f13c1
author Willy Tarreau <w@1wt.eu> 1659343049 +0200
committer Willy Tarreau <w@1wt.eu> 1660323169 +0200
encoding latin1

MINOR: ebtree: add ebmb_lookup_shorter() to pursue lookups

This function is designed to enlarge the scope of a lookup performed
by a caller via ebmb_lookup_longest() that was not satisfied with the
result. It will first visit next duplicates, and if none are found,
it will go up in the tree to visit similar keys with shorter prefixes
and will return them if they match. We only use the starting point's
value to perform the comparison since it was expected to be valid for
the looked up key, hence it has all bits in common with its own length.

The algorithm is a bit complex because when going up we may visit nodes
that are located beneath the level we just come from. However it is
guaranteed that keys having a shorter prefix will be present above the
current location, though they may be attached to the left branch of a
cover node, so we just visit all nodes as long as their prefix is too
large, possibly go down along the left branch on cover nodes, and stop
when either there's a match, or there's a non-matching prefix anymore.

The following tricky case now works fine and properly finds 10.0.0.0/7
when looking up 11.0.0.1 from tree version 1 though both belong to
different sub-trees:

  prepare map #1
    add map @1 #1 10.0.0.0/7 10.0.0.0/7
    add map @1 #1 10.0.0.0/7 10.0.0.0/7
  commit map @1 #1
  prepare map #1
    add map @2 #1 11.0.0.0/8 11.0.0.0/8
    add map @2 #1 11.0.0.0/8 11.0.0.0/8

  prepare map #1
    add map @1 #1 10.0.0.0/7 10.0.0.0/7
  commit map @1 #1
  prepare map #1
    add map @2 #1 10.0.0.0/7 10.0.0.0/7
    add map @2 #1 11.0.0.0/8 11.0.0.0/8
    add map @2 #1 11.0.0.0/8 11.0.0.0/8

(cherry picked from commit 81f3b80e32778627e7ee9802ef238d16b0822f33)
[wt: backported as needed by following patch]
Signed-off-by: Willy Tarreau <w@1wt.eu>
(cherry picked from commit a4aafe8f9c769fc46df0273d14aa5eea803edb51)
Signed-off-by: Willy Tarreau <w@1wt.eu>
(cherry picked from commit c0cfd78eb177c5599a81903262182800731d737d)
Signed-off-by: Willy Tarreau <w@1wt.eu>