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