On Thu, Apr 18, 2019 at 10:41:55PM -0700, Jason Merrill wrote:
> > + node = splay_tree_predecessor (cases, (splay_tree_key) min_value);
> ...
> > + if (CASE_HIGH ((tree) node->value)
> > + && tree_int_cst_compare (CASE_HIGH ((tree) node->value),
> > + min_value) >= 0)
> ...
> > + node = splay_tree_predecessor (cases,
> > + (splay_tree_key) min_value);
> ....
> > + node = splay_tree_lookup (cases, (splay_tree_key) max_value);
> > + if (node == NULL)
> > + node = splay_tree_predecessor (cases, (splay_tree_key) max_value);
> > + /* Handle a single node that might partially overlap the range. */
> > + if (node
> > + && node->key
> > + && CASE_HIGH ((tree) node->value)
> > + && tree_int_cst_compare (CASE_HIGH ((tree) node->value),
> > + max_value) > 0)
> ...
> > + while ((node = splay_tree_successor (cases,
> > + (splay_tree_key) max_value))
>
> Hmm, why are the code sections for dealing with the lower bound and
> upper bound asymmetrical? That is, why not start the upper bound
> consideration with splay_tree_successor?
Because of the case 1 ... 4: GNU extension. Without that it would be
mostly symmetrical (well, there still would be a difference, because we put
the default: before all other cases, so we still need to test
node->key != 0 for the splay_tree_predecessor case but don't have to test
that for splay_tree_successor. But with the GNU extension, we still use
the low bound of the range as the key, which makes it asymmetrical.
splay_tree_predecessor (cases, (splay_tree_key) min_value)
if it is not default: can be either the overlapping case (first part of the
range outside of range, then part of the range in range of the corresponding
type) or non-overlapping case. There is at most one overlapping case there
and all further predecessors are necessarily outside of range.
On the other side,
splay_tree_successor (cases, (splay_tree_key) max_value)
is never default: and is always completely outside of range (and its
successors are as well). If we want to find the (single) overlapping case that
overlaps the max_value, then it could be either
splay_tree_lookup (cases, (splay_tree_key) max_value)
or
splay_tree_predecessor (cases, (splay_tree_key) max_value)
(the first one if there is e.g. a range case max_value ... max_value + N:
and the second one if there is e.g. a range case max_value - M ... max_value
+ N: where both M and N are positive integers).
Of course, the overlapping case could be also
case min_value - M ... max_value + N:
in which case both the earlier and later code will find the same node and
each will complain about one boundary of that node and adjust that boundary.
Jakub
