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 OHOS_DISTRIBUTED_DATA_FRAMEWORKS_COMMON_LRU_BUCKET_H
17#define OHOS_DISTRIBUTED_DATA_FRAMEWORKS_COMMON_LRU_BUCKET_H
18
19#include <map>
20#include <mutex>
21#include <list>
22
23namespace OHOS {
24template<typename _Key, typename _Tp>
25class LRUBucket {
26public:
27    LRUBucket(size_t capacity)
28        : size_(0), capacity_(capacity) {}
29
30    LRUBucket(LRUBucket &&bucket) noexcept = delete;
31    LRUBucket(const LRUBucket &bucket) = delete;
32    LRUBucket &operator=(LRUBucket &&bucket) noexcept = delete;
33    LRUBucket &operator=(const LRUBucket &bucket) = delete;
34
35    ~LRUBucket()
36    {
37        std::lock_guard<decltype(mutex_)> lock(mutex_);
38        while (size_ > 0) {
39            PopBack();
40        }
41    }
42
43    size_t Size() const
44    {
45        return size_;
46    }
47
48    size_t Capacity() const
49    {
50        return capacity_;
51    }
52
53    bool ResetCapacity(size_t capacity)
54    {
55        std::lock_guard<decltype(mutex_)> lock(mutex_);
56        capacity_ = capacity;
57        while (capacity_ < size_) {
58            PopBack();
59        }
60        return capacity_ == capacity;
61    }
62
63    /**
64     * The time complexity is O(log(index size))
65     **/
66    bool Get(const _Key &key, _Tp &value, bool isLRU = true)
67    {
68        std::lock_guard<decltype(mutex_)> lock(mutex_);
69        auto it = indexes_.find(key);
70        if (it != indexes_.end()) {
71            if (isLRU) {
72                // move node from the list;
73                Remove(it->second);
74                // insert node to the head
75                Insert(&head_, it->second);
76            }
77            value = it->second->value_;
78            return true;
79        }
80        return false;
81    }
82
83    /**
84     * The time complexity is O(log(index size))
85     **/
86    bool Set(const _Key &key, const _Tp &value)
87    {
88        std::lock_guard<decltype(mutex_)> lock(mutex_);
89        if (capacity_ == 0) {
90            return false;
91        }
92
93        auto it = indexes_.find(key);
94        if (it != indexes_.end()) {
95            Update(it->second, value);
96            Remove(it->second);
97            Insert(&head_, it->second);
98            return true;
99        }
100
101        while (capacity_ <= size_) {
102            PopBack();
103        }
104
105        auto *node = new(std::nothrow) Node(value);
106        if (node == nullptr) {
107            return false;
108        }
109
110        Insert(&head_, node);
111        auto pair = indexes_.emplace(key, node);
112        node->iterator_ = pair.first;
113        return true;
114    }
115
116    /**
117     * Just update the values, not change the lru
118     **/
119    bool Update(const _Key &key, const _Tp &value)
120    {
121        std::lock_guard<decltype(mutex_)> lock(mutex_);
122        auto it = indexes_.find(key);
123        if (it != indexes_.end()) {
124            Update(it->second, value);
125            return true;
126        }
127        return false;
128    }
129
130    /**
131     * The time complexity is O(min(indexes, values))
132     * Just update the values, not change the lru chain
133     */
134    bool Update(const std::map<_Key, _Tp> &values)
135    {
136        std::lock_guard<decltype(mutex_)> lock(mutex_);
137        auto idx = indexes_.begin();
138        auto val = values.begin();
139        bool updated = false;
140        auto comp = indexes_.key_comp();
141        while (idx != indexes_.end() && val != values.end()) {
142            if (comp(idx->first, val->first)) {
143                ++idx;
144                continue;
145            }
146            if (comp(val->first, idx->first)) {
147                ++val;
148                continue;
149            }
150            updated = true;
151            Update(idx->second, val->second);
152            ++idx;
153            ++val;
154        }
155        return updated;
156    }
157
158    /**
159     * The time complexity is O(log(index size))
160     * */
161    bool Delete(const _Key &key)
162    {
163        std::lock_guard<decltype(mutex_)> lock(mutex_);
164        auto it = indexes_.find(key);
165        if (it != indexes_.end()) {
166            Remove(it->second);
167            Delete(it->second);
168            return true;
169        }
170        return false;
171    }
172
173private:
174    struct Node final {
175        using iterator = typename std::map<_Key, Node *>::iterator;
176        Node(const _Tp &value) : value_(value) {}
177        Node() : value_() {}
178        ~Node() = default;
179        _Tp value_;
180        iterator iterator_;
181        Node *prev_ = this;
182        Node *next_ = this;
183    };
184
185    void PopBack()
186    {
187        auto *node = head_.prev_;
188        Remove(node);
189        Delete(node);
190    }
191
192    void Update(Node *node, const _Tp &value)
193    {
194        node->value_ = value;
195    }
196
197    void Remove(Node *node)
198    {
199        node->prev_->next_ = node->next_;
200        node->next_->prev_ = node->prev_;
201        size_--;
202    }
203
204    void Insert(Node *prev, Node *node)
205    {
206        prev->next_->prev_ = node;
207        node->next_ = prev->next_;
208        prev->next_ = node;
209        node->prev_ = prev;
210        size_++;
211    }
212
213    void Delete(Node *node)
214    {
215        indexes_.erase(node->iterator_);
216        delete node;
217    }
218
219    mutable std::recursive_mutex mutex_;
220    std::map<_Key, Node *> indexes_;
221    Node head_;
222    size_t size_;
223    size_t capacity_;
224};
225} // namespace OHOS
226#endif // OHOS_DISTRIBUTED_DATA_FRAMEWORKS_COMMON_LRU_BUCKET_H
227