KiCad PCB EDA Suite
lru_cache.h
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2015 Mario Luzeiro <mrluzeiro@ua.pt>
5  * Copyright (C) 1992-2015 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
31 #ifndef LRU_CACHE_H
32 #define LRU_CACHE_H
33 
34 
35 #include <list>
36 #include <iterator>
37 #include <map>
38 #include <stdexcept>
39 #include <wx/string.h>
40 
41 
58 template< typename t_value >
60 {
61 
62 private:
63 
68  typedef std::pair< wxString, t_value > KEY_VALUE_PAIR;
69 
74  typedef std::list< KEY_VALUE_PAIR > CACHED_LIST;
75 
76 
81  typedef typename CACHED_LIST::iterator LIST_ITERATOR;
82 
83 
88  typedef std::map< wxString, LIST_ITERATOR > WXSTR_HASH_MAP;
89 
94  typedef typename WXSTR_HASH_MAP::iterator MAP_ITERATOR;
95 
96 
100  CACHED_LIST m_cached_list;
101 
105  WXSTR_HASH_MAP m_map_iterators;
106 
107 
111  size_t m_maxSize;
112 
113 public:
114 
115 
120  LRU_WXSTR_CACHE( size_t aMaxSize = 1 ) : m_maxSize( aMaxSize ) {}
121 
122 
128  void Insert( const wxString &aKey, const t_value &aValue )
129  {
130  MAP_ITERATOR it = m_map_iterators.find( aKey );
131 
132  if( it != m_map_iterators.end() )
133  {
134  // It already exists, so must remove it from list and form the map
135  // it->second have a iterator from the list m_cached_list
136  m_cached_list.erase( it->second );
137  m_map_iterators.erase( it );
138  }
139 
140  // Inserts a new element at the beginning of the list, a pair of <aKey, aValue>
141  m_cached_list.push_front( KEY_VALUE_PAIR( aKey, aValue) );
142 
143  // Insert a new key and the added list iterator to the map
144  m_map_iterators[aKey] = m_cached_list.begin();
145 
146  // Manage the size of the list
147  if( m_cached_list.size() > m_maxSize )
148  {
149  // Get an iterator to the end of the list
150  LIST_ITERATOR last_it = m_cached_list.end();
151 
152  // This gets the real iterator that is the latest one
153  last_it--;
154 
155  // Remove the key from the map
156  m_map_iterators.erase( last_it->first );
157 
158  // Removes the last element in the list
159  m_cached_list.pop_back();
160  }
161  }
162 
163 
172  const t_value& Get( const wxString &aKey )
173  {
174  MAP_ITERATOR map_it = m_map_iterators.find( aKey );
175 
176  if( map_it == m_map_iterators.end() )
177  {
178  throw std::range_error( "Requested a key that dont exists" );
179  }
180 
181  // This will update the list and put in the beginning the iterator that we are getting
182  m_cached_list.splice( m_cached_list.begin(), m_cached_list, map_it->second );
183 
184  // Return the t_value from the <key, value> pair that was in the list
185  return map_it->second->second;
186  }
187 
188 
194  bool Exists( const wxString &aKey ) const
195  {
196  return ( m_map_iterators.find( aKey ) != m_map_iterators.end() );
197  }
198 
199 
206  void Resize( size_t aNewSize )
207  {
208  m_maxSize = aNewSize;
209 
210  while( m_map_iterators.size() > m_maxSize )
211  {
212  // Remove the key from the map
213  m_map_iterators.erase( m_cached_list.back().first );
214 
215  // Remove the back of the list
216  m_cached_list.pop_back();
217  }
218  }
219 
220 
225  size_t Size() const
226  {
227  return m_map_iterators.size();
228  }
229 
230 
235  size_t MaxSize() const
236  {
237  return m_maxSize;
238  }
239 
240 
241 };
242 
243 #endif // LRU_CACHE_H
WXSTR_HASH_MAP m_map_iterators
Cache map with iterators of the list.
Definition: lru_cache.h:105
bool Exists(const wxString &aKey) const
Function Exists.
Definition: lru_cache.h:194
size_t Size() const
Function Size.
Definition: lru_cache.h:225
CACHED_LIST m_cached_list
list of cached items
Definition: lru_cache.h:100
std::map< wxString, LIST_ITERATOR > WXSTR_HASH_MAP
Declares WXSTR_HASH_MAP Declares a map type of LIST_ITERATOR based on a wxString key.
Definition: lru_cache.h:88
std::list< KEY_VALUE_PAIR > CACHED_LIST
Declares LIST_ITERATOR Declares a iterator type for a list of KEY_VALUE_PAIR.
Definition: lru_cache.h:74
void Resize(size_t aNewSize)
Function Resize If aNewSize is smaller than the current maxSize then the items back in the list are d...
Definition: lru_cache.h:206
size_t m_maxSize
Max capacity of the cache.
Definition: lru_cache.h:111
std::pair< wxString, t_value > KEY_VALUE_PAIR
Declares KEY_VALUE_PAIR Declares a pair with the key (wxString) and a value.
Definition: lru_cache.h:68
LRU_WXSTR_CACHE(size_t aMaxSize=1)
Constructor LRU_WXSTR_CACHE.
Definition: lru_cache.h:120
size_t MaxSize() const
Function MaxSize.
Definition: lru_cache.h:235
Template LRU_WXSTR_CACHE template for a wxString key based LRU cache.
Definition: lru_cache.h:59
CACHED_LIST::iterator LIST_ITERATOR
Declares LIST_ITERATOR Declares a iterator type for a list of KEY_VALUE_PAIR.
Definition: lru_cache.h:81
void Insert(const wxString &aKey, const t_value &aValue)
Function Insert.
Definition: lru_cache.h:128
WXSTR_HASH_MAP::iterator MAP_ITERATOR
Declares MAP_ITERATOR Declares a iterator for the map.
Definition: lru_cache.h:94
const t_value & Get(const wxString &aKey)
Function Get Returns an existent value from the given key.
Definition: lru_cache.h:172