/Users/deen/code/yugabyte-db/src/yb/util/lru_cache.h
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) YugaByte, Inc. |
2 | | // |
3 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
4 | | // in compliance with the License. You may obtain a copy of the License at |
5 | | // |
6 | | // http://www.apache.org/licenses/LICENSE-2.0 |
7 | | // |
8 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
9 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
10 | | // or implied. See the License for the specific language governing permissions and limitations |
11 | | // under the License. |
12 | | // |
13 | | |
14 | | #ifndef YB_UTIL_LRU_CACHE_H |
15 | | #define YB_UTIL_LRU_CACHE_H |
16 | | |
17 | | #include <boost/multi_index_container.hpp> |
18 | | #include <boost/multi_index/hashed_index.hpp> |
19 | | #include <boost/multi_index/sequenced_index.hpp> |
20 | | |
21 | | namespace yb { |
22 | | |
23 | | // The cache that stores at most specified number of recently added entries. |
24 | | template <class Value> |
25 | | class LRUCache { |
26 | | private: |
27 | | class IdTag; |
28 | | |
29 | | using Impl = boost::multi_index_container< |
30 | | Value, |
31 | | boost::multi_index::indexed_by< |
32 | | boost::multi_index::sequenced<>, |
33 | | boost::multi_index::hashed_unique< |
34 | | boost::multi_index::tag<IdTag>, |
35 | | boost::multi_index::identity<Value> |
36 | | > |
37 | | > |
38 | | >; |
39 | | |
40 | | public: |
41 | | typedef typename Impl::const_iterator const_iterator; |
42 | | |
43 | 56.7k | explicit LRUCache(size_t capacity) : capacity_(capacity) {} |
44 | | |
45 | | // Insert entry in cache. |
46 | 563k | void insert(const Value& value) { |
47 | 563k | auto p = impl_.push_front(value); |
48 | | |
49 | 563k | if (!p.second) { |
50 | 0 | impl_.relocate(impl_.begin(), p.first); |
51 | 563k | } else if (impl_.size() > capacity_) { |
52 | 377k | impl_.pop_back(); |
53 | 377k | } |
54 | 563k | } |
55 | | |
56 | 563k | void Insert(const Value& value) { |
57 | 563k | insert(value); |
58 | 563k | } |
59 | | |
60 | | // Erase entry from cache. Returns number of removed entries. |
61 | | template <class Key> |
62 | 1.80M | size_t erase(const Key& key) { |
63 | 1.80M | return impl_.template get<IdTag>().erase(key); |
64 | 1.80M | } |
65 | | |
66 | | // Erase entry from cache. Returns true if entry was removed. |
67 | | template <class Key> |
68 | 1.80M | size_t Erase(const Key& key) { |
69 | 1.80M | return erase(key); |
70 | 1.80M | } |
71 | | |
72 | | const_iterator begin() const { |
73 | | return impl_.begin(); |
74 | | } |
75 | | |
76 | | const_iterator end() const { |
77 | | return impl_.end(); |
78 | | } |
79 | | |
80 | | private: |
81 | | const size_t capacity_; |
82 | | Impl impl_; |
83 | | }; |
84 | | |
85 | | } // namespace yb |
86 | | |
87 | | #endif // YB_UTIL_LRU_CACHE_H |