diff options
| author | ruki <[email protected]> | 2025-03-21 23:20:56 +0800 |
|---|---|---|
| committer | ruki <[email protected]> | 2025-04-08 15:31:54 +0800 |
| commit | 5d6d739f00f781f91d30ffe93811128b968a151f (patch) | |
| tree | f4ccb7b29110f92d2acdfce97f07a17311f70362 /xmake/core/base/graph.lua | |
| parent | 53d124455837e9afa2c78e41b88f0f973fdf83e7 (diff) | |
improve jobgraph
Diffstat (limited to 'xmake/core/base/graph.lua')
| -rw-r--r-- | xmake/core/base/graph.lua | 28 |
1 files changed, 8 insertions, 20 deletions
diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua index b2d22a3c4..5d4ac1abb 100644 --- a/xmake/core/base/graph.lua +++ b/xmake/core/base/graph.lua @@ -223,28 +223,19 @@ function graph:partial_topo_sort_next(limit) end end - -- return empty batch if queue is empty (all processed or cycle detected) + local node if self._partial_topo_queue:empty() then - -- check if all vertices were processed + -- return empty node if queue is empty (all processed or cycle detected) local processed_count = self._partial_topo_processed:size() self._partial_topo_has_cycle = processed_count ~= #self:vertices() - - -- if this is the first call and we detect a cycle, mark as complete - if processed_count == 0 then - self._partial_topo_in_progress = false - end - return nil, self._partial_topo_has_cycle - end - - -- get one node with zero in-degree - local node - if not self._partial_topo_queue:empty() then + else + -- get one node with zero in-degree node = self._partial_topo_queue:pop() self._partial_topo_processed:insert(node) self._partial_topo_remaining_count = self._partial_topo_remaining_count - 1 - -- update in-degrees based on the nodes in this batch + -- update in-degrees based on the nodes in this node local edges = self:adjacent_edges(node) if edges then for _, e in ipairs(edges) do @@ -256,7 +247,7 @@ function graph:partial_topo_sort_next(limit) if self._partial_topo_in_degree[w] == 0 then self._partial_topo_non_zero_indegree_count = self._partial_topo_non_zero_indegree_count - 1 - -- if in-degree becomes zero, add to queue for next batch + -- if in-degree becomes zero, add to queue for next node if not self._partial_topo_processed:has(w) then self._partial_topo_queue:push(w) end @@ -271,13 +262,10 @@ function graph:partial_topo_sort_next(limit) return node, true end - -- if queue is now empty and all vertices processed, reset state + -- if queue is empty but we still have unprocessed nodes, we have a cycle if self._partial_topo_queue:empty() then local processed_count = self._partial_topo_processed:size() - if processed_count == #self:vertices() then - self._partial_topo_in_progress = false - else - -- if queue is empty but we still have unprocessed nodes, we have a cycle + if processed_count ~= #self:vertices() then self._partial_topo_has_cycle = true end end |