annotate DEPENDENCIES/generic/include/boost/regex/pending/object_cache.hpp @ 133:4acb5d8d80b6 tip

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