1 #ifndef OSRM_PARTITIONER_CUSTOMIZE_CELL_STORAGE_HPP 2 #define OSRM_PARTITIONER_CUSTOMIZE_CELL_STORAGE_HPP 3 4 #include "partitioner/multi_level_partition.hpp" 5 6 #include "util/assert.hpp" 7 #include "util/for_each_range.hpp" 8 #include "util/log.hpp" 9 #include "util/typedefs.hpp" 10 #include "util/vector_view.hpp" 11 12 #include "storage/io_fwd.hpp" 13 #include "storage/shared_memory_ownership.hpp" 14 15 #include "customizer/cell_metric.hpp" 16 17 #include <boost/iterator/iterator_facade.hpp> 18 #include <boost/range/iterator_range.hpp> 19 20 #include <tbb/parallel_sort.h> 21 22 #include <algorithm> 23 #include <numeric> 24 #include <utility> 25 #include <vector> 26 27 namespace osrm 28 { 29 namespace partitioner 30 { 31 namespace detail 32 { 33 template <storage::Ownership Ownership> class CellStorageImpl; 34 } 35 using CellStorage = detail::CellStorageImpl<storage::Ownership::Container>; 36 using CellStorageView = detail::CellStorageImpl<storage::Ownership::View>; 37 38 namespace serialization 39 { 40 template <storage::Ownership Ownership> 41 inline void read(storage::tar::FileReader &reader, 42 const std::string &name, 43 detail::CellStorageImpl<Ownership> &storage); 44 template <storage::Ownership Ownership> 45 inline void write(storage::tar::FileWriter &writer, 46 const std::string &name, 47 const detail::CellStorageImpl<Ownership> &storage); 48 } // namespace serialization 49 50 namespace detail 51 { 52 template <storage::Ownership Ownership> class CellStorageImpl 53 { 54 public: 55 using ValueOffset = std::uint64_t; 56 using BoundaryOffset = std::uint64_t; 57 using BoundarySize = std::uint32_t; 58 59 static constexpr auto INVALID_VALUE_OFFSET = std::numeric_limits<ValueOffset>::max(); 60 static constexpr auto INVALID_BOUNDARY_OFFSET = std::numeric_limits<BoundaryOffset>::max(); 61 62 struct CellData 63 { 64 ValueOffset value_offset = INVALID_VALUE_OFFSET; 65 BoundaryOffset source_boundary_offset = INVALID_BOUNDARY_OFFSET; 66 BoundaryOffset destination_boundary_offset = INVALID_BOUNDARY_OFFSET; 67 BoundarySize num_source_nodes = 0; 68 BoundarySize num_destination_nodes = 0; 69 }; 70 71 private: 72 template <typename T> using Vector = util::ViewOrVector<T, Ownership>; 73 74 // Implementation of the cell view. We need a template parameter here 75 // because we need to derive a read-only and read-write view from this. 76 template <typename WeightValueT, typename DurationValueT, typename DistanceValueT> 77 class CellImpl 78 { 79 private: 80 using WeightPtrT = WeightValueT *; 81 using DurationPtrT = DurationValueT *; 82 using DistancePtrT = DistanceValueT *; 83 BoundarySize num_source_nodes; 84 BoundarySize num_destination_nodes; 85 86 WeightPtrT const weights; 87 DurationPtrT const durations; 88 DistancePtrT const distances; 89 const NodeID *const source_boundary; 90 const NodeID *const destination_boundary; 91 92 using RowIterator = WeightPtrT; 93 // Possibly replace with 94 // http://www.boost.org/doc/libs/1_55_0/libs/range/doc/html/range/reference/adaptors/reference/strided.html 95 96 template <typename ValuePtrT> 97 class ColumnIterator : public boost::iterator_facade<ColumnIterator<ValuePtrT>, 98 decltype(*std::declval<ValuePtrT>()), 99 boost::random_access_traversal_tag> 100 { 101 102 using ValueT = decltype(*std::declval<ValuePtrT>()); 103 typedef boost:: 104 iterator_facade<ColumnIterator<ValueT>, ValueT, boost::random_access_traversal_tag> 105 base_t; 106 107 public: 108 typedef typename base_t::value_type value_type; 109 typedef typename base_t::difference_type difference_type; 110 typedef typename base_t::reference reference; 111 typedef std::random_access_iterator_tag iterator_category; 112 ColumnIterator()113 explicit ColumnIterator() : current(nullptr), stride(1) {} 114 ColumnIterator(ValuePtrT begin,std::size_t row_length)115 explicit ColumnIterator(ValuePtrT begin, std::size_t row_length) 116 : current(begin), stride(row_length) 117 { 118 BOOST_ASSERT(begin != nullptr); 119 } 120 121 private: increment()122 void increment() { current += stride; } decrement()123 void decrement() { current -= stride; } advance(difference_type offset)124 void advance(difference_type offset) { current += stride * offset; } equal(const ColumnIterator & other) const125 bool equal(const ColumnIterator &other) const { return current == other.current; } dereference() const126 reference dereference() const { return *current; } distance_to(const ColumnIterator & other) const127 difference_type distance_to(const ColumnIterator &other) const 128 { 129 return (other.current - current) / static_cast<std::intptr_t>(stride); 130 } 131 132 friend class ::boost::iterator_core_access; 133 ValuePtrT current; 134 const std::size_t stride; 135 }; 136 GetOutRange(const ValuePtr ptr,const NodeID node) const137 template <typename ValuePtr> auto GetOutRange(const ValuePtr ptr, const NodeID node) const 138 { 139 auto iter = std::find(source_boundary, source_boundary + num_source_nodes, node); 140 if (iter == source_boundary + num_source_nodes) 141 return boost::make_iterator_range(ptr, ptr); 142 143 auto row = std::distance(source_boundary, iter); 144 auto begin = ptr + num_destination_nodes * row; 145 auto end = begin + num_destination_nodes; 146 return boost::make_iterator_range(begin, end); 147 } 148 GetInRange(const ValuePtr ptr,const NodeID node) const149 template <typename ValuePtr> auto GetInRange(const ValuePtr ptr, const NodeID node) const 150 { 151 auto iter = 152 std::find(destination_boundary, destination_boundary + num_destination_nodes, node); 153 if (iter == destination_boundary + num_destination_nodes) 154 return boost::make_iterator_range(ColumnIterator<ValuePtr>{}, 155 ColumnIterator<ValuePtr>{}); 156 157 auto column = std::distance(destination_boundary, iter); 158 auto begin = ColumnIterator<ValuePtr>{ptr + column, num_destination_nodes}; 159 auto end = ColumnIterator<ValuePtr>{ 160 ptr + column + num_source_nodes * num_destination_nodes, num_destination_nodes}; 161 return boost::make_iterator_range(begin, end); 162 } 163 164 public: GetOutWeight(NodeID node) const165 auto GetOutWeight(NodeID node) const { return GetOutRange(weights, node); } 166 GetInWeight(NodeID node) const167 auto GetInWeight(NodeID node) const { return GetInRange(weights, node); } 168 GetOutDuration(NodeID node) const169 auto GetOutDuration(NodeID node) const { return GetOutRange(durations, node); } 170 GetInDuration(NodeID node) const171 auto GetInDuration(NodeID node) const { return GetInRange(durations, node); } 172 GetInDistance(NodeID node) const173 auto GetInDistance(NodeID node) const { return GetInRange(distances, node); } 174 GetOutDistance(NodeID node) const175 auto GetOutDistance(NodeID node) const { return GetOutRange(distances, node); } 176 GetSourceNodes() const177 auto GetSourceNodes() const 178 { 179 return boost::make_iterator_range(source_boundary, source_boundary + num_source_nodes); 180 } 181 GetDestinationNodes() const182 auto GetDestinationNodes() const 183 { 184 return boost::make_iterator_range(destination_boundary, 185 destination_boundary + num_destination_nodes); 186 } 187 CellImpl(const CellData & data,WeightPtrT const all_weights,DurationPtrT const all_durations,DistancePtrT const all_distances,const NodeID * const all_sources,const NodeID * const all_destinations)188 CellImpl(const CellData &data, 189 WeightPtrT const all_weights, 190 DurationPtrT const all_durations, 191 DistancePtrT const all_distances, 192 const NodeID *const all_sources, 193 const NodeID *const all_destinations) 194 : num_source_nodes{data.num_source_nodes}, 195 num_destination_nodes{data.num_destination_nodes}, weights{all_weights + 196 data.value_offset}, 197 durations{all_durations + data.value_offset}, distances{all_distances + 198 data.value_offset}, 199 source_boundary{all_sources + data.source_boundary_offset}, 200 destination_boundary{all_destinations + data.destination_boundary_offset} 201 { 202 BOOST_ASSERT(all_weights != nullptr); 203 BOOST_ASSERT(all_durations != nullptr); 204 BOOST_ASSERT(all_distances != nullptr); 205 BOOST_ASSERT(num_source_nodes == 0 || all_sources != nullptr); 206 BOOST_ASSERT(num_destination_nodes == 0 || all_destinations != nullptr); 207 } 208 209 // Consturcts an emptry cell without weights. Useful when only access 210 // to the cell structure is needed, without a concrete metric. CellImpl(const CellData & data,const NodeID * const all_sources,const NodeID * const all_destinations)211 CellImpl(const CellData &data, 212 const NodeID *const all_sources, 213 const NodeID *const all_destinations) 214 : num_source_nodes{data.num_source_nodes}, 215 num_destination_nodes{data.num_destination_nodes}, weights{nullptr}, 216 durations{nullptr}, distances{nullptr}, source_boundary{all_sources + 217 data.source_boundary_offset}, 218 destination_boundary{all_destinations + data.destination_boundary_offset} 219 { 220 BOOST_ASSERT(num_source_nodes == 0 || all_sources != nullptr); 221 BOOST_ASSERT(num_destination_nodes == 0 || all_destinations != nullptr); 222 } 223 }; 224 LevelIDToIndex(LevelID level) const225 std::size_t LevelIDToIndex(LevelID level) const { return level - 1; } 226 227 public: 228 using Cell = CellImpl<EdgeWeight, EdgeDuration, EdgeDistance>; 229 using ConstCell = CellImpl<const EdgeWeight, const EdgeDuration, const EdgeDistance>; 230 CellStorageImpl()231 CellStorageImpl() {} 232 233 template <typename GraphT, 234 typename = std::enable_if<Ownership == storage::Ownership::Container>> CellStorageImpl(const partitioner::MultiLevelPartition & partition,const GraphT & base_graph)235 CellStorageImpl(const partitioner::MultiLevelPartition &partition, const GraphT &base_graph) 236 { 237 // pre-allocate storge for CellData so we can have random access to it by cell id 238 unsigned number_of_cells = 0; 239 for (LevelID level = 1u; level < partition.GetNumberOfLevels(); ++level) 240 { 241 level_to_cell_offset.push_back(number_of_cells); 242 number_of_cells += partition.GetNumberOfCells(level); 243 } 244 level_to_cell_offset.push_back(number_of_cells); 245 cells.resize(number_of_cells); 246 247 std::vector<std::pair<CellID, NodeID>> level_source_boundary; 248 std::vector<std::pair<CellID, NodeID>> level_destination_boundary; 249 250 std::size_t number_of_unconneced = 0; 251 252 for (LevelID level = 1u; level < partition.GetNumberOfLevels(); ++level) 253 { 254 auto level_offset = level_to_cell_offset[LevelIDToIndex(level)]; 255 256 level_source_boundary.clear(); 257 level_destination_boundary.clear(); 258 259 for (auto node = 0u; node < base_graph.GetNumberOfNodes(); ++node) 260 { 261 const CellID cell_id = partition.GetCell(level, node); 262 bool is_source_node = false; 263 bool is_destination_node = false; 264 bool is_boundary_node = false; 265 266 for (auto edge : base_graph.GetAdjacentEdgeRange(node)) 267 { 268 auto other = base_graph.GetTarget(edge); 269 const auto &data = base_graph.GetEdgeData(edge); 270 271 is_boundary_node |= partition.GetCell(level, other) != cell_id; 272 is_source_node |= partition.GetCell(level, other) == cell_id && data.forward; 273 is_destination_node |= 274 partition.GetCell(level, other) == cell_id && data.backward; 275 } 276 277 if (is_boundary_node) 278 { 279 if (is_source_node) 280 level_source_boundary.emplace_back(cell_id, node); 281 if (is_destination_node) 282 level_destination_boundary.emplace_back(cell_id, node); 283 284 // if a node is unconnected we still need to keep it for correctness 285 // this adds it to the destination array to form an "empty" column 286 if (!is_source_node && !is_destination_node) 287 { 288 number_of_unconneced++; 289 util::Log(logWARNING) << "Found unconnected boundary node " << node << "(" 290 << cell_id << ") on level " << (int)level; 291 level_destination_boundary.emplace_back(cell_id, node); 292 } 293 } 294 } 295 296 tbb::parallel_sort(level_source_boundary.begin(), level_source_boundary.end()); 297 tbb::parallel_sort(level_destination_boundary.begin(), 298 level_destination_boundary.end()); 299 300 const auto insert_cell_boundary = [this, level_offset](auto &boundary, 301 auto set_num_nodes_fn, 302 auto set_boundary_offset_fn, 303 auto begin, 304 auto end) { 305 BOOST_ASSERT(std::distance(begin, end) > 0); 306 307 const auto cell_id = begin->first; 308 BOOST_ASSERT(level_offset + cell_id < cells.size()); 309 auto &cell = cells[level_offset + cell_id]; 310 set_num_nodes_fn(cell, std::distance(begin, end)); 311 set_boundary_offset_fn(cell, boundary.size()); 312 313 std::transform(begin, 314 end, 315 std::back_inserter(boundary), 316 [](const auto &cell_and_node) { return cell_and_node.second; }); 317 }; 318 319 util::for_each_range( 320 level_source_boundary.begin(), 321 level_source_boundary.end(), 322 [this, insert_cell_boundary](auto begin, auto end) { 323 insert_cell_boundary( 324 source_boundary, 325 [](auto &cell, auto value) { cell.num_source_nodes = value; }, 326 [](auto &cell, auto value) { cell.source_boundary_offset = value; }, 327 begin, 328 end); 329 }); 330 util::for_each_range( 331 level_destination_boundary.begin(), 332 level_destination_boundary.end(), 333 [this, insert_cell_boundary](auto begin, auto end) { 334 insert_cell_boundary( 335 destination_boundary, 336 [](auto &cell, auto value) { cell.num_destination_nodes = value; }, 337 [](auto &cell, auto value) { cell.destination_boundary_offset = value; }, 338 begin, 339 end); 340 }); 341 } 342 343 // a partition that contains boundary nodes that have no arcs going into 344 // the cells or coming out of it is bad. These nodes should be reassigned 345 // to a different cell. 346 if (number_of_unconneced > 0) 347 { 348 util::Log(logWARNING) << "Node needs to either have incoming or outgoing edges in cell." 349 << " Number of unconnected nodes is " << number_of_unconneced; 350 } 351 352 // Set cell values offsets and calculate total storage size 353 ValueOffset value_offset = 0; 354 for (auto &cell : cells) 355 { 356 cell.value_offset = value_offset; 357 value_offset += cell.num_source_nodes * cell.num_destination_nodes; 358 } 359 } 360 361 // Returns a new metric that can be used with this container MakeMetric() const362 customizer::CellMetric MakeMetric() const 363 { 364 customizer::CellMetric metric; 365 366 if (cells.empty()) 367 { 368 return metric; 369 } 370 371 const auto &last_cell = cells.back(); 372 ValueOffset total_size = 373 last_cell.value_offset + last_cell.num_source_nodes * last_cell.num_destination_nodes; 374 375 metric.weights.resize(total_size + 1, INVALID_EDGE_WEIGHT); 376 metric.durations.resize(total_size + 1, MAXIMAL_EDGE_DURATION); 377 metric.distances.resize(total_size + 1, INVALID_EDGE_DISTANCE); 378 379 return metric; 380 } 381 382 template <typename = std::enable_if<Ownership == storage::Ownership::View>> CellStorageImpl(Vector<NodeID> source_boundary_,Vector<NodeID> destination_boundary_,Vector<CellData> cells_,Vector<std::uint64_t> level_to_cell_offset_)383 CellStorageImpl(Vector<NodeID> source_boundary_, 384 Vector<NodeID> destination_boundary_, 385 Vector<CellData> cells_, 386 Vector<std::uint64_t> level_to_cell_offset_) 387 : source_boundary(std::move(source_boundary_)), 388 destination_boundary(std::move(destination_boundary_)), cells(std::move(cells_)), 389 level_to_cell_offset(std::move(level_to_cell_offset_)) 390 { 391 } 392 GetCell(const customizer::detail::CellMetricImpl<Ownership> & metric,LevelID level,CellID id) const393 ConstCell GetCell(const customizer::detail::CellMetricImpl<Ownership> &metric, 394 LevelID level, 395 CellID id) const 396 { 397 const auto level_index = LevelIDToIndex(level); 398 BOOST_ASSERT(level_index < level_to_cell_offset.size()); 399 const auto offset = level_to_cell_offset[level_index]; 400 const auto cell_index = offset + id; 401 BOOST_ASSERT(cell_index < cells.size()); 402 return ConstCell{cells[cell_index], 403 metric.weights.data(), 404 metric.durations.data(), 405 metric.distances.data(), 406 source_boundary.empty() ? nullptr : source_boundary.data(), 407 destination_boundary.empty() ? nullptr : destination_boundary.data()}; 408 } 409 GetUnfilledCell(LevelID level,CellID id) const410 ConstCell GetUnfilledCell(LevelID level, CellID id) const 411 { 412 const auto level_index = LevelIDToIndex(level); 413 BOOST_ASSERT(level_index < level_to_cell_offset.size()); 414 const auto offset = level_to_cell_offset[level_index]; 415 const auto cell_index = offset + id; 416 BOOST_ASSERT(cell_index < cells.size()); 417 return ConstCell{cells[cell_index], 418 source_boundary.empty() ? nullptr : source_boundary.data(), 419 destination_boundary.empty() ? nullptr : destination_boundary.data()}; 420 } 421 422 template <typename = std::enable_if<Ownership == storage::Ownership::Container>> GetCell(customizer::CellMetric & metric,LevelID level,CellID id) const423 Cell GetCell(customizer::CellMetric &metric, LevelID level, CellID id) const 424 { 425 const auto level_index = LevelIDToIndex(level); 426 BOOST_ASSERT(level_index < level_to_cell_offset.size()); 427 const auto offset = level_to_cell_offset[level_index]; 428 const auto cell_index = offset + id; 429 BOOST_ASSERT(cell_index < cells.size()); 430 return Cell{cells[cell_index], 431 metric.weights.data(), 432 metric.durations.data(), 433 metric.distances.data(), 434 source_boundary.data(), 435 destination_boundary.data()}; 436 } 437 438 friend void serialization::read<Ownership>(storage::tar::FileReader &reader, 439 const std::string &name, 440 detail::CellStorageImpl<Ownership> &storage); 441 friend void serialization::write<Ownership>(storage::tar::FileWriter &writer, 442 const std::string &name, 443 const detail::CellStorageImpl<Ownership> &storage); 444 445 private: 446 Vector<NodeID> source_boundary; 447 Vector<NodeID> destination_boundary; 448 Vector<CellData> cells; 449 Vector<std::uint64_t> level_to_cell_offset; 450 }; 451 } // namespace detail 452 } // namespace partitioner 453 } // namespace osrm 454 455 #endif // OSRM_PARTITIONER_CUSTOMIZE_CELL_STORAGE_HPP 456