1 /* 2 * Copyright 2020, Andrew Lindesay <apl@lindesay.co.nz>. 3 * All rights reserved. Distributed under the terms of the MIT License. 4 */ 5 #ifndef LRU_CACHE_H 6 #define LRU_CACHE_H 7 8 9 #include <HashMap.h> 10 11 12 namespace BPrivate { 13 14 15 template<typename Key, typename Value> 16 class LRUOrderingNode { 17 private: 18 typedef LRUOrderingNode<Key, Value> LRUNode; 19 20 public: 21 LRUOrderingNode() 22 : 23 fKey(), 24 fValue(), 25 fOlder(NULL), 26 fNewer(NULL) 27 { 28 } 29 30 LRUOrderingNode(const Key& key, const Value& value) 31 : 32 fKey(key), 33 fValue(value), 34 fOlder(NULL), 35 fNewer(NULL) 36 { 37 } 38 39 Key fKey; 40 Value fValue; 41 LRUNode* fOlder; 42 LRUNode* fNewer; 43 }; 44 45 46 /*! \brief This is a hash map that maintains a limited number of entries. Once 47 this number of entries has been exceeded then it will start to discard 48 entries. The first entries to be discarded are the ones that are the least 49 recently used; hence the prefix "LRU". 50 */ 51 52 template<typename Key, typename Value> 53 class LRUCache { 54 public: 55 typedef LRUOrderingNode<Key, Value> LRUNode; 56 57 LRUCache(int32 limit) 58 : 59 fNewestNode(NULL), 60 fOldestNode(NULL), 61 fLimit(limit) 62 { 63 if (fLimit < 0) 64 fLimit = 0; 65 } 66 67 ~LRUCache() 68 { 69 Clear(); 70 } 71 72 status_t InitCheck() const 73 { 74 return fMap.InitCheck(); 75 } 76 77 status_t Put(const Key& key, const Value& value) 78 { 79 LRUNode* node = fMap.Get(key); 80 81 if (node != NULL) { 82 if (node->fValue != value) { 83 node->fValue = value; 84 _DisconnectNodeAndMakeNewest(node); 85 } 86 } else { 87 node = new(std::nothrow) LRUNode(key, value); 88 if (node == NULL) 89 return B_NO_MEMORY; 90 status_t result = fMap.Put(key, node); 91 if (result != B_OK) { 92 delete node; 93 return result; 94 } 95 _SetNewestNode(node); 96 _PurgeExcess(); 97 } 98 99 return B_OK; 100 } 101 102 Value Remove(const Key& key) 103 { 104 LRUNode* node = fMap.Get(key); 105 if (node != NULL) { 106 _DisconnectNode(node); 107 Value result = node->fValue; 108 fMap.Remove(key); 109 delete node; 110 return result; 111 } 112 return Value(); 113 } 114 115 void Clear() 116 { 117 fMap.Clear(); 118 LRUNode* node = fNewestNode; 119 while (node != NULL) { 120 LRUNode *next = node->fOlder; 121 delete node; 122 node = next; 123 } 124 } 125 126 Value Get(const Key& key) 127 { 128 LRUNode* node = fMap.Get(key); 129 if (node != NULL) { 130 _DisconnectNodeAndMakeNewest(node); 131 return node->fValue; 132 } 133 return Value(); 134 } 135 136 bool ContainsKey(const Key& key) const 137 { 138 return fMap.ContainsKey(key); 139 } 140 141 int32 Size() const 142 { 143 return fMap.Size(); 144 } 145 146 private: 147 148 void _DisconnectNodeAndMakeNewest(LRUNode* node) { 149 if (node != fNewestNode) { 150 _DisconnectNode(node); 151 node->fOlder = NULL; 152 node->fNewer = NULL; 153 _SetNewestNode(node); 154 } 155 } 156 157 void _DisconnectNode(LRUNode* node) 158 { 159 LRUNode *older = node->fOlder; 160 LRUNode *newer = node->fNewer; 161 if (newer != NULL) 162 newer->fOlder = older; 163 if (older != NULL) 164 older->fNewer = newer; 165 if (fNewestNode == node) 166 fNewestNode = older; 167 if (fOldestNode == node) 168 fOldestNode = newer; 169 } 170 171 void _SetNewestNode(LRUNode* node) 172 { 173 if (node != fNewestNode) { 174 node->fOlder = fNewestNode; 175 node->fNewer = NULL; 176 if (fNewestNode != NULL) 177 fNewestNode->fNewer = node; 178 fNewestNode = node; 179 if (fOldestNode == NULL) 180 fOldestNode = node; 181 } 182 } 183 184 void _PurgeOldestNode() 185 { 186 if (fOldestNode == NULL) 187 debugger("attempt to purge oldest node but there is none to purge"); 188 Remove(fOldestNode->fKey); 189 } 190 191 void _PurgeExcess() 192 { 193 while(Size() > fLimit) 194 _PurgeOldestNode(); 195 } 196 197 protected: 198 HashMap<Key, LRUNode*> fMap; 199 LRUNode* fNewestNode; 200 LRUNode* fOldestNode; 201 202 private: 203 int32 fLimit; 204 }; 205 206 }; // namespace BPrivate 207 208 using BPrivate::LRUCache; 209 210 #endif // LRU_CACHE_H 211