/* | |
* | |
* Copyright (c) 2004 | |
* John Maddock | |
* | |
* Use, modification and distribution are subject to the | |
* Boost Software License, Version 1.0. (See accompanying file | |
* LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
* | |
*/ | |
/* | |
* LOCATION: see http://www.boost.org for most recent version. | |
* FILE object_cache.hpp | |
* VERSION see <boost/version.hpp> | |
* DESCRIPTION: Implements a generic object cache. | |
*/ | |
#ifndef BOOST_REGEX_OBJECT_CACHE_HPP | |
#define BOOST_REGEX_OBJECT_CACHE_HPP | |
#include <map> | |
#include <list> | |
#include <stdexcept> | |
#include <string> | |
#include <boost/config.hpp> | |
#include <boost/shared_ptr.hpp> | |
#ifdef BOOST_HAS_THREADS | |
#include <boost/regex/pending/static_mutex.hpp> | |
#endif | |
namespace boost{ | |
template <class Key, class Object> | |
class object_cache | |
{ | |
public: | |
typedef std::pair< ::boost::shared_ptr<Object const>, Key const*> value_type; | |
typedef std::list<value_type> list_type; | |
typedef typename list_type::iterator list_iterator; | |
typedef std::map<Key, list_iterator> map_type; | |
typedef typename map_type::iterator map_iterator; | |
typedef typename list_type::size_type size_type; | |
static boost::shared_ptr<Object const> get(const Key& k, size_type l_max_cache_size); | |
private: | |
static boost::shared_ptr<Object const> do_get(const Key& k, size_type l_max_cache_size); | |
struct data | |
{ | |
list_type cont; | |
map_type index; | |
}; | |
// Needed by compilers not implementing the resolution to DR45. For reference, | |
// see http://www.open-std.org/JTC1/SC22/WG21/docs/cwg_defects.html#45. | |
friend struct data; | |
}; | |
template <class Key, class Object> | |
boost::shared_ptr<Object const> object_cache<Key, Object>::get(const Key& k, size_type l_max_cache_size) | |
{ | |
#ifdef BOOST_HAS_THREADS | |
static boost::static_mutex mut = BOOST_STATIC_MUTEX_INIT; | |
boost::static_mutex::scoped_lock l(mut); | |
if(l) | |
{ | |
return do_get(k, l_max_cache_size); | |
} | |
// | |
// what do we do if the lock fails? | |
// for now just throw, but we should never really get here... | |
// | |
::boost::throw_exception(std::runtime_error("Error in thread safety code: could not acquire a lock")); | |
#ifdef BOOST_NO_UNREACHABLE_RETURN_DETECTION | |
return boost::shared_ptr<Object>(); | |
#endif | |
#else | |
return do_get(k, l_max_cache_size); | |
#endif | |
} | |
template <class Key, class Object> | |
boost::shared_ptr<Object const> object_cache<Key, Object>::do_get(const Key& k, size_type l_max_cache_size) | |
{ | |
typedef typename object_cache<Key, Object>::data object_data; | |
typedef typename map_type::size_type map_size_type; | |
static object_data s_data; | |
// | |
// see if the object is already in the cache: | |
// | |
map_iterator mpos = s_data.index.find(k); | |
if(mpos != s_data.index.end()) | |
{ | |
// | |
// Eureka! | |
// We have a cached item, bump it up the list and return it: | |
// | |
if(--(s_data.cont.end()) != mpos->second) | |
{ | |
// splice out the item we want to move: | |
list_type temp; | |
temp.splice(temp.end(), s_data.cont, mpos->second); | |
// and now place it at the end of the list: | |
s_data.cont.splice(s_data.cont.end(), temp, temp.begin()); | |
BOOST_ASSERT(*(s_data.cont.back().second) == k); | |
// update index with new position: | |
mpos->second = --(s_data.cont.end()); | |
BOOST_ASSERT(&(mpos->first) == mpos->second->second); | |
BOOST_ASSERT(&(mpos->first) == s_data.cont.back().second); | |
} | |
return s_data.cont.back().first; | |
} | |
// | |
// if we get here then the item is not in the cache, | |
// so create it: | |
// | |
boost::shared_ptr<Object const> result(new Object(k)); | |
// | |
// Add it to the list, and index it: | |
// | |
s_data.cont.push_back(value_type(result, static_cast<Key const*>(0))); | |
s_data.index.insert(std::make_pair(k, --(s_data.cont.end()))); | |
s_data.cont.back().second = &(s_data.index.find(k)->first); | |
map_size_type s = s_data.index.size(); | |
BOOST_ASSERT(s_data.index[k]->first.get() == result.get()); | |
BOOST_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second); | |
BOOST_ASSERT(s_data.index.find(k)->first == k); | |
if(s > l_max_cache_size) | |
{ | |
// | |
// We have too many items in the list, so we need to start | |
// popping them off the back of the list, but only if they're | |
// being held uniquely by us: | |
// | |
list_iterator pos = s_data.cont.begin(); | |
list_iterator last = s_data.cont.end(); | |
while((pos != last) && (s > l_max_cache_size)) | |
{ | |
if(pos->first.unique()) | |
{ | |
list_iterator condemmed(pos); | |
++pos; | |
// now remove the items from our containers, | |
// then order has to be as follows: | |
BOOST_ASSERT(s_data.index.find(*(condemmed->second)) != s_data.index.end()); | |
s_data.index.erase(*(condemmed->second)); | |
s_data.cont.erase(condemmed); | |
--s; | |
} | |
else | |
--pos; | |
} | |
BOOST_ASSERT(s_data.index[k]->first.get() == result.get()); | |
BOOST_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second); | |
BOOST_ASSERT(s_data.index.find(k)->first == k); | |
} | |
return result; | |
} | |
} | |
#endif |