Iterator over AST

diff --git a/src/AST/iterator.cc b/src/AST/iterator.cc
new file mode 100644 (file)
index 0000000..ac81e96
--- /dev/null
+++ b/src/AST/iterator.cc
@@ -0,0 +1,68 @@
+#include "iterator.h"
+#include "boolean.h"
+#include "csolver.h"
+
+BooleanIterator::BooleanIterator(CSolver * _solver) :
+       solverit(_solver->getConstraints()) {
+       updateNext();
+}
+
+BooleanIterator::~BooleanIterator() {
+       delete solverit;
+}
+
+bool BooleanIterator::hasNext() {
+       return boolean.getSize() != 0;
+}
+
+void BooleanIterator::updateNext() {
+       if (boolean.getSize() != 0) {
+               boolean.pop();
+               index.pop();
+       }
+       
+       while(true) {
+               if (boolean.getSize() == 0) {
+                       if (solverit->hasNext()) {
+                               Boolean *b=solverit->next().getBoolean();
+                               if (discovered.add(b)) {
+                                       boolean.push(b);
+                                       index.push(0);
+                               } else
+                                       continue;
+                       } else
+                               return;
+               }
+               Boolean *topboolean=boolean.last();
+               uint topindex=index.last();
+               switch(topboolean->type) {
+               case ORDERCONST:
+               case BOOLEANVAR:
+               case PREDICATEOP:
+               case BOOLCONST:
+                       return;
+               case LOGICOP: {
+                       BooleanLogic * logicop=(BooleanLogic*) topboolean;
+                       uint size=logicop->inputs.getSize();
+                       if (topindex == size)
+                               return;
+                       index.pop();
+                       index.push(topindex+1);
+                       Boolean *newchild=logicop->inputs.get(topindex).getBoolean();
+                       if (discovered.add(newchild)) {
+                               boolean.push(logicop->inputs.get(topindex).getBoolean());
+                               index.push(0);
+                       }
+                       break;
+               }
+               default:
+                       ASSERT(0);
+               }
+       }
+}
+
+Boolean * BooleanIterator::next() {
+       Boolean * b = boolean.last();
+       updateNext();
+       return b;
+}

diff --git a/src/AST/iterator.h b/src/AST/iterator.h
new file mode 100644 (file)
index 0000000..b82ee37
--- /dev/null
+++ b/src/AST/iterator.h
@@ -0,0 +1,29 @@
+#ifndef ITERATOR_H
+#define ITERATOR_H
+#include "classlist.h"
+#include "structs.h"
+
+class BooleanIterator {
+ public:
+       BooleanIterator(CSolver * _solver);
+       ~BooleanIterator();
+       bool hasNext();
+       Boolean * next();
+       CMEMALLOC;
+ private:
+       SetIteratorBooleanEdge * solverit;
+       HashsetBoolean discovered;
+       Vector<Boolean *> boolean;
+       Vector<uint> index;
+       void updateNext();
+};
+
+class ElementIterator {
+ public:
+       CMEMALLOC;
+ private:
+       BooleanIterator bit;
+};
+
+
+#endif

diff --git a/src/Collections/corestructs.h b/src/Collections/corestructs.h
index e30a5309b57b0330c37fe9ff307ddc5f02fc1163..5e8a7de935b8f1e3818ed156efc9d03c7cb150f0 100644 (file)
--- a/src/Collections/corestructs.h
+++ b/src/Collections/corestructs.h
@@ -4,6 +4,11 @@
 #include "cppvector.h"
 #include "hashset.h"
 
