tree 93ed723fb93893bde3aa0cd7edea3b163e345ad7
parent 0dc9e6dca2b32a288dcd272b4606a01fa712010c
author Willy Tarreau <w@1wt.eu> 1659343049 +0200
committer Willy Tarreau <w@1wt.eu> 1659347986 +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