From ba305a7ca6f5d380d4cb2ead12c5bed5444b8423 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Mon, 4 Nov 2013 08:34:15 +0100 Subject: Improved comments on topological sort in edif backend --- backends/edif/edif.cc | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'backends') diff --git a/backends/edif/edif.cc b/backends/edif/edif.cc index ced0c8e6..17ae08cc 100644 --- a/backends/edif/edif.cc +++ b/backends/edif/edif.cc @@ -209,16 +209,17 @@ struct EdifBackend : public Backend { module_deps[mod_it.second].insert(design->modules.at(cell_it.second->type)); } - // bubble-sort equivialent to topological sort.. + // simple good-enough topological sort + // (O(n*m) on n elements and depth m) while (module_deps.size() > 0) { size_t sorted_modules_idx = sorted_modules.size(); for (auto &it : module_deps) { for (auto &dep : it.second) if (module_deps.count(dep) > 0) - goto no_ready_yet; + goto not_ready_yet; // log("Next in topological sort: %s\n", RTLIL::id2cstr(it.first->name)); sorted_modules.push_back(it.first); - no_ready_yet:; + not_ready_yet:; } if (sorted_modules_idx == sorted_modules.size()) log_error("Cyclic dependency between modules found! Cycle includes module %s.\n", RTLIL::id2cstr(module_deps.begin()->first->name)); -- cgit v1.2.3