c45f9b7155
Fix a bug where std::same_as<...> constraint was incorrectly used as a simple requirement instead of a nested requirement or part of a conjunction. This caused the constraint to be always satisfied regardless of the actual types involved. This change promotes std::same_as<...> to a top-level constraint, ensuring proper type checking while improving code readability. Signed-off-by: Kefu Chai <kefu.chai@scylladb.com> Closes scylladb/scylladb#23068
78 lines
2.3 KiB
C++
78 lines
2.3 KiB
C++
/*
|
|
* Copyright (C) 2024-present ScyllaDB
|
|
*/
|
|
|
|
/*
|
|
* SPDX-License-Identifier: LicenseRef-ScyllaDB-Source-Available-1.0
|
|
*/
|
|
|
|
#pragma once
|
|
|
|
#include <stdexcept>
|
|
#include <vector>
|
|
#include <map>
|
|
#include <seastar/core/future.hh>
|
|
#include <seastar/coroutine/maybe_yield.hh>
|
|
#include "utils/stall_free.hh"
|
|
|
|
namespace utils {
|
|
|
|
template <typename Container, typename T>
|
|
concept VerticiesContainer = requires(const Container& c) {
|
|
c.begin();
|
|
c.end();
|
|
c.size();
|
|
} && std::same_as<typename Container::value_type, T>;
|
|
|
|
/**
|
|
* Topological sort a DAG using Kahn's algorithm.
|
|
*
|
|
* @param vertices Contains all vertices of the graph
|
|
* @param adjacency_map Entry {k, v} means there is an k->v edge in the graph
|
|
* @return a vector of topologically sorted vertices.
|
|
If there is an edge k->v, then vertex k will be before vertex v.
|
|
* @throws std::runtime_error when a graph has any cycle.
|
|
*/
|
|
template<typename T, typename Compare = std::less<T>, typename Container>
|
|
requires VerticiesContainer<Container, T>
|
|
seastar::future<std::vector<T>> topological_sort(const Container& vertices, const std::multimap<T, T, Compare>& adjacency_map) {
|
|
std::map<T, size_t, Compare> ref_count_map; // Contains counters how many edges point (reference) to a vertex
|
|
std::vector<T> sorted;
|
|
sorted.reserve(vertices.size());
|
|
|
|
for (auto& edge: adjacency_map) {
|
|
ref_count_map[edge.second]++;
|
|
}
|
|
|
|
// Push to result vertices which reference counter == 0
|
|
for (auto& v: vertices) {
|
|
if (!ref_count_map.contains(v)) {
|
|
sorted.emplace_back(v);
|
|
}
|
|
}
|
|
|
|
// Iterate over already sorted vertices,
|
|
// decrease counter of vertices to which sorted vertices points,
|
|
// push to the end of `sorted` vector vertices which counter == 0.
|
|
for (size_t i = 0; i < sorted.size(); i++) {
|
|
auto [it_begin, it_end] = adjacency_map.equal_range(sorted[i]);
|
|
|
|
while (it_begin != it_end) {
|
|
auto d = it_begin->second;
|
|
if (--ref_count_map[d] == 0) {
|
|
sorted.push_back(d);
|
|
}
|
|
++it_begin;
|
|
}
|
|
co_await seastar::coroutine::maybe_yield();
|
|
}
|
|
co_await utils::clear_gently(ref_count_map);
|
|
|
|
if (sorted.size() != vertices.size()) {
|
|
throw std::runtime_error("Detected cycle in the graph.");
|
|
}
|
|
co_return sorted;
|
|
}
|
|
|
|
}
|