ceph/src/rocksdb/utilities/persistent_cache/lrulist.h

   1 //  Copyright (c) 2013, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under the BSD-style license found in the
   3 //  LICENSE file in the root directory of this source tree. An additional grant
   4 //  of patent rights can be found in the PATENTS file in the same directory.
   5 //
   6 #pragma once
   7
   8 #ifndef ROCKSDB_LITE
   9
  10 #include <atomic>
  11
  12 #include "util/mutexlock.h"
  13
  14 namespace rocksdb {
  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 {
  22   explicit LRUElement() : next_(nullptr), prev_(nullptr), refs_(0) {}
  23
  24   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:
  38   virtual ~LRUList() {
  39     MutexLock _(&lock_);
  40     assert(!head_);
  41     assert(!tail_);
  42   }
  43
  44   // Push element into the LRU at the cold end
  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
  68   inline void Unlink(T* const t) {
  69     MutexLock _(&lock_);
  70     UnlinkImpl(t);
  71   }
  72
  73   // Evict an element from the LRU
  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
  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
 106   inline bool IsEmpty() const {
 107     MutexLock _(&lock_);
 108     return !head_ && !tail_;
 109   }
 110
 111  private:
 112   // Unlink an element from the LRU
 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
 140   inline void PushBack(T* const t) {
 141     MutexLock _(&lock_);
 142     PushBackImpl(t);
 143   }
 144
 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
 173
 174 #endif