include/ftl/small_map.h - LeafOS-Project/android_frameworks_native - Gitiles

 /*
  * Copyright 2020 The Android Open Source Project
  *
  * 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.
  */

 #pragma once

 #include <ftl/initializer_list.h>
 #include <ftl/optional.h>
 #include <ftl/small_vector.h>

 #include <algorithm>
 #include <functional>
 #include <type_traits>
 #include <utility>

 namespace android::ftl {

 // Associative container with unique, unordered keys. Unlike std::unordered_map, key-value pairs are
 // stored in contiguous storage for cache efficiency. The map is allocated statically until its size
 // exceeds N, at which point mappings are relocated to dynamic memory. The try_emplace operation has
 // a non-standard analogue try_replace that destructively emplaces. The API also defines an in-place
 // counterpart to insert_or_assign: emplace_or_replace. Lookup is done not via a subscript operator,
 // but immutable getters that can optionally transform the value.
 //
 // SmallMap<K, V, 0> unconditionally allocates on the heap.
 //
 // Example usage:
 //
 //   ftl::SmallMap<int, std::string, 3> map;
 //   assert(map.empty());
 //   assert(!map.dynamic());
 //
 //   map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
 //   assert(map.size() == 3u);
 //   assert(!map.dynamic());
 //
 //   assert(map.contains(123));
 //   assert(map.get(42).transform([](const std::string& s) { return s.size(); }) == 3u);
 //
 //   const auto opt = map.get(-1);
 //   assert(opt);
 //
 //   std::string& ref = *opt;
 //   assert(ref.empty());
 //   ref = "xyz";
 //
 //   map.emplace_or_replace(0, "vanilla", 2u, 3u);
 //   assert(map.dynamic());
 //
 //   assert(map == SmallMap(ftl::init::map(-1, "xyz"sv)(0, "nil"sv)(42, "???"sv)(123, "abc"sv)));
 //
 template <typename K, typename V, std::size_t N, typename KeyEqual = std::equal_to<K>>
 class SmallMap final {
   using Map = SmallVector<std::pair<const K, V>, N>;

   template <typename, typename, std::size_t, typename>
   friend class SmallMap;

  public:
   using key_type = K;
   using mapped_type = V;

   using value_type = typename Map::value_type;
   using size_type = typename Map::size_type;
   using difference_type = typename Map::difference_type;

   using reference = typename Map::reference;
   using iterator = typename Map::iterator;

   using const_reference = typename Map::const_reference;
   using const_iterator = typename Map::const_iterator;

   // Creates an empty map.
   SmallMap() = default;

   // Constructs at most N key-value pairs in place by forwarding per-pair constructor arguments.
   // The template arguments K, V, and N are inferred using the deduction guide defined below.
   // The syntax for listing pairs is as follows:
   //
   //   ftl::SmallMap map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
   //   static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, std::string, 3>>);
   //
   // The types of the key and value are deduced if the first pair contains exactly two arguments:
   //
   //   ftl::SmallMap map = ftl::init::map(0, 'a')(1, 'b')(2, 'c');
   //   static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, char, 3>>);
   //
   template <typename U, std::size_t... Sizes, typename... Types>
   SmallMap(InitializerList<U, std::index_sequence<Sizes...>, Types...>&& list)
       : map_(std::move(list)) {
     deduplicate();
   }

   // Copies or moves key-value pairs from a convertible map.
   template <typename Q, typename W, std::size_t M, typename E>
   SmallMap(SmallMap<Q, W, M, E> other) : map_(std::move(other.map_)) {}

   static constexpr size_type static_capacity() { return N; }

   size_type max_size() const { return map_.max_size(); }
   size_type size() const { return map_.size(); }
   bool empty() const { return map_.empty(); }

   // Returns whether the map is backed by static or dynamic storage.
   bool dynamic() const {
     if constexpr (static_capacity() > 0) {
       return map_.dynamic();
     } else {
       return true;
     }
   }

   iterator begin() { return map_.begin(); }
   const_iterator begin() const { return cbegin(); }
   const_iterator cbegin() const { return map_.cbegin(); }

   iterator end() { return map_.end(); }
   const_iterator end() const { return cend(); }
   const_iterator cend() const { return map_.cend(); }

   // Returns whether a mapping exists for the given key.
   bool contains(const key_type& key) const { return get(key).has_value(); }

   // Returns a reference to the value for the given key, or std::nullopt if the key was not found.
   //
   //   ftl::SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
   //
   //   const auto opt = map.get('c');
   //   assert(opt == 'C');
   //
   //   char d = 'd';
   //   const auto ref = map.get('d').value_or(std::ref(d));
   //   ref.get() = 'D';
   //   assert(d == 'D');
   //
   auto get(const key_type& key) const -> Optional<std::reference_wrapper<const mapped_type>> {
     for (const auto& [k, v] : *this) {
       if (KeyEqual{}(k, key)) {
         return std::cref(v);
       }
     }
     return {};
   }

   auto get(const key_type& key) -> Optional<std::reference_wrapper<mapped_type>> {
     for (auto& [k, v] : *this) {
       if (KeyEqual{}(k, key)) {
         return std::ref(v);
       }
     }
     return {};
   }

   // Returns an iterator to an existing mapping for the given key, or the end() iterator otherwise.
   const_iterator find(const key_type& key) const { return const_cast<SmallMap&>(*this).find(key); }
   iterator find(const key_type& key) { return find(key, begin()); }

   // Inserts a mapping unless it exists. Returns an iterator to the inserted or existing mapping,
   // and whether the mapping was inserted.
   //
   // On emplace, if the map reaches its static or dynamic capacity, then all iterators are
   // invalidated. Otherwise, only the end() iterator is invalidated.
   //
   template <typename... Args>
   std::pair<iterator, bool> try_emplace(const key_type& key, Args&&... args) {
     if (const auto it = find(key); it != end()) {
       return {it, false};
     }

     decltype(auto) ref_or_it =
         map_.emplace_back(std::piecewise_construct, std::forward_as_tuple(key),
                           std::forward_as_tuple(std::forward<Args>(args)...));

     if constexpr (static_capacity() > 0) {
       return {&ref_or_it, true};
     } else {
       return {ref_or_it, true};
     }
   }

   // Replaces a mapping if it exists, and returns an iterator to it. Returns the end() iterator
   // otherwise.
   //
   // The value is replaced via move constructor, so type V does not need to define copy/move
   // assignment, e.g. its data members may be const.
   //
   // The arguments may directly or indirectly refer to the mapping being replaced.
   //
   // Iterators to the replaced mapping point to its replacement, and others remain valid.
   //
   template <typename... Args>
   iterator try_replace(const key_type& key, Args&&... args) {
     const auto it = find(key);
     if (it == end()) return it;
     map_.replace(it, std::piecewise_construct, std::forward_as_tuple(key),
                  std::forward_as_tuple(std::forward<Args>(args)...));
     return it;
   }

   // In-place counterpart of std::unordered_map's insert_or_assign. Returns true on emplace, or
   // false on replace.
   //
   // The value is emplaced and replaced via move constructor, so type V does not need to define
   // copy/move assignment, e.g. its data members may be const.
   //
   // On emplace, if the map reaches its static or dynamic capacity, then all iterators are
   // invalidated. Otherwise, only the end() iterator is invalidated. On replace, iterators
   // to the replaced mapping point to its replacement, and others remain valid.
   //
   template <typename... Args>
   std::pair<iterator, bool> emplace_or_replace(const key_type& key, Args&&... args) {
     const auto [it, ok] = try_emplace(key, std::forward<Args>(args)...);
     if (ok) return {it, ok};
     map_.replace(it, std::piecewise_construct, std::forward_as_tuple(key),
                  std::forward_as_tuple(std::forward<Args>(args)...));
     return {it, ok};
   }

   // Removes a mapping if it exists, and returns whether it did.
   //
   // The last() and end() iterators, as well as those to the erased mapping, are invalidated.
   //
   bool erase(const key_type& key) { return erase(key, begin()); }

   // Removes all mappings.
   //
   // All iterators are invalidated.
   //
   void clear() { map_.clear(); }

  private:
   iterator find(const key_type& key, iterator first) {
     return std::find_if(first, end(),
                         [&key](const auto& pair) { return KeyEqual{}(pair.first, key); });
   }

   bool erase(const key_type& key, iterator first) {
     const auto it = find(key, first);
     if (it == end()) return false;
     map_.unstable_erase(it);
     return true;
   }

   void deduplicate() {
     for (auto it = begin(); it != end();) {
       if (const auto key = it->first; ++it != end()) {
         while (erase(key, it));
       }
     }
   }

   Map map_;
 };

 // Deduction guide for in-place constructor.
 template <typename K, typename V, typename E, std::size_t... Sizes, typename... Types>
 SmallMap(InitializerList<KeyValue<K, V, E>, std::index_sequence<Sizes...>, Types...>&&)
     -> SmallMap<K, V, sizeof...(Sizes), E>;

 // Returns whether the key-value pairs of two maps are equal.
 template <typename K, typename V, std::size_t N, typename Q, typename W, std::size_t M, typename E>
 bool operator==(const SmallMap<K, V, N, E>& lhs, const SmallMap<Q, W, M, E>& rhs) {
   if (lhs.size() != rhs.size()) return false;

   for (const auto& [k, v] : lhs) {
     const auto& lv = v;
     if (!rhs.get(k).transform([&lv](const W& rv) { return lv == rv; }).value_or(false)) {
       return false;
     }
   }

   return true;
 }

 // TODO: Remove in C++20.
 template <typename K, typename V, std::size_t N, typename Q, typename W, std::size_t M, typename E>
 inline bool operator!=(const SmallMap<K, V, N, E>& lhs, const SmallMap<Q, W, M, E>& rhs) {
   return !(lhs == rhs);
 }

 }  // namespace android::ftl
	/*
	* Copyright 2020 The Android Open Source Project
	*
	* 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.
	*/

	#pragma once

	#include <ftl/initializer_list.h>
	#include <ftl/optional.h>
	#include <ftl/small_vector.h>

	#include <algorithm>
	#include <functional>
	#include <type_traits>
	#include <utility>

	namespace android::ftl {

	// Associative container with unique, unordered keys. Unlike std::unordered_map, key-value pairs are
	// stored in contiguous storage for cache efficiency. The map is allocated statically until its size
	// exceeds N, at which point mappings are relocated to dynamic memory. The try_emplace operation has
	// a non-standard analogue try_replace that destructively emplaces. The API also defines an in-place
	// counterpart to insert_or_assign: emplace_or_replace. Lookup is done not via a subscript operator,
	// but immutable getters that can optionally transform the value.
	//
	// SmallMap<K, V, 0> unconditionally allocates on the heap.
	//
	// Example usage:
	//
	// ftl::SmallMap<int, std::string, 3> map;
	// assert(map.empty());
	// assert(!map.dynamic());
	//
	// map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
	// assert(map.size() == 3u);
	// assert(!map.dynamic());
	//
	// assert(map.contains(123));
	// assert(map.get(42).transform([](const std::string& s) { return s.size(); }) == 3u);
	//
	// const auto opt = map.get(-1);
	// assert(opt);
	//
	// std::string& ref = *opt;
	// assert(ref.empty());
	// ref = "xyz";
	//
	// map.emplace_or_replace(0, "vanilla", 2u, 3u);
	// assert(map.dynamic());
	//
	// assert(map == SmallMap(ftl::init::map(-1, "xyz"sv)(0, "nil"sv)(42, "???"sv)(123, "abc"sv)));
	//
	template <typename K, typename V, std::size_t N, typename KeyEqual = std::equal_to<K>>
	class SmallMap final {
	using Map = SmallVector<std::pair<const K, V>, N>;

	template <typename, typename, std::size_t, typename>
	friend class SmallMap;

	public:
	using key_type = K;
	using mapped_type = V;

	using value_type = typename Map::value_type;
	using size_type = typename Map::size_type;
	using difference_type = typename Map::difference_type;

	using reference = typename Map::reference;
	using iterator = typename Map::iterator;

	using const_reference = typename Map::const_reference;
	using const_iterator = typename Map::const_iterator;

	// Creates an empty map.
	SmallMap() = default;

	// Constructs at most N key-value pairs in place by forwarding per-pair constructor arguments.
	// The template arguments K, V, and N are inferred using the deduction guide defined below.
	// The syntax for listing pairs is as follows:
	//
	// ftl::SmallMap map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
	// static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, std::string, 3>>);
	//
	// The types of the key and value are deduced if the first pair contains exactly two arguments:
	//
	// ftl::SmallMap map = ftl::init::map(0, 'a')(1, 'b')(2, 'c');
	// static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, char, 3>>);
	//
	template <typename U, std::size_t... Sizes, typename... Types>
	SmallMap(InitializerList<U, std::index_sequence<Sizes...>, Types...>&& list)
	: map_(std::move(list)) {
	deduplicate();
	}

	// Copies or moves key-value pairs from a convertible map.
	template <typename Q, typename W, std::size_t M, typename E>
	SmallMap(SmallMap<Q, W, M, E> other) : map_(std::move(other.map_)) {}

	static constexpr size_type static_capacity() { return N; }

	size_type max_size() const { return map_.max_size(); }
	size_type size() const { return map_.size(); }
	bool empty() const { return map_.empty(); }

	// Returns whether the map is backed by static or dynamic storage.
	bool dynamic() const {
	if constexpr (static_capacity() > 0) {
	return map_.dynamic();
	} else {
	return true;
	}
	}

	iterator begin() { return map_.begin(); }
	const_iterator begin() const { return cbegin(); }
	const_iterator cbegin() const { return map_.cbegin(); }

	iterator end() { return map_.end(); }
	const_iterator end() const { return cend(); }
	const_iterator cend() const { return map_.cend(); }

	// Returns whether a mapping exists for the given key.
	bool contains(const key_type& key) const { return get(key).has_value(); }

	// Returns a reference to the value for the given key, or std::nullopt if the key was not found.
	//
	// ftl::SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
	//
	// const auto opt = map.get('c');
	// assert(opt == 'C');
	//
	// char d = 'd';
	// const auto ref = map.get('d').value_or(std::ref(d));
	// ref.get() = 'D';
	// assert(d == 'D');
	//
	auto get(const key_type& key) const -> Optional<std::reference_wrapper<const mapped_type>> {
	for (const auto& [k, v] : *this) {
	if (KeyEqual{}(k, key)) {
	return std::cref(v);
	}
	}
	return {};
	}

	auto get(const key_type& key) -> Optional<std::reference_wrapper<mapped_type>> {
	for (auto& [k, v] : *this) {
	if (KeyEqual{}(k, key)) {
	return std::ref(v);
	}
	}
	return {};
	}

	// Returns an iterator to an existing mapping for the given key, or the end() iterator otherwise.
	const_iterator find(const key_type& key) const { return const_cast<SmallMap&>(*this).find(key); }
	iterator find(const key_type& key) { return find(key, begin()); }

	// Inserts a mapping unless it exists. Returns an iterator to the inserted or existing mapping,
	// and whether the mapping was inserted.
	//
	// On emplace, if the map reaches its static or dynamic capacity, then all iterators are
	// invalidated. Otherwise, only the end() iterator is invalidated.
	//
	template <typename... Args>
	std::pair<iterator, bool> try_emplace(const key_type& key, Args&&... args) {
	if (const auto it = find(key); it != end()) {
	return {it, false};
	}

	decltype(auto) ref_or_it =
	map_.emplace_back(std::piecewise_construct, std::forward_as_tuple(key),
	std::forward_as_tuple(std::forward<Args>(args)...));

	if constexpr (static_capacity() > 0) {
	return {&ref_or_it, true};
	} else {
	return {ref_or_it, true};
	}
	}

	// Replaces a mapping if it exists, and returns an iterator to it. Returns the end() iterator
	// otherwise.
	//
	// The value is replaced via move constructor, so type V does not need to define copy/move
	// assignment, e.g. its data members may be const.
	//
	// The arguments may directly or indirectly refer to the mapping being replaced.
	//
	// Iterators to the replaced mapping point to its replacement, and others remain valid.
	//
	template <typename... Args>
	iterator try_replace(const key_type& key, Args&&... args) {
	const auto it = find(key);
	if (it == end()) return it;
	map_.replace(it, std::piecewise_construct, std::forward_as_tuple(key),
	std::forward_as_tuple(std::forward<Args>(args)...));
	return it;
	}

	// In-place counterpart of std::unordered_map's insert_or_assign. Returns true on emplace, or
	// false on replace.
	//
	// The value is emplaced and replaced via move constructor, so type V does not need to define
	// copy/move assignment, e.g. its data members may be const.
	//
	// On emplace, if the map reaches its static or dynamic capacity, then all iterators are
	// invalidated. Otherwise, only the end() iterator is invalidated. On replace, iterators
	// to the replaced mapping point to its replacement, and others remain valid.
	//
	template <typename... Args>
	std::pair<iterator, bool> emplace_or_replace(const key_type& key, Args&&... args) {
	const auto [it, ok] = try_emplace(key, std::forward<Args>(args)...);
	if (ok) return {it, ok};
	map_.replace(it, std::piecewise_construct, std::forward_as_tuple(key),
	std::forward_as_tuple(std::forward<Args>(args)...));
	return {it, ok};
	}

	// Removes a mapping if it exists, and returns whether it did.
	//
	// The last() and end() iterators, as well as those to the erased mapping, are invalidated.
	//
	bool erase(const key_type& key) { return erase(key, begin()); }

	// Removes all mappings.
	//
	// All iterators are invalidated.
	//
	void clear() { map_.clear(); }

	private:
	iterator find(const key_type& key, iterator first) {
	return std::find_if(first, end(),
	[&key](const auto& pair) { return KeyEqual{}(pair.first, key); });
	}

	bool erase(const key_type& key, iterator first) {
	const auto it = find(key, first);
	if (it == end()) return false;
	map_.unstable_erase(it);
	return true;
	}

	void deduplicate() {
	for (auto it = begin(); it != end();) {
	if (const auto key = it->first; ++it != end()) {
	while (erase(key, it));
	}
	}
	}

	Map map_;
	};

	// Deduction guide for in-place constructor.
	template <typename K, typename V, typename E, std::size_t... Sizes, typename... Types>
	SmallMap(InitializerList<KeyValue<K, V, E>, std::index_sequence<Sizes...>, Types...>&&)
	-> SmallMap<K, V, sizeof...(Sizes), E>;

	// Returns whether the key-value pairs of two maps are equal.
	template <typename K, typename V, std::size_t N, typename Q, typename W, std::size_t M, typename E>
	bool operator==(const SmallMap<K, V, N, E>& lhs, const SmallMap<Q, W, M, E>& rhs) {
	if (lhs.size() != rhs.size()) return false;

	for (const auto& [k, v] : lhs) {
	const auto& lv = v;
	if (!rhs.get(k).transform([&lv](const W& rv) { return lv == rv; }).value_or(false)) {
	return false;
	}
	}

	return true;
	}

	// TODO: Remove in C++20.
	template <typename K, typename V, std::size_t N, typename Q, typename W, std::size_t M, typename E>
	inline bool operator!=(const SmallMap<K, V, N, E>& lhs, const SmallMap<Q, W, M, E>& rhs) {
	return !(lhs == rhs);
	}

	} // namespace android::ftl