From 8b7232fa4c6557fa03211353d37824c3ad1010e0 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Wed, 14 Jun 2017 14:49:14 -0700 Subject: [PATCH] Initial Skeletons --- src/.dir-locals.el | 1 + src/Makefile | 2 +- src/classlist.h | 8 ++++ src/constraint.cc | 2 +- src/csolver.h | 34 +++++++++++++++ src/element.cc | 5 +++ src/element.h | 13 ++++++ src/function.cc | 1 + src/function.h | 11 +++++ src/hashtable.h | 6 +-- src/mutableset.cc | 2 + src/mutableset.h | 9 ++++ src/mymemory.h | 2 +- src/ops.h | 17 ++++++++ src/order.cc | 0 src/order.h | 12 ++++++ src/predicate.cc | 1 + src/predicate.h | 12 ++++++ src/set.cc | 103 ++++++++------------------------------------- src/set.h | 66 +++++++---------------------- src/table.cc | 1 + src/table.h | 11 +++++ src/types.h | 34 --------------- 23 files changed, 177 insertions(+), 176 deletions(-) create mode 100644 src/.dir-locals.el create mode 100644 src/csolver.h create mode 100644 src/element.cc create mode 100644 src/element.h create mode 100644 src/function.cc create mode 100644 src/function.h create mode 100644 src/mutableset.cc create mode 100644 src/mutableset.h create mode 100644 src/ops.h create mode 100644 src/order.cc create mode 100644 src/order.h create mode 100644 src/predicate.cc create mode 100644 src/predicate.h create mode 100644 src/table.cc create mode 100644 src/table.h delete mode 100644 src/types.h diff --git a/src/.dir-locals.el b/src/.dir-locals.el new file mode 100644 index 0000000..ce85e5f --- /dev/null +++ b/src/.dir-locals.el @@ -0,0 +1 @@ +((nil . ((indent-tabs-mode . t)))) \ No newline at end of file diff --git a/src/Makefile b/src/Makefile index b7a06f8..6ca77fc 100644 --- a/src/Makefile +++ b/src/Makefile @@ -4,7 +4,7 @@ PHONY += directories MKDIR_P = mkdir -p OBJ_DIR = bin -CPP_SOURCES := constraint.cc inc_solver.cc set.cc +CPP_SOURCES := constraint.cc inc_solver.cc set.cc mutableset.cc element.cc function.cc order.cc table.cc predicate.cc OBJECTS := $(CPP_SOURCES:%.cc=$(OBJ_DIR)/%.o) $(C_SOURCES:%.c=$(OBJ_DIR)/%.o) diff --git a/src/classlist.h b/src/classlist.h index 80ec636..cb9f19b 100644 --- a/src/classlist.h +++ b/src/classlist.h @@ -15,6 +15,14 @@ class Constraint; class IncrementalSolver; +class Set; +class MutableSet; +class Element; +class Function; +class Predicate; +class Table; +class Order; typedef unsigned int uint; +typedef uint64_t VarType; #endif diff --git a/src/constraint.cc b/src/constraint.cc index 74d01af..7d210d1 100644 --- a/src/constraint.cc +++ b/src/constraint.cc @@ -220,7 +220,7 @@ Constraint * generateLTConstraint(uint numvars, Constraint ** vars, uint value) } andarray[andi++]=new Constraint(OR, ori, orarray); - value=value+(1<<(__builtin_ctz(value))); //flip the last one + value=value+(1<<(__builtin_ctz(value))); //flip the last one } } diff --git a/src/csolver.h b/src/csolver.h new file mode 100644 index 0000000..9d260e0 --- /dev/null +++ b/src/csolver.h @@ -0,0 +1,34 @@ +#ifndef CSOLVER_H +#define CSOLVER_H +#include "classlist.h" +#include "ops.h" + +class CSolver { + Set * createSet(Type type, uint64_t ** elements); + Set * createSet(Type type, uint64_t lowrange, uint64_t highrange); + MutableSet * createMutableSet(Type type); + + void addItem(MutableSet * set, uint64_t element); + int64_t createUniqueItem(MutableSet * set); + + Element * getElementVar(Set * set); + Constraint * getBooleanVar(); + + Function * createFunctionOperator(enum ArithOp op, Set ** domain, Set * range, enum OverFlowBehavior overflowbehavior, Constraint * overflowstatus); + Function * createFunctionOperator(enum ArithOp op); //Does Not Overflow + Predicate * createPredicateOperator(enum CompOp op, Set ** domain); + + Table * createTable(Set **domains, Set * range); + void addTableEntry(Element ** inputs, Element *result); + Function * completeTable(struct Table *); + + Element * applyFunction(Function * function, Element ** array); + Constraint * applyPredicate(Predicate * predicate, Element ** inputs); + Constraint * applyLogicalOperation(enum LogicOp op, Constraint ** array); + + void addConstraint(Constraint * constraint); + + Order * createOrder(enum OrderType type, Set * set); + Constraint * orderedConstraint(Order * order, uint64_t first, uint64_t second); +}; +#endif diff --git a/src/element.cc b/src/element.cc new file mode 100644 index 0000000..2b9d1e1 --- /dev/null +++ b/src/element.cc @@ -0,0 +1,5 @@ +#include "element.h" + +Element::Element(Set * s) : + set(s) { +} diff --git a/src/element.h b/src/element.h new file mode 100644 index 0000000..bf2772c --- /dev/null +++ b/src/element.h @@ -0,0 +1,13 @@ +#ifndef ELEMENT_H +#define ELEMENT_H +#include "classlist.h" +#include "mymemory.h" + +class Element { + public: + Element(Set *s); + MEMALLOC; + private: + Set *set; +}; +#endif diff --git a/src/function.cc b/src/function.cc new file mode 100644 index 0000000..d4b693e --- /dev/null +++ b/src/function.cc @@ -0,0 +1 @@ +#include "function.h" diff --git a/src/function.h b/src/function.h new file mode 100644 index 0000000..7b2b7dc --- /dev/null +++ b/src/function.h @@ -0,0 +1,11 @@ +#ifndef FUNCTION_H +#define FUNCTION_H +#include "classlist.h" +#include "mymemory.h" +class Function { + public: + + MEMALLOC; + private: +}; +#endif diff --git a/src/hashtable.h b/src/hashtable.h index 5e6ad50..1a0a41e 100644 --- a/src/hashtable.h +++ b/src/hashtable.h @@ -81,7 +81,7 @@ public: capacitymask = initialcapacity - 1; threshold = (unsigned int)(initialcapacity * loadfactor); - size = 0; // Initial number of elements in the hash + size = 0; // Initial number of elements in the hash } /** @brief Hash table destructor */ @@ -327,7 +327,7 @@ public: exit(EXIT_FAILURE); } - table = newtable; // Update the global hashtable upon resize() + table = newtable; // Update the global hashtable upon resize() capacity = newsize; capacitymask = newsize - 1; @@ -353,7 +353,7 @@ public: search->val = bin->val; } - _free(oldtable); // Free the memory of the old hash table + _free(oldtable); // Free the memory of the old hash table } double getLoadFactor() {return loadfactor;} unsigned int getCapacity() {return capacity;} diff --git a/src/mutableset.cc b/src/mutableset.cc new file mode 100644 index 0000000..76bb779 --- /dev/null +++ b/src/mutableset.cc @@ -0,0 +1,2 @@ +#include "mutableset.h" + diff --git a/src/mutableset.h b/src/mutableset.h new file mode 100644 index 0000000..479f16c --- /dev/null +++ b/src/mutableset.h @@ -0,0 +1,9 @@ +#ifndef MUTABLESET_H +#define MUTABLESET_H +#include "set.h" + +class MutableSet : Set { +public: + void addElement(uint64_t element) { members->push_back(element); } +}; +#endif diff --git a/src/mymemory.h b/src/mymemory.h index 58eb953..642ea1d 100644 --- a/src/mymemory.h +++ b/src/mymemory.h @@ -34,7 +34,7 @@ void operator delete[](void *p, size_t size) { \ model_free(p); \ } \ - void * operator new(size_t size, void *p) { /* placement new */ \ + void * operator new(size_t size, void *p) { /* placement new */ \ return p; \ } diff --git a/src/ops.h b/src/ops.h new file mode 100644 index 0000000..40e6f99 --- /dev/null +++ b/src/ops.h @@ -0,0 +1,17 @@ +#ifndef OPS_H +#define OPS_H +enum LogicOp {AND, OR, NOT, XOR, IMPLIES}; +enum ArithOp {ADD, SUB}; +enum CompOp {EQUALS}; +enum OrderType {PARTIAL, TOTAL}; + +/** + * FLAGFORCESOVERFLOW forces the operation to overflow if the boolean flag is true + * OVERFLOWSETSFLAG -- sets the flag if the operation overflows + * FLAGIFFOVERFLOW -- flag is set iff the operation overflows + * IGNORE -- doesn't constrain output if the result cannot be represented + * WRAPAROUND -- wraps around like stand integer arithmetic + */ +enum OverFlowBehavior {IGNORE, WRAPAROUND, FLAGFORCESOVERFLOW, OVERFLOWSETSFLAG, FLAGIFFOVERFLOW}; + +#endif diff --git a/src/order.cc b/src/order.cc new file mode 100644 index 0000000..e69de29 diff --git a/src/order.h b/src/order.h new file mode 100644 index 0000000..32c6c2c --- /dev/null +++ b/src/order.h @@ -0,0 +1,12 @@ +#ifndef ORDER_H +#define ORDER_H +#include "classlist.h" +#include "mymemory.h" + +class Order { + public: + MEMALLOC; + + private: +}; +#endif diff --git a/src/predicate.cc b/src/predicate.cc new file mode 100644 index 0000000..dcec97a --- /dev/null +++ b/src/predicate.cc @@ -0,0 +1 @@ +#include "predicate.h" diff --git a/src/predicate.h b/src/predicate.h new file mode 100644 index 0000000..110cf4d --- /dev/null +++ b/src/predicate.h @@ -0,0 +1,12 @@ +#ifndef PREDICATE_H +#define PREDICATE_H +#include "classlist.h" +#include "mymemory.h" + +class Predicate { + public: + + MEMALLOC; + private: +}; +#endif diff --git a/src/set.cc b/src/set.cc index 2d1c04f..043aece 100644 --- a/src/set.cc +++ b/src/set.cc @@ -1,94 +1,27 @@ -/* - * To change this license header, choose License Headers in Project Properties. - * To change this template file, choose Tools | Templates - * and open the template in the editor. - */ - #include "set.h" #include #include -Node::Node(uint64 val, Node* r, Node* l){ - range=false; - beginOrVal=val; - left = l; - right=r; -} - -Node::Node(uint64 val):Node(val, NULL, NULL){} - -Node::Node(uint64 begin, uint64 end, Node* r, Node* l){ - range=true; - beginOrVal=begin; - this->end= end; - right=r; - left=l; -} - -Node::Node(uint64 begin, uint64 end):Node(begin, end, NULL, NULL){} - -Comparison Node::compare(uint64 val){ - if(range){ - if(val> end) - return GREATER; - else if(val < beginOrVal) - return LESS; - else - return EQUAL; - }else{ - if(val> beginOrVal) - return GREATER; - else if(val< beginOrVal) - return LESS; - else - return EQUAL; - } +Set::Set(VarType t, uint64_t* elements, int num) : + type (t), + isRange(false), + low(0), + high(0), + members(new ModelVector()) { + members->reserve(num); + for(int i=0;ipush_back(elements[i]); } -void Node::addNode(Node* n){ - assert(!n->isRange()); - Comparison comp = compare(n->getBeginOrRange()); - if(comp == GREATER){ - if(right!=NULL) - right->addNode(n); - else - right=n; - }else if(comp == LESS){ - if(left!= NULL) - left->addNode(n); - else - left = n; - } - +Set::Set(VarType t, uint64_t lowrange, uint64_t highrange) : + type(t), + isRange(true), + low(lowrange), + high(highrange), + members(NULL) { } -Set::Set(Type t, uint64* elements, int num){ - type=t; - size=num; - for(int i=0; ilowrange); - type =t; - size = highrange-lowrange+1; - root = new Node(lowrange,highrange); -} - -Set::Set(Type t): type(t), - size(0), - root(NULL) -{ -} - -void Set::addItem(uint64 element){ - Node* n = new Node(element); - if(root==NULL) - root=n; - else - root->addNode(n); -} - - \ No newline at end of file diff --git a/src/set.h b/src/set.h index 81b2dcc..8799208 100644 --- a/src/set.h +++ b/src/set.h @@ -1,10 +1,4 @@ /* - * To change this license header, choose License Headers in Project Properties. - * To change this template file, choose Tools | Templates - * and open the template in the editor. - */ - -/* * File: set.h * Author: hamed * @@ -14,54 +8,24 @@ #ifndef SET_H #define SET_H -#include "types.h" +#include "classlist.h" +#include "stl-model.h" +#include "mymemory.h" -enum Comparison{LESS, EQUAL, GREATER}; +class Set { +public: + Set(VarType t, uint64_t * elements, int num); + Set(VarType t, uint64_t lowrange, uint64_t highrange); + ~Set(); -class Node{ + MEMALLOC; private: - bool range; - // If it isn't a range, begin contains the actual value of the element - uint64 beginOrVal; - uint64 end; - Node* right; - Node* left; -public: - Node(uint64 val, Node* r, Node* l); - Node(uint64 val); - Node(uint64 begin, uint64 end, Node* r, Node* l); - Node(uint64 begin, uint64 end); - bool isRange(){return range;} - uint64 getBeginOrRange(){return beginOrVal;} - Comparison compare(uint64 val); - /** - * Searches the tree, if new node exists in the tree ( whether its value - * is in range of another node, or there is another node with the value of - * node n) this function just returns! - * @param n - */ - void addNode(Node* n); -}; -// For now, we can consider it as a simple binary tree, but we can have fancier -// trees for future -class Set{ - Type type; - uint64 size; - Node* root; - Set(Type t, uint64 * elements, int num); - Set(Type t, uint64 lowrange, uint64 highrange); - Set(Type t); - /** - * For know all sets are considered to be mutable, we can change it later on - * if it was necessary. - * @param set - * @param element - */ - void addItem(uint64 element); - ELEMENT* createUniqueItem(Set * set); + VarType type; + bool isRange; + uint64_t low, high; +protected: + ModelVector *members; }; - - -#endif /* SET_H */ +#endif/* SET_H */ diff --git a/src/table.cc b/src/table.cc new file mode 100644 index 0000000..e89d72a --- /dev/null +++ b/src/table.cc @@ -0,0 +1 @@ +#include "table.h" diff --git a/src/table.h b/src/table.h new file mode 100644 index 0000000..96f719d --- /dev/null +++ b/src/table.h @@ -0,0 +1,11 @@ +#ifndef TABLE_H +#define TABLE_H +#include "classlist.h" +#include "mymemory.h" + +class Table { + public: + MEMALLOC; + private: +}; +#endif diff --git a/src/types.h b/src/types.h deleted file mode 100644 index 487fb5f..0000000 --- a/src/types.h +++ /dev/null @@ -1,34 +0,0 @@ -/* - * To change this license header, choose License Headers in Project Properties. - * To change this template file, choose Tools | Templates - * and open the template in the editor. - */ - -/* - * File: Type.h - * Author: hamed - * - * Created on June 13, 2017, 1:33 PM - */ - -#ifndef TYPE_H -#define TYPE_H - -#ifdef __cplusplus -extern "C" { -#endif - -typedef unsigned long int uint64; -typedef uint64 Type; - -struct Element{ - uint64 value; -}; - -typedef struct Element ELEMENT; -#ifdef __cplusplus -} -#endif - -#endif /* TYPE_H */ - -- 2.34.1