Files F3995331

versions-algorithm-data_dependency.cpp
No OneTemporary
Actions

File Metadata

Created
Tue, Jul 7, 3:38 AM

versions-algorithm-data_dependency.cpp
View Options

/*
* File: algorithm-data_dependency
* Date: Dec 23, 2016
* Author: pgess <v.melnychenko@xreate.org>
*/
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <map>
#include "gtest/gtest.h"
#include <initializer_list>
#include <cstdio>
const int V_NOVERSION = -2;
const int V_ENDOFLIFE = -1;
struct Symbol {
std::string name;
int version;
Symbol getNextVersion() const{
return Symbol{name, version+1};
}
};
namespace std
{
template<>
struct hash<Symbol>
{
typedef Symbol argument_type;
typedef std::size_t result_type;
result_type operator()(argument_type const& s) const
{
result_type const h1 ( std::hash<std::string>()(s.name) );
return h1 ^ (s.version << 1); // or use boost::hash_combine
}
};
template<>
struct equal_to<Symbol>
{
typedef Symbol argument_type;
bool operator()(const argument_type& __x, const argument_type& __y) const
{ return __x.name == __y.name && __x.version == __y.version; }
};
}
//Ограничения:
// - точно знаем следующую версию на этапе декл. (C.NV.1)
class DDSolver{
public:
void l1_applyLowerBound(const Symbol& left, const std::initializer_list<Symbol>& dependencies){
for (Symbol right: dependencies){
//lower bound:
__infs.emplace(left, right);
__sups.emplace(right, left);
}
}
void l1_applyOwnUpperBound(const Symbol& left){
//own upper bound:
//C.NV.1
__infs.emplace(left.getNextVersion(), left);
__sups.emplace(left, left.getNextVersion());
}
void l1_applyDependentUpperBound(const Symbol& left, const std::initializer_list<Symbol>& dependencies){
// additionally apply dependent upper bound
for (Symbol right: dependencies){
auto right2 = right.getNextVersion();
__infs.emplace(right2, left);
__sups.emplace(left, right2);
}
}
void addVariable(const Symbol& left, const std::initializer_list<Symbol>& dependencies){
l1_applyLowerBound(left, dependencies);
l1_applyOwnUpperBound(left);
//initialization upper bound
l1_applyDependentUpperBound(left, dependencies);
}
//TODO assert: only aliases allowed
void addAlias(const Symbol& left, const std::initializer_list<Symbol>& dependencies){
l1_applyLowerBound(left, dependencies);
l1_applyOwnUpperBound(left);
//lifetime upper bound
l1_applyDependentUpperBound(left.getNextVersion(), dependencies);
}
bool checkCyclicComponent(const Symbol& s, std::unordered_set<Symbol>& symbolsVisited, std::unordered_set<Symbol>& symbolsSups){
if (symbolsVisited.count(s)) return false;
symbolsVisited.insert(s);
symbolsSups.insert(s);
auto rangeInf = __infs.equal_range(s);
if (__infs.count(s))
for (auto sInf = rangeInf.first; sInf != rangeInf.second; ++sInf){
if (symbolsSups.count(sInf->second)) {
__flagCycle = std::make_pair(sInf->second, s);
return true;
}
if(checkCyclicComponent(sInf->second, symbolsVisited, symbolsSups)) return true;
}
symbolsSups.erase(s);
return false;
}
bool checkCyclicFull(){
std::unordered_set<Symbol> symbolsVisited, symbolsSups;
std::unordered_multimap<Symbol, Symbol>::iterator s;
for (s = __infs.begin(); s != __infs.end(); ++s){
if(checkCyclicComponent(s->first, symbolsVisited, symbolsSups)) return true;
}
return false;
}
bool validate(){
return !checkCyclicFull();
}
void solve(){
std::unordered_set<Symbol> binEnabled, binFrontier;
//seed
for (auto edge: __sups){
if (! __infs.count(edge.first)){
binEnabled.insert(edge.first);
binFrontier.insert(edge.first);
}
}
while (binFrontier.size()){
const Symbol& node= *binFrontier.begin();
//print node:
std:: printf("put (%s, %d)\n", node.name.c_str(), node.version);
auto rangeSups = __sups.equal_range(node);
for(auto sup=rangeSups.first; sup != rangeSups.second; ++sup){
bool flagEnabled = true;
auto rangeInfs = __infs.equal_range(sup->second);
for (auto inf=rangeInfs.first; inf != rangeInfs.second; ++inf){
if (!binEnabled.count(inf->second)){
flagEnabled = false;
break;
}
}
if (flagEnabled){
binEnabled.insert(sup->second);
binFrontier.insert(sup->second);
}
}
binFrontier.erase(node);
}
}
void solve2(Symbol nodeEntry, std::unordered_set<Symbol>& binPreviousNodes, std::unordered_set<Symbol>& binEnabledNodes){
binPreviousNodes.insert(nodeEntry);
auto rangeChilds = __infs.equal_range(nodeEntry);
for(auto node=rangeChilds.first; node != rangeChilds.second; ++node){
if (binEnabledNodes.count(node->second)) continue;
auto nodeError = binPreviousNodes.find(node->second);
if (nodeError != binPreviousNodes.end()){
std:: printf("(%s, %d) - (%s, %d)",
nodeError->name.c_str(), nodeError->version,
node->second.name.c_str(), node->second.version);
assert(false);
}
solve2(node->second, binPreviousNodes, binEnabledNodes);
}
std:: printf("put (%s, %d)\n", nodeEntry.name.c_str(), nodeEntry.version);
binEnabledNodes.insert(nodeEntry);
binPreviousNodes.erase(nodeEntry);
// auto rangeParents = __sups.equal_range(nodeEntry);
// for(auto node=rangeParents.first; node != rangeParents.second; ++node){
// std::unordered_set<Symbol> binEmpty;
// solve2(node->second, binEmpty, binEnabledNodes);
// }
}
void __debug_printGraph(){
for (auto edge: __infs){
std:: printf("(%s, %d) <- (%s, %d) \n",
edge.second.name.c_str(), edge.second.version,
edge.first.name.c_str(), edge.first.version);
}
}
private:
std::unordered_multimap<Symbol, Symbol> __sups;
std::unordered_multimap<Symbol, Symbol> __infs;
public:
std::pair<Symbol, Symbol> __flagCycle;
};
TEST(Datadependency, test1){
DDSolver solver;
solver.addAlias(Symbol{"c", V_NOVERSION}, {Symbol{"a", 0}});
solver.addVariable(Symbol{"a", 1}, {Symbol{"b", 0}});
solver.addVariable(Symbol{"b", 1}, {Symbol{"c", V_NOVERSION}});
solver.__debug_printGraph();
ASSERT_FALSE(solver.validate());
std:: printf("(%s, %d) - (%s, %d)",
solver.__flagCycle.first.name.c_str(), solver.__flagCycle.first.version,
solver.__flagCycle.second.name.c_str(), solver.__flagCycle.second.version);
}
TEST(Datadependency, test2){
DDSolver solver;
solver.addVariable(Symbol{"c", V_NOVERSION}, {Symbol{"a", 0}});
solver.addVariable(Symbol{"a", 1}, {Symbol{"b", 0}});
solver.addVariable(Symbol{"b", 1}, {Symbol{"c", V_NOVERSION}});
ASSERT_TRUE(solver.validate());
solver.solve();
}
TEST(Datadependency, test3){
DDSolver solver;
solver.addVariable(Symbol{"c", V_NOVERSION}, {Symbol{"a", 0}});
solver.addVariable(Symbol{"a", 1}, {Symbol{"b", 0}});
solver.addVariable(Symbol{"b", 1}, {Symbol{"c", V_NOVERSION}});
std::unordered_set<Symbol> binPreviousNodes, binEnabledNodes;
solver.solve2(Symbol{"b", 1}, binPreviousNodes, binEnabledNodes);
ASSERT_TRUE(true);
}
TEST(Datadependency, test4){
DDSolver solver;
solver.addVariable(Symbol{"c", V_NOVERSION}, {Symbol{"a", 0}});
solver.addVariable(Symbol{"a", 1}, {Symbol{"b", 0}});
solver.addVariable(Symbol{"b", 1}, {Symbol{"c", V_NOVERSION}});
std::unordered_set<Symbol> binPreviousNodes, binEnabledNodes;
solver.solve2(Symbol{"b", 1}, binPreviousNodes, binEnabledNodes);
ASSERT_TRUE(true);
}
TEST(Datadependency, test5){
DDSolver solver;
solver.addAlias(Symbol{"b", V_NOVERSION}, {Symbol{"a", 0}});
solver.addVariable(Symbol{"a", 1}, {Symbol{"b", V_NOVERSION}});
std:: printf("(%s, %d) - (%s, %d)",
solver.__flagCycle.first.name.c_str(), solver.__flagCycle.first.version,
solver.__flagCycle.second.name.c_str(), solver.__flagCycle.second.version);
ASSERT_TRUE(solver.validate());
}
TEST(Datadependency, test6){
DDSolver solver;
solver.addVariable(Symbol{"a", 1}, {Symbol{"a", 0}});
std::unordered_set<Symbol> binPreviousNodes, binEnabledNodes;
solver.solve2(Symbol{"a", 1}, binPreviousNodes, binEnabledNodes);
ASSERT_TRUE(solver.validate());
}

Event Timeline

Email: pr.h7@xreate.org · 2019 Xreate.org · Powered by Phabricator