regex/v4/object_cache.hpp

0001 /*
0002  *
0003  * Copyright (c) 2004
0004  * John Maddock
0005  *
0006  * Use, modification and distribution are subject to the
0007  * Boost Software License, Version 1.0. (See accompanying file
0008  * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0009  *
0010  */
0011
0012  /*
0013   *   LOCATION:    see http://www.boost.org for most recent version.
0014   *   FILE         object_cache.hpp
0015   *   VERSION      see <boost/version.hpp>
0016   *   DESCRIPTION: Implements a generic object cache.
0017   */
0018
0019 #ifndef BOOST_REGEX_OBJECT_CACHE_HPP
0020 #define BOOST_REGEX_OBJECT_CACHE_HPP
0021
0022 #include <boost/regex/config.hpp>
0023 #include <boost/shared_ptr.hpp>
0024 #include <map>
0025 #include <list>
0026 #include <stdexcept>
0027 #include <string>
0028 #ifdef BOOST_HAS_THREADS
0029 #include <boost/regex/pending/static_mutex.hpp>
0030 #endif
0031
0032 namespace boost{
0033
0034 template <class Key, class Object>
0035 class object_cache
0036 {
0037 public:
0038    typedef std::pair< ::boost::shared_ptr<Object const>, Key const*> value_type;
0039    typedef std::list<value_type> list_type;
0040    typedef typename list_type::iterator list_iterator;
0041    typedef std::map<Key, list_iterator> map_type;
0042    typedef typename map_type::iterator map_iterator;
0043    typedef typename list_type::size_type size_type;
0044    static boost::shared_ptr<Object const> get(const Key& k, size_type l_max_cache_size);
0045
0046 private:
0047    static boost::shared_ptr<Object const> do_get(const Key& k, size_type l_max_cache_size);
0048
0049    struct data
0050    {
0051       list_type   cont;
0052       map_type    index;
0053    };
0054
0055    // Needed by compilers not implementing the resolution to DR45. For reference,
0056    // see http://www.open-std.org/JTC1/SC22/WG21/docs/cwg_defects.html#45.
0057    friend struct data;
0058 };
0059
0060 #ifdef BOOST_MSVC
0061 #pragma warning(push)
0062 #pragma warning(disable: 4702)
0063 #endif
0064 template <class Key, class Object>
0065 boost::shared_ptr<Object const> object_cache<Key, Object>::get(const Key& k, size_type l_max_cache_size)
0066 {
0067 #ifdef BOOST_HAS_THREADS
0068    static boost::static_mutex mut = BOOST_STATIC_MUTEX_INIT;
0069    boost::static_mutex::scoped_lock l(mut);
0070    if (l)
0071    {
0072       return do_get(k, l_max_cache_size);
0073    }
0074    //
0075    // what do we do if the lock fails?
0076    // for now just throw, but we should never really get here...
0077    //
0078    ::boost::throw_exception(std::runtime_error("Error in thread safety code: could not acquire a lock"));
0079 #if defined(BOOST_NO_UNREACHABLE_RETURN_DETECTION) || defined(BOOST_NO_EXCEPTIONS)
0080    return boost::shared_ptr<Object>();
0081 #endif
0082 #else
0083    return do_get(k, l_max_cache_size);
0084 #endif
0085 }
0086 #ifdef BOOST_MSVC
0087 #pragma warning(pop)
0088 #endif
0089
0090 template <class Key, class Object>
0091 boost::shared_ptr<Object const> object_cache<Key, Object>::do_get(const Key& k, size_type l_max_cache_size)
0092 {
0093    typedef typename object_cache<Key, Object>::data object_data;
0094    typedef typename map_type::size_type map_size_type;
0095    static object_data s_data;
0096
0097    //
0098    // see if the object is already in the cache:
0099    //
0100    map_iterator mpos = s_data.index.find(k);
0101    if(mpos != s_data.index.end())
0102    {
0103       //
0104       // Eureka!
0105       // We have a cached item, bump it up the list and return it:
0106       //
0107       if(--(s_data.cont.end()) != mpos->second)
0108       {
0109          // splice out the item we want to move:
0110          list_type temp;
0111          temp.splice(temp.end(), s_data.cont, mpos->second);
0112          // and now place it at the end of the list:
0113          s_data.cont.splice(s_data.cont.end(), temp, temp.begin());
0114          BOOST_REGEX_ASSERT(*(s_data.cont.back().second) == k);
0115          // update index with new position:
0116          mpos->second = --(s_data.cont.end());
0117          BOOST_REGEX_ASSERT(&(mpos->first) == mpos->second->second);
0118          BOOST_REGEX_ASSERT(&(mpos->first) == s_data.cont.back().second);
0119       }
0120       return s_data.cont.back().first;
0121    }
0122    //
0123    // if we get here then the item is not in the cache,
0124    // so create it:
0125    //
0126    boost::shared_ptr<Object const> result(new Object(k));
0127    //
0128    // Add it to the list, and index it:
0129    //
0130    s_data.cont.push_back(value_type(result, static_cast<Key const*>(0)));
0131    s_data.index.insert(std::make_pair(k, --(s_data.cont.end())));
0132    s_data.cont.back().second = &(s_data.index.find(k)->first);
0133    map_size_type s = s_data.index.size();
0134    BOOST_REGEX_ASSERT(s_data.index[k]->first.get() == result.get());
0135    BOOST_REGEX_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second);
0136    BOOST_REGEX_ASSERT(s_data.index.find(k)->first == k);
0137    if(s > l_max_cache_size)
0138    {
0139       //
0140       // We have too many items in the list, so we need to start
0141       // popping them off the back of the list, but only if they're
0142       // being held uniquely by us:
0143       //
0144       list_iterator pos = s_data.cont.begin();
0145       list_iterator last = s_data.cont.end();
0146       while((pos != last) && (s > l_max_cache_size))
0147       {
0148          if(pos->first.unique())
0149          {
0150             list_iterator condemmed(pos);
0151             ++pos;
0152             // now remove the items from our containers,
0153             // then order has to be as follows:
0154             BOOST_REGEX_ASSERT(s_data.index.find(*(condemmed->second)) != s_data.index.end());
0155             s_data.index.erase(*(condemmed->second));
0156             s_data.cont.erase(condemmed);
0157             --s;
0158          }
0159          else
0160             ++pos;
0161       }
0162       BOOST_REGEX_ASSERT(s_data.index[k]->first.get() == result.get());
0163       BOOST_REGEX_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second);
0164       BOOST_REGEX_ASSERT(s_data.index.find(k)->first == k);
0165    }
0166    return result;
0167 }
0168
0169 }
0170
0171 #endif