Skip to content
  • Matthijs Mekking's avatar
    Rewrite qp fix_iterator() · f8821012
    Matthijs Mekking authored
    The fix_iterator() function had a lot of bugs in it and while fixing
    them, the number of corner cases and the complexity of the function
    got out of hand. Rewrite the function with the following modifications:
    The function now requires that the iterator is pointing to a leaf node.
    This removes the cases we have to deal when the iterator was left on a
    dead branch.
    From the leaf node, pop up the iterator stack until we encounter the
    branch where the offset point is before the point where the search key
    differs. This will bring us to the right branch, or at the first
    unmatched node, in which case we pop up to the parent branch. From
    there it is easier to retrieve the predecessor.
    Once we are at the right branch, all we have to do is find the right
    twig (which is either the twig for the character at the position where
    the search key differs, or the previous twig) and walk down from there
    to the greatest leaf or, in case there is no good twig, get the
    previous twig from the successor and get the greatest leaf from there.
    If there is no previous twig to select in this branch, because every
    leaf from this branch node is greater than the one we wanted, we need
    to pop up the stack again and resume at the parent branch. This is
    achieved by calling prevleaf().