[gjs: 3/7] Revert "object: Use vector for holding the list of wrapped objects"

[Philip Chimento <pchimento src gnome org>]

commit 624acaab5bcdf455f0e66288efd7248f7c66c1b7
Author: veena <veenanitks gmail com>
Date:   Tue Jun 1 00:30:55 2021 +0530

    Revert "object: Use vector for holding the list of wrapped objects"
    
    This reverts commit 2c843387b33b7472ebd61380b29db3db26dff710.

 gi/object.cpp | 102 ++++++++++++++++++++++++++++++++++++++++++++--------------
 gi/object.h   |  29 +++++++++++++++--
 2 files changed, 104 insertions(+), 27 deletions(-)
---
diff --git a/gi/object.cpp b/gi/object.cpp
index 72146db2..03cfd7bc 100644
--- a/gi/object.cpp
+++ b/gi/object.cpp
@@ -13,7 +13,6 @@
 #include <limits>
 #include <string>
 #include <tuple>        // for tie
-#include <type_traits>
 #include <utility>      // for move
 #include <vector>
 
@@ -73,15 +72,14 @@ class JSTracer;
 #if defined(__x86_64__) && defined(__clang__)
 /* This isn't meant to be comprehensive, but should trip on at least one CI job
  * if sizeof(ObjectInstance) is increased. */
