3rdparty/boost/boost/regex/pending/object_cache.hpp

   1 /*
   2  *
   3  * Copyright (c) 2004
   4  * John Maddock
   5  *
   6  * Use, modification and distribution are subject to the
   7  * Boost Software License, Version 1.0. (See accompanying file
   8  * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   9  *
  10  */
  11
  12  /*
  13   *   LOCATION:    see http://www.boost.org for most recent version.
  14   *   FILE         object_cache.hpp
  15   *   VERSION      see <boost/version.hpp>
  16   *   DESCRIPTION: Implements a generic object cache.
  17   */
  18
  19 #ifndef BOOST_REGEX_OBJECT_CACHE_HPP
  20 #define BOOST_REGEX_OBJECT_CACHE_HPP
  21
  22 #include <boost/config.hpp>
  23 #include <boost/shared_ptr.hpp>
  24 #include <map>
  25 #include <list>
  26 #include <stdexcept>
  27 #include <string>
  28 #ifdef BOOST_HAS_THREADS
  29 #include <boost/regex/pending/static_mutex.hpp>
  30 #endif
  31
  32 namespace boost{
  33
  34 template <class Key, class Object>
  35 class object_cache
  36 {
  37 public:
  38    typedef std::pair< ::boost::shared_ptr<Object const>, Key const*> value_type;
  39    typedef std::list<value_type> list_type;
  40    typedef typename list_type::iterator list_iterator;
  41    typedef std::map<Key, list_iterator> map_type;
  42    typedef typename map_type::iterator map_iterator;
  43    typedef typename list_type::size_type size_type;
  44    static boost::shared_ptr<Object const> get(const Key& k, size_type l_max_cache_size);
  45
  46 private:
  47    static boost::shared_ptr<Object const> do_get(const Key& k, size_type l_max_cache_size);
  48
  49    struct data
  50    {
  51       list_type   cont;
  52       map_type    index;
  53    };
  54
  55    // Needed by compilers not implementing the resolution to DR45. For reference,
  56    // see http://www.open-std.org/JTC1/SC22/WG21/docs/cwg_defects.html#45.
  57    friend struct data;
  58 };
  59
  60 template <class Key, class Object>
  61 boost::shared_ptr<Object const> object_cache<Key, Object>::get(const Key& k, size_type l_max_cache_size)
  62 {
  63 #ifdef BOOST_HAS_THREADS
  64    static boost::static_mutex mut = BOOST_STATIC_MUTEX_INIT;
  65
  66    boost::static_mutex::scoped_lock l(mut);
  67    if(l)
  68    {
  69       return do_get(k, l_max_cache_size);
  70    }
  71    //
  72    // what do we do if the lock fails?
  73    // for now just throw, but we should never really get here...
  74    //
  75    ::boost::throw_exception(std::runtime_error("Error in thread safety code: could not acquire a lock"));
  76 #if defined(BOOST_NO_UNREACHABLE_RETURN_DETECTION) || defined(BOOST_NO_EXCEPTIONS)
  77    return boost::shared_ptr<Object>();
  78 #endif
  79 #else
  80    return do_get(k, l_max_cache_size);
  81 #endif
  82 }
  83
  84 template <class Key, class Object>
  85 boost::shared_ptr<Object const> object_cache<Key, Object>::do_get(const Key& k, size_type l_max_cache_size)
  86 {
  87    typedef typename object_cache<Key, Object>::data object_data;
  88    typedef typename map_type::size_type map_size_type;
  89    static object_data s_data;
  90
  91    //
  92    // see if the object is already in the cache:
  93    //
  94    map_iterator mpos = s_data.index.find(k);
  95    if(mpos != s_data.index.end())
  96    {
  97       //
  98       // Eureka!
  99       // We have a cached item, bump it up the list and return it:
 100       //
 101       if(--(s_data.cont.end()) != mpos->second)
 102       {
 103          // splice out the item we want to move:
 104          list_type temp;
 105          temp.splice(temp.end(), s_data.cont, mpos->second);
 106          // and now place it at the end of the list:
 107          s_data.cont.splice(s_data.cont.end(), temp, temp.begin());
 108          BOOST_ASSERT(*(s_data.cont.back().second) == k);
 109          // update index with new position:
 110          mpos->second = --(s_data.cont.end());
 111          BOOST_ASSERT(&(mpos->first) == mpos->second->second);
 112          BOOST_ASSERT(&(mpos->first) == s_data.cont.back().second);
 113       }
 114       return s_data.cont.back().first;
 115    }
 116    //
 117    // if we get here then the item is not in the cache,
 118    // so create it:
 119    //
 120    boost::shared_ptr<Object const> result(new Object(k));
 121    //
 122    // Add it to the list, and index it:
 123    //
 124    s_data.cont.push_back(value_type(result, static_cast<Key const*>(0)));
 125    s_data.index.insert(std::make_pair(k, --(s_data.cont.end())));
 126    s_data.cont.back().second = &(s_data.index.find(k)->first);
 127    map_size_type s = s_data.index.size();
 128    BOOST_ASSERT(s_data.index[k]->first.get() == result.get());
 129    BOOST_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second);
 130    BOOST_ASSERT(s_data.index.find(k)->first == k);
 131    if(s > l_max_cache_size)
 132    {
 133       //
 134       // We have too many items in the list, so we need to start
 135       // popping them off the back of the list, but only if they're
 136       // being held uniquely by us:
 137       //
 138       list_iterator pos = s_data.cont.begin();
 139       list_iterator last = s_data.cont.end();
 140       while((pos != last) && (s > l_max_cache_size))
 141       {
 142          if(pos->first.unique())
 143          {
 144             list_iterator condemmed(pos);
 145             ++pos;
 146             // now remove the items from our containers,
 147             // then order has to be as follows:
 148             BOOST_ASSERT(s_data.index.find(*(condemmed->second)) != s_data.index.end());
 149             s_data.index.erase(*(condemmed->second));
 150             s_data.cont.erase(condemmed);
 151             --s;
 152          }
 153          else
 154             ++pos;
 155       }
 156       BOOST_ASSERT(s_data.index[k]->first.get() == result.get());
 157       BOOST_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second);
 158       BOOST_ASSERT(s_data.index.find(k)->first == k);
 159    }
 160    return result;
 161 }
 162
 163 }
 164
 165 #endif