SetU32::const_iterator SetU32::lower_bound()

in glean/rts/ownership/setu32.cpp [126:159]

• 33 lines of code
• 3 McCabe index (conditional complexity)

SetU32::const_iterator SetU32::lower_bound(
    SetU32::const_iterator start,
    SetU32::const_iterator finish,
    uint32_t id) {
  struct Local {
    static std::pair<uint32_t, uint32_t> lengths(
        std::vector<Hdr>::const_iterator first,
        std::vector<Hdr>::const_iterator last) {
      uint32_t dense = 0;
      uint32_t sparse = 0;
      while (first != last) {
          dense += first->denseLen();
          sparse += first->sparseLen();
          ++first;
      }
      return {dense, sparse};
    }
  };

  auto pos = std::lower_bound(
    start.hdrs,
    finish.hdrs,
    id,
    [](auto x, auto id) { return x.before(id); });
  const auto l = pos - start.hdrs;
  const auto r = finish.hdrs - pos;
  if (l <= r) {
    const auto [d,s] = Local::lengths(start.hdrs, pos);
    return {pos, start.block.dense + d, start.block.sparse + s};
  } else {
    const auto [d,s] = Local::lengths(pos, finish.hdrs);
    return {pos, finish.block.dense - d, finish.block.sparse - s};
  }
}