[gjs: 1/2] object: Embed wrapped object list into ObjectInstance

[Philip Chimento <pchimento src gnome org>]

commit 27f5405f6a48286ad70904c626a49ba52a40990c
Author: Carlos Garnacho <carlosg gnome org>
Date:   Mon Apr 9 19:01:57 2018 +0200

    object: Embed wrapped object list into ObjectInstance
    
    Replace the usage of std::set by making ObjectInstance keep links to the
    previous/next ObjectInstance. This makes insertion/removal O(1), while
    keeping the O(n) behavior when objects are checked en masse, and reduces
    memory overhead since we now need 2 pointers per object instead of
    a full node in a R-B tree plus per-node malloc overhead.
    
    https://gitlab.gnome.org/GNOME/gjs/issues/142
    
    Closes: #142

 gi/object.cpp | 127 +++++++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 107 insertions(+), 20 deletions(-)
---
diff --git a/gi/object.cpp b/gi/object.cpp
index a927b645..6d4e1bfe 100644
--- a/gi/object.cpp
+++ b/gi/object.cpp
@@ -54,6 +54,65 @@
 #include <util/log.h>
 #include <girepository.h>
 
+typedef class GjsListLink GjsListLink;
+typedef struct ObjectInstance ObjectInstance;
+
+static GjsListLink* object_instance_get_link(ObjectInstance *priv);
+
+class GjsListLink {
+ private:
+    ObjectInstance *m_prev;
+    ObjectInstance *m_next;
+
+ public:
+    ObjectInstance* prev() {
+        return m_prev;
+    }
+
+    ObjectInstance* next() {
+        return m_next;
+    }
+
+    void prepend(ObjectInstance *this_instance,
+                 ObjectInstance *head) {
+        GjsListLink *elem = object_instance_get_link(head);
+
+        g_assert(object_instance_get_link(this_instance) == this);
+
+        if (elem->m_prev) {
+            GjsListLink *prev = object_instance_get_link(elem->m_prev);
+            prev->m_next = this_instance;
+            this->m_prev = elem->m_prev;
+        }
+
+        elem->m_prev = this_instance;
+        this->m_next = head;
+    }
+
+    void unlink() {
+        if (m_prev)
+            object_instance_get_link(m_prev)->m_next = m_next;
+        if (m_next)
+            object_instance_get_link(m_next)->m_prev = m_prev;
+
+        m_prev = m_next = NULL;
+    }
+
+    int size() {
+        GjsListLink *elem = this;
+        int count = 0;
+
+        do {
+            count++;
+            if (!elem->m_next)
+                break;
+            elem = object_instance_get_link(elem->m_next);
+        } while (elem);
+
+        return count;
+    }
+};
+
 struct ObjectInstance {
     GIObjectInfo *info;
     GObject *gobj; /* NULL if we are the prototype and not an instance */
@@ -68,6 +127,8 @@ struct ObjectInstance {
        prototypes) */
     GTypeClass *klass;
 
+    GjsListLink instance_link;
+
     unsigned js_object_finalized : 1;
     unsigned g_object_finalized  : 1;
 
@@ -84,7 +145,7 @@ using ParamRefArray = std::vector<ParamRef>;
 static std::unordered_map<GType, ParamRefArray> class_init_properties;
 
 static bool weak_pointer_callback = false;
-static std::set<ObjectInstance *> wrapped_gobject_list;
+ObjectInstance *wrapped_gobject_list;
 
 extern struct JSClass gjs_object_instance_class;
 GJS_DEFINE_PRIV_FROM_JS(ObjectInstance, gjs_object_instance_class)
@@ -959,6 +1020,28 @@ object_instance_props_to_g_parameters(JSContext                  *context,
     return true;
 }
 
+static GjsListLink *
+object_instance_get_link(ObjectInstance *priv)
+{
+    return &priv->instance_link;
+}
+
+static void
+object_instance_unlink(ObjectInstance *priv)
+{
+    if (wrapped_gobject_list == priv)
+        wrapped_gobject_list = priv->instance_link.next();
+    priv->instance_link.unlink();
+}
+
+static void
+object_instance_link(ObjectInstance *priv)
+{
+    if (wrapped_gobject_list)
+        priv->instance_link.prepend(priv, wrapped_gobject_list);
+    wrapped_gobject_list = priv;
+}
+
 static void
 wrapped_gobj_dispose_notify(gpointer      data,
                             GObject      *where_the_object_was)
@@ -966,7 +1049,7 @@ wrapped_gobj_dispose_notify(gpointer      data,
     auto *priv = static_cast<ObjectInstance *>(data);
 
     priv->g_object_finalized = true;
-    wrapped_gobject_list.erase(priv);
+    object_instance_unlink(priv);
     gjs_debug_lifecycle(GJS_DEBUG_GOBJECT, "Wrapped GObject %p disposed",
                         where_the_object_was);
 }
@@ -985,7 +1068,7 @@ gobj_no_longer_kept_alive_func(JS::HandleObject obj,
                         G_OBJECT_TYPE_NAME(priv->gobj));
 
     priv->keep_alive.reset();
-    wrapped_gobject_list.erase(priv);
+    object_instance_unlink(priv);
 }
 
 static void
