1 /* 2 * Copyright (C) 2024 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #pragma once 18 19 #include <list> 20 #include <unordered_map> 21 22 namespace android::audio_utils { 23 24 /** 25 * linked_hash_map 26 * 27 * A hash map that iterates in order of oldest to newest inserted. 28 * See also Java LinkedHashMap. 29 * 30 * O(1) lookup, insertion, deletion, iteration (with std::unordered_map and std::list) 31 * 32 * This can be used to hold historical records indexed on a key, 33 * whose container size can be controlled by evicting the least recently used record. 34 * 35 * The class is not thread safe: Locking must occur at the caller. 36 * 37 * This is a basic implementation, many STL map methods are not implemented. 38 * 39 * @tparam K Key type 40 * @tparam V Value type 41 * @tparam M Map type (std::unordered_map or std::map) 42 * @tparam L List type should have fast and stable iterator 43 * insertion and erasure. 44 */ 45 template<typename K, typename V, 46 template<typename, typename, typename...> class M = std::unordered_map, 47 template<typename, typename...> class L = std::list> 48 class linked_hash_map { 49 using List = L<std::pair<K, V>>; 50 51 // if K is large, could use a map with a reference_wrapper<K>. 52 // or a set with an iterator_wrapper<List::iterator>. 53 using Map = M<K, typename List::iterator>; 54 55 public: 56 // The iterator returned is the list iterator. 57 using iterator = List::iterator; 58 59 // Equivalent linked hash maps must contain the same elements 60 // inserted in the same order. 61 bool operator==(const linked_hash_map<K, V, M, L>& other) const { 62 return list_ == other.list_; 63 } 64 65 // The iterators returned are List::iterator. find(const K & k)66 auto find(const K& k) { 67 auto map_it = map_.find(k); 68 if (map_it == map_.end()) return list_.end(); 69 return map_it->second; 70 } 71 erase(const List::iterator & it)72 auto erase(const List::iterator& it) { 73 if (it != list_.end()) { 74 map_.erase(it->first); 75 return list_.erase(it); 76 } 77 return it; 78 } 79 size()80 auto size() const { return list_.size(); } begin()81 auto begin() const { return list_.begin(); } end()82 auto end() const { return list_.end(); } 83 begin()84 auto begin() { return list_.begin(); } end()85 auto end() { return list_.end(); } 86 template <typename KU> 87 auto& operator[](KU&& k) { 88 auto map_it = map_.find(k); 89 if (map_it != map_.end()) return map_it->second->second; 90 auto it = list_.insert(list_.end(), 91 std::make_pair(std::forward<KU>(k), V{})); // oldest to newest. 92 map_[it->first] = it; 93 return it->second; 94 } 95 96 private: 97 Map map_; 98 List list_; // oldest is first. 99 }; 100 101 } // namespace android::audio_utils 102