Simulant  21.12-194
A portable game engine for Windows, OSX, Linux, Dreamcast, and PSP
lru_cache.h
1 #pragma once
2 
3 #include <unordered_map>
4 #include "optional.h"
5 
6 namespace smlt {
7 
8 template<typename Key, typename Value>
9 class LRUCache {
10 private:
11  struct Entry {
12  Entry(const Key& key, const Value& value):
13  key(key), value(value) {}
14 
15  Entry* prev = nullptr;
16  Entry* next = nullptr;
17 
18  Key key;
19  Value value;
20  };
21 
22  std::unordered_map<Key, Entry*> cache_;
23  mutable Entry* entries_ = nullptr;
24  mutable Entry* tail_ = nullptr;
25 
26  std::size_t max_size_ = 64;
27 
28  void pop_tail() {
29  if(!tail_) {
30  assert(cache_.empty());
31  assert(!entries_);
32  return;
33  }
34 
35  Entry* old_tail = tail_;
36  tail_ = tail_->prev;
37  if(tail_) {
38  assert(entries_);
39  tail_->next = nullptr;
40  } else {
41  /* No tail? Must be last entry */
42  entries_ = nullptr;
43  }
44 
45  cache_.erase(old_tail->key);
46 
47  delete old_tail;
48  }
49 
50 #ifndef NDEBUG
51  void check_valid() const {
52  auto it = entries_;
53  auto count = 0u;
54  while(it) {
55  assert(it != it->next);
56 
57  ++count;
58  it = it->next;
59  }
60 
61  assert(cache_.size() == count);
62  }
63 #endif
64 
65 public:
66  ~LRUCache() {
67  clear();
68  }
69 
70  optional<Value> get(const Key& key) const {
71  auto it = cache_.find(key);
72  if(it != cache_.end()) {
73  auto entry = it->second;
74 
75  if(entry != entries_) {
76  // Remove from list
77  if(entry->prev) entry->prev->next = entry->next;
78  if(entry->next) entry->next->prev = entry->prev;
79 
80  if(tail_ == entry) {
81  tail_ = entry->prev;
82  }
83 
84  // Insert at the beginning
85  entry->prev = nullptr;
86  entry->next = entries_;
87  entries_->prev = entry;
88  entries_ = entry;
89  }
90 
91 #ifndef NDEBUG
92  check_valid();
93 #endif
94  return optional<Value>(entry->value);
95  }
96 
97  return optional<Value>();
98  }
99 
100  void clear() {
101  while(size()) {
102  pop_tail();
103  }
104  }
105 
106  bool insert(const Key& key, const Value& value) {
107  auto it = cache_.find(key);
108  if(it != cache_.end()) {
109  // Can't insert duplicate key
110  return false;
111  }
112 
113  /* Insert at the beginning */
114  Entry* new_entry = new Entry(key, value);
115 
116  if(!tail_) {
117  /* First, and last */
118  tail_ = new_entry;
119  }
120 
121  new_entry->next = entries_;
122  if(entries_) {
123  entries_->prev = new_entry;
124  }
125 
126  entries_ = new_entry;
127  cache_.insert(std::make_pair(key, new_entry));
128 
129  /* If we grew too big, remove the last entry */
130  if(cache_.size() > max_size_) {
131  pop_tail();
132  }
133 
134 #ifndef NDEBUG
135  check_valid();
136 #endif
137  return true;
138  }
139 
140  bool erase(const Key& key) {
141  auto it = cache_.find(key);
142  if(it == cache_.end()) {
143  return false;
144  }
145 
146  assert(it->second.key == key);
147 
148  /* Move to the end. Just saves duplicating removal code */
149  auto entry = it->second;
150  if(entry != tail_) {
151  if(entry->prev) entry->prev->next = entry->next;
152  if(entry->next) entry->next->prev = entry->prev;
153 
154  entry->prev = tail_;
155  tail_->next = entry;
156  tail_ = entry;
157  }
158 
159  /* Pop the tail */
160  pop_tail();
161 #ifndef NDEBUG
162  check_valid();
163 #endif
164  return true;
165  }
166 
167  void set_max_size(std::size_t size) {
168  while(cache_.size() > size) {
169  pop_tail();
170  }
171 
172  max_size_ = size;
173  }
174 
175  std::size_t size() const {
176  return cache_.size();
177  }
178 
179  std::size_t max_size() const {
180  return max_size_;
181  }
182 };
183 
184 }
smlt
Definition: animation.cpp:25
smlt::optional
Definition: optional.h:13
smlt::Key
Definition: spatial_hash.h:36
smlt::LRUCache
Definition: lru_cache.h:9