]>
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 | ||
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 | ||
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 | ||
60 | template <class Key, class Object> | |
61 | boost::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(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 | ||
84 | template <class Key, class Object> | |
85 | boost::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 |