@@ -1195,14 +1278,15 @@ gjs_object_prepare_shutdown(void)
      *   toggle ref removal -> gobj dispose -> toggle ref notify
      * by emptying the toggle queue earlier in the shutdown sequence. */
     std::vector<ObjectInstance *> to_be_released;
-    for (auto iter = wrapped_gobject_list.begin(); iter != wrapped_gobject_list.end(); ) {
-        ObjectInstance *priv = *iter;
-        if (priv->keep_alive.rooted()) {
-            to_be_released.push_back(priv);
-            iter = wrapped_gobject_list.erase(iter);
-        } else {
-            iter++;
+    ObjectInstance *link = wrapped_gobject_list;
+    while (link) {
+        ObjectInstance *next = link->instance_link.next();
+        if (link->keep_alive.rooted()) {
+            to_be_released.push_back(link);
+            object_instance_unlink(link);
         }
+
+        link = next;
     }
     for (ObjectInstance *priv : to_be_released)
         release_native_object(priv);
@@ -1248,16 +1332,17 @@ update_heap_wrapper_weak_pointers(JSContext     *cx,
 {
     gjs_debug_lifecycle(GJS_DEBUG_GOBJECT, "Weak pointer update callback, "
                         "%zu wrapped GObject(s) to examine",
-                        wrapped_gobject_list.size());
+                        wrapped_gobject_list->instance_link.size());
 
     std::vector<GObject *> to_be_disassociated;
+    ObjectInstance *priv = wrapped_gobject_list;
 
-    for (auto iter = wrapped_gobject_list.begin(); iter != wrapped_gobject_list.end(); ) {
-        ObjectInstance *priv = *iter;
-        if (priv->keep_alive.rooted() || priv->keep_alive == nullptr ||
-            !priv->keep_alive.update_after_gc()) {
-            iter++;
-        } else {
+    while (priv) {
+        ObjectInstance *next = priv->instance_link.next();
+
+        if (!priv->keep_alive.rooted() &&
+            priv->keep_alive != nullptr &&
+            priv->keep_alive.update_after_gc()) {
             /* Ouch, the JS object is dead already. Disassociate the
              * GObject and hope the GObject dies too. (Remove it from
              * the weak pointer list first, since the disassociation
@@ -1268,8 +1353,10 @@ update_heap_wrapper_weak_pointers(JSContext     *cx,
                                 "%p (%s)", priv->keep_alive.get(), priv->gobj,
                                 G_OBJECT_TYPE_NAME(priv->gobj));
             to_be_disassociated.push_back(priv->gobj);
-            iter = wrapped_gobject_list.erase(iter);
+            object_instance_unlink(priv);
         }
+
+        priv = next;
     }
 
     for (GObject *gobj : to_be_disassociated)
@@ -1304,7 +1391,7 @@ associate_js_gobject (JSContext       *context,
 
     priv->keep_alive = object;
     ensure_weak_pointer_callback(context);
-    wrapped_gobject_list.insert(priv);
+    object_instance_link(priv);
 
     g_object_weak_ref(gobj, wrapped_gobj_dispose_notify, priv);
 }
@@ -1600,7 +1687,7 @@ object_instance_finalize(JSFreeOp  *fop,
 
         priv->keep_alive.reset();
     }
-    wrapped_gobject_list.erase(priv);
+    object_instance_unlink(priv);
 
     if (priv->info) {
         g_base_info_unref( (GIBaseInfo*) priv->info);