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(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 | |
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 |
166 | |