/*

 *

 * 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 max_cache_size);

private:

   static boost::shared_ptr<Object const> do_get(const Key& k, size_type 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 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, 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"));

   return boost::shared_ptr<Object>();

#else

   return do_get(k, 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 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 > 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 > 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