layers/sync/sync_access_map.h

/* Copyright (c) 2019-2026 The Khronos Group Inc.
 * Copyright (c) 2019-2026 Valve Corporation
 * Copyright (c) 2019-2026 LunarG, Inc.
 * Copyright (C) 2019-2026 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * John Zulauf <jzulauf@lunarg.com>
 *
 */
#pragma once

#include "sync/sync_common.h"
#include "sync/sync_access_state.h"
#include "containers/range.h"
#include "containers/container_utils.h"

#include <algorithm>
#include <cassert>
#include <map>
#include <utility>

namespace syncval {

// There are two types of comparisons of AccessMap ranges:
//  a)  Two non-empty, non-overlapping ranges.
//      This happens when we compare two ranges from the access map, for example, during insert operation.
//      The "less" comparison that works here is: (range_a.end <= range_b.begin)
//
//  b)  Non-empty range vs empty range. The empty range here is a single point passed to LowerBound.
//      We compare this single point against non-empty ranges from the access map.
//      The "less" comparison from a) works for b) too, except one configuration, when point A coincides
//      with the beginning of non-empty range B. The comparison must return false here (e.g. not less).
//      That's because the lower bound for such point A is a range B itself. The comparision from a) has
//      to be extended with additional check: (range_a.begin < range_b.begin). This correctly handles
//      this special case and does not affect result of (range_a.end <= range_b.begin) in all other cases.
struct AccessMapCompare {
    bool operator()(const AccessRange& a, const AccessRange& b) const { return a.end <= b.begin && a.begin < b.begin; }
};

// Implements an ordered map of non-overlapping, non-empty ranges
class AccessMap {
    using ImplMap = std::map<AccessRange, AccessState, AccessMapCompare>;

  public:
    using index_type = ResourceAddress;
    using value_type = ImplMap::value_type;
    using iterator = ImplMap::iterator;
    using const_iterator = ImplMap::const_iterator;

  public:
    // Use explicit assignment to control all places where this happens
    void Assign(const AccessMap& other);
    AccessMap& operator=(const AccessMap& other) = delete;
    AccessMap& operator=(AccessMap&& other) = delete;

    iterator begin() { return impl_map_.begin(); }
    const_iterator begin() const { return impl_map_.begin(); }
    iterator end() { return impl_map_.end(); }
    const_iterator end() const { return impl_map_.end(); }

    iterator LowerBound(ResourceAddress range_begin);
    const_iterator LowerBound(ResourceAddress range_begin) const;
    size_t Size() const { return impl_map_.size(); }

    void Clear() { impl_map_.clear(); }
    iterator Erase(const iterator& pos);
    void Erase(iterator first, iterator last);
    // Merge at least two entries in [first, last), retaining the last entry's state.
    // The caller must ensure the entries are adjacent and their states can be merged.
    iterator Merge(iterator first, iterator last);
    iterator Insert(const_iterator hint, const AccessRange& range, const AccessState& access_state);
    iterator InfillGap(const_iterator range_lower_bound, const AccessRange& range, const AccessState& access_state);
    void InfillGaps(const AccessRange& range, const AccessState& access_state);
    iterator Split(const iterator split_it, const index_type& index);

    AccessMap() : impl_map_(AccessMapCompare()) {}

  private:
    // No replacement insert
    std::pair<iterator, bool> Insert(const AccessRange& range, const AccessState& access_state);

  private:
    ImplMap impl_map_;
};

// Split a range into pieces bound by the intersection of the iterator's range and the supplied range
AccessMap::iterator Split(AccessMap::iterator in, AccessMap& map, const AccessRange& range);

// Combines directly adjacent ranges with equal AccessState
void Consolidate(AccessMap& map);

// Apply an operation over a range map, infilling where content is absent, updating where content is present.
// The passed pos must either be a lower bound (can be the end iterator) or be strictly less than the range.
// Map entries that intersect range.begin or range.end are split at the intersection point.
template <typename InfillUpdateOps>
AccessMap::iterator InfillUpdateRange(AccessMap& map, AccessMap::iterator pos, const AccessRange& range,
                                      const InfillUpdateOps& ops) {
    assert(range.non_empty());

    const auto end = map.end();
    assert(pos == map.LowerBound(range.begin) || pos->first.strictly_less(range));

    if (pos != end && pos->first.strictly_less(range)) {
        // pos is not a lower bound for the range (pos < range), but if the range is
        // monotonically increasing, the next map entry may be the lower bound
        ++pos;

        // If the new pos is not a lower bound, run the full search
        if (pos != end && pos->first.strictly_less(range)) {
            pos = map.LowerBound(range.begin);
        }
    }
    assert(pos == map.LowerBound(range.begin));

    if (pos != end && range.begin > pos->first.begin) {
        // Lower bound starts before the range.
        // Split the entry so that a new entry starts exactly at the range.begin
        pos = map.Split(pos, range.begin);
        ++pos;
    }

    AccessMap::index_type current_begin = range.begin;
    while (pos != end && current_begin < range.end) {
        if (current_begin < pos->first.begin) {  // infill the gap
            const AccessRange gap_range(current_begin, std::min(range.end, pos->first.begin));

            ops.infill(map, pos, gap_range);

            // Advance current location.
            // Do not advance pos, as it's the next map entry to visit
            current_begin = pos->first.begin;
        } else {  // update existing entry
            assert(current_begin == pos->first.begin);

            // Split the current map entry if it goes beyond range.end.
            // This ensures the update is restricted to the given range.
            if (pos->first.end > range.end) {
                pos = map.Split(pos, range.end);
            }

            ops.update(pos);

            // Advance both current location and map entry
            current_begin = pos->first.end;
            ++pos;
        }
    }

    // Fill to the end if needed
    if (current_begin < range.end) {
        ops.infill(map, pos, AccessRange(current_begin, range.end));
    }
    return pos;
}

}  // namespace syncval