-static_assert(sizeof(ObjectInstance) <= 56,
+static_assert(sizeof(ObjectInstance) <= 88,
               "Think very hard before increasing the size of ObjectInstance. "
               "There can be tens of thousands of them alive in a typical "
               "gnome-shell run.");
 #endif  // x86-64 clang
 
 bool ObjectInstance::s_weak_pointer_callback = false;
-decltype(ObjectInstance::s_wrapped_gobject_list)
-    ObjectInstance::s_wrapped_gobject_list;
+ObjectInstance *ObjectInstance::wrapped_gobject_list = nullptr;
 
 static const auto DISPOSED_OBJECT = std::numeric_limits<uintptr_t>::max();
 
@@ -113,15 +111,61 @@ void ObjectBase::type_query_dynamic_safe(GTypeQuery* query) {
     g_type_query(type, query);
 }
 
-void ObjectInstance::link() {
-    g_assert(std::find(s_wrapped_gobject_list.begin(),
-                       s_wrapped_gobject_list.end(),
-                       this) == s_wrapped_gobject_list.end());
-    s_wrapped_gobject_list.push_back(this);
+void
+GjsListLink::prepend(ObjectInstance *this_instance,
+                     ObjectInstance *head)
+{
+    GjsListLink *elem = head->get_link();
+
+    g_assert(this_instance->get_link() == this);
+
+    if (elem->m_prev) {
+        GjsListLink *prev = elem->m_prev->get_link();
+        prev->m_next = this_instance;
+        this->m_prev = elem->m_prev;
+    }
+
+    elem->m_prev = this_instance;
+    this->m_next = head;
 }
 
-void ObjectInstance::unlink() {
-    Gjs::remove_one_from_unsorted_vector(&s_wrapped_gobject_list, this);
+void
+GjsListLink::unlink(void)
+{
+    if (m_prev)
+        m_prev->get_link()->m_next = m_next;
+    if (m_next)
+        m_next->get_link()->m_prev = m_prev;
+
+    m_prev = m_next = nullptr;
+}
+
+size_t
+GjsListLink::size(void) const
+{
+    const GjsListLink *elem = this;
+    size_t count = 0;
+
+    do {
+        count++;
+        if (!elem->m_next)
+            break;
+        elem = elem->m_next->get_link();
+    } while (elem);
+
+    return count;
+}
+
+void ObjectInstance::link(void) {
+    if (wrapped_gobject_list)
+        m_instance_link.prepend(this, wrapped_gobject_list);
+    wrapped_gobject_list = this;
+}
+
+void ObjectInstance::unlink(void) {
+    if (wrapped_gobject_list == this)
+        wrapped_gobject_list = m_instance_link.next();
+    m_instance_link.unlink();
 }
 
 const void* ObjectBase::jsobj_addr(void) const {
@@ -1100,20 +1144,29 @@ ObjectInstance::gobj_dispose_notify(void)
         discard_wrapper();
 }
 
+void ObjectInstance::iterate_wrapped_gobjects(
+    const ObjectInstance::Action& action) {
+    ObjectInstance *link = ObjectInstance::wrapped_gobject_list;
+    while (link) {
+        ObjectInstance *next = link->next();
+        action(link);
+        link = next;
+    }
+}
+
 void ObjectInstance::remove_wrapped_gobjects_if(
     const ObjectInstance::Predicate& predicate,
     const ObjectInstance::Action& action) {
-    s_wrapped_gobject_list.erase(
-        std::remove_if(s_wrapped_gobject_list.begin(),
-                       s_wrapped_gobject_list.end(),
-                       ([predicate, action](ObjectInstance* link) {
-                           if (predicate(link)) {
-                               action(link);
-                               return true;
-                           }
-                           return false;
-                       })),
-        s_wrapped_gobject_list.end());
+    std::vector<ObjectInstance *> removed;
+    iterate_wrapped_gobjects([&predicate, &removed](ObjectInstance* link) {
+        if (predicate(link)) {
+            removed.push_back(link);
+            link->unlink();
+        }
+    });
+
+    for (ObjectInstance *priv : removed)
+        action(priv);
 }
 
 /*
@@ -1124,7 +1177,7 @@ void ObjectInstance::remove_wrapped_gobjects_if(
  */
 void ObjectInstance::context_dispose_notify(void*, GObject* where_the_object_was
                                             [[maybe_unused]]) {
-    std::for_each(s_wrapped_gobject_list.begin(), s_wrapped_gobject_list.end(),
+    ObjectInstance::iterate_wrapped_gobjects(
         std::mem_fn(&ObjectInstance::handle_context_dispose));
 }
 
@@ -1137,6 +1190,7 @@ void ObjectInstance::handle_context_dispose(void) {
     if (wrapper_is_rooted()) {
         debug_lifecycle("Was rooted, but unrooting due to GjsContext dispose");
         discard_wrapper();
+        unlink();
     }
 }
 
@@ -1402,8 +1456,6 @@ void ObjectInstance::update_heap_wrapper_weak_pointers(JSContext*,
     ObjectInstance::remove_wrapped_gobjects_if(
         std::mem_fn(&ObjectInstance::weak_pointer_was_finalized),
         std::mem_fn(&ObjectInstance::disassociate_js_gobject));
-
-    s_wrapped_gobject_list.shrink_to_fit();
 }
 
 bool
diff --git a/gi/object.h b/gi/object.h
index 0d9d40fe..6003bd5e 100644
--- a/gi/object.h
+++ b/gi/object.h
@@ -50,6 +50,20 @@ struct ObjectInstance;
 class ObjectInstance;
 class ObjectPrototype;
 
+class GjsListLink {
+ private:
+    ObjectInstance* m_prev = nullptr;
+    ObjectInstance* m_next = nullptr;
+
+ public:
+    [[nodiscard]] ObjectInstance* prev() const { return m_prev; }
+    [[nodiscard]] ObjectInstance* next() const { return m_next; }
+
+    void prepend(ObjectInstance* this_instance, ObjectInstance* head);
+    void unlink(void);
+    [[nodiscard]] size_t size() const;
+};
+
 /*
  * ObjectBase:
  *
@@ -287,6 +301,7 @@ class ObjectInstance : public GIWrapperInstance<ObjectBase, ObjectPrototype,
     // a list of all GClosures installed on this object (from signal connections
     // and scope-notify callbacks passed to methods), used when tracing
     std::forward_list<GClosure*> m_closures;
+    GjsListLink m_instance_link;
 
     bool m_wrapper_finalized : 1;
     bool m_gobj_disposed : 1;
@@ -392,18 +407,28 @@ class ObjectInstance : public GIWrapperInstance<ObjectBase, ObjectPrototype,
     /* Methods to manipulate the linked list of instances */
 
  private:
-    static std::vector<ObjectInstance*> s_wrapped_gobject_list;
+    static ObjectInstance* wrapped_gobject_list;
+    [[nodiscard]] ObjectInstance* next() const {
+        return m_instance_link.next();
+    }
     void link(void);
     void unlink(void);
     [[nodiscard]] static size_t num_wrapped_gobjects() {
-        return s_wrapped_gobject_list.size();
+        return wrapped_gobject_list
+                   ? wrapped_gobject_list->m_instance_link.size()
+                   : 0;
     }
     using Action = std::function<void(ObjectInstance*)>;
     using Predicate = std::function<bool(ObjectInstance*)>;
+    static void iterate_wrapped_gobjects(const Action& action);
     static void remove_wrapped_gobjects_if(const Predicate& predicate,
                                            const Action& action);
 
  public:
+    [[nodiscard]] [[gnu::const]] GjsListLink* get_link() {
+        return &m_instance_link;
+    }
+
     static void prepare_shutdown(void);
 
     /* JSClass operations */