1 //  Copyright (c) 2013, Facebook, Inc.  All rights reserved.
2 //  This source code is licensed under both the GPLv2 (found in the
3 //  COPYING file in the root directory) and Apache 2.0 License
4 //  (found in the LICENSE.Apache file in the root directory).
5 //
6 #pragma once
7 
8 #ifndef ROCKSDB_LITE
9 
10 #include <atomic>
11 
12 #include "util/mutexlock.h"
13 
14 namespace ROCKSDB_NAMESPACE {
15 
16 // LRU element definition
17 //
18 // Any object that needs to be part of the LRU algorithm should extend this
19 // class
20 template <class T>
21 struct LRUElement {
LRUElementLRUElement22   explicit LRUElement() : next_(nullptr), prev_(nullptr), refs_(0) {}
23 
~LRUElementLRUElement24   virtual ~LRUElement() { assert(!refs_); }
25 
26   T* next_;
27   T* prev_;
28   std::atomic<size_t> refs_;
29 };
30 
31 // LRU implementation
32 //
33 // In place LRU implementation. There is no copy or allocation involved when
34 // inserting or removing an element. This makes the data structure slim
35 template <class T>
36 class LRUList {
37  public:
~LRUList()38   virtual ~LRUList() {
39     MutexLock _(&lock_);
40     assert(!head_);
41     assert(!tail_);
42   }
43 
44   // Push element into the LRU at the cold end
Push(T * const t)45   inline void Push(T* const t) {
46     assert(t);
47     assert(!t->next_);
48     assert(!t->prev_);
49 
50     MutexLock _(&lock_);
51 
52     assert((!head_ && !tail_) || (head_ && tail_));
53     assert(!head_ || !head_->prev_);
54     assert(!tail_ || !tail_->next_);
55 
56     t->next_ = head_;
57     if (head_) {
58       head_->prev_ = t;
59     }
60 
61     head_ = t;
62     if (!tail_) {
63       tail_ = t;
64     }
65   }
66 
67   // Unlink the element from the LRU
Unlink(T * const t)68   inline void Unlink(T* const t) {
69     MutexLock _(&lock_);
70     UnlinkImpl(t);
71   }
72 
73   // Evict an element from the LRU
Pop()74   inline T* Pop() {
75     MutexLock _(&lock_);
76 
77     assert(tail_ && head_);
78     assert(!tail_->next_);
79     assert(!head_->prev_);
80 
81     T* t = head_;
82     while (t && t->refs_) {
83       t = t->next_;
84     }
85 
86     if (!t) {
87       // nothing can be evicted
88       return nullptr;
89     }
90 
91     assert(!t->refs_);
92 
93     // unlike the element
94     UnlinkImpl(t);
95     return t;
96   }
97 
98   // Move the element from the front of the list to the back of the list
Touch(T * const t)99   inline void Touch(T* const t) {
100     MutexLock _(&lock_);
101     UnlinkImpl(t);
102     PushBackImpl(t);
103   }
104 
105   // Check if the LRU is empty
IsEmpty()106   inline bool IsEmpty() const {
107     MutexLock _(&lock_);
108     return !head_ && !tail_;
109   }
110 
111  private:
112   // Unlink an element from the LRU
UnlinkImpl(T * const t)113   void UnlinkImpl(T* const t) {
114     assert(t);
115 
116     lock_.AssertHeld();
117 
118     assert(head_ && tail_);
119     assert(t->prev_ || head_ == t);
120     assert(t->next_ || tail_ == t);
121 
122     if (t->prev_) {
123       t->prev_->next_ = t->next_;
124     }
125     if (t->next_) {
126       t->next_->prev_ = t->prev_;
127     }
128 
129     if (tail_ == t) {
130       tail_ = tail_->prev_;
131     }
132     if (head_ == t) {
133       head_ = head_->next_;
134     }
135 
136     t->next_ = t->prev_ = nullptr;
137   }
138 
139   // Insert an element at the hot end
PushBack(T * const t)140   inline void PushBack(T* const t) {
141     MutexLock _(&lock_);
142     PushBackImpl(t);
143   }
144 
PushBackImpl(T * const t)145   inline void PushBackImpl(T* const t) {
146     assert(t);
147     assert(!t->next_);
148     assert(!t->prev_);
149 
150     lock_.AssertHeld();
151 
152     assert((!head_ && !tail_) || (head_ && tail_));
153     assert(!head_ || !head_->prev_);
154     assert(!tail_ || !tail_->next_);
155 
156     t->prev_ = tail_;
157     if (tail_) {
158       tail_->next_ = t;
159     }
160 
161     tail_ = t;
162     if (!head_) {
163       head_ = tail_;
164     }
165   }
166 
167   mutable port::Mutex lock_;  // synchronization primitive
168   T* head_ = nullptr;         // front (cold)
169   T* tail_ = nullptr;         // back (hot)
170 };
171 
172 }  // namespace ROCKSDB_NAMESPACE
173 
174 #endif
175