| 143 | } // namespace unnamed |
| 144 | |
| 145 | std::pair<void*, int> cast_graph::impl::cast( |
| 146 | void* const p, class_id src, class_id target |
| 147 | , class_id dynamic_id, void const* dynamic_ptr) const |
| 148 | { |
| 149 | if (src == target) |
| 150 | return std::make_pair(p, 0); |
| 151 | |
| 152 | if (src >= m_vertices.size() || target >= m_vertices.size()) |
| 153 | return std::pair<void*, int>(static_cast<void*>(0), -1); |
| 154 | |
| 155 | std::ptrdiff_t const object_offset = |
| 156 | static_cast<char const*>(dynamic_ptr) - static_cast<char const*>(p); |
| 157 | |
| 158 | cache_entry cached = m_cache.get(src, target, dynamic_id, object_offset); |
| 159 | |
| 160 | if (cached.first != cache::unknown) |
| 161 | { |
| 162 | if (cached.first == cache::invalid) |
| 163 | return std::pair<void*, int>(static_cast<void*>(0), -1); |
| 164 | return std::make_pair(static_cast<char*>(p) + cached.first, cached.second); |
| 165 | } |
| 166 | |
| 167 | std::queue<queue_entry> q; |
| 168 | q.push(queue_entry(p, src, 0)); |
| 169 | |
| 170 | boost::dynamic_bitset<> visited(m_vertices.size()); |
| 171 | |
| 172 | while (!q.empty()) |
| 173 | { |
| 174 | queue_entry const qe = q.front(); |
| 175 | q.pop(); |
| 176 | |
| 177 | visited[qe.vertex_id] = true; |
| 178 | vertex const& v = m_vertices[qe.vertex_id]; |
| 179 | |
| 180 | if (v.id == target) |
| 181 | { |
| 182 | m_cache.put( |
| 183 | src, target, dynamic_id, object_offset |
| 184 | , static_cast<char*>(qe.p) - static_cast<char*>(p), qe.distance |
| 185 | ); |
| 186 | |
| 187 | return std::make_pair(qe.p, qe.distance); |
| 188 | } |
| 189 | |
| 190 | BOOST_FOREACH(edge const& e, v.edges) |
| 191 | { |
| 192 | if (visited[e.target]) |
| 193 | continue; |
| 194 | if (void* casted = e.cast(qe.p)) |
| 195 | q.push(queue_entry(casted, e.target, qe.distance + 1)); |
| 196 | } |
| 197 | } |
| 198 | |
| 199 | m_cache.put(src, target, dynamic_id, object_offset, cache::invalid, -1); |
| 200 | |
| 201 | return std::pair<void*, int>(static_cast<void*>(0), -1); |
| 202 | } |