src/Backend/constraint.h

   1 #ifndef CONSTRAINT_H
   2 #define CONSTRAINT_H
   3 #include "classlist.h"
   4 #include "vector.h"
   5
   6 #define NEGATE_EDGE 1
   7 #define EDGE_IS_VAR_CONSTANT 2
   8 #define VAR_SHIFT 2
   9 #define EDGE_MASK (NEGATE_EDGE | EDGE_IS_VAR_CONSTANT)
  10
  11 typedef int Literal;
  12
  13 struct Edge;
  14 typedef struct Edge Edge;
  15
  16 struct Node;
  17 typedef struct Node Node;
  18
  19 struct Edge {
  20         Node *node_ptr;
  21 };
  22
  23 VectorDef(Edge, Edge)
  24
  25 enum NodeType {
  26         NodeType_AND,
  27         NodeType_ITE,
  28         NodeType_IFF
  29 };
  30
  31 typedef enum NodeType NodeType;
  32
  33 struct Node {
  34         uint numEdges;
  35         union {
  36                 NodeType type;
  37                 uint capacity;
  38         };
  39         Edge edges[];
  40 };
  41
  42 typedef struct Node Node;
  43
  44 #define DEFAULT_CNF_ARRAY_SIZE 2048
  45
  46 struct CNF {
  47         uint varcount;
  48         uint asize;
  49         IncrementalSolver *solver;
  50         int * array;
  51         long long solveTime;
  52         long long encodeTime;
  53         bool unsat;
  54 };
  55
  56 typedef struct CNF CNF;
  57
  58 static inline Edge constraintNegate(Edge e) {
  59         Edge eneg = { (Node *) (((uintptr_t) e.node_ptr) ^ NEGATE_EDGE)};
  60         return eneg;
  61 }
  62
  63 static inline bool sameNodeVarEdge(Edge e1, Edge e2) {
  64         return !(((uintptr_t) e1.node_ptr ^ (uintptr_t) e2.node_ptr) & (~(uintptr_t) NEGATE_EDGE));
  65 }
  66
  67 static inline bool sameSignEdge(Edge e1, Edge e2) {
  68         return !(((uintptr_t) e1.node_ptr ^ (uintptr_t) e2.node_ptr) & NEGATE_EDGE);
  69 }
  70
  71 static inline bool sameNodeOppSign(Edge e1, Edge e2) {
  72         return (((uintptr_t) e1.node_ptr) ^ ((uintptr_t)e2.node_ptr)) == NEGATE_EDGE;
  73 }
  74
  75 static inline bool isNegEdge(Edge e) {
  76         return ((uintptr_t)e.node_ptr) & NEGATE_EDGE;
  77 }
  78
  79 static inline bool isPosEdge(Edge e) {
  80         return !(((uintptr_t)e.node_ptr) & NEGATE_EDGE);
  81 }
  82
  83 static inline bool isNodeEdge(Edge e) {
  84         return !(((uintptr_t)e.node_ptr) & EDGE_IS_VAR_CONSTANT);
  85 }
  86
  87 static inline bool isNegNodeEdge(Edge e) {
  88         return (((uintptr_t) e.node_ptr) & (NEGATE_EDGE | EDGE_IS_VAR_CONSTANT)) == NEGATE_EDGE;
  89 }
  90
  91 static inline bool isPosNodeEdge(Edge e) {
  92         return (((uintptr_t) e.node_ptr) & (NEGATE_EDGE | EDGE_IS_VAR_CONSTANT)) == 0;
  93 }
  94
  95 static inline Node *getNodePtrFromEdge(Edge e) {
  96         return (Node *) (((uintptr_t) e.node_ptr) & ~((uintptr_t) EDGE_MASK));
  97 }
  98
  99 static inline NodeType getNodeType(Edge e) {
 100         Node *n = getNodePtrFromEdge(e);
 101         return n->type;
 102 }
 103
 104 static inline bool equalsEdge(Edge e1, Edge e2) {
 105         return e1.node_ptr == e2.node_ptr;
 106 }
 107
 108 static inline bool ltEdge(Edge e1, Edge e2) {
 109         return (uintptr_t) e1.node_ptr < (uintptr_t) e2.node_ptr;
 110 }
 111
 112 static inline uint getNodeSize(Edge e) {
 113         Node *n = getNodePtrFromEdge(e);
 114         return n->numEdges;
 115 }
 116
 117 static inline Edge *getEdgeArray(Edge e) {
 118         Node *n = getNodePtrFromEdge(e);
 119         return n->edges;
 120 }
 121
 122 static inline Edge getNonNeg(Edge e) {
 123         Edge enew = {(Node *)(((uintptr_t)e.node_ptr) & (~((uintptr_t)NEGATE_EDGE)))};
 124         return enew;
 125 }
 126
 127 static inline bool edgeIsConst(Edge e) {
 128         return (((uintptr_t) e.node_ptr) & ~((uintptr_t)NEGATE_EDGE)) == EDGE_IS_VAR_CONSTANT;
 129 }
 130
 131 static inline bool edgeIsNull(Edge e) {
 132         return e.node_ptr == NULL;
 133 }
 134
 135 static inline bool edgeIsVarConst(Edge e) {
 136         return ((uintptr_t)e.node_ptr) & EDGE_IS_VAR_CONSTANT;
 137 }
 138
 139 static inline Edge constraintNegateIf(Edge e, bool negate) {
 140         Edge eret = {(Node *)(((uintptr_t)e.node_ptr) ^ negate)};
 141         return eret;
 142 }
 143
 144 static inline Literal getEdgeVar(Edge e) {
 145         int val = (int) (((uintptr_t) e.node_ptr) >> VAR_SHIFT);
 146         return isNegEdge(e) ? -val : val;
 147 }
 148
 149 CNF *createCNF();
 150 void deleteCNF(CNF *cnf);
 151 void resetCNF(CNF *cnf);
 152
 153 uint hashNode(NodeType type, uint numEdges, Edge *edges);
 154 Node *allocNode(NodeType type, uint numEdges, Edge *edges);
 155 bool compareNodes(Node *node, NodeType type, uint numEdges, Edge *edges);
 156 Edge createNode(NodeType type, uint numEdges, Edge *edges);
 157 Edge constraintOR(CNF *cnf, uint numEdges, Edge *edges);
 158 Edge constraintAND(CNF *cnf, uint numEdges, Edge *edges);
 159 Edge constraintOR2(CNF *cnf, Edge left, Edge right);
 160 Edge constraintAND2(CNF *cnf, Edge left, Edge right);
 161 Edge constraintIMPLIES(CNF *cnf, Edge left, Edge right);
 162 Edge constraintIFF(CNF *cnf, Edge left, Edge right);
 163 static inline Edge constraintXOR(CNF *cnf, Edge left, Edge right) {return constraintNegate(constraintIFF(cnf, left,right));}
 164 Edge constraintITE(CNF *cnf, Edge cond, Edge thenedge, Edge elseedge);
 165 Edge constraintNewVar(CNF *cnf);
 166 void countPass(CNF *cnf);
 167 void countConstraint(CNF *cnf, VectorEdge *stack, Edge e);
 168 void addConstraintCNF(CNF *cnf, Edge constraint);
 169 int solveCNF(CNF *cnf);
 170 bool getValueCNF(CNF *cnf, Edge var);
 171 void printCNF(Edge e);
 172 Node *allocBaseNode(NodeType type, uint numEdges);
 173 Node *allocResizeNode(uint capacity);
 174 Edge cloneEdge(Edge e);
 175 void addEdgeToResizeNode(Node ** node, Edge e);
 176 void mergeFreeNodeToResizeNode(Node **node, Node * innode);
 177 void mergeNodeToResizeNode(Node **node, Node * innode);
 178 void freeEdgeRec(Edge e);
 179
 180 Edge generateBinaryConstraint(CNF *cnf, uint numvars, Edge *vars, uint value);
 181 Edge generateLTValueConstraint(CNF *cnf, uint numvars, Edge *vars, uint value);
 182 Edge generateEquivNVConstraint(CNF *cnf, uint numvars, Edge *var1, Edge *var2);
 183 Edge generateLTConstraint(CNF *cnf, uint numvars, Edge *var1, Edge *var2);
 184 Edge generateLTEConstraint(CNF *cnf, uint numvars, Edge *var1, Edge *var2);
 185
 186 extern Edge E_True;
 187 extern Edge E_False;
 188 extern Edge E_BOGUS;
 189 extern Edge E_NULL;
 190 #endif