Initial mark/sweep GC and infrastructure.
authorethereal <ethereal@ethv.net>
Wed, 22 Oct 2014 02:48:27 +0000 (19:48 -0700)
committerethereal <ethereal@ethv.net>
Wed, 22 Oct 2014 02:48:27 +0000 (19:48 -0700)
There is likely a bug somewhere in the code, as the refcounts are off.

doc/objects [new file with mode: 0644]
src/main.cpp
src/object/object.cpp
src/object/object.hpp
src/object/property.hpp
src/object/ref.hpp [new file with mode: 0644]
src/object/store.cpp [new file with mode: 0644]
src/object/store.hpp
src/object/structure.hpp

diff --git a/doc/objects b/doc/objects
new file mode 100644 (file)
index 0000000..711518b
--- /dev/null
@@ -0,0 +1,9 @@
+Some notes on how objects are referenced:
+- Direct object use should be limited to within a function scope when possible,
+    or at most between private helper functions in a single class. Any time an
+    object is passed around between modules, an object::ref should be used
+    instead.
+- Object IDs should not be used except by object:: namespace code. object::ref
+    instances are lightweight enough. Using them as hashing keys is acceptable,
+    or as unique identifiers for the purposes of human pretty-printing.
+- 
index 9d24a3c..bbe804a 100644 (file)
@@ -23,50 +23,36 @@ public:
     std::string val;
 };
 
-class adj_list : object::property {};
+class adj_list : public object::property {};
 class adj2_list : object::property {};
 class wadj_list : public int_prop {
 public:
     wadj_list(int v) : int_prop(v) {}
 };
 
+void dump_all(const char *why, object::store &st) {
+    core::strstream ss;
+    st.dump_all(ss);
+    std::cout << why << std::endl << ss.operator std::string() << std::endl;
+}
+
 int main(int core_unused argc, const char core_unused *argv[]) {
     object::store st;
-    object::object obj1 = st.make(), obj2 = st.make();
-
-    obj1.set(int_prop());
-    obj2.set(str_prop());
-
-    if(object::filter<int_prop>::matches(obj1)) std::cout << "obj1 has int" << std::endl;
-    if(object::filter<int_prop>::matches(obj2)) std::cout << "obj2 has int" << std::endl;
-
-    obj1.set(str_prop());
-
-    if(object::filter<int_prop,str_prop>::matches(obj1)) std::cout << "obj1 has int/str" << std::endl;
-    if(object::filter<int_prop,str_prop>::matches(obj2)) std::cout << "obj2 has int/str" << std::endl;
+    object::ref o1 = st.make();
+    object::ref o2 = st.make();
 
     using astruct = object::structure<adj_list>;
-    astruct::make_link(obj1, obj2);
-
-    if(astruct::is_linked(obj1, obj2)) std::cout << "obj1 -> obj2 linked" << std::endl;
-    if(astruct::is_linked(obj2, obj1)) std::cout << "obj2 -> obj1 linked" << std::endl;
-
-    using a2struct = object::structure<adj_list>;
-    astruct::make_link(obj2, obj2);
-    if(a2struct::is_linked(obj2, obj2)) std::cout << "obj2 -> obj2 2linked" << std::endl;
-
-    using wstruct = object::structure<wadj_list>;
-    wstruct::make_link(obj1, obj2, std::move(wadj_list(42)));
-
-    std::cout << "obj1 -> obj2 link weight: " << wstruct::get_link(obj1, obj2).val << std::endl;
-
-    auto astruct2 = object::structure2<adj_list>();
-
-    astruct2.add_link(obj1, obj2);
 
-    auto astruct3 = object::structure3<adj_list>(st);
+    dump_all("Before structure", st);
+    {
+        astruct as(st);
+        as.make_link(o1, o2);
 
-    astruct3.make_link(obj1.id(), obj2.id());
+        dump_all("During structure", st);
+    }
+    dump_all("After structure", st);
+    st.gc();
+    dump_all("After GC", st);
 
     return 0;
 }
index f2461ae..5a2d09e 100644 (file)
@@ -2,4 +2,6 @@
 
 namespace object {
 
+constexpr object::id_t object::invalid_id;
+
 } // namespace object
index aaf0ed2..44415ea 100644 (file)
@@ -8,27 +8,29 @@
 #include <type_traits>
 
 #include <core/strstream.hpp>
