• Austin Clements's avatar
    Simpler, iterative, and bounded radix_iterator · b1bdb3f4
    Austin Clements 提交于
    Previously, the radix iterator unconditionally found the next non-null
    leaf node, even if it fell outside of the range the iterator was
    derived from.  This was obviously an efficiency issue, but it also
    introduced unnecessary sharing because of the reads outside of the
    iterator's range.  Now it takes an explicit upper bound and will stop
    resolving elements when it reaches that bound.  The end() iterator is
    now naturally represented in terms of this bound, rather than in terms
    of a special-case key.
    
    For asharing vm, this eliminates all violations of the commutativity
    rule.
    
    Since I couldn't figure out how to nicely work this bound into the
    existing recursive traversal implementation, I reworked it to be
    iterative and, I think, made it much simpler in the process.  This
    does make one notable semantic change: previously the radix iterator
    cached the element it pointed to, so an update to that element would
    not affect the value returned by the iterator.  It no longer caches
    it, which makes it behave more like a regular collection iterator.
    b1bdb3f4
radix.hh 7.5 KB