IMPORT: cebtree: private: fix the duplicate detection in the lookup shortcut

IMPORT: cebtree: private: fix the duplicate detection in the lookup shortcut

Commit 6b5cd28 ("OPTIM: descent: stop at the node when the path to the
leaf is not used") made _ceb_descend() stop as soon as a match is found
on the key when the caller requests none of the ret_* pointers needed by
insert and delete. This overlooked a special case needed for duplicates,
which require to descend to the leaf. The detection performed at the end
of the function is:

  if (is_leaf && _ceb_gettag(node->b[0]) && _ceb_gettag(node->b[1]) &&
     (_ceb_clrtag(node->b[0]) != node || _ceb_clrtag(node->b[1]) != node))

It needs <is_leaf>, i.e. the knowledge that the node was reached through
a leaf pointer which is not its own, because a node's role (node/leaf)
is only figured by the path used to reach it, and the state of the leaf
itself is not sufficient. For example, inserting "s1", "s2", or "s2",
"s2" both produce a second node whose b[0] is a tagged pointer to the
first node and whose b[1] is a tagged pointer to itself. Only the tag
of the pointer leading to it differs.

Two independent problems follow:

  - the shortcut to the leaf from the commit above does not update
    <is_leaf>. For arrays and strings it assigns "node = ln"/"node = rn"
    then breaks, so is_leaf still describes the node we came from, and
    a duplicate is reported as a regular leaf ;

  - the shortcut may stop on an inner node instead of the leaf, and an
    inner node carrying the searched key says nothing about the possible
    presence of a list of duplicates hanging below it. For example, in
    (0,2a,3,2b), the descent will visit 0,3,2b and this is the last 2
    that was inserted and not the one we want to return.

As a result *_prev_dup() returned NULL instead of the previous duplicate
as soon as the tree contained another key, i.e. exactly when the tree is
deep enough for the descent to enter the loop. *_next_dup() is immune to
the first problem since it never looks at is_dup, but not to the second
one. Less visibly, *_lookup() also uses is_dup, to walk back to the
first element of a list, and with is_dup wrongly zero it returned the
last one.

The fix keeps the shortcut everywhere it is harmless, as the whole point
of that commit was to avoid useless operations. Only three call sites
both reach this block and request is_dup: _ceb_lookup() with CEB_WM_KEQ,
and _ceb_next_dup() and _ceb_prev_dup() with CEB_WM_KNX/CEB_WM_KPR. All
the others either pass a blocking ret_* pointer (insert, delete,
next/prev, lookup_le/lt/ge/gt) or use a method below CEB_WM_KEQ which
never enters the block. Thus we have this:

  - for arrays and strings, the shortcut jumps to the matching branch,
    which for a list of duplicates is its last element, so it is taken
    whenever that branch is already a leaf, and <is_leaf> is updated
    accordingly. Only the inner node case is given up ;

  - for ints, the shortcut stops on the matching node itself, which is
    the dual-role node, i.e. the *first* element of the list. That is
    exactly what _ceb_lookup() must return, so it is kept there, and
    excluded only for _next_dup()/_prev_dup() which need the last
    element in order to walk the list.

More importantly, performance-wise, no operation that was already correct
descends further than before. Int lookups in multi-key trees are now
slightly slower since they need to reach a leaf or a dup tree, but that
is the price to pay to find the real first element. On the other hand,
string lookups are now slightly faster (~10%).

Now tests/testdups does not return any failure out of 6298 sequences.

The bug affects all versions since v0.3.0.

This is cebtree commit de4dfd14816cc7b0e360ae0dbabc615c73fe6de3.

[wt: this could sometimes miss duplicate server names since 3.3 and
 commit 413e903a22 ("MEDIUM: server: switch conf.name to cebis_tree"),
 as Amaury found. This must be backported to 3.3]