1 /*
2  * Copyright (c) 2024 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #ifndef HGM_LRU_CACHE_H
17 #define HGM_LRU_CACHE_H
18 
19 #include <list>
20 #include <unordered_map>
21 
22 namespace OHOS::Rosen {
23 template<typename ValueType>
24 class HgmLRUCache {
25 public:
26     using Value = ValueType;
HgmLRUCache(uint32_t capacity)27     explicit HgmLRUCache(uint32_t capacity) : capacity_(capacity) {}
28     virtual ~HgmLRUCache() = default;
29 
Existed(Value value)30     bool Existed(Value value) const
31     {
32         return searchHelper_.find(value) != searchHelper_.end();
33     }
34 
Put(Value value)35     void Put(Value value)
36     {
37         if (capacity_ == 0) {
38             return;
39         }
40         if (auto iter = searchHelper_.find(value); iter != searchHelper_.end()) {
41             // exist: move to head
42             valueCache_.erase(iter->second);
43             valueCache_.push_front(value);
44             searchHelper_[value] = valueCache_.begin();
45         } else if (valueCache_.size() >= capacity_) {
46             // full: remove least recently used
47             searchHelper_.erase(valueCache_.back());
48             valueCache_.pop_back();
49 
50             valueCache_.push_front(value);
51             searchHelper_[value] = valueCache_.begin();
52         } else {
53             // add
54             valueCache_.push_front(value);
55             searchHelper_[value] = valueCache_.begin();
56         }
57     }
58 
Erase(Value value)59     void Erase(Value value)
60     {
61         if (auto iter = searchHelper_.find(value); iter != searchHelper_.end()) {
62             valueCache_.erase(iter->second);
63             searchHelper_.erase(iter);
64         }
65     }
66 
Clear()67     void Clear()
68     {
69         valueCache_.clear();
70         searchHelper_.clear();
71     }
72 
Size()73     size_t Size() { return valueCache_.size(); }
74 
75 private:
76     uint32_t capacity_;
77     typename std::list<Value> valueCache_;
78     std::unordered_map<Value, typename std::list<Value>::iterator> searchHelper_;
79 };
80 }
81 #endif // HGM_LRU_CACHE_H