| 116 | } |
| 117 | |
| 118 | AccessMap::iterator AccessMap::Split(const iterator split_it, const index_type& index) { |
| 119 | const auto range = split_it->first; |
| 120 | |
| 121 | if (!range.includes(index)) { |
| 122 | return split_it; // If we don't have a valid split point, just return the iterator |
| 123 | } |
| 124 | |
| 125 | AccessRange lower_range(range.begin, index); |
| 126 | |
| 127 | if (lower_range.empty()) { |
| 128 | // This is a noop, we're keeping the upper half which is the same as split_it |
| 129 | return split_it; |
| 130 | } |
| 131 | |
| 132 | // Save the contents and erase |
| 133 | auto value = split_it->second; |
| 134 | auto next_it = impl_map_.erase(split_it); |
| 135 | |
| 136 | AccessRange upper_range(index, range.end); |
| 137 | assert(!upper_range.empty()); // Upper range cannot be empty |
| 138 | |
| 139 | // Copy value to the upper range |
| 140 | // NOTE: we insert from upper to lower because that's what emplace_hint can do in constant time |
| 141 | assert(impl_map_.find(upper_range) == impl_map_.end()); |
| 142 | next_it = impl_map_.emplace_hint(next_it, std::make_pair(upper_range, value)); |
| 143 | |
| 144 | // Move value to the lower range (we can move since the upper range already got a copy of value) |
| 145 | assert(impl_map_.find(lower_range) == impl_map_.end()); |
| 146 | next_it = impl_map_.emplace_hint(next_it, std::make_pair(lower_range, std::move(value))); |
| 147 | |
| 148 | // Iterator to the beginning of the lower range |
| 149 | return next_it; |
| 150 | } |
| 151 | |
| 152 | AccessMap::iterator Split(AccessMap::iterator in, AccessMap& map, const AccessRange& range) { |
| 153 | assert(in != map.end()); // Not designed for use with invalid iterators... |