/*
 *
 * 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"));
#ifdef BOOST_NO_UNREACHABLE_RETURN_DETECTION
   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