+#include <core/typename.hpp>
 
 #include "property.hpp"
 
 namespace object {
 
 class store;
+class ref;
 
 class object {
 public:
     using id_t = long;
+    static constexpr id_t invalid_id = -1;
 private:
     std::unordered_map<std::type_index, boost::any> m_properties;
+    std::unordered_map<std::type_index, std::function<void (core::strstream &, boost::any &)>> m_dump_helpers;
+    //std::unordered_map<std::type_index, void (core::strstream &, boost::any &)> m_dump_helpers;
     id_t m_id;
-    int m_refcount;
+    friend class ref;
     store &m_store;
 private:
     friend class store;
-    object(store &store, id_t id) : m_id(id), m_refcount(1), m_store(store) {}
-
-    void inc() { m_refcount ++; }
-    bool dec() { m_refcount --; return m_refcount == 0; }
+    object(store &store, id_t id) : m_id(id), m_store(store) {}
 public:
     id_t id() const { return m_id; }
 
@@ -60,11 +62,32 @@ public:
         return *get_raw<T>();
     }
 
+
     template<typename T>
     bool set(T && v) {
+        std::function<void (core::strstream &, boost::any &)> wrapper_fct(dump_wrapper<T>);
+        m_dump_helpers[std::type_index(typeid(T))] = wrapper_fct;
         return m_properties.insert(
             std::make_pair(std::type_index(typeid(T)), v)).second;
     }
+
+    void dump(core::strstream &into) {
+        into << "[Object " << m_id << "] = {";
+        bool first = true;
+        for(auto &prop : m_properties) {
+            if(!first) into << ", ";
+            else first = false;
+            into << core::demangle(prop.second.type().name()) << " = (";
+            m_dump_helpers[prop.second.type()](into, prop.second);
+            into << ")";
+        }
+        into << "}";
+    }
+private:
+    template<typename T>
+    static void dump_wrapper(core::strstream &s, boost::any &p) {
+        boost::any_cast<T>(p).dump(s);
+    }
 };
 
 } // namespace object
index 78b1fa4..6a3df06 100644 (file)
@@ -1,11 +1,15 @@
 #ifndef OBJECT_PROPERTY_HPP
 #define OBJECT_PROPERTY_HPP
 
+#include <core/strstream.hpp>
+
 namespace object {
 
 class property {
 public:
     virtual ~property() = default;
+
+    virtual void dump(core::strstream &) {}
 };
 
 } // namespace object
diff --git a/src/object/ref.hpp b/src/object/ref.hpp
new file mode 100644 (file)
index 0000000..e3cbefa
--- /dev/null
@@ -0,0 +1,54 @@
+#ifndef OBJECT_REF_HPP
+#define OBJECT_REF_HPP
+
+#include "object.hpp"
+#include "store.hpp"
+
+namespace object {
+
+class store;
+
+class ref {
+private:
+    store &m_store;
+    object::id_t m_context;
+    object &m_target;
+public:
+    /** Constructs an outside reference to the given object. */
+    ref(const object &object) : m_store(object.m_store),
+        m_context(object::invalid_id), m_target(m_store.get(object.id()))
+        { cons(); }
+    /** Constructs an inside reference to the target from the given context. */
+    ref(const object &context, const object &target) :
+        m_store(context.m_store), m_context(context.id()),
+        m_target(m_store.get(target.id()))
+        { check_same(context, target); cons(); }
+    ref(const ref &context, const ref &target) : ref(*context, *target) {}
+    ref(const object &context, const ref &target) : ref(context, *target) {}
+    ref(const ref &context, const object &target) : ref(*context, target) {}
+    /** Copy constructor. */
+    ref(const ref &other) : m_store(other.m_store), m_target(other.m_target) {
+        m_context = other.m_context;
+        cons();
+    }
+    ~ref() { dcon(); }
+
+    object::id_t context() const { return m_context; }
+    object::id_t target() const { return m_target.id(); }
+
+    object *operator->() const { return &m_target; }
+    object &operator*() { return m_target; }
+    const object &operator*() const { return m_target; }
+private:
+    inline void check_same(const object &a, const object &b) {
+        if(&a.m_store != &b.m_store) 
+            throw std::runtime_error("Can only have reference context from "
+                "same object store as target");
+    }
+    inline void cons() { m_store.add_ref(m_context, m_target.id()); }
+    inline void dcon() { m_store.remove_ref(m_context, m_target.id()); }
+};
+
+} // namespace object
+
+#endif
diff --git a/src/object/store.cpp b/src/object/store.cpp
new file mode 100644 (file)
index 0000000..f2df29e
--- /dev/null
@@ -0,0 +1,51 @@
+#include <iostream>
+#include <queue>
+
+#include "store.hpp"
+#include "ref.hpp"
+
+namespace object {
+
+ref store::make() {
+    object::id_t id = m_lastid ++;
+
+    return ref(m_objects.insert(std::make_pair(id,
+        object(*this, id))).first->second);
+}
+
+void store::gc() {
+    std::queue<object::id_t> tovisit;
+    tovisit.push(object::invalid_id);
+
+    std::set<object::id_t> seen;
+    seen.insert(object::invalid_id);
+
+    while(tovisit.size() > 0) {
+        object::id_t next = tovisit.front(); tovisit.pop();
+        
+        for(auto it : m_refs[next]) {
+            if(seen.count(it.first)) continue;
+            seen.insert(it.first);
+            tovisit.push(it.first);
+        }
+    }
+
+    std::vector<object::id_t> todestroy;
+    for(auto it : m_objects) {
+        std::cout << "object " << it.first << " count: " << seen.count(it.first) << std::endl;
+        if(seen.count(it.first)) continue;
+        else {
+            todestroy.push_back(it.first);
+        }
+    }
+    for(auto id : todestroy) destroy(id);
+}
+
+void store::dump_all(core::strstream &into) {
+    for(auto &object : m_objects) {
+        object.second.dump(into);
+        into << "\n";
+    }
+}
+
+} // namespace object
index 4fc7168..0659fd7 100644 (file)
@@ -2,29 +2,32 @@
 #define OBJECT_STORE_HPP
 
 #include <map>
