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 <map>
  23 #include <list>
  24 #include <stdexcept>
  25 #include <string>
  26 #include <boost/config.hpp>
  27 #include <boost/shared_ptr.hpp>
  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 max_cache_size);
  45
  46 private:
  47    static boost::shared_ptr<Object const> do_get(const Key& k, size_type 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 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, 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    return boost::shared_ptr<Object>();
  77 #else
  78    return do_get(k, max_cache_size);
  79 #endif
  80 }
  81
  82 template <class Key, class Object>
  83 boost::shared_ptr<Object const> object_cache<Key, Object>::do_get(const Key& k, size_type max_cache_size)
  84 {
  85    typedef typename object_cache<Key, Object>::data object_data;
  86    typedef typename map_type::size_type map_size_type;
  87    static object_data s_data;
  88
  89    //
  90    // see if the object is already in the cache:
  91    //
  92    map_iterator mpos = s_data.index.find(k);
  93    if(mpos != s_data.index.end())
  94    {
  95       //
  96       // Eureka!
  97       // We have a cached item, bump it up the list and return it:
  98       //
  99       if(--(s_data.cont.end()) != mpos->second)
 100       {
 101          // splice out the item we want to move:
 102          list_type temp;
 103          temp.splice(temp.end(), s_data.cont, mpos->second);
 104          // and now place it at the end of the list:
 105          s_data.cont.splice(s_data.cont.end(), temp, temp.begin());
 106          BOOST_ASSERT(*(s_data.cont.back().second) == k);
 107          // update index with new position:
 108          mpos->second = --(s_data.cont.end());
 109          BOOST_ASSERT(&(mpos->first) == mpos->second->second);
 110          BOOST_ASSERT(&(mpos->first) == s_data.cont.back().second);
 111       }
 112       return s_data.cont.back().first;
 113    }
 114    //
 115    // if we get here then the item is not in the cache,
 116    // so create it:
 117    //
 118    boost::shared_ptr<Object const> result(new Object(k));
 119    //
 120    // Add it to the list, and index it:
 121    //
 122    s_data.cont.push_back(value_type(result, static_cast<Key const*>(0)));
 123    s_data.index.insert(std::make_pair(k, --(s_data.cont.end())));
 124    s_data.cont.back().second = &(s_data.index.find(k)->first);
 125    map_size_type s = s_data.index.size();
 126    BOOST_ASSERT(s_data.index[k]->first.get() == result.get());
 127    BOOST_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second);
 128    BOOST_ASSERT(s_data.index.find(k)->first == k);
 129    if(s > max_cache_size)
 130    {
 131       //
 132       // We have too many items in the list, so we need to start
 133       // popping them off the back of the list, but only if they're
 134       // being held uniquely by us:
 135       //
 136       list_iterator pos = s_data.cont.begin();
 137       list_iterator last = s_data.cont.end();
 138       while((pos != last) && (s > max_cache_size))
 139       {
 140          if(pos->first.unique())
 141          {
 142             list_iterator condemmed(pos);
 143             ++pos;
 144             // now remove the items from our containers,
 145             // then order has to be as follows:
 146             BOOST_ASSERT(s_data.index.find(*(condemmed->second)) != s_data.index.end());
 147             s_data.index.erase(*(condemmed->second));
 148             s_data.cont.erase(condemmed);
 149             --s;
 150          }
 151          else
 152             --pos;
 153       }
 154       BOOST_ASSERT(s_data.index[k]->first.get() == result.get());
 155       BOOST_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second);
 156       BOOST_ASSERT(s_data.index.find(k)->first == k);
 157    }
 158    return result;
 159 }
 160
 161 }
 162
 163 #endif