1 // Copyright Daniel Wallin 2009. Use, modification and distribution is
2 // subject to the Boost Software License, Version 1.0. (See accompanying
3 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
4
5 #define LUABIND_BUILDING
6
7 #include <luabind/detail/inheritance.hpp>
8 #include <luabind/typeid.hpp>
9
10 #include <boost/dynamic_bitset.hpp>
11 #include <boost/foreach.hpp>
12 #include <boost/tuple/tuple.hpp>
13 #include <boost/tuple/tuple_comparison.hpp>
14
15 #include <limits>
16 #include <map>
17 #include <queue>
18 #include <vector>
19
20
21 namespace luabind { namespace detail {
22
23 LUABIND_API char classid_map_tag = 0;
24 LUABIND_API char class_map_tag = 0;
25 char cast_graph_tag = 0;
26
27 class_id const class_id_map::local_id_base =
28 std::numeric_limits<class_id>::max() / 2;
29
30 namespace
31 {
32
33 struct edge
34 {
edgeluabind::detail::__anon61cba4fe0111::edge35 edge(class_id target_, cast_function cast_)
36 : target(target_)
37 , cast(cast_)
38 {}
39
40 class_id target;
41 cast_function cast;
42 };
43
operator <(edge const & x,edge const & y)44 bool operator<(edge const& x, edge const& y)
45 {
46 return x.target < y.target;
47 }
48
49 struct vertex
50 {
vertexluabind::detail::__anon61cba4fe0111::vertex51 vertex(class_id id_)
52 : id(id_)
53 {}
54
55 class_id id;
56 std::vector<edge> edges;
57 };
58
59 typedef std::pair<std::ptrdiff_t, int> cache_entry;
60
61 class cache
62 {
63 public:
64 static std::ptrdiff_t const unknown;
65 static std::ptrdiff_t const invalid;
66
67 cache_entry get(
68 class_id src, class_id target, class_id dynamic_id
69 , std::ptrdiff_t object_offset) const;
70
71 void put(
72 class_id src, class_id target, class_id dynamic_id
73 , std::ptrdiff_t object_offset
74 , std::ptrdiff_t offset, int distance);
75
76 void invalidate();
77
78 private:
79 typedef boost::tuple<
80 class_id, class_id, class_id, std::ptrdiff_t> key_type;
81 typedef std::map<key_type, cache_entry> map_type;
82 map_type m_cache;
83 };
84
85 std::ptrdiff_t const cache::unknown =
86 std::numeric_limits<std::ptrdiff_t>::max();
87 std::ptrdiff_t const cache::invalid = cache::unknown - 1;
88
get(class_id src,class_id target,class_id dynamic_id,std::ptrdiff_t object_offset) const89 cache_entry cache::get(
90 class_id src, class_id target, class_id dynamic_id
91 , std::ptrdiff_t object_offset) const
92 {
93 map_type::const_iterator i = m_cache.find(
94 key_type(src, target, dynamic_id, object_offset));
95 return i != m_cache.end() ? i->second : cache_entry(unknown, -1);
96 }
97
put(class_id src,class_id target,class_id dynamic_id,std::ptrdiff_t object_offset,std::ptrdiff_t offset,int distance)98 void cache::put(
99 class_id src, class_id target, class_id dynamic_id
100 , std::ptrdiff_t object_offset, std::ptrdiff_t offset, int distance)
101 {
102 m_cache.insert(std::make_pair(
103 key_type(src, target, dynamic_id, object_offset)
104 , cache_entry(offset, distance)
105 ));
106 }
107
invalidate()108 void cache::invalidate()
109 {
110 m_cache.clear();
111 }
112
113 } // namespace unnamed
114
115 class cast_graph::impl
116 {
117 public:
118 std::pair<void*, int> cast(
119 void* p, class_id src, class_id target
120 , class_id dynamic_id, void const* dynamic_ptr) const;
121 void insert(class_id src, class_id target, cast_function cast);
122
123 private:
124 std::vector<vertex> m_vertices;
125 mutable cache m_cache;
126 };
127
128 namespace
129 {
130
131 struct queue_entry
132 {
queue_entryluabind::detail::__anon61cba4fe0211::queue_entry133 queue_entry(void* p_, class_id vertex_id_, int distance_)
134 : p(p_)
135 , vertex_id(vertex_id_)
136 , distance(distance_)
137 {}
138
139 void* p;
140 class_id vertex_id;
141 int distance;
142 };
143
144 } // namespace unnamed
145
cast(void * const p,class_id src,class_id target,class_id dynamic_id,void const * dynamic_ptr) const146 std::pair<void*, int> cast_graph::impl::cast(
147 void* const p, class_id src, class_id target
148 , class_id dynamic_id, void const* dynamic_ptr) const
149 {
150 if (src == target)
151 return std::make_pair(p, 0);
152
153 if (src >= m_vertices.size() || target >= m_vertices.size())
154 return std::pair<void*, int>(static_cast<void*>(0), -1);
155
156 std::ptrdiff_t const object_offset =
157 static_cast<char const*>(dynamic_ptr) - static_cast<char const*>(p);
158
159 cache_entry cached = m_cache.get(src, target, dynamic_id, object_offset);
160
161 if (cached.first != cache::unknown)
162 {
163 if (cached.first == cache::invalid)
164 return std::pair<void*, int>(static_cast<void*>(0), -1);
165 return std::make_pair(static_cast<char*>(p) + cached.first, cached.second);
166 }
167
168 std::queue<queue_entry> q;
169 q.push(queue_entry(p, src, 0));
170
171 boost::dynamic_bitset<> visited(m_vertices.size());
172
173 while (!q.empty())
174 {
175 queue_entry const qe = q.front();
176 q.pop();
177
178 visited[qe.vertex_id] = true;
179 vertex const& v = m_vertices[qe.vertex_id];
180
181 if (v.id == target)
182 {
183 m_cache.put(
184 src, target, dynamic_id, object_offset
185 , static_cast<char*>(qe.p) - static_cast<char*>(p), qe.distance
186 );
187
188 return std::make_pair(qe.p, qe.distance);
189 }
190
191 BOOST_FOREACH(edge const& e, v.edges)
192 {
193 if (visited[e.target])
194 continue;
195 if (void* casted = e.cast(qe.p))
196 q.push(queue_entry(casted, e.target, qe.distance + 1));
197 }
198 }
199
200 m_cache.put(src, target, dynamic_id, object_offset, cache::invalid, -1);
201
202 return std::pair<void*, int>(static_cast<void*>(0), -1);
203 }
204
insert(class_id src,class_id target,cast_function cast_)205 void cast_graph::impl::insert(
206 class_id src, class_id target, cast_function cast_)
207 {
208 class_id const max_id = std::max(src, target);
209
210 if (max_id >= m_vertices.size())
211 {
212 m_vertices.reserve(max_id + 1);
213 for (class_id i = m_vertices.size(); i < max_id + 1; ++i)
214 m_vertices.push_back(vertex(i));
215 }
216
217 std::vector<edge>& edges = m_vertices[src].edges;
218
219 std::vector<edge>::iterator i = std::lower_bound(
220 edges.begin(), edges.end(), edge(target, 0)
221 );
222
223 if (i == edges.end() || i->target != target)
224 {
225 edges.insert(i, edge(target, cast_));
226 m_cache.invalidate();
227 }
228 }
229
cast(void * p,class_id src,class_id target,class_id dynamic_id,void const * dynamic_ptr) const230 std::pair<void*, int> cast_graph::cast(
231 void* p, class_id src, class_id target
232 , class_id dynamic_id, void const* dynamic_ptr) const
233 {
234 return m_impl->cast(p, src, target, dynamic_id, dynamic_ptr);
235 }
236
insert(class_id src,class_id target,cast_function cast_)237 void cast_graph::insert(class_id src, class_id target, cast_function cast_)
238 {
239 m_impl->insert(src, target, cast_);
240 }
241
cast_graph()242 cast_graph::cast_graph()
243 : m_impl(new impl)
244 {}
245
~cast_graph()246 cast_graph::~cast_graph()
247 {}
248
allocate_class_id(type_id const & cls)249 LUABIND_API class_id allocate_class_id(type_id const& cls)
250 {
251 typedef std::map<type_id, class_id> map_type;
252
253 static map_type registered;
254 static class_id id = 0;
255
256 std::pair<map_type::iterator, bool> inserted = registered.insert(
257 std::make_pair(cls, id));
258
259 if (inserted.second)
260 ++id;
261
262 return inserted.first->second;
263 }
264
265 }} // namespace luabind::detail
266