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