+#include <set>
 
 #include "object.hpp"
 
 namespace object {
 
+class ref;
+
 class store {
 private:
     std::map<object::id_t, object> m_objects;
+    //std::map<std::pair<object::id_t, object::id_t>, int> m_refs;
+    std::map<object::id_t, std::map<object::id_t, int>> m_refs;
     object::id_t m_lastid;
 protected:
-    friend class object;
-    void destroy(object::id_t id) {
-        if(m_objects.count(id) == 0)
-            throw std::runtime_error("Object does not exist in store");
-        m_objects.erase(m_objects.find(id));
+    // keep these functions hidden to prevent them from being misused.
+    friend class ref;
+    void add_ref(object::id_t context, object::id_t target) {
+        std::cout << "adding reference between " << context << " and " << target << std::endl;
+        m_refs[context][target] ++;
     }
-public:
-    store() : m_lastid(1) {}
-
-    object &make() {
-        object::id_t id = m_lastid ++;
-        return m_objects.insert(
-            std::make_pair(id, object(*this, id))).first->second;
+    void remove_ref(object::id_t context, object::id_t target) {
+        std::cout << "removing reference between " << context << " and " << target << std::endl;
+        m_refs[context][target] --;
+        if(m_refs[context][target] == 0) m_refs[context].erase(target);
+        if(m_refs[context].size() == 0) m_refs.erase(context);
     }
 
     object &get(object::id_t id) {
@@ -33,19 +36,19 @@ public:
         return m_objects.find(id)->second;
     }
 
-    const object &get(object::id_t id) const {
+    void destroy(object::id_t id) {
         if(m_objects.count(id) == 0)
             throw std::runtime_error("Object does not exist in store");
-        return m_objects.find(id)->second;
+        m_objects.erase(m_objects.find(id));
     }
+public:
+    store() : m_lastid(1) {}
 
-    void inc(object::id_t id) {
-        get(id).inc();
-    }
+    ref make();
 
-    void dec(object::id_t id) {
-        if(get(id).dec()) destroy(id);
-    }
+    void gc();
+
+    void dump_all(core::strstream &into);
 };
 
 } // namespace object
index 53f92e3..2501850 100644 (file)
 #include "object.hpp"
 #include "property.hpp"
 #include "store.hpp"
+#include "ref.hpp"
 
 namespace object {
 
 class property;
 
-template<typename link_type>
-class structure2 {
-private:
-    std::map<object::id_t, std::map<object::id_t, link_type>> m_links;
-public:
-    void add_link(const object &from, const object &to,
-        link_type &&link = link_type()) {
-
-        add_link(from.id(), to.id(), std::move(link));
-    }
-
-    void add_link(object::id_t from, object::id_t to,
-        link_type &&link = link_type()) {
-        m_links[from][to] = link;
-    }
-    
-    bool has_link(const object &from, const object &to) const
-        { return has_link(from.id(), to.id()); }
-
-    bool has_link(object::id_t from, object::id_t to) const {
-        if(m_links.count(from) == 0) return false;
-        const auto &imap = m_links.find(from)->second;
-        return imap.find(to) != imap.end();
-    }
-
-    link_type &link(object &from, object &to) {
-        if(!has_link(from.id(), to.id()))
-            throw std::runtime_error("No structural link between requested objects");
-
-        return m_links[from][to];
-    }
+namespace helpers {
 
-    const link_type &link(object &from, object &to) const {
-        if(!has_link(from.id(), to.id()))
-            throw std::runtime_error("No structural link between requested objects");
-        
-        return m_links.find(from)->second.find(to)->second;
-    }
-
-    void remove_link(object &from, object &to) {
-        if(!has_link(from.id(), to.id()))
-            throw std::runtime_error("Cannot remove nonexistent edge.");
-    }
+struct per_structure {
+    std::map<object::id_t, ref> links;
 };
 
-template<typename fundamental>
-class structure {
-private:
-    class link_t {
-        object &obj;
-        fundamental property;
-        link_t(object &obj, fundamental && property) : obj(obj), property(std::move(property)) {}
-        friend class structure<fundamental>;
-    };
-    class adj_t : property {
-        std::map<object::id_t, link_t> m_links;
-        friend class structure<fundamental>;
-    };
+struct structure_property : public property {
 public:
-    static bool make_link(object &from, object &target, fundamental && property = fundamental()) {
-        if(!from.has<adj_t>()) from.set(adj_t());
-        auto &links = from.get<adj_t>().m_links;
-        // already present?
-        auto it = links.find(target.id());
-        if(it != links.end()) return false;
-
-        links.insert(std::make_pair(target.id(), link_t(target, std::move(property))));
-
-        return true;
-    }
-
-    static bool is_linked(object &from, object &target) {
-        if(!from.has<adj_t>()) return false;
-        return from.get<adj_t>().m_links.count(target.id()) == 1;
-    }
-
-    static fundamental &get_link(object &from, object &target) {
-        auto &links = from.get<adj_t>().m_links;
-        auto it = links.find(target.id());
-        if(it == links.end()) throw std::runtime_error("no such link");
-
-        return it->second.property;
+    std::map<object::id_t, per_structure> ps;
+
+    virtual void dump(core::strstream &into) {
+        bool first = true;
+        for(auto p : ps) {
+            if(!first) into << ", ";
+            else first = false;
+
+            into << p.first << " -> [";
+            bool f2 = true;
+            for(auto l : p.second.links) {
+                if(!f2) into << ", ";
+                else f2 = false;
+                into << l.first << ": " << l.second->id();
+            }
+            into << "]";
+        }
     }
 };
 
-// object.structure_property[structure ID][destination ID] = edge object ID
-class structure_property : property,
-    public std::map<object::id_t, std::map<object::id_t, object::id_t>> {};
+} // namespace helpers
 
 template<typename linkinfo_t>
-class structure3 {
-private:
-    class link_t : public property {
-    public:
-        
-    };
+class structure {
 private:
     store &m_store;
-    object::id_t m_rootobj;
+    ref m_rootobj;
 public:
-    structure3(store &store) : m_store(store) {
-        m_rootobj = store.make().id();
+    structure(store &store) : m_store(store), m_rootobj(store.make()) {}
+
+    void make_link(const ref &from, const ref &to,
+        linkinfo_t &&property = linkinfo_t()) {
+        
+        // if it doesn't have a structure property yet, add one.
+        if(!from->has<helpers::structure_property>())
+            from->set(helpers::structure_property());
+        // if it doesn't have a link object for this structure, add one.
+        auto &str = from->get<helpers::structure_property>();
+        auto it = str.ps.find(m_rootobj->id());
+        if(it == str.ps.end()) {
+            str.ps.insert(std::make_pair(m_rootobj->id(),
+                helpers::per_structure()));
+            it = str.ps.find(m_rootobj->id());
+        }
+
+        // create a link object and insert it into the data structures.
+        ref link = m_store.make();
+        link->set(property);
+        // note that the reference is from the root object.
+        it->second.links.insert(std::make_pair(to->id(), ref(m_rootobj, link)));
     }
 
+    /*
     void make_link(object::id_t from, object::id_t to,
         linkinfo_t && property = linkinfo_t()) {
         
@@ -133,20 +91,7 @@ public:
         lobject.set(property);
 
         it->second.insert(std::make_pair(to, lobject.id()));
-    }
-
-    linkinfo_t &get_link(object::id_t from, object::id_t to) {
-        // if it doesn't have a structure property yet, add one.
-        object &fobj = m_store.get(from);
-        if(!fobj.has<structure_property>()) fobj.set(structure_property());
-        // if it doesn't have a link object for this structure, add one.
-        auto &str = fobj.get<structure_property>();
-        auto it = str.find(m_rootobj);
-        if(it == str.end()) {
-            str.insert(std::make_pair(m_rootobj, std::map<object::id_t, object::id_t>()));
-            it = str.find(m_rootobj);
-        }
-    }
+    }*/
 };
 
 } // namespace object