| 315 | /** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */ |
| 316 | template<typename BS> |
| 317 | std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader, bool topological=true) |
| 318 | { |
| 319 | std::vector<DepGraphIndex> linearization; |
| 320 | TestBitSet todo = depgraph.Positions(); |
| 321 | // In every iteration one transaction is appended to linearization. |
| 322 | while (todo.Any()) { |
| 323 | // Compute the set of transactions to select from. |
| 324 | TestBitSet potential_next; |
| 325 | if (topological) { |
| 326 | // Find all transactions with no not-yet-included ancestors. |
| 327 | for (auto j : todo) { |
| 328 | if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) { |
| 329 | potential_next.Set(j); |
| 330 | } |
| 331 | } |
| 332 | } else { |
| 333 | // Allow any element to be selected next, regardless of topology. |
| 334 | potential_next = todo; |
| 335 | } |
| 336 | // There must always be one (otherwise there is a cycle in the graph). |
| 337 | assert(potential_next.Any()); |
| 338 | // Read a number from reader, and interpret it as index into potential_next. |
| 339 | uint64_t idx{0}; |
| 340 | try { |
| 341 | reader >> VARINT(idx); |
| 342 | } catch (const std::ios_base::failure&) {} |
| 343 | idx %= potential_next.Count(); |
| 344 | // Find out which transaction that corresponds to. |
| 345 | for (auto j : potential_next) { |
| 346 | if (idx == 0) { |
| 347 | // When found, add it to linearization and remove it from todo. |
| 348 | linearization.push_back(j); |
| 349 | assert(todo[j]); |
| 350 | todo.Reset(j); |
| 351 | break; |
| 352 | } |
| 353 | --idx; |
| 354 | } |
| 355 | } |
| 356 | return linearization; |
| 357 | } |
| 358 | |
| 359 | /** Given a dependency graph, construct a tree-structured graph. |
| 360 | * |