src/developer/memory/metrics/mas_cache.h

// Copyright 2026 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.

#ifndef SRC_DEVELOPER_MEMORY_METRICS_MAS_CACHE_H_
#define SRC_DEVELOPER_MEMORY_METRICS_MAS_CACHE_H_

#include <optional>
#include <unordered_map>
#include <utility>

namespace memory {

// MarkAndSweepCache implements a cache that uses a mark-and-sweep strategy
// to prune entries. It supports O(1) lookup and insertion.
// Thread safety: only safe to use from a single thread.
template <typename Key, typename Value>
class MarkAndSweepCache {
 private:
  // Wraps the cached value and the mark bit indicating whether the entry
  // was recently accessed.
  struct Entry {
    Value value;
    bool marked;

    Entry(Value val, bool m) : value(std::move(val)), marked(m) {}
  };

  std::unordered_map<Key, Entry> map_;

 public:
  MarkAndSweepCache() = default;

  // Returns the value associated with the key if it exists, and marks it as active.
  std::optional<Value> Find(const Key& key) {
    auto it = map_.find(key);
    if (it != map_.end()) {
      // Accessing the entry marks it so it survives the next sweep.
      it->second.marked = true;
      return it->second.value;
    }
    return std::nullopt;
  }

  // Inserts the value for the key if not present, and always marks the entry as active.
  bool Emplace(Key key, Value value) {
    auto [it, inserted] = map_.try_emplace(std::move(key), std::move(value), true);
    if (!inserted) {
      // If the entry already exists, we do not overwrite the value, but we do
      // mark it as active so it survives the next sweep.
      it->second.marked = true;
    }
    return inserted;
  }

  // Removes the entry for the key if present.
  // Returns true if an entry was removed, false otherwise.
  bool Erase(const Key& key) { return map_.erase(key) > 0; }

  // Removes all entries that have not been marked active since the last sweep.
  void Sweep() {
    for (auto it = map_.begin(); it != map_.end();) {
      if (!it->second.marked) {
        it = map_.erase(it);
      } else {
        // Unmark surviving entries so they must be accessed again to survive
        // the subsequent sweep.
        it->second.marked = false;
        ++it;
      }
    }
  }
};

}  // namespace memory

#endif  // SRC_DEVELOPER_MEMORY_METRICS_MAS_CACHE_H_