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

source code of boost/boost/regex/pending/object_cache.hpp