+//How much should we shift pointers when computing hash functions
+//5 appears to be the minimum value for Ubuntu 64-bit
+
+#define PTRSHIFT 5
+
 class BooleanEdge {
  public:
  BooleanEdge() : b(NULL) {}
@@ -25,12 +30,12 @@ inline bool boolEdgeEquals(BooleanEdge b1, BooleanEdge b2) {
 }
 
 inline unsigned int boolEdgeHash(BooleanEdge b) {
-       return (unsigned int) (((uintptr_t)b.getRaw())>>4);
+       return (unsigned int) (((uintptr_t)b.getRaw())>>PTRSHIFT);
 }
                                                                        
-typedef Hashset<BooleanEdge, uintptr_t, 4, & boolEdgeHash, & boolEdgeEquals> HashsetBooleanEdge;
-typedef Hashset<Order *, uintptr_t, 4> HashsetOrder;
-typedef SetIterator<BooleanEdge, uintptr_t, 4, & boolEdgeHash, & boolEdgeEquals> SetIteratorBooleanEdge;
-typedef SetIterator<Order *, uintptr_t, 4> SetIteratorOrder;
+typedef Hashset<BooleanEdge, uintptr_t, PTRSHIFT, & boolEdgeHash, & boolEdgeEquals> HashsetBooleanEdge;
+typedef Hashset<Order *, uintptr_t, PTRSHIFT> HashsetOrder;
+typedef SetIterator<BooleanEdge, uintptr_t, PTRSHIFT, & boolEdgeHash, & boolEdgeEquals> SetIteratorBooleanEdge;
+typedef SetIterator<Order *, uintptr_t, PTRSHIFT> SetIteratorOrder;
 
 #endif

diff --git a/src/Collections/structs.h b/src/Collections/structs.h
index e9c645f3a1dc85c1b8ed166cd820aa6910c9ff1f..801cb8784e6bcabd66e1984adfdf4a4067b4d452 100644 (file)
--- a/src/Collections/structs.h
+++ b/src/Collections/structs.h
@@ -19,21 +19,23 @@ unsigned int order_pair_hash_function(OrderPair *This);
 bool order_pair_equals(OrderPair *key1, OrderPair *key2);
 
 
-typedef Hashset<TableEntry *, uintptr_t, 4, table_entry_hash_function, table_entry_equals> HashsetTableEntry;
-typedef Hashset<OrderNode *, uintptr_t, 4, order_node_hash_function, order_node_equals> HashsetOrderNode;
-typedef Hashset<OrderEdge *, uintptr_t, 4, order_edge_hash_function, order_edge_equals> HashsetOrderEdge;
-typedef Hashset<OrderElement *, uintptr_t, 4, order_element_hash_function, order_element_equals> HashsetOrderElement;
-typedef Hashset<Boolean *, uintptr_t, 4> HashsetBoolean;
-typedef SetIterator<Boolean *, uintptr_t, 4> SetIteratorBoolean;
-
-typedef Hashtable<OrderNode *, HashsetOrderNode *, uintptr_t, 4> HashtableNodeToNodeSet;
-typedef Hashtable<OrderPair *, OrderPair *, uintptr_t, 4, order_pair_hash_function, order_pair_equals> HashtableOrderPair;
-typedef Hashtable<void *, void *, uintptr_t, 4> CloneMap;
-typedef Hashtable<Order *, IntegerEncodingRecord *, uintptr_t, 4> HashTableOrderIntEncoding;
-
-typedef SetIterator<TableEntry *, uintptr_t, 4, table_entry_hash_function, table_entry_equals> SetIteratorTableEntry;
-typedef SetIterator<OrderEdge *, uintptr_t, 4, order_edge_hash_function, order_edge_equals> SetIteratorOrderEdge;
-typedef SetIterator<OrderNode *, uintptr_t, 4, order_node_hash_function, order_node_equals> SetIteratorOrderNode;
-typedef SetIterator<OrderElement *, uintptr_t, 4, order_element_hash_function, order_element_equals> SetIteratorOrderElement;
+typedef Hashset<TableEntry *, uintptr_t, PTRSHIFT, table_entry_hash_function, table_entry_equals> HashsetTableEntry;
+typedef Hashset<OrderNode *, uintptr_t, PTRSHIFT, order_node_hash_function, order_node_equals> HashsetOrderNode;
+typedef Hashset<OrderEdge *, uintptr_t, PTRSHIFT, order_edge_hash_function, order_edge_equals> HashsetOrderEdge;
+typedef Hashset<OrderElement *, uintptr_t, PTRSHIFT, order_element_hash_function, order_element_equals> HashsetOrderElement;
+typedef Hashset<Boolean *, uintptr_t, PTRSHIFT> HashsetBoolean;
+typedef SetIterator<Boolean *, uintptr_t, PTRSHIFT> SetIteratorBoolean;
+
+typedef Hashtable<OrderNode *, HashsetOrderNode *, uintptr_t, PTRSHIFT> HashtableNodeToNodeSet;
+typedef Hashtable<OrderPair *, OrderPair *, uintptr_t, PTRSHIFT, order_pair_hash_function, order_pair_equals> HashtableOrderPair;
+typedef Hashtable<void *, void *, uintptr_t, PTRSHIFT> CloneMap;
+
+
+typedef Hashtable<Set *, EncodingNode *, uintptr_t, PTRSHIFT> HashTableEncoding;
+
+typedef SetIterator<TableEntry *, uintptr_t, PTRSHIFT, table_entry_hash_function, table_entry_equals> SetIteratorTableEntry;
+typedef SetIterator<OrderEdge *, uintptr_t, PTRSHIFT, order_edge_hash_function, order_edge_equals> SetIteratorOrderEdge;
+typedef SetIterator<OrderNode *, uintptr_t, PTRSHIFT, order_node_hash_function, order_node_equals> SetIteratorOrderNode;
+typedef SetIterator<OrderElement *, uintptr_t, PTRSHIFT, order_element_hash_function, order_element_equals> SetIteratorOrderElement;
 
 #endif

diff --git a/src/Makefile b/src/Makefile
index 442a1c6cf993de1a268f0ea6148db0e132500e06..e099994e89c59b1445a63c705e84609cc6615a5a 100644 (file)
--- a/src/Makefile
+++ b/src/Makefile
@@ -4,16 +4,16 @@ PHONY += directories
 MKDIR_P = mkdir -p
 OBJ_DIR = bin
 
-CPP_SOURCES := $(wildcard *.cc) $(wildcard AST/*.cc) $(wildcard ASTTransform/*.cc) $(wildcard Translator/*.cc) $(wildcard ASTAnalyses/*.cc) $(wildcard ASTAnalyses/Order/*.cc) $(wildcard ASTAnalyses/Polarity/*.cc) $(wildcard Tuner/*.cc) $(wildcard Collections/*.cc) $(wildcard Backend/*.cc) $(wildcard Encoders/*.cc)
+CPP_SOURCES := $(wildcard *.cc) $(wildcard AST/*.cc) $(wildcard ASTTransform/*.cc) $(wildcard Translator/*.cc) $(wildcard ASTAnalyses/*.cc) $(wildcard ASTAnalyses/Order/*.cc) $(wildcard ASTAnalyses/Encoding/*.cc) $(wildcard ASTAnalyses/Polarity/*.cc) $(wildcard Tuner/*.cc) $(wildcard Collections/*.cc) $(wildcard Backend/*.cc) $(wildcard Encoders/*.cc)
 
-C_SOURCES := $(wildcard *.c) $(wildcard AST/*.c) $(wildcard ASTTransform/*.c) $(wildcard Translator/*.c) $(wildcard ASTAnalyses/*.c) $(wildcard ASTAnalyses/Order/*.c) $(wildcard ASTAnalyses/Polarity/*.c) $(wildcard Tuner/*.c) $(wildcard Collections/*.c) $(wildcard Backend/*.c) $(wildcard Encoders/*.c)
+C_SOURCES := $(wildcard *.c) $(wildcard AST/*.c) $(wildcard ASTTransform/*.c) $(wildcard Translator/*.c) $(wildcard ASTAnalyses/*.c) $(wildcard ASTAnalyses/Order/*.c) $(wildcard ASTAnalyses/Encoding/*.c) $(wildcard ASTAnalyses/Polarity/*.c) $(wildcard Tuner/*.c) $(wildcard Collections/*.c) $(wildcard Backend/*.c) $(wildcard Encoders/*.c)
 
-HEADERS := $(wildcard *.h) $(wildcard AST/*.h) $(wildcard ASTTransform/*.h) $(wildcard Translator/*.h) $(wildcard ASTAnalyses/*.h) $(wildcard ASTAnalyses/Order/*.h) $(wildcard ASTAnalyses/Polarity/*.h) $(wildcard Tuner/*.h) $(wildcard Collections/*.h) $(wildcard Backend/*.h) $(wildcard Encoders/*.h)
+HEADERS := $(wildcard *.h) $(wildcard AST/*.h) $(wildcard ASTTransform/*.h) $(wildcard Translator/*.h) $(wildcard ASTAnalyses/*.h) $(wildcard ASTAnalyses/Order/*.h) $(wildcard ASTAnalyses/Encoding/*.h) $(wildcard ASTAnalyses/Polarity/*.h) $(wildcard Tuner/*.h) $(wildcard Collections/*.h) $(wildcard Backend/*.h) $(wildcard Encoders/*.h)
 
 OBJECTS := $(CPP_SOURCES:%.cc=$(OBJ_DIR)/%.o) $(C_SOURCES:%.c=$(OBJ_DIR)/%.o)
 
 CFLAGS := -Wall -g -O0
-CFLAGS += -IAST -IASTTransform -IASTAnalyses -IASTAnalyses/Polarity -IASTAnalyses/Order -ITranslator -ICollections -IBackend -I. -IEncoders -ITuner
+CFLAGS += -IAST -IASTTransform -IASTAnalyses -IASTAnalyses/Polarity -IASTAnalyses/Order -IASTAnalyses/Encoding -ITranslator -ICollections -IBackend -I. -IEncoders -ITuner
 LDFLAGS := -ldl -lrt -rdynamic
 SHARED := -shared
 
@@ -34,6 +34,7 @@ ${OBJ_DIR}:
        ${MKDIR_P} ${OBJ_DIR}/AST
        ${MKDIR_P} ${OBJ_DIR}/ASTAnalyses
        ${MKDIR_P} ${OBJ_DIR}/ASTAnalyses/Order
+       ${MKDIR_P} ${OBJ_DIR}/ASTAnalyses/Encoding
        ${MKDIR_P} ${OBJ_DIR}/ASTAnalyses/Polarity
        ${MKDIR_P} ${OBJ_DIR}/ASTTransform
        ${MKDIR_P} ${OBJ_DIR}/Translator

diff --git a/src/Test/buildconstraintstest.cc b/src/Test/buildconstraintstest.cc
old mode 100755 (executable)
new mode 100644 (file)

diff --git a/src/Test/cnftest.cc b/src/Test/cnftest.cc
old mode 100755 (executable)
new mode 100644 (file)

diff --git a/src/Test/elemequalsattest.cc b/src/Test/elemequalsattest.cc
old mode 100755 (executable)
new mode 100644 (file)

diff --git a/src/Test/elemequalunsattest.cc b/src/Test/elemequalunsattest.cc
old mode 100755 (executable)
new mode 100644 (file)

diff --git a/src/Test/funcencodingtest.cc b/src/Test/funcencodingtest.cc
old mode 100755 (executable)
new mode 100644 (file)

diff --git a/src/Test/logicopstest.cc b/src/Test/logicopstest.cc
old mode 100755 (executable)
new mode 100644 (file)

diff --git a/src/Test/ltelemconsttest.cc b/src/Test/ltelemconsttest.cc
old mode 100755 (executable)
new mode 100644 (file)

diff --git a/src/Test/ordergraphtest.cc b/src/Test/ordergraphtest.cc
old mode 100755 (executable)
new mode 100644 (file)

diff --git a/src/Test/ordertest.cc b/src/Test/ordertest.cc
old mode 100755 (executable)
new mode 100644 (file)

diff --git a/src/Test/tablefuncencodetest.cc b/src/Test/tablefuncencodetest.cc
old mode 100755 (executable)
new mode 100644 (file)

diff --git a/src/Test/tablepredicencodetest.cc b/src/Test/tablepredicencodetest.cc
old mode 100755 (executable)
new mode 100644 (file)

diff --git a/src/classlist.h b/src/classlist.h
index d56a6507b856f90209208a71b9a89be8e9ee8ea5..5cddf5846a35d53b71e7c6f0810697f5645551fe 100644 (file)
--- a/src/classlist.h
+++ b/src/classlist.h
@@ -63,6 +63,10 @@ class TunableDesc;
 class OrderResolver;
 class DecomposeOrderResolver;
 
+class EncodingGraph;
+class EncodingNode;
+class EncodingEdge;
+
 struct IncrementalSolver;
 typedef struct IncrementalSolver IncrementalSolver;
 struct TableEntry;