57c57
< template <typename V>
---
> template <typename V, int max_cache_size=0>
126a127
> cache.remove(p);
132a134,136
> for (auto it = p; it != q; it++) {
> cache.remove(p);
> }
138a143
> cache.erase(cache.begin(), cache.end());
179a185,209
> * Add an address range map entry to the cache.
> *
> * @param it Iterator to the entry in the address range map
> */
> void
> addNewEntryToCache(const_iterator it) const
> {
> if (max_cache_size != 0) {
> // If there's a cache, add this element to it.
> if (cache.size() >= max_cache_size) {
> // If the cache is full, move the last element to the
> // front and overwrite it with the new value. This
> // avoids creating or destroying elements of the list.
> auto last = cache.end();
> last--;
> *last = it;
> if (max_cache_size > 1)
> cache.splice(cache.begin(), cache, last);
> } else {
> cache.push_front(it);
> }
> }
> }
>
> /**
192a223,233
> // Check the cache first
> for (auto c = cache.begin(); c != cache.end(); c++) {
> auto it = *c;
> if (cond(it->first)) {
> // If this entry matches, promote it to the front
> // of the cache and return it.
> cache.splice(cache.begin(), cache, c);
> return it;
> }
> }
>
194a236
> addNewEntryToCache(next);
204a247
> addNewEntryToCache(i);
214a258,265
>
> /**
> * A list of iterator that correspond to the max_cache_size most
> * recently used entries in the address range map. This mainly
> * used to optimize lookups. The elements in the list should
> * always be valid iterators of the tree.
> */
> mutable std::list<const_iterator> cache;