From 53de92ca887e4386d8d6acb462be4e4a7978a90b Mon Sep 17 00:00:00 2001
From: Matthias Andreas Benkard <code@mail.matthias.benkard.de>
Date: Sun, 9 Dec 2012 09:34:27 +0100
Subject: Initial check-in.

---
 cells-impl.hpp | 212 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 212 insertions(+)
 create mode 100644 cells-impl.hpp

(limited to 'cells-impl.hpp')

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
-- 
cgit v1.2.3