1 /*
2  * Copyright (c) 2022 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 LRU_MAP_H
17 #define LRU_MAP_H
18 #include <map>
19 #include <mutex>
20 #include <queue>
21 
22 #include "db_errno.h"
23 #include "macro_utils.h"
24 
25 namespace DistributedDB {
26 // LRU map
27 template<typename K, typename V>
28 class LruMap final {
29 public:
30     LruMap() = default;
31     ~LruMap() = default;
32 
33     DISABLE_COPY_ASSIGN_MOVE(LruMap);
34 
Get(const K & key,V & outValue)35     int Get(const K &key, V &outValue)
36     {
37         std::lock_guard<std::mutex> autoLock(lruLock_);
38         if (cache_.find(key) == cache_.end()) {
39             return -E_NOT_FOUND;
40         }
41         outValue = cache_[key];
42         return Elimination(key, outValue);
43     }
44 
Put(const K & key,const V & inValue)45     int Put(const K &key, const V &inValue)
46     {
47         std::lock_guard<std::mutex> autoLock(lruLock_);
48         cache_[key] = inValue;
49         return Elimination(key, inValue);
50     }
51 
RemoveWithPrefixKey(const K & prefixKey)52     void RemoveWithPrefixKey(const K &prefixKey)
53     {
54         std::lock_guard<std::mutex> autoLock(lruLock_);
55         auto iterator = eliminationChain_.begin();
56         while (iterator != eliminationChain_.end()) {
57             const K &key = (*iterator).first;
58             if (key.find(prefixKey) == 0) {
59                 (void)cache_.erase(key);
60                 iterator = eliminationChain_.erase(iterator);
61             } else {
62                 iterator++;
63             }
64         }
65     }
66 
67 private:
68     // move the node to last and remove the first node until the size less than limit
Elimination(const K & key,const V & val)69     int Elimination(const K &key, const V &val)
70     {
71         auto iterator = eliminationChain_.begin();
72         while (iterator != eliminationChain_.end()) {
73             if ((*iterator).first == key) {
74                 eliminationChain_.erase(iterator);
75                 break;
76             }
77             iterator++;
78         }
79         std::pair<K, V> entry = {key, val};
80         eliminationChain_.push_back(entry);
81         while (eliminationChain_.size() > MAX_CACHE_ITEMS) {
82             std::pair<K, V> &pair = eliminationChain_.front();
83             cache_.erase(pair.first);
84             eliminationChain_.pop_front();
85         }
86         return E_OK;
87     }
88 
89     std::mutex lruLock_;
90     std::map<K, V> cache_;
91     std::deque<std::pair<K, V>> eliminationChain_;
92 
93     static const int MAX_CACHE_ITEMS = 200;
94 };
95 } // namespace DistributedDB
96 #endif // LRU_MAP_H