1 #ifndef OSRM_PARTITIONER_MULTI_LEVEL_PARTITION_HPP
2 #define OSRM_PARTITIONER_MULTI_LEVEL_PARTITION_HPP
3
4 #include "util/exception.hpp"
5 #include "util/for_each_pair.hpp"
6 #include "util/msb.hpp"
7 #include "util/typedefs.hpp"
8 #include "util/vector_view.hpp"
9
10 #include "storage/shared_memory_ownership.hpp"
11 #include "storage/tar_fwd.hpp"
12
13 #include <algorithm>
14 #include <array>
15 #include <climits>
16 #include <cmath>
17 #include <cstdint>
18 #include <numeric>
19 #include <vector>
20
21 #include <boost/range/adaptor/reversed.hpp>
22
23 namespace osrm
24 {
25 namespace partitioner
26 {
27 namespace detail
28 {
29 template <storage::Ownership Ownership> class MultiLevelPartitionImpl;
30 }
31 using MultiLevelPartition = detail::MultiLevelPartitionImpl<storage::Ownership::Container>;
32 using MultiLevelPartitionView = detail::MultiLevelPartitionImpl<storage::Ownership::View>;
33
34 namespace serialization
35 {
36 template <storage::Ownership Ownership>
37 void read(storage::tar::FileReader &reader,
38 const std::string &name,
39 detail::MultiLevelPartitionImpl<Ownership> &mlp);
40 template <storage::Ownership Ownership>
41 void write(storage::tar::FileWriter &writer,
42 const std::string &name,
43 const detail::MultiLevelPartitionImpl<Ownership> &mlp);
44 } // namespace serialization
45
46 namespace detail
47 {
48
49 template <storage::Ownership Ownership> class MultiLevelPartitionImpl final
50 {
51 // we will support at most 16 levels
52 static const constexpr std::uint8_t MAX_NUM_LEVEL = 16;
53 static const constexpr std::uint8_t NUM_PARTITION_BITS = sizeof(PartitionID) * CHAR_BIT;
54
55 template <typename T> using Vector = util::ViewOrVector<T, Ownership>;
56
57 public:
58 // Contains all data necessary to describe the level hierarchy
59 struct LevelData
60 {
61
62 std::uint32_t num_level;
63 std::array<std::uint8_t, MAX_NUM_LEVEL - 1> lidx_to_offset;
64 std::array<PartitionID, MAX_NUM_LEVEL - 1> lidx_to_mask;
65 std::array<LevelID, NUM_PARTITION_BITS> bit_to_level;
66 std::array<std::uint32_t, MAX_NUM_LEVEL - 1> lidx_to_children_offsets;
67 };
68 using LevelDataPtr = typename std::conditional<Ownership == storage::Ownership::View,
69 LevelData *,
70 std::unique_ptr<LevelData>>::type;
71
72 MultiLevelPartitionImpl();
73
74 // cell_sizes is index by level (starting at 0, the base graph).
75 // However level 0 always needs to have cell size 1, since it is the
76 // basegraph.
77 template <typename = typename std::enable_if<Ownership == storage::Ownership::Container>>
MultiLevelPartitionImpl(const std::vector<std::vector<CellID>> & partitions,const std::vector<std::uint32_t> & lidx_to_num_cells)78 MultiLevelPartitionImpl(const std::vector<std::vector<CellID>> &partitions,
79 const std::vector<std::uint32_t> &lidx_to_num_cells)
80 : level_data(MakeLevelData(lidx_to_num_cells))
81 {
82 InitializePartitionIDs(partitions);
83 }
84
85 template <typename = typename std::enable_if<Ownership == storage::Ownership::View>>
MultiLevelPartitionImpl(LevelDataPtr level_data,Vector<PartitionID> partition_,Vector<CellID> cell_to_children_)86 MultiLevelPartitionImpl(LevelDataPtr level_data,
87 Vector<PartitionID> partition_,
88 Vector<CellID> cell_to_children_)
89 : level_data(std::move(level_data)), partition(std::move(partition_)),
90 cell_to_children(std::move(cell_to_children_))
91 {
92 }
93
94 // returns the index of the cell the vertex is contained at level l
GetCell(LevelID l,NodeID node) const95 CellID GetCell(LevelID l, NodeID node) const
96 {
97 auto p = partition[node];
98 auto lidx = LevelIDToIndex(l);
99 auto masked = p & level_data->lidx_to_mask[lidx];
100 return masked >> level_data->lidx_to_offset[lidx];
101 }
102
GetQueryLevel(NodeID start,NodeID target,NodeID node) const103 LevelID GetQueryLevel(NodeID start, NodeID target, NodeID node) const
104 {
105 return std::min(GetHighestDifferentLevel(start, node),
106 GetHighestDifferentLevel(target, node));
107 }
108
GetHighestDifferentLevel(NodeID first,NodeID second) const109 LevelID GetHighestDifferentLevel(NodeID first, NodeID second) const
110 {
111 if (partition[first] == partition[second])
112 return 0;
113
114 auto msb = util::msb(partition[first] ^ partition[second]);
115 return level_data->bit_to_level[msb];
116 }
117
GetNumberOfLevels() const118 std::uint8_t GetNumberOfLevels() const { return level_data->num_level; }
119
GetNumberOfCells(LevelID level) const120 std::uint32_t GetNumberOfCells(LevelID level) const
121 {
122 return GetCell(level, GetSentinelNode());
123 }
124
125 // Returns the lowest cell id (at `level - 1`) of all children `cell` at `level`
BeginChildren(LevelID level,CellID cell) const126 CellID BeginChildren(LevelID level, CellID cell) const
127 {
128 BOOST_ASSERT(level > 1);
129 auto lidx = LevelIDToIndex(level);
130 auto offset = level_data->lidx_to_children_offsets[lidx];
131 return cell_to_children[offset + cell];
132 }
133
134 // Returns the highest cell id (at `level - 1`) of all children `cell` at `level`
EndChildren(LevelID level,CellID cell) const135 CellID EndChildren(LevelID level, CellID cell) const
136 {
137 BOOST_ASSERT(level > 1);
138 auto lidx = LevelIDToIndex(level);
139 auto offset = level_data->lidx_to_children_offsets[lidx];
140 return cell_to_children[offset + cell + 1];
141 }
142
143 friend void serialization::read<Ownership>(storage::tar::FileReader &reader,
144 const std::string &name,
145 MultiLevelPartitionImpl &mlp);
146 friend void serialization::write<Ownership>(storage::tar::FileWriter &writer,
147 const std::string &name,
148 const MultiLevelPartitionImpl &mlp);
149
150 private:
MakeLevelData(const std::vector<std::uint32_t> & lidx_to_num_cells)151 auto MakeLevelData(const std::vector<std::uint32_t> &lidx_to_num_cells)
152 {
153 std::uint32_t num_level = lidx_to_num_cells.size() + 1;
154 auto offsets = MakeLevelOffsets(lidx_to_num_cells);
155 auto masks = MakeLevelMasks(offsets, num_level);
156 auto bits = MakeBitToLevel(offsets, num_level);
157 return std::make_unique<LevelData>(LevelData{num_level, offsets, masks, bits, {{0}}});
158 }
159
LevelIDToIndex(LevelID l) const160 inline std::size_t LevelIDToIndex(LevelID l) const { return l - 1; }
161
162 // We save the sentinel as last node in the partition information.
163 // It has the highest cell id in each level so we can derived the range
164 // of cell ids efficiently.
GetSentinelNode() const165 inline NodeID GetSentinelNode() const { return partition.size() - 1; }
166
SetCellID(LevelID l,NodeID node,CellID cell_id)167 void SetCellID(LevelID l, NodeID node, CellID cell_id)
168 {
169 auto lidx = LevelIDToIndex(l);
170
171 auto shifted_id = static_cast<std::uint64_t>(cell_id) << level_data->lidx_to_offset[lidx];
172 auto cleared_cell = partition[node] & ~level_data->lidx_to_mask[lidx];
173 partition[node] = cleared_cell | shifted_id;
174 }
175
176 // If we have N cells per level we need log_2 bits for every cell ID
MakeLevelOffsets(const std::vector<std::uint32_t> & lidx_to_num_cells) const177 auto MakeLevelOffsets(const std::vector<std::uint32_t> &lidx_to_num_cells) const
178 {
179 std::array<std::uint8_t, MAX_NUM_LEVEL - 1> offsets;
180
181 auto lidx = 0UL;
182 auto sum_bits = 0;
183 for (auto num_cells : lidx_to_num_cells)
184 {
185 // bits needed to number all contained vertexes
186 auto bits = static_cast<std::uint64_t>(std::ceil(std::log2(num_cells + 1)));
187 offsets[lidx++] = sum_bits;
188 sum_bits += bits;
189 if (sum_bits > NUM_PARTITION_BITS)
190 {
191 throw util::exception(
192 "Can't pack the partition information at level " + std::to_string(lidx) +
193 " into a " + std::to_string(NUM_PARTITION_BITS) +
194 "bit integer. Would require " + std::to_string(sum_bits) + " bits.");
195 }
196 }
197 // sentinel
198 offsets[lidx++] = sum_bits;
199 BOOST_ASSERT(lidx < MAX_NUM_LEVEL);
200
201 return offsets;
202 }
203
MakeLevelMasks(const std::array<std::uint8_t,MAX_NUM_LEVEL-1> & level_offsets,std::uint32_t num_level) const204 auto MakeLevelMasks(const std::array<std::uint8_t, MAX_NUM_LEVEL - 1> &level_offsets,
205 std::uint32_t num_level) const
206 {
207 std::array<PartitionID, MAX_NUM_LEVEL - 1> masks;
208
209 auto lidx = 0UL;
210 util::for_each_pair(level_offsets.begin(),
211 level_offsets.begin() + num_level,
212 [&](const auto offset, const auto next_offset) {
213 // create mask that has `bits` ones at its LSBs.
214 // 000011
215 BOOST_ASSERT(offset <= NUM_PARTITION_BITS);
216 PartitionID mask = (1ULL << offset) - 1ULL;
217 // 001111
218 BOOST_ASSERT(next_offset <= NUM_PARTITION_BITS);
219 // Check offset for shift overflow. Offsets are strictly increasing,
220 // so we only need the check on the last mask.
221 PartitionID next_mask = next_offset == NUM_PARTITION_BITS
222 ? -1ULL
223 : (1ULL << next_offset) - 1ULL;
224 // 001100
225 masks[lidx++] = next_mask ^ mask;
226 });
227
228 return masks;
229 }
230
MakeBitToLevel(const std::array<std::uint8_t,MAX_NUM_LEVEL-1> & level_offsets,std::uint32_t num_level) const231 auto MakeBitToLevel(const std::array<std::uint8_t, MAX_NUM_LEVEL - 1> &level_offsets,
232 std::uint32_t num_level) const
233 {
234 std::array<LevelID, NUM_PARTITION_BITS> bit_to_level;
235
236 for (auto l = 1u; l < num_level; ++l)
237 {
238 auto bits = level_offsets[l - 1];
239 // set all bits to point to the correct level.
240 for (auto idx = bits; idx < NUM_PARTITION_BITS; ++idx)
241 {
242 bit_to_level[idx] = l;
243 }
244 }
245
246 return bit_to_level;
247 }
248
InitializePartitionIDs(const std::vector<std::vector<CellID>> & partitions)249 void InitializePartitionIDs(const std::vector<std::vector<CellID>> &partitions)
250 {
251 auto num_nodes = partitions.front().size();
252 std::vector<NodeID> permutation(num_nodes);
253 std::iota(permutation.begin(), permutation.end(), 0);
254 // We include a sentinel element at the end of the partition
255 partition.resize(num_nodes + 1, 0);
256 NodeID sentinel = num_nodes;
257
258 // Sort nodes bottum-up by cell id.
259 // This ensures that we get a nice grouping from parent to child cells:
260 //
261 // intitial:
262 // level 0: 0 1 2 3 4 5
263 // level 1: 2 1 3 4 3 4
264 // level 2: 2 2 0 1 0 1
265 //
266 // first round:
267 // level 0: 1 0 2 4 3 5
268 // level 1: 1 2 3 3 4 4 (< sorted)
269 // level 2: 2 2 0 0 1 1
270 //
271 // second round:
272 // level 0: 2 4 3 5 1 0
273 // level 1: 3 3 4 4 1 2
274 // level 2: 0 0 1 1 2 2 (< sorted)
275 for (const auto &partition : partitions)
276 {
277 std::stable_sort(permutation.begin(),
278 permutation.end(),
279 [&partition](const auto lhs, const auto rhs) {
280 return partition[lhs] < partition[rhs];
281 });
282 }
283
284 // top down assign new cell ids
285 LevelID level = partitions.size();
286 for (const auto &partition : boost::adaptors::reverse(partitions))
287 {
288 BOOST_ASSERT(permutation.size() > 0);
289 CellID last_cell_id = partition[permutation.front()];
290 CellID cell_id = 0;
291 for (const auto node : permutation)
292 {
293 if (last_cell_id != partition[node])
294 {
295 cell_id++;
296 last_cell_id = partition[node];
297 }
298 SetCellID(level, node, cell_id);
299 }
300 // Store the number of cells of the level in the sentinel
301 SetCellID(level, sentinel, cell_id + 1);
302 level--;
303 }
304
305 level_data->lidx_to_children_offsets[0] = 0;
306
307 for (auto level_idx = 0UL; level_idx < partitions.size() - 1; ++level_idx)
308 {
309 const auto &parent_partition = partitions[level_idx + 1];
310
311 level_data->lidx_to_children_offsets[level_idx + 1] = cell_to_children.size();
312
313 CellID last_parent_id = parent_partition[permutation.front()];
314 cell_to_children.push_back(GetCell(level_idx + 1, permutation.front()));
315 for (const auto node : permutation)
316 {
317 if (last_parent_id != parent_partition[node])
318 {
319 // Note: we use the new cell id here, not the ones contained
320 // in the input partition
321 cell_to_children.push_back(GetCell(level_idx + 1, node));
322 last_parent_id = parent_partition[node];
323 }
324 }
325 // insert sentinel for the last cell
326 cell_to_children.push_back(GetCell(level_idx + 1, permutation.back()) + 1);
327 }
328 }
329
330 LevelDataPtr level_data = {};
331 Vector<PartitionID> partition;
332 Vector<CellID> cell_to_children;
333 };
334
335 template <>
MultiLevelPartitionImpl()336 inline MultiLevelPartitionImpl<storage::Ownership::Container>::MultiLevelPartitionImpl()
337 : level_data(std::make_unique<LevelData>())
338 {
339 }
340
341 template <>
MultiLevelPartitionImpl()342 inline MultiLevelPartitionImpl<storage::Ownership::View>::MultiLevelPartitionImpl()
343 : level_data(nullptr)
344 {
345 }
346 } // namespace detail
347 } // namespace partitioner
348 } // namespace osrm
349
350 #endif
351