]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
b32b8144 FG |
22 | #include <boost/config.hpp> |
23 | #include <boost/shared_ptr.hpp> | |
7c673cae FG |
24 | #include <map> |
25 | #include <list> | |
26 | #include <stdexcept> | |
27 | #include <string> | |
7c673cae FG |
28 | #ifdef BOOST_HAS_THREADS |
29 | #include <boost/regex/pending/static_mutex.hpp> | |
30 | #endif | |
31 | ||
32 | namespace boost{ | |
33 | ||
34 | template <class Key, class Object> | |
35 | class object_cache | |
36 | { | |
37 | public: | |
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 | ||
46 | private: | |
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 | ||
20effc67 TL |
60 | #ifdef BOOST_MSVC |
61 | #pragma warning(push) | |
62 | #pragma warning(disable: 4702) | |
63 | #endif | |
7c673cae FG |
64 | template <class Key, class Object> |
65 | boost::shared_ptr<Object const> object_cache<Key, Object>::get(const Key& k, size_type l_max_cache_size) | |
66 | { | |
67 | #ifdef BOOST_HAS_THREADS | |
68 | static boost::static_mutex mut = BOOST_STATIC_MUTEX_INIT; | |
69 | ||
70 | boost::static_mutex::scoped_lock l(mut); | |
71 | if(l) | |
72 | { | |
73 | return do_get(k, l_max_cache_size); | |
74 | } | |
75 | // | |
76 | // what do we do if the lock fails? | |
77 | // for now just throw, but we should never really get here... | |
78 | // | |
79 | ::boost::throw_exception(std::runtime_error("Error in thread safety code: could not acquire a lock")); | |
80 | #if defined(BOOST_NO_UNREACHABLE_RETURN_DETECTION) || defined(BOOST_NO_EXCEPTIONS) | |
81 | return boost::shared_ptr<Object>(); | |
82 | #endif | |
83 | #else | |
84 | return do_get(k, l_max_cache_size); | |
85 | #endif | |
86 | } | |
20effc67 TL |
87 | #ifdef BOOST_MSVC |
88 | #pragma warning(pop) | |
89 | #endif | |
7c673cae FG |
90 | |
91 | template <class Key, class Object> | |
92 | boost::shared_ptr<Object const> object_cache<Key, Object>::do_get(const Key& k, size_type l_max_cache_size) | |
93 | { | |
94 | typedef typename object_cache<Key, Object>::data object_data; | |
95 | typedef typename map_type::size_type map_size_type; | |
96 | static object_data s_data; | |
97 | ||
98 | // | |
99 | // see if the object is already in the cache: | |
100 | // | |
101 | map_iterator mpos = s_data.index.find(k); | |
102 | if(mpos != s_data.index.end()) | |
103 | { | |
104 | // | |
105 | // Eureka! | |
106 | // We have a cached item, bump it up the list and return it: | |
107 | // | |
108 | if(--(s_data.cont.end()) != mpos->second) | |
109 | { | |
110 | // splice out the item we want to move: | |
111 | list_type temp; | |
112 | temp.splice(temp.end(), s_data.cont, mpos->second); | |
113 | // and now place it at the end of the list: | |
114 | s_data.cont.splice(s_data.cont.end(), temp, temp.begin()); | |
115 | BOOST_ASSERT(*(s_data.cont.back().second) == k); | |
116 | // update index with new position: | |
117 | mpos->second = --(s_data.cont.end()); | |
118 | BOOST_ASSERT(&(mpos->first) == mpos->second->second); | |
119 | BOOST_ASSERT(&(mpos->first) == s_data.cont.back().second); | |
120 | } | |
121 | return s_data.cont.back().first; | |
122 | } | |
123 | // | |
124 | // if we get here then the item is not in the cache, | |
125 | // so create it: | |
126 | // | |
127 | boost::shared_ptr<Object const> result(new Object(k)); | |
128 | // | |
129 | // Add it to the list, and index it: | |
130 | // | |
131 | s_data.cont.push_back(value_type(result, static_cast<Key const*>(0))); | |
132 | s_data.index.insert(std::make_pair(k, --(s_data.cont.end()))); | |
133 | s_data.cont.back().second = &(s_data.index.find(k)->first); | |
134 | map_size_type s = s_data.index.size(); | |
135 | BOOST_ASSERT(s_data.index[k]->first.get() == result.get()); | |
136 | BOOST_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second); | |
137 | BOOST_ASSERT(s_data.index.find(k)->first == k); | |
138 | if(s > l_max_cache_size) | |
139 | { | |
140 | // | |
141 | // We have too many items in the list, so we need to start | |
142 | // popping them off the back of the list, but only if they're | |
143 | // being held uniquely by us: | |
144 | // | |
145 | list_iterator pos = s_data.cont.begin(); | |
146 | list_iterator last = s_data.cont.end(); | |
147 | while((pos != last) && (s > l_max_cache_size)) | |
148 | { | |
149 | if(pos->first.unique()) | |
150 | { | |
151 | list_iterator condemmed(pos); | |
152 | ++pos; | |
153 | // now remove the items from our containers, | |
154 | // then order has to be as follows: | |
155 | BOOST_ASSERT(s_data.index.find(*(condemmed->second)) != s_data.index.end()); | |
156 | s_data.index.erase(*(condemmed->second)); | |
157 | s_data.cont.erase(condemmed); | |
158 | --s; | |
159 | } | |
160 | else | |
161 | ++pos; | |
162 | } | |
163 | BOOST_ASSERT(s_data.index[k]->first.get() == result.get()); | |
164 | BOOST_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second); | |
165 | BOOST_ASSERT(s_data.index.find(k)->first == k); | |
166 | } | |
167 | return result; | |
168 | } | |
169 | ||
170 | } | |
171 | ||
172 | #endif |