regex/v5/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 <memory>
0024 #include <map>
0025 #include <list>
0026 #include <stdexcept>
0027 #include <string>
0028 #ifdef BOOST_HAS_THREADS
0029 #include <mutex>
0030 #endif
0031
0032 namespace boost{
0033
0034 template <class Key, class Object>
0035 class object_cache
0036 {
0037 public:
0038    typedef std::pair< ::std::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 std::shared_ptr<Object const> get(const Key& k, size_type l_max_cache_size);
0045
0046 private:
0047    static std::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_REGEX_MSVC
0061 #pragma warning(push)
0062 #pragma warning(disable: 4702)
0063 #endif
0064 template <class Key, class Object>
0065 std::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 std::mutex mut;
0069    std::lock_guard<std::mutex> l(mut);
0070    return do_get(k, l_max_cache_size);
0071 #else
0072    return do_get(k, l_max_cache_size);
0073 #endif
0074 }
0075 #ifdef BOOST_REGEX_MSVC
0076 #pragma warning(pop)
0077 #endif
0078
0079 template <class Key, class Object>
0080 std::shared_ptr<Object const> object_cache<Key, Object>::do_get(const Key& k, size_type l_max_cache_size)
0081 {
0082    typedef typename object_cache<Key, Object>::data object_data;
0083    typedef typename map_type::size_type map_size_type;
0084    static object_data s_data;
0085
0086    //
0087    // see if the object is already in the cache:
0088    //
0089    map_iterator mpos = s_data.index.find(k);
0090    if(mpos != s_data.index.end())
0091    {
0092       //
0093       // Eureka!
0094       // We have a cached item, bump it up the list and return it:
0095       //
0096       if(--(s_data.cont.end()) != mpos->second)
0097       {
0098          // splice out the item we want to move:
0099          list_type temp;
0100          temp.splice(temp.end(), s_data.cont, mpos->second);
0101          // and now place it at the end of the list:
0102          s_data.cont.splice(s_data.cont.end(), temp, temp.begin());
0103          BOOST_REGEX_ASSERT(*(s_data.cont.back().second) == k);
0104          // update index with new position:
0105          mpos->second = --(s_data.cont.end());
0106          BOOST_REGEX_ASSERT(&(mpos->first) == mpos->second->second);
0107          BOOST_REGEX_ASSERT(&(mpos->first) == s_data.cont.back().second);
0108       }
0109       return s_data.cont.back().first;
0110    }
0111    //
0112    // if we get here then the item is not in the cache,
0113    // so create it:
0114    //
0115    std::shared_ptr<Object const> result(new Object(k));
0116    //
0117    // Add it to the list, and index it:
0118    //
0119    s_data.cont.push_back(value_type(result, static_cast<Key const*>(0)));
0120    s_data.index.insert(std::make_pair(k, --(s_data.cont.end())));
0121    s_data.cont.back().second = &(s_data.index.find(k)->first);
0122    map_size_type s = s_data.index.size();
0123    BOOST_REGEX_ASSERT(s_data.index[k]->first.get() == result.get());
0124    BOOST_REGEX_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second);
0125    BOOST_REGEX_ASSERT(s_data.index.find(k)->first == k);
0126    if(s > l_max_cache_size)
0127    {
0128       //
0129       // We have too many items in the list, so we need to start
0130       // popping them off the back of the list, but only if they're
0131       // being held uniquely by us:
0132       //
0133       list_iterator pos = s_data.cont.begin();
0134       list_iterator last = s_data.cont.end();
0135       while((pos != last) && (s > l_max_cache_size))
0136       {
0137          if(pos->first.use_count() == 1)
0138          {
0139             list_iterator condemmed(pos);
0140             ++pos;
0141             // now remove the items from our containers,
0142             // then order has to be as follows:
0143             BOOST_REGEX_ASSERT(s_data.index.find(*(condemmed->second)) != s_data.index.end());
0144             s_data.index.erase(*(condemmed->second));
0145             s_data.cont.erase(condemmed);
0146             --s;
0147          }
0148          else
0149             ++pos;
0150       }
0151       BOOST_REGEX_ASSERT(s_data.index[k]->first.get() == result.get());
0152       BOOST_REGEX_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second);
0153       BOOST_REGEX_ASSERT(s_data.index.find(k)->first == k);
0154    }
0155    return result;
0156 }
0157
0158 }
0159
0160 #endif