1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
/*
*
* Copyright (c) 2004
* John Maddock
*
* Use, modification and distribution are subject to the
* Boost Software License, Version 1.0. (See accompanying file
* LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
*
*/
/*
* LOCATION: see http://www.boost.org for most recent version.
* FILE object_cache.hpp
* VERSION see <cutl/details/boost/version.hpp>
* DESCRIPTION: Implements a generic object cache.
*/
#ifndef BOOST_REGEX_OBJECT_CACHE_HPP
#define BOOST_REGEX_OBJECT_CACHE_HPP
#include <map>
#include <list>
#include <stdexcept>
#include <string>
#include <cutl/details/boost/config.hpp>
#include <cutl/details/boost/shared_ptr.hpp>
#ifdef BOOST_HAS_THREADS
#include <cutl/details/boost/regex/pending/static_mutex.hpp>
#endif
namespace cutl_details_boost{
template <class Key, class Object>
class object_cache
{
public:
typedef std::pair< ::cutl_details_boost::shared_ptr<Object const>, Key const*> value_type;
typedef std::list<value_type> list_type;
typedef typename list_type::iterator list_iterator;
typedef std::map<Key, list_iterator> map_type;
typedef typename map_type::iterator map_iterator;
typedef typename list_type::size_type size_type;
static cutl_details_boost::shared_ptr<Object const> get(const Key& k, size_type l_max_cache_size);
private:
static cutl_details_boost::shared_ptr<Object const> do_get(const Key& k, size_type l_max_cache_size);
struct data
{
list_type cont;
map_type index;
};
// Needed by compilers not implementing the resolution to DR45. For reference,
// see http://www.open-std.org/JTC1/SC22/WG21/docs/cwg_defects.html#45.
friend struct data;
};
template <class Key, class Object>
cutl_details_boost::shared_ptr<Object const> object_cache<Key, Object>::get(const Key& k, size_type l_max_cache_size)
{
#ifdef BOOST_HAS_THREADS
static cutl_details_boost::static_mutex mut = BOOST_STATIC_MUTEX_INIT;
cutl_details_boost::static_mutex::scoped_lock l(mut);
if(l)
{
return do_get(k, l_max_cache_size);
}
//
// what do we do if the lock fails?
// for now just throw, but we should never really get here...
//
::cutl_details_boost::throw_exception(std::runtime_error("Error in thread safety code: could not acquire a lock"));
#if defined(BOOST_NO_UNREACHABLE_RETURN_DETECTION) || defined(BOOST_NO_EXCEPTIONS)
return cutl_details_boost::shared_ptr<Object>();
#endif
#else
return do_get(k, l_max_cache_size);
#endif
}
template <class Key, class Object>
cutl_details_boost::shared_ptr<Object const> object_cache<Key, Object>::do_get(const Key& k, size_type l_max_cache_size)
{
typedef typename object_cache<Key, Object>::data object_data;
typedef typename map_type::size_type map_size_type;
static object_data s_data;
//
// see if the object is already in the cache:
//
map_iterator mpos = s_data.index.find(k);
if(mpos != s_data.index.end())
{
//
// Eureka!
// We have a cached item, bump it up the list and return it:
//
if(--(s_data.cont.end()) != mpos->second)
{
// splice out the item we want to move:
list_type temp;
temp.splice(temp.end(), s_data.cont, mpos->second);
// and now place it at the end of the list:
s_data.cont.splice(s_data.cont.end(), temp, temp.begin());
BOOST_ASSERT(*(s_data.cont.back().second) == k);
// update index with new position:
mpos->second = --(s_data.cont.end());
BOOST_ASSERT(&(mpos->first) == mpos->second->second);
BOOST_ASSERT(&(mpos->first) == s_data.cont.back().second);
}
return s_data.cont.back().first;
}
//
// if we get here then the item is not in the cache,
// so create it:
//
cutl_details_boost::shared_ptr<Object const> result(new Object(k));
//
// Add it to the list, and index it:
//
s_data.cont.push_back(value_type(result, static_cast<Key const*>(0)));
s_data.index.insert(std::make_pair(k, --(s_data.cont.end())));
s_data.cont.back().second = &(s_data.index.find(k)->first);
map_size_type s = s_data.index.size();
BOOST_ASSERT(s_data.index[k]->first.get() == result.get());
BOOST_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second);
BOOST_ASSERT(s_data.index.find(k)->first == k);
if(s > l_max_cache_size)
{
//
// We have too many items in the list, so we need to start
// popping them off the back of the list, but only if they're
// being held uniquely by us:
//
list_iterator pos = s_data.cont.begin();
list_iterator last = s_data.cont.end();
while((pos != last) && (s > l_max_cache_size))
{
if(pos->first.unique())
{
list_iterator condemmed(pos);
++pos;
// now remove the items from our containers,
// then order has to be as follows:
BOOST_ASSERT(s_data.index.find(*(condemmed->second)) != s_data.index.end());
s_data.index.erase(*(condemmed->second));
s_data.cont.erase(condemmed);
--s;
}
else
++pos;
}
BOOST_ASSERT(s_data.index[k]->first.get() == result.get());
BOOST_ASSERT(&(s_data.index.find(k)->first) == s_data.cont.back().second);
BOOST_ASSERT(s_data.index.find(k)->first == k);
}
return result;
}
}
#endif
|
