X-Git-Url: http://git.tdb.fi/?a=blobdiff_plain;f=source%2Fgame%2Fsystemscheduler.cpp;fp=source%2Fgame%2Fsystemscheduler.cpp;h=d6fb9a55e6b0f80b2984b15ab55c0693622a9669;hb=e4f03880d49bdbe0c7269be0f40f23b197bcea77;hp=0000000000000000000000000000000000000000;hpb=423b49f2857f8e1597b652bfd41dbf3ae45f7ec5;p=libs%2Fgame.git

diff --git a/source/game/systemscheduler.cpp b/source/game/systemscheduler.cpp
new file mode 100644
index 0000000..d6fb9a5
--- /dev/null
+++ b/source/game/systemscheduler.cpp
@@ -0,0 +1,154 @@
+#include "systemscheduler.h"
+#include <limits>
+#include <msp/core/algorithm.h>
+#include <msp/strings/format.h>
+#include "system.h"
+
+using namespace std;
+
+namespace Msp::Game {
+
+SystemScheduler::SystemScheduler(Reflection::Reflector &r):
+	reflector(r)
+{ }
+
+void SystemScheduler::add_system(System &s)
+{
+	nodes.emplace_back(&s, reflector.find_class(typeid(s)));
+}
+
+void SystemScheduler::remove_system(System &s)
+{
+	erase_if(nodes, [&s](const GraphNode &n){ return n.system==&s; });
+	for(auto i=groups.begin(); i!=groups.end(); )
+	{
+		erase_if(i->systems, [&s](System *gs){ return gs==&s; });
+		if(i->systems.empty())
+			i = groups.erase(i);
+		else
+			++i;
+	}
+}
+
+void SystemScheduler::schedule()
+{
+	for(GraphNode &n: nodes)
+	{
+		n.scheduled_order = ~0U;
+		n.predecessors.clear();
+	}
+
+	for(auto i=nodes.begin(); i!=nodes.end(); ++i)
+		for(auto j=i; ++j!=nodes.end(); )
+		{
+			int order = get_order(*i, *j);
+			if(order<0)
+				j->predecessors.push_back(&*i);
+			else if(order>0)
+				i->predecessors.push_back(&*j);
+		}
+
+	groups.clear();
+	unsigned unscheduled_count = nodes.size();
+	while(unscheduled_count)
+	{
+		unsigned order = groups.size();
+		Group &group = groups.emplace_back();
+		for(GraphNode &n: nodes)
+			if(!~n.scheduled_order && ranges::all_of(n.predecessors, [order](GraphNode *p){ return p->scheduled_order<order; }))
+			{
+				group.systems.push_back(n.system);
+				n.scheduled_order = order;
+				--unscheduled_count;
+			}
+	}
+}
+
+int SystemScheduler::get_order(const GraphNode &node1, const GraphNode &node2)
+{
+	if(int order = get_explicit_order(node1, node2))
+		return order;
+	return get_data_order(node1, node2);
+}
+
+int SystemScheduler::get_explicit_order(const GraphNode &node1, const GraphNode &node2)
+{
+	const vector<System::Dependency> &deps1 = node1.system->get_dependencies();
+	const vector<System::Dependency> &deps2 = node2.system->get_dependencies();
+
+	auto get_dep_type = [](const System::Dependency &d){ return &d.get_type(); };
+	auto i = ranges::find(deps1, node2.type, get_dep_type);
+	int flags1 = (i!=deps1.end() ? i->get_flags()&System::ORDER_MASK : 0);
+	i = ranges::find(deps2, node1.type, get_dep_type);
+	int flags2 = (i!=deps2.end() ? i->get_flags()&System::ORDER_MASK : 0);
+	if(flags1&flags2)
+		throw scheduling_error(format("Conflicting ordering between %s and %s", node1.type->get_name(), node2.type->get_name()));
+	else if(flags1==System::RUN_BEFORE || flags2==System::RUN_AFTER)
+		return -1;
+	else if(flags1==System::RUN_AFTER || flags2==System::RUN_BEFORE)
+		return 1;
+	else
+		return 0;
+}
+
+int SystemScheduler::get_data_order(const GraphNode &node1, const GraphNode &node2)
+{
+	int data_order = 0;
+	const Reflection::ClassBase *ordered_data = nullptr;
+	const Reflection::ClassBase *unordered_data = nullptr;
+	for(const System::Dependency &d1: node1.system->get_dependencies())
+	{
+		int flags1 = d1.get_flags()&System::DATA_MASK;
+		if(!flags1)
+			continue;
+
+		for(const System::Dependency &d2: node2.system->get_dependencies())
+		{
+			int flags2 = d2.get_flags()&System::DATA_MASK;
+			if(!flags2)
+				continue;
+
+			const Reflection::ClassBase *common_type = nullptr;
+			if(&d1.get_type()==&d2.get_type() || d1.get_type().is_base_of(d2.get_type()))
+				common_type = &d1.get_type();
+			else if(d2.get_type().is_base_of(d1.get_type()))
+				common_type = &d2.get_type();
+			else
+				continue;
+
+			int order = 0;
+			// Read-only access to old data always comes first
+			if(flags1==System::READ_OLD)
+				order = -1;
+			else if(flags2==System::READ_OLD)
+				order = 1;
+			// Read-only access to fresh data always comes last
+			else if(flags1==System::READ_FRESH)
+				order = 1;
+			else if(flags2==System::READ_FRESH)
+				order = -1;
+			// Chained updates always come after non-chained writes
+			else if(flags1==System::CHAINED_UPDATE && (flags2==System::WRITE || flags2==System::UPDATE))
+				order = 1;
+			else if(flags2==System::CHAINED_UPDATE && (flags1==System::WRITE || flags1==System::UPDATE))
+				order = -1;
+			else
+				unordered_data = common_type;
+
+			if(order && data_order && order!=data_order)
+				throw scheduling_error(format("Ambiguous data ordering between %s and %s, accessing %s and %s",
+					node1.type->get_name(), node2.type->get_name(), ordered_data->get_name(), common_type->get_name()));
+
+			data_order = order;
+			ordered_data = common_type;
+		}
+	}
+
+	if(!data_order && unordered_data)
+		throw scheduling_error(format("Ambiguous data ordering between %s and %s, accessing %s",
+			node1.type->get_name(), node2.type->get_name(), unordered_data->get_name()));
+
+	return data_order;
+}
+
+} // namespace Msp::Game