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 return result; 93 _SetNewestNode(node); 94 _PurgeExcess(); 95 } 96 97 return B_OK; 98 } 99 100 Value Remove(const Key& key) 101 { 102 LRUNode* node = fMap.Get(key); 103 if (node != NULL) { 104 _DisconnectNode(node); 105 Value result = node->fValue; 106 fMap.Remove(key); 107 delete node; 108 return result; 109 } 110 return Value(); 111 } 112 113 void Clear() 114 { 115 fMap.Clear(); 116 LRUNode* node = fNewestNode; 117 while (node != NULL) { 118 LRUNode *next = node->fOlder; 119 delete node; 120 node = next; 121 } 122 } 123 124 Value Get(const Key& key) 125 { 126 LRUNode* node = fMap.Get(key); 127 if (node != NULL) { 128 _DisconnectNodeAndMakeNewest(node); 129 return node->fValue; 130 } 131 return Value(); 132 } 133 134 bool ContainsKey(const Key& key) const 135 { 136 return fMap.ContainsKey(key); 137 } 138 139 int32 Size() const 140 { 141 return fMap.Size(); 142 } 143 144 private: 145 146 void _DisconnectNodeAndMakeNewest(LRUNode* node) { 147 if (node != fNewestNode) { 148 _DisconnectNode(node); 149 node->fOlder = NULL; 150 node->fNewer = NULL; 151 _SetNewestNode(node); 152 } 153 } 154 155 void _DisconnectNode(LRUNode* node) 156 { 157 LRUNode *older = node->fOlder; 158 LRUNode *newer = node->fNewer; 159 if (newer != NULL) 160 newer->fOlder = older; 161 if (older != NULL) 162 older->fNewer = newer; 163 if (fNewestNode == node) 164 fNewestNode = older; 165 if (fOldestNode == node) 166 fOldestNode = newer; 167 } 168 169 void _SetNewestNode(LRUNode* node) 170 { 171 if (node != fNewestNode) { 172 node->fOlder = fNewestNode; 173 node->fNewer = NULL; 174 if (fNewestNode != NULL) 175 fNewestNode->fNewer = node; 176 fNewestNode = node; 177 if (fOldestNode == NULL) 178 fOldestNode = node; 179 } 180 } 181 182 void _PurgeOldestNode() 183 { 184 if (fOldestNode == NULL) 185 debugger("attempt to purge oldest node but there is none to purge"); 186 Remove(fOldestNode->fKey); 187 } 188 189 void _PurgeExcess() 190 { 191 while(Size() > fLimit) 192 _PurgeOldestNode(); 193 } 194 195 protected: 196 HashMap<Key, LRUNode*> fMap; 197 LRUNode* fNewestNode; 198 LRUNode* fOldestNode; 199 200 private: 201 int32 fLimit; 202 }; 203 204 }; // namespace BPrivate 205 206 using BPrivate::LRUCache; 207 208 #endif // LRU_CACHE_H 209