diff options
| -rw-r--r-- | cells-impl.hpp | 212 | ||||
| -rw-r--r-- | cells-test.cpp | 63 | ||||
| -rw-r--r-- | cells.hpp | 87 | ||||
| -rw-r--r-- | dynvars-impl.hpp | 80 | ||||
| -rw-r--r-- | dynvars-test.cpp | 39 | ||||
| -rw-r--r-- | dynvars.hpp | 46 | ||||
| -rw-r--r-- | makefile | 19 |
7 files changed, 546 insertions, 0 deletions
diff --git a/cells-impl.hpp b/cells-impl.hpp new file mode 100644 index 0000000..893d51c --- /dev/null +++ b/cells-impl.hpp @@ -0,0 +1,212 @@ +// Copyright 2012, Matthias Andreas Benkard. + +#pragma once + +#ifndef CELLS_IMPL_HPP +#define CELLS_IMPL_HPP + +#include "cells.hpp" + +#include "dynvars.hpp" + +#include <exception> +#include <stdexcept> +#include <functional> +#include <memory> +#include <unordered_map> +#include <unordered_set> +#include <forward_list> +#include <deque> + +#ifndef thread_local +//#define thread_local __thread +#define thread_local +#endif + +namespace cells { + using std::cout; + using std::cerr; + using std::endl; + + using namespace dynvars; + + struct dag_node { + dag_node(std::shared_ptr<observer> item_) : item(item_) { } + std::shared_ptr<observer> item; + std::unordered_set<dag_node*> incoming_edges; + std::unordered_set<dag_node*> outgoing_edges; + }; + + struct transaction { + std::unordered_map<std::shared_ptr<observer>, std::shared_ptr<dag_node>> dag; + }; + + static thread_local dynvar<std::forward_list<std::shared_ptr<observer>>> current_dependencies; + static thread_local dynvar<transaction> current_transaction; + + void observer::clear_dependencies() { + for (auto const& dep : dependencies) { + dep->remove_dependent(this); + } + dependencies = {}; + } + + void observer::add_dependent(std::shared_ptr<observer> dependent) { + dependents.push_front(dependent); + } + + void observer::remove_dependent(observer* dependent) { + dependents.remove_if([&](std::weak_ptr<observer> const& other) -> bool { + std::shared_ptr<observer> other2 = other.lock(); + // note: this should also work for empty other + return (other2.get() == dependent); + }); + } + + void observer::reset_dependencies(std::forward_list<std::shared_ptr<observer>> const& newdeps) { + clear_dependencies(); + dependencies = newdeps; + for (auto const& dep : newdeps) { + dep->add_dependent(shared_from_this()); + } + } + + void observer::mark() { + if (!current_transaction) { + with_transaction([&]() { this->mark(); }); + return; + } + std::shared_ptr<observer> self = shared_from_this(); + if (current_transaction->dag.find(self) == + current_transaction->dag.end()) { + std::unordered_set<dag_node*> incoming_edges; + std::unordered_set<dag_node*> outgoing_edges; + std::shared_ptr<dag_node> node = std::make_shared<dag_node>(self); + current_transaction->dag[self] = std::shared_ptr<dag_node>(node); + for (std::weak_ptr<observer> x : dependents) { + std::shared_ptr<observer> px = x.lock(); + if (px) { + px->mark(); + std::shared_ptr<dag_node> xn = current_transaction->dag[px]; + xn->incoming_edges.insert(node.get()); + node->outgoing_edges.insert(xn.get()); + } + } + } + } + + observer::~observer() { + clear_dependencies(); + } + + template <typename T> + cell<T>::cell() { + } + + template <typename T> + void cell<T>::update() { + T oldval = current_value; + with<std::forward_list<std::shared_ptr<observer>>, void> + (current_dependencies, + std::forward_list<std::shared_ptr<observer>>(), + [=]{ + current_value = recompute(current_value); + reset_dependencies(*current_dependencies); + }); + } + + template <typename T> + T& cell<T>::get() { + if (current_dependencies) { + current_dependencies->push_front(shared_from_this()); + return current_value; + } else { + return current_value; + } + } + + template <typename T> + cell<T>::~cell() { + } + + template <typename T> + T formula_cell<T>::recompute(T old) { + return alt_formula(old); + } + + template <typename T> + T formula_cell<T>::init() { + return formula(); + } + + template <typename T> + void formula_cell<T>::reset(T value) { + this->alt_formula = ([=](T) { return value; }); + this->formula = ([=]() { return value; }); + this->mark(); + } + + template <typename T> + void formula_cell<T>::reset(std::function<T ()> formula) { + this->formula = formula; + this->alt_formula = ([=](T old) { return formula(); }); + this->mark(); + } + + template <typename T> + void formula_cell<T>::reset(std::function<T ()> formula, + std::function<T (T)> alt_formula) { + this->formula = formula; + this->alt_formula = alt_formula; + this->mark(); + } + + template <typename T> + formula_cell<T>::~formula_cell() { + } + + void with_transaction(std::function<void ()> thunk) { + using std::cout; + using std::cerr; + using std::endl; + with<transaction, void>(current_transaction, transaction(), [&]() -> void { + //cerr << "; transaction." << endl; + thunk(); + + //cerr << "; affected nodes: " << current_transaction->dag.size() << endl; + std::deque<std::shared_ptr<observer>> nodes; + + // topological sort + std::forward_list<dag_node*> independent_nodes; + auto left = current_transaction->dag.size(); + + for (auto const& o_and_n : current_transaction->dag) { + auto node = o_and_n.second; + if (node->incoming_edges.size() == 0) { + independent_nodes.push_front(node.get()); + } + } + while (!independent_nodes.empty()) { + left--; + auto node = independent_nodes.front(); + independent_nodes.pop_front(); + nodes.push_back(node->item); + for (dag_node* other : node->outgoing_edges) { + other->incoming_edges.erase(node); + if (other->incoming_edges.size() == 0) { + independent_nodes.push_front(other); + } + } + } + if (left != 0) { + throw std::logic_error("Cell cycle detected"); + } + + for (auto const& node : nodes) { + node->update(); + } + }); + } +} + +#endif //CELLS_IMPL_HPP diff --git a/cells-test.cpp b/cells-test.cpp new file mode 100644 index 0000000..6905054 --- /dev/null +++ b/cells-test.cpp @@ -0,0 +1,63 @@ +// Copyright 2012, Matthias Andreas Benkard. + +#include "cells.hpp" + +#include <memory> +#include <iostream> + +struct unit { }; + +using namespace cells; +using std::cout; +using std::endl; + +typedef formula_cell<double> fcell; +typedef shared_ptr<fcell> sfcell; +typedef formula_cell<unit> ucell; +typedef shared_ptr<ucell> sucell; + +int main(int argc, char** argv) { + sfcell x0 = fcell::make(); + sfcell x1 = fcell::make(); + sfcell x2 = fcell::make(); + sfcell y = fcell::make(); + sfcell z = fcell::make(); + sucell a = ucell::make(); + sucell b = ucell::make(); + + with_transaction([=](){ + x0->reset(10); + x1->reset([=](){ return *x0 + 5; }); + x2->reset([=](){ return *x0 * 2; }); + y->reset([=](){ return *x1 * *x2; }); + z->reset([=](){ return *x0 * *y; }); + a->reset([=]() -> unit { cout << "z is now " << *z << "." << endl; return unit(); }); + b->reset([=]() -> unit { cout << "x2 is now " << *x2 << "." << endl; return unit(); }); + }); + + x0->reset(15); + x0->reset(-20); + y->reset(-3); + x1->reset([=]() { return (double)*x0; }); + y->reset([=]() { return *x1 + *x2; }); +} + + +/* + * z + * |\ + * | \ + * | \ + * | \ + * | \ + * | \ + * | \ + * | y + * | /| + * | / | + * | / | + * | x1 x2 + * | / | + * | / | + * x0------+ + */ diff --git a/cells.hpp b/cells.hpp new file mode 100644 index 0000000..27b3633 --- /dev/null +++ b/cells.hpp @@ -0,0 +1,87 @@ +// Copyright 2012, Matthias Andreas Benkard. + +#pragma once + +#ifndef CELLS_HPP +#define CELLS_HPP + +#include <functional> +#include <memory> +#include <forward_list> +#include <algorithm> + +namespace cells { + + class observer : public virtual std::enable_shared_from_this<observer> { + private: + std::forward_list<std::weak_ptr<observer>> dependents; + std::forward_list<std::shared_ptr<observer>> dependencies; + + void clear_dependencies(); + void mark_dependents(); + + protected: + void mark(); + + public: + void add_dependent(std::shared_ptr<observer> dependent); + void remove_dependent(observer* dependent); + void reset_dependencies(std::forward_list<std::shared_ptr<observer>> const& newdeps); + + virtual void update() = 0; + + virtual ~observer(); + }; + + + template <typename T> + class cell : public observer { + private: + T current_value; + + protected: + cell(); + virtual void update(); + virtual T recompute(T) = 0; + virtual T init() = 0; + + public: + T& get(); + T& operator *() { return get(); } + //T operator ()() { return get(); } + operator T() { return get(); } + + virtual ~cell(); + }; + + + template <typename T> + class formula_cell : public cell<T> { + //friend class std::shared_ptr<formula_cell<T>>; + //friend std::shared_ptr<formula_cell<T>> std::make_shared<formula_cell<T>>(); + private: + std::function<T ()> formula; + std::function<T (T old)> alt_formula; + + protected: + formula_cell() { } + virtual T recompute(T); + virtual T init(); + + public: + //static std::shared_ptr<formula_cell<T>> make() { return std::make_shared<formula_cell<T>>(); } + static std::shared_ptr<formula_cell<T>> make() { return std::shared_ptr<formula_cell<T>>(new formula_cell()); } + + void reset(T value); + void reset(std::function<T ()>); + void reset(std::function<T ()>, std::function<T (T old)>); + + virtual ~formula_cell(); + }; + + void with_transaction(std::function<void ()>); +} + +#endif //CELLS_HPP + +#include "cells-impl.hpp" diff --git a/dynvars-impl.hpp b/dynvars-impl.hpp new file mode 100644 index 0000000..5890888 --- /dev/null +++ b/dynvars-impl.hpp @@ -0,0 +1,80 @@ +// Copyright 2012, Matthias Andreas Benkard. + +#pragma once + +#ifndef DYNVARS_IMPL_HPP +#define DYNVARS_IMPL_HPP + +#include <cstdlib> +#include <cstdio> +#include <iostream> +#include <functional> +#include <memory> +#include <future> +#include <list> + +#include "dynvars.hpp" + +namespace dynvars { + +using namespace ::std; + +template <typename T> +dynvar<T>::dynvar(T val) { + this->push(val); +} + +template <typename T> +dynvar<T>& dynvar<T>::operator =(T val) { + if (!value_stack.empty()) { + this->pop(); + } + this->push(val); + return *this; +} + +template <typename T> +void dynvar<T>::push(T val) { + value_stack.push_front(val); +} + +template <typename T> +void dynvar<T>::pop() { + value_stack.pop_front(); +} + +template <typename T> +dynvar<T>::operator bool() const { + return !value_stack.empty(); +} + +template <typename T> +T& dynvar<T>::operator *() { + return value_stack.front(); +} + +template <typename T> +T* dynvar<T>::operator ->() { + return &value_stack.front(); +} + +template <typename R> +dyn<R>::dyn(dynvar<R>& var, R val) : myvar(var) { + myvar.push(val); +} + +template <typename R> +dyn<R>::~dyn() { + myvar.pop(); +} + +template <typename R, typename T> +T +with(dynvar<R>& var, R val, function<T ()> f) { + dyn<R> d_(var, val); + return f(); +} + +} + +#endif //DYNVARS_IMPL_HPP diff --git a/dynvars-test.cpp b/dynvars-test.cpp new file mode 100644 index 0000000..c80a7ca --- /dev/null +++ b/dynvars-test.cpp @@ -0,0 +1,39 @@ +#include <cstdlib> +#include <cstdio> +#include <iostream> +#include <functional> +#include <memory> +#include <future> + +#include "dynvars.hpp" + +#include <boost/signals2.hpp> + +using namespace ::std; +using namespace ::boost::signals2; +using namespace ::dynvars; + +#define thread_local __thread +thread_local dynvar<string> greetee; + +function<void ()> +make_greeter(const string& greeting) { + return [=]() { + cout << greeting << " " << *greetee << "!" << endl; + }; +}; + +int +main(int argc, char **argv) { + greetee = "nobody"; + signal<void ()> sig; + + sig.connect(make_greeter("Hi")); + + sig(); + with<string, void>(greetee, "luser", [&](){ sig(); }); + with<string, void>(greetee, "geek", [&](){ sig(); }); + sig(); + + return EXIT_SUCCESS; +} diff --git a/dynvars.hpp b/dynvars.hpp new file mode 100644 index 0000000..fbe852a --- /dev/null +++ b/dynvars.hpp @@ -0,0 +1,46 @@ +// Copyright 2012, Matthias Andreas Benkard. + +#pragma once + +#ifndef DYNVARS_HPP +#define DYNVARS_HPP + +#include <functional> +#include <list> + +#define thread_local __thread + +namespace dynvars { + +template <typename T> +class dynvar { +private: + std::list<T> value_stack; +public: + dynvar() { }; + dynvar(T val); + dynvar<T>& operator =(T val); + void push(T val); + void pop(); + T& operator *(); + T* operator ->(); + operator bool() const; +}; + +template <typename R> +class dyn { + dynvar<R>& myvar; +public: + dyn(dynvar<R>& var, R val); + ~dyn(); +}; + +template <typename R, typename T> +T +with(dynvar<R>& var, R val, std::function<T ()> f); + +} + +#endif //DYNVARS_HPP + +#include "dynvars-impl.hpp" diff --git a/makefile b/makefile new file mode 100644 index 0000000..9848e0c --- /dev/null +++ b/makefile @@ -0,0 +1,19 @@ +CXX = clang++ +CXXFLAGS = -g -O0 -stdlib=libc++ -std=c++11 + +.PHONY: all clean distclean + +all: cells-test dynvars-test + +dynvars-test: dynvars-test.cpp dynvars.hpp dynvars-impl.hpp + $(CXX) $(CXXFLAGS) dynvars-test.cpp -o dynvars-test + +cells-test: cells-test.cpp dynvars.hpp dynvars-impl.hpp cells.hpp cells-impl.hpp + $(CXX) $(CXXFLAGS) cells-test.cpp -o cells-test + +clean: + rm -f dynvars-test cells-test + rm -rf dynvars-test.dSYM cells-test.dSYM + +distclean: clean + rm -f *~ |