Как я уже говорил, движок XNE основывается на микроядре. То есть есть ядро, обладающее минимальным функционалом и есть куча модулей, которые уже и реализуют основные функции движка.
Модули находятся на разных уровнях абстракциях. Есть низкоуровневые, а есть высокоуровневые. Поэтому от одних модулей зависят другие, от которых, в свою очередь, зависят третьи. В результате получаем направленный граф. Который должен быть так же и ацикличным.
Что бы правильно загружать и уничтожать модули надо соблюдать строгую последовательность этих операций. При инициализации текущего модуля должны быть проинициализированы все его зависимые модули. При разрушении тоже самое, но в обратной последовательности.
Допустим есть следующие модули: filesystem, logging, render, audio, scene manager, game
filesystem не зависит ни от какого модуля
logging зависит от filesystem
render -> filesystem, logging
audio -> filesystem, logging
scene manager -> filesystem, logging, render, audio
game -> scene manager, filesystem, logging
Тут мы имеем сложный граф зависимостей. Который не является деревом. Этот граф надо преобразовать в список, проходя по которому можно будет последовательно запустить или остановить модули.
Например вот такой: filesystem -> logging -> audio -> render -> scene manager -> game
Хотя различных списков может быть много.
Также надо как-то проверять наличие циклов в графе зависимостей, иначе построить такой список будет невозможно.
Вообщем, я уже почти сам построил нужный алгоритм, как нашёл у себя в сундуке древний манускрипт, называется он "C++ Boost Graph Library", открыв его я узнал, что моя проблема является довольно тривиальной и очень общей. Мне просто надо пройти граф зависимостей по алгоритму depth first search, а построение списков зависимостей является, так называемой, топологической сортировкой. Ну в принципе я тоже самое и придумал, только не знал как называть.
К счастью, в BGL это всё уже реализовано, так что не надо придумывать велосипеды.
Вот небольшой пример кода использования топологической сортировки. При наличии циклов, алгоритм выкинет исключение, которое можно перехватить самому и поругаться.
#include <iostream>
#include <utility>
#include <algorithm>
#include <list>
#include <vector>
#include <boost/graph/vector_as_graph.hpp>
#include <boost/graph/topological_sort.hpp>
using namespace boost;
int main()
{
const char* modules[] = {
"render",
"filesystem",
"scene manager",
"game",
"audio",
"physics"
};
const int nModules = sizeof(modules)/sizeof(char*);
std::vector<std::list<int> > modulesGraph(nModules);
modulesGraph[0].push_back(1); // render -> filesystem
modulesGraph[2].push_back(0); // scene manager -> render
modulesGraph[2].push_back(1); // scene manager -> filesystem
modulesGraph[2].push_back(4); // scene manager -> audio
modulesGraph[2].push_back(5); // scene manager -> physics
modulesGraph[3].push_back(2); // game -> scene manager
modulesGraph[3].push_back(1); // game -> filesystem
modulesGraph[3].push_back(0); // game -> render
modulesGraph[4].push_back(1); // audio -> filesystem
modulesGraph[5].push_back(1); // physics -> filesystem
std::vector<int> modulesOrder;
topological_sort(modulesGraph, std::back_inserter(modulesOrder), vertex_index_map(identity_property_map()));
for (std::vector<int>::iterator it = modulesOrder.begin(); it != modulesOrder.end(); ++it)
std::cout << modules[*it] << std::endl;
return EXIT_SUCCESS;
}Syhi-подсветка кода
#include <utility>
#include <algorithm>
#include <list>
#include <vector>
#include <boost/graph/vector_as_graph.hpp>
#include <boost/graph/topological_sort.hpp>
using namespace boost;
int main()
{
const char* modules[] = {
"render",
"filesystem",
"scene manager",
"game",
"audio",
"physics"
};
const int nModules = sizeof(modules)/sizeof(char*);
std::vector<std::list<int> > modulesGraph(nModules);
modulesGraph[0].push_back(1); // render -> filesystem
modulesGraph[2].push_back(0); // scene manager -> render
modulesGraph[2].push_back(1); // scene manager -> filesystem
modulesGraph[2].push_back(4); // scene manager -> audio
modulesGraph[2].push_back(5); // scene manager -> physics
modulesGraph[3].push_back(2); // game -> scene manager
modulesGraph[3].push_back(1); // game -> filesystem
modulesGraph[3].push_back(0); // game -> render
modulesGraph[4].push_back(1); // audio -> filesystem
modulesGraph[5].push_back(1); // physics -> filesystem
std::vector<int> modulesOrder;
topological_sort(modulesGraph, std::back_inserter(modulesOrder), vertex_index_map(identity_property_map()));
for (std::vector<int>::iterator it = modulesOrder.begin(); it != modulesOrder.end(); ++it)
std::cout << modules[*it] << std::endl;
return EXIT_SUCCESS;
}Syhi-подсветка кода
на выходе получим следующее:
filesystem
render
audio
physics
scene manager
game