src/developer/debug/zxdb/symbols/address_range_map_builder.cc

// Copyright 2024 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/developer/debug/zxdb/symbols/address_range_map_builder.h"

#include "src/developer/debug/shared/largest_less_or_equal.h"

namespace zxdb {

void AddressRangeMapBuilder::AddRange(const AddressRange& range,
                                      AddressRangeMap::Value die_offset) {
  if (map_.empty()) {
    map_.emplace(range, die_offset);
    return;
  }

  // The first existing range beginning at or after the new one (computes >=).
  auto lower = map_.lower_bound(range);

  // We actually want to find the LAST range less than or equal to.
  if (lower == map_.end()) {
    // Past the beginning of the last range.
    --lower;
  } else if (lower->first.begin() > range.begin()) {
    // Past the beginning of the found range.
    if (lower == map_.begin()) {
      // Input is before the first existing range, just insert it.
      map_.emplace(range, die_offset);
      return;
    }
    --lower;
  }

  AddressRange found_range = lower->first;  // Need copy because we will invalidate "lower" below.
  if (range.begin() >= found_range.end()) {
    // Input is past the end, just insert it.
    map_.emplace(range, die_offset);
    return;
  }

  // If we get here, the existing range needs splitting.
  AddressRangeMap::Value found_value = lower->second;

  // Save the insert position before deleting the existing range. |lower| IS INVALIDATED.
  auto insert_hint = lower;
  ++insert_hint;
  map_.erase(lower);

  // Any range before the new one gets the existing value.
  if (found_range.begin() < range.begin()) {
    map_.emplace_hint(insert_hint, AddressRange(found_range.begin(), range.begin()), found_value);
  }

  // Always followed by the new range.
  map_.emplace_hint(insert_hint, range, die_offset);

  // Any range after the new one gets the existing value.
  if (found_range.end() > range.end()) {
    map_.emplace_hint(insert_hint, AddressRange(range.end(), found_range.end()), found_value);
  }
}

void AddressRangeMapBuilder::AddRanges(const AddressRanges& ranges,
                                       AddressRangeMap::Value die_offset) {
  for (const auto& r : ranges) {
    AddRange(r, die_offset);
  }
}

AddressRangeMap AddressRangeMapBuilder::GetMap() const {
  if (map_.empty()) {
    return AddressRangeMap();
  }

  std::vector<AddressRangeMap::Record> output;
  // Reserve extra space because there will be gaps.
  output.reserve(map_.size() + map_.size() / 2);

  // Flatten the map.
  uint64_t prev_end = std::numeric_limits<uint64_t>::max();
  for (auto [range, value] : map_) {
    if (range.begin() > prev_end) {
      // Mark the blank space between the previous range and this one.
      output.emplace_back(prev_end, AddressRangeMap::kNullValue);
    }
    output.emplace_back(range.begin(), value);
    prev_end = range.end();
  }

  // Mark the end of the last range.
  output.emplace_back(prev_end, AddressRangeMap::kNullValue);

  return AddressRangeMap(std::move(output));
}

}  // namespace zxdb