1 /* 2 * Copyright 2020-2021, 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 // this will delete the objects in map which are the nodes in the 119 // linked list; for this reason don't delete them here as well 120 // because this will lead to a double-free of the object. 121 fNewestNode = NULL; 122 fOldestNode = NULL; 123 } 124 125 Value Get(const Key& key) 126 { 127 LRUNode* node = fMap.Get(key); 128 if (node != NULL) { 129 _DisconnectNodeAndMakeNewest(node); 130 return node->fValue; 131 } 132 return Value(); 133 } 134 135 bool ContainsKey(const Key& key) const 136 { 137 return fMap.ContainsKey(key); 138 } 139 140 int32 Size() const 141 { 142 return fMap.Size(); 143 } 144 145 private: 146 147 void _DisconnectNodeAndMakeNewest(LRUNode* node) { 148 if (node != fNewestNode) { 149 _DisconnectNode(node); 150 node->fOlder = NULL; 151 node->fNewer = NULL; 152 _SetNewestNode(node); 153 } 154 } 155 156 void _DisconnectNode(LRUNode* node) 157 { 158 LRUNode *older = node->fOlder; 159 LRUNode *newer = node->fNewer; 160 if (newer != NULL) 161 newer->fOlder = older; 162 if (older != NULL) 163 older->fNewer = newer; 164 if (fNewestNode == node) 165 fNewestNode = older; 166 if (fOldestNode == node) 167 fOldestNode = newer; 168 } 169 170 void _SetNewestNode(LRUNode* node) 171 { 172 if (node != fNewestNode) { 173 node->fOlder = fNewestNode; 174 node->fNewer = NULL; 175 if (fNewestNode != NULL) 176 fNewestNode->fNewer = node; 177 fNewestNode = node; 178 if (fOldestNode == NULL) 179 fOldestNode = node; 180 } 181 } 182 183 void _PurgeOldestNode() 184 { 185 if (fOldestNode == NULL) 186 debugger("attempt to purge oldest node but there is none to purge"); 187 Remove(fOldestNode->fKey); 188 } 189 190 void _PurgeExcess() 191 { 192 while(Size() > fLimit) 193 _PurgeOldestNode(); 194 } 195 196 protected: 197 HashMap<Key, LRUNode*> fMap; 198 LRUNode* fNewestNode; 199 LRUNode* fOldestNode; 200 201 private: 202 int32 fLimit; 203 }; 204 205 }; // namespace BPrivate 206 207 using BPrivate::LRUCache; 208 209 #endif // LRU_CACHE_H 210