From 4b73b70e0c569e1ff9592c2c3b717c58356e58e6 Mon Sep 17 00:00:00 2001 From: Hamed Date: Wed, 9 Aug 2017 02:29:54 -0700 Subject: [PATCH] Building a graph for each order --- src/Collections/structs.c | 14 ++++- src/Collections/structs.h | 3 ++ src/Encoders/orderencoder.c | 93 ++++++++++++++++++++++++++++++++ src/Encoders/orderencoder.h | 39 ++++++++++++++ src/Encoders/ordergraph.c | 2 - src/Encoders/ordergraphbuilder.c | 21 -------- src/Encoders/ordergraphbuilder.h | 15 ------ src/classlist.h | 6 +++ 8 files changed, 154 insertions(+), 39 deletions(-) create mode 100644 src/Encoders/orderencoder.c create mode 100644 src/Encoders/orderencoder.h delete mode 100644 src/Encoders/ordergraphbuilder.c delete mode 100644 src/Encoders/ordergraphbuilder.h diff --git a/src/Collections/structs.c b/src/Collections/structs.c index 211dcd9..78a1447 100644 --- a/src/Collections/structs.c +++ b/src/Collections/structs.c @@ -4,6 +4,7 @@ #include "tableentry.h" #include "ordernode.h" #include "orderedge.h" +#include "ordergraph.h" VectorImpl(Table, Table *, 4); VectorImpl(Set, Set *, 4); @@ -15,6 +16,8 @@ VectorImpl(Order, Order *, 4); VectorImpl(TableEntry, TableEntry *, 4); VectorImpl(ASTNode, ASTNode *, 4); VectorImpl(Int, uint64_t, 4); +VectorImpl(OrderNode, OrderNode*, 4); +VectorImpl(OrderGraph, OrderGraph*, 4); inline unsigned int Ptr_hash_function(void * hash) { return (unsigned int)((int64)hash >> 4); @@ -70,9 +73,18 @@ static inline bool order_edge_equals(OrderEdge* key1, OrderEdge* key2){ return key1->sink == key2->sink && key1->source == key2->source && key1->order == key2->order; } +static inline unsigned int node_info_hash_function(OrderNode * hash) { + return (uint)((int64)hash >> 4); +} + +static inline bool node_info_equals(OrderNode * key1, OrderNode * key2) { + return key1 == key2; +} + HashTableImpl(OrderPair, OrderPair *, OrderPair *, order_pair_hash_Function, order_pair_equals, ourfree); +HashTableImpl(Node, OrderNode *, NodeInfo *, node_info_hash_function, node_info_equals, ourfree); + HashSetImpl(TableEntry, TableEntry*, table_entry_hash_Function, table_entry_equals); HashSetImpl(OrderNode, OrderNode*, order_node_hash_Function, order_node_equals); HashSetImpl(OrderEdge, OrderEdge*, order_edge_hash_Function, order_edge_equals); - diff --git a/src/Collections/structs.h b/src/Collections/structs.h index 0ce6ecb..451ac07 100644 --- a/src/Collections/structs.h +++ b/src/Collections/structs.h @@ -20,9 +20,12 @@ VectorDef(Order, Order *); VectorDef(TableEntry, TableEntry *); VectorDef(ASTNode, ASTNode *); VectorDef(Int, uint64_t); +VectorDef(OrderNode, OrderNode*); +VectorDef(OrderGraph, OrderGraph*); HashTableDef(Void, void *, void *); HashTableDef(OrderPair, OrderPair *, OrderPair *); +HashTableDef(Node, OrderNode*, NodeInfo*); HashSetDef(Void, void *); HashSetDef(TableEntry, TableEntry*); diff --git a/src/Encoders/orderencoder.c b/src/Encoders/orderencoder.c new file mode 100644 index 0000000..f9b099d --- /dev/null +++ b/src/Encoders/orderencoder.c @@ -0,0 +1,93 @@ + +#include "orderencoder.h" +#include "structs.h" +#include "csolver.h" +#include "boolean.h" +#include "ordergraph.h" +#include "order.h" + + +NodeInfo* allocNodeInfo(){ + NodeInfo* This = (NodeInfo*) ourmalloc(sizeof(NodeInfo)); + This->finishTime = 0; + This->status = NOTVISITED; + return This; +} + +void deleteNodeInfo(NodeInfo* info){ + ourfree(info); +} + +OrderEncoder* allocOrderEncoder(){ + OrderEncoder* This = (OrderEncoder*) ourmalloc(sizeof(OrderEncoder)); + initDefVectorOrderGraph( &This->graphs ); + return This; +} + +void deleteOrderEncoder(OrderEncoder* This){ + uint size = getSizeVectorOrderGraph(&This->graphs); + for(uint i=0; igraphs, i)); + } + ourfree(This); +} + +OrderEncoder* buildOrderGraphs(CSolver* This){ + uint size = getSizeVectorOrder(This->allOrders); + OrderEncoder* oEncoder = allocOrderEncoder(); + for(uint i=0; iallOrders, i); + uint constrSize = getSizeVectorBoolean(&order->constraints); + for(uint j=0; jconstraints, j)); + } + pushVectorOrderGraph(&oEncoder->graphs, orderGraph); + } + return oEncoder; +} + +void DFS(OrderGraph* graph, VectorOrderNode* finishNodes, HashTableNode* nodeToInfo, bool isReverse){ + uint timer=0; + HSIteratorOrderNode* iterator = iteratorOrderNode(graph->nodes); + while(hasNextOrderNode(iterator)){ + OrderNode* node = nextOrderNode(iterator); + NodeInfo* info= getNode(nodeToInfo, node); + if(info->status == NOTVISITED){ + info->status = VISITED; + //TODO ... + } + } + deleteIterOrderNode(iterator); +} + +void DFSNodeVisit(OrderNode* node, VectorOrderNode* finishNodes, HashTableNode* nodeToInfo, uint* timer, bool isReverse){ + NodeInfo* info= getNode(nodeToInfo, node); +} + +void initializeNodeInfoSCC(OrderGraph* graph, HashTableNode* nodeToInfo){ + HSIteratorOrderNode* iterator = iteratorOrderNode(graph->nodes); + while(hasNextOrderNode(iterator)){ + putNode(nodeToInfo, nextOrderNode(iterator), allocNodeInfo()); + } + deleteIterOrderNode(iterator); +} + +void computeStronglyConnectedComponentGraph(OrderGraph* graph){ + VectorOrderNode finishNodes; + initDefVectorOrderNode(& finishNodes); + HashTableNode* nodeToInfo = allocHashTableNode(HT_INITIAL_CAPACITY, HT_DEFAULT_FACTOR); + initializeNodeInfoSCC(graph, nodeToInfo); + // TODO + deleteHashTableNode(nodeToInfo); +} + +void orderAnalysis(CSolver* solver){ + OrderEncoder* oEncoder = buildOrderGraphs(solver); + uint size = getSizeVectorOrderGraph(&oEncoder->graphs); + for(uint i=0; igraphs, i); + computeStronglyConnectedComponentGraph(graph); + } +} + diff --git a/src/Encoders/orderencoder.h b/src/Encoders/orderencoder.h new file mode 100644 index 0000000..67e6103 --- /dev/null +++ b/src/Encoders/orderencoder.h @@ -0,0 +1,39 @@ +/* + * File: orderencoder.h + * Author: hamed + * + * Created on August 8, 2017, 6:36 PM + */ + +#ifndef ORDERGRAPHBUILDER_H +#define ORDERGRAPHBUILDER_H +#include "classlist.h" +#include "structs.h" +#include "mymemory.h" + +enum NodeStatus {NOTVISITED, VISITED, FINISHED}; +typedef enum NodeStatus NodeStatus; + +struct NodeInfo{ + NodeStatus status; + uint finishTime; +}; + +struct OrderEncoder{ + VectorOrderGraph graphs; +}; + +NodeInfo* allocNodeInfo(); +void deleteNodeInfo(NodeInfo* info); +OrderEncoder* allocOrderEncoder(); +void deleteOrderEncoder(OrderEncoder* This); + +OrderEncoder* buildOrderGraphs(CSolver* This); +void computeStronglyConnectedComponentGraph(OrderGraph* graph); +void orderAnalysis(CSolver* solver); +void initializeNodeInfoSCC(OrderGraph* graph, HashTableNode* nodeToInfo); +void DFSNodeVisit(OrderNode* node, VectorOrderNode* finishNodes, HashTableNode* nodeToInfo, uint* timer, bool isReverse); +void DFS(OrderGraph* graph, VectorOrderNode* finishNodes, HashTableNode* nodeToInfo, bool isReverse); + +#endif /* ORDERGRAPHBUILDER_H */ + diff --git a/src/Encoders/ordergraph.c b/src/Encoders/ordergraph.c index fbb73d3..d438ad4 100644 --- a/src/Encoders/ordergraph.c +++ b/src/Encoders/ordergraph.c @@ -60,10 +60,8 @@ void addOrderConstraintToOrderGraph(OrderGraph* graph, Boolean* constr){ OrderNode* from = getOrderNodeFromOrderGraph(graph, bOrder->first, bOrder->order); OrderNode* to = getOrderNodeFromOrderGraph(graph, bOrder->second, bOrder->order); addOrderEdge(graph, from, to, constr); - } - void deleteOrderGraph(OrderGraph* graph){ HSIteratorOrderNode* iterator = iteratorOrderNode(graph->nodes); while(hasNextOrderNode(iterator)){ diff --git a/src/Encoders/ordergraphbuilder.c b/src/Encoders/ordergraphbuilder.c deleted file mode 100644 index 285840a..0000000 --- a/src/Encoders/ordergraphbuilder.c +++ /dev/null @@ -1,21 +0,0 @@ - -#include "ordergraphbuilder.h" -#include "structs.h" -#include "csolver.h" -#include "boolean.h" -#include "ordergraph.h" - - -void buildOrderGraph(CSolver* This){ - uint size = getSizeVectorBoolean(This->constraints); - OrderGraph* orderGraph = allocOrderGraph(); - for(uint i=0; iconstraints, i); - if(GETBOOLEANTYPE(constraint) == ORDERCONST){ - addOrderConstraintToOrderGraph(orderGraph, constraint); - } - } - //TODO: We should add the orderGraph to our encoder - deleteOrderGraph(orderGraph); -} - diff --git a/src/Encoders/ordergraphbuilder.h b/src/Encoders/ordergraphbuilder.h deleted file mode 100644 index 3a31a25..0000000 --- a/src/Encoders/ordergraphbuilder.h +++ /dev/null @@ -1,15 +0,0 @@ -/* - * File: ordergraphbuilder.h - * Author: hamed - * - * Created on August 8, 2017, 6:36 PM - */ - -#ifndef ORDERGRAPHBUILDER_H -#define ORDERGRAPHBUILDER_H -#include "classlist.h" - -void buildOrderGraph(CSolver* This); -void computeStronglyConnectedComponentGraph(OrderGraph* graph); -#endif /* ORDERGRAPHBUILDER_H */ - diff --git a/src/classlist.h b/src/classlist.h index 171e662..dd37128 100644 --- a/src/classlist.h +++ b/src/classlist.h @@ -91,6 +91,12 @@ typedef struct OrderNode OrderNode; struct OrderEdge; typedef struct OrderEdge OrderEdge; +struct OrderEncoder; +typedef struct OrderEncoder OrderEncoder; + +struct NodeInfo; +typedef struct NodeInfo NodeInfo; + typedef unsigned int uint; typedef long int int64; typedef uint64_t VarType; -- 2.34.1