From 927b6bf9fc31106ddc731af427dc1b4b621a1d27 Mon Sep 17 00:00:00 2001 From: Brian Demsky Date: Thu, 7 Sep 2017 16:53:39 -0700 Subject: [PATCH] Iterator over AST --- src/AST/iterator.cc | 68 +++++++++++++++++++++++++++++++ src/AST/iterator.h | 29 +++++++++++++ src/Collections/corestructs.h | 15 ++++--- src/Collections/structs.h | 34 ++++++++-------- src/Makefile | 9 ++-- src/Test/buildconstraintstest.cc | 0 src/Test/cnftest.cc | 0 src/Test/elemequalsattest.cc | 0 src/Test/elemequalunsattest.cc | 0 src/Test/funcencodingtest.cc | 0 src/Test/logicopstest.cc | 0 src/Test/ltelemconsttest.cc | 0 src/Test/ordergraphtest.cc | 0 src/Test/ordertest.cc | 0 src/Test/tablefuncencodetest.cc | 0 src/Test/tablepredicencodetest.cc | 0 src/classlist.h | 4 ++ 17 files changed, 134 insertions(+), 25 deletions(-) create mode 100644 src/AST/iterator.cc create mode 100644 src/AST/iterator.h mode change 100755 => 100644 src/Test/buildconstraintstest.cc mode change 100755 => 100644 src/Test/cnftest.cc mode change 100755 => 100644 src/Test/elemequalsattest.cc mode change 100755 => 100644 src/Test/elemequalunsattest.cc mode change 100755 => 100644 src/Test/funcencodingtest.cc mode change 100755 => 100644 src/Test/logicopstest.cc mode change 100755 => 100644 src/Test/ltelemconsttest.cc mode change 100755 => 100644 src/Test/ordergraphtest.cc mode change 100755 => 100644 src/Test/ordertest.cc mode change 100755 => 100644 src/Test/tablefuncencodetest.cc mode change 100755 => 100644 src/Test/tablepredicencodetest.cc diff --git a/src/AST/iterator.cc b/src/AST/iterator.cc new file mode 100644 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 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; + Vector index; + void updateNext(); +}; + +class ElementIterator { + public: + CMEMALLOC; + private: + BooleanIterator bit; +}; + + +#endif diff --git a/src/Collections/corestructs.h b/src/Collections/corestructs.h index e30a530..5e8a7de 100644 --- 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 HashsetBooleanEdge; -typedef Hashset HashsetOrder; -typedef SetIterator SetIteratorBooleanEdge; -typedef SetIterator SetIteratorOrder; +typedef Hashset HashsetBooleanEdge; +typedef Hashset HashsetOrder; +typedef SetIterator SetIteratorBooleanEdge; +typedef SetIterator SetIteratorOrder; #endif diff --git a/src/Collections/structs.h b/src/Collections/structs.h index e9c645f..801cb87 100644 --- 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 HashsetTableEntry; -typedef Hashset HashsetOrderNode; -typedef Hashset HashsetOrderEdge; -typedef Hashset HashsetOrderElement; -typedef Hashset HashsetBoolean; -typedef SetIterator SetIteratorBoolean; - -typedef Hashtable HashtableNodeToNodeSet; -typedef Hashtable HashtableOrderPair; -typedef Hashtable CloneMap; -typedef Hashtable HashTableOrderIntEncoding; - -typedef SetIterator SetIteratorTableEntry; -typedef SetIterator SetIteratorOrderEdge; -typedef SetIterator SetIteratorOrderNode; -typedef SetIterator SetIteratorOrderElement; +typedef Hashset HashsetTableEntry; +typedef Hashset HashsetOrderNode; +typedef Hashset HashsetOrderEdge; +typedef Hashset HashsetOrderElement; +typedef Hashset HashsetBoolean; +typedef SetIterator SetIteratorBoolean; + +typedef Hashtable HashtableNodeToNodeSet; +typedef Hashtable HashtableOrderPair; +typedef Hashtable CloneMap; + + +typedef Hashtable HashTableEncoding; + +typedef SetIterator SetIteratorTableEntry; +typedef SetIterator SetIteratorOrderEdge; +typedef SetIterator SetIteratorOrderNode; +typedef SetIterator SetIteratorOrderElement; #endif diff --git a/src/Makefile b/src/Makefile index 442a1c6..e099994 100644 --- 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 new mode 100644 diff --git a/src/Test/cnftest.cc b/src/Test/cnftest.cc old mode 100755 new mode 100644 diff --git a/src/Test/elemequalsattest.cc b/src/Test/elemequalsattest.cc old mode 100755 new mode 100644 diff --git a/src/Test/elemequalunsattest.cc b/src/Test/elemequalunsattest.cc old mode 100755 new mode 100644 diff --git a/src/Test/funcencodingtest.cc b/src/Test/funcencodingtest.cc old mode 100755 new mode 100644 diff --git a/src/Test/logicopstest.cc b/src/Test/logicopstest.cc old mode 100755 new mode 100644 diff --git a/src/Test/ltelemconsttest.cc b/src/Test/ltelemconsttest.cc old mode 100755 new mode 100644 diff --git a/src/Test/ordergraphtest.cc b/src/Test/ordergraphtest.cc old mode 100755 new mode 100644 diff --git a/src/Test/ordertest.cc b/src/Test/ordertest.cc old mode 100755 new mode 100644 diff --git a/src/Test/tablefuncencodetest.cc b/src/Test/tablefuncencodetest.cc old mode 100755 new mode 100644 diff --git a/src/Test/tablepredicencodetest.cc b/src/Test/tablepredicencodetest.cc old mode 100755 new mode 100644 diff --git a/src/classlist.h b/src/classlist.h index d56a650..5cddf58 100644 --- 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; -- 2.34.1