Iterator over AST
authorBrian Demsky <bdemsky@uci.edu>
Thu, 7 Sep 2017 23:53:39 +0000 (16:53 -0700)
committerbdemsky <bdemsky@uci.edu>
Thu, 7 Sep 2017 23:55:15 +0000 (16:55 -0700)
17 files changed:
src/AST/iterator.cc [new file with mode: 0644]
src/AST/iterator.h [new file with mode: 0644]
src/Collections/corestructs.h
src/Collections/structs.h
src/Makefile
src/Test/buildconstraintstest.cc [changed mode: 0755->0644]
src/Test/cnftest.cc [changed mode: 0755->0644]
src/Test/elemequalsattest.cc [changed mode: 0755->0644]
src/Test/elemequalunsattest.cc [changed mode: 0755->0644]
src/Test/funcencodingtest.cc [changed mode: 0755->0644]
src/Test/logicopstest.cc [changed mode: 0755->0644]
src/Test/ltelemconsttest.cc [changed mode: 0755->0644]
src/Test/ordergraphtest.cc [changed mode: 0755->0644]
src/Test/ordertest.cc [changed mode: 0755->0644]
src/Test/tablefuncencodetest.cc [changed mode: 0755->0644]
src/Test/tablepredicencodetest.cc [changed mode: 0755->0644]
src/classlist.h

diff --git a/src/AST/iterator.cc b/src/AST/iterator.cc
new file mode 100644 (file)
index 0000000..ac81e96
--- /dev/null
@@ -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
@@ -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
index e30a530..5e8a7de 100644 (file)
@@ -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
index e9c645f..801cb87 100644 (file)
@@ -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
index 442a1c6..e099994 100644 (file)
@@ -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
old mode 100755 (executable)
new mode 100644 (file)
old mode 100755 (executable)
new mode 100644 (file)
old mode 100755 (executable)
new mode 100644 (file)
old mode 100755 (executable)
new mode 100644 (file)
old mode 100755 (executable)
new mode 100644 (file)
old mode 100755 (executable)
new mode 100644 (file)
old mode 100755 (executable)
new mode 100644 (file)
old mode 100755 (executable)
new mode 100644 (file)
old mode 100755 (executable)
new mode 100644 (file)
old mode 100755 (executable)
new mode 100644 (file)
old mode 100755 (executable)
new mode 100644 (file)
index d56a650..5cddf58 100644 (file)
@@ -63,6 +63,10 @@ class TunableDesc;
 class OrderResolver;
 class DecomposeOrderResolver;
 
+class EncodingGraph;
+class EncodingNode;
+class EncodingEdge;
+
 struct IncrementalSolver;
 typedef struct IncrementalSolver IncrementalSolver;
 struct TableEntry;