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