object_cache.hpp 5.13 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
/*
 *
 * Copyright (c) 2004
 * John Maddock
 *
 * Use, modification and distribution are subject to the 
 * Boost Software License, Version 1.0. (See accompanying file 
 * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 *
 */

 /*
  *   LOCATION:    see http://www.boost.org for most recent version.
  *   FILE         object_cache.hpp
  *   VERSION      see <boost/version.hpp>
  *   DESCRIPTION: Implements a generic object cache.
  */

#ifndef BOOST_REGEX_OBJECT_CACHE_HPP
#define BOOST_REGEX_OBJECT_CACHE_HPP

#include <map>
#include <list>
#include <stdexcept>
#include <string>
#include <boost/config.hpp>
#include <boost/shared_ptr.hpp>
#ifdef BOOST_HAS_THREADS
#include <boost/regex/pending/static_mutex.hpp>
#endif

namespace boost{

template <class Key, class Object>
class object_cache
{
public:
   typedef std::pair< ::boost::shared_ptr<Object const>, Key const*> value_type;
   typedef std::list<value_type> list_type;
   typedef typename list_type::iterator list_iterator;
   typedef std::map<Key, list_iterator> map_type;
   typedef typename map_type::iterator map_iterator;
   typedef typename list_type::size_type size_type;
   static boost::shared_ptr<Object const> get(const Key& k, size_type l_max_cache_size);

private:
   static boost::shared_ptr<Object const> do_get(const Key& k, size_type l_max_cache_size);

   struct data
   {
      list_type   cont;
      map_type    index;
   };

   // Needed by compilers not implementing the resolution to DR45. For reference,
   // see http://www.open-std.org/JTC1/SC22/WG21/docs/cwg_defects.html#45.
   friend struct data;
};

template <class Key, class Object>
boost::shared_ptr<Object const> object_cache<Key, Object>::get(const Key& k, size_type l_max_cache_size)
{
#ifdef BOOST_HAS_THREADS
   static boost::static_mutex mut = BOOST_STATIC_MUTEX_INIT;

   boost::static_mutex::scoped_lock l(mut);
   if(l)
   {
      return do_get(k, l_max_cache_size);
   }
   //
   // what do we do if the lock fails?
   // for now just throw, but we should never really get here...
   //
   ::boost::throw_exception(std::runtime_error("Error in thread safety code: could not acquire a lock"));
#if defined(BOOST_NO_UNREACHABLE_RETURN_DETECTION) || defined(BOOST_NO_EXCEPTIONS)
   return boost::shared_ptr<Object>();
#endif
#else
   return do_get(k, l_max_cache_size);
#endif
}

template <class Key, class Object>
boost::shared_ptr<Object const> object_cache<Key, Object>::do_get(const Key& k, size_type l_max_cache_size)
{
   typedef typename object_cache<Key, Object>::data object_data;
   typedef typename map_type::size_type map_size_type;
   static object_data s_data;

   //
   // see if the object is already in the cache:
   //
   map_iterator mpos = s_data.index.find(k);
   if(mpos != s_data.index.end())
   {
      //
      // Eureka! 
      // We have a cached item, bump it up the list and return it:
      //
      if(--(s_data.cont.end()) != mpos->second)
      {
         // splice out the item we want to move:
         list_type temp;
         temp.splice(temp.end(), s_data.cont, mpos->second);
         // and now place it at the end of the list:
         s_data.cont.splice(s_data.cont.end(), temp, temp.begin());
         BOOST_ASSERT(*(s_data.cont.back().second) == k);
         // update index with new position:
         mpos->second = --(s_data.cont.end());
         BOOST_ASSERT(&(mpos->first) == mpos->second->second);
         BOOST_ASSERT(&(mpos->first) == s_data.cont.back().second);
      }
      return s_data.cont.back().first;
   }
   //
   // if we get here then the item is not in the cache,
   // so create it:
   //
   boost::shared_ptr<Object const> result(new Object(k));
   //
   // Add it to the list, and index it:
   //
   s_data.cont.push_back(value_type(result, static_cast<Key const*>(0)));
   s_data.index.insert(std::make_pair(k, --(s_data.cont.end())));
   s_data.cont.back().second = &(s_data.index.find(k)->first);
   map_size_type s = s_data.index.size();
   BOOST_ASSERT(s_data.index[k]->first.get() == result.get());
   BOOST_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second);
   BOOST_ASSERT(s_data.index.find(k)->first == k);
   if(s > l_max_cache_size)
   {
      //
      // We have too many items in the list, so we need to start
      // popping them off the back of the list, but only if they're
      // being held uniquely by us:
      //
      list_iterator pos = s_data.cont.begin();
      list_iterator last = s_data.cont.end();
      while((pos != last) && (s > l_max_cache_size))
      {
         if(pos->first.unique())
         {
            list_iterator condemmed(pos);
            ++pos;
            // now remove the items from our containers, 
            // then order has to be as follows:
            BOOST_ASSERT(s_data.index.find(*(condemmed->second)) != s_data.index.end());
            s_data.index.erase(*(condemmed->second));
            s_data.cont.erase(condemmed); 
            --s;
         }
         else
            --pos;
      }
      BOOST_ASSERT(s_data.index[k]->first.get() == result.get());
      BOOST_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second);
      BOOST_ASSERT(s_data.index.find(k)->first == k);
   }
   return result;
}

}

#endif