[cogl] cogl-pipeline: Use BSD lists for the list of pipeline children

[Neil Roberts <nroberts src gnome org>]

commit b9b41723c166f9ce4928b9e5a3a92102c36865fd
Author: Neil Roberts <neil linux intel com>
Date:   Mon Jun 13 16:11:31 2011 +0100

    cogl-pipeline: Use BSD lists for the list of pipeline children
    
    Instead of having a separate GList for the children we can use the
    linked list code from FreeBSD and store the list node directly in the
    struct. That way we can avoid having a separate slice allocation for
    the list node. It also means that we effectively have a pointer to the
    list node given a pointer to the pipeline node. That means we can
    unparent a pipeline without having to walk the entire list of
    children. With this change there is no need to have the optimisation
    to fast track a pipeline that only has one child which simplifies the
    code somewhat.
    
    With this patch we are removing a pointer and a gboolean from the
    CoglPipeline struct and adding two pointers. On 32-bit architectures
    this should end up exactly the same size because a gboolean is the
    same size as a pointer. On 64-bit architectures I think it should end
    up 4 bytes smaller because it also ends up removing two cases where a
    pointer follows a gboolean which presumably would mean the compiler
    would have to insert 4 bytes of padding to keep the pointer aligned to
    8 bytes.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=652514

 cogl/cogl-pipeline-private.h |   27 ++++++++++---------------
 cogl/cogl-pipeline.c         |   44 +++++++++++------------------------------
 2 files changed, 23 insertions(+), 48 deletions(-)
---
diff --git a/cogl/cogl-pipeline-private.h b/cogl/cogl-pipeline-private.h
index c7aa323..897ae35 100644
--- a/cogl/cogl-pipeline-private.h
+++ b/cogl/cogl-pipeline-private.h
@@ -34,6 +34,7 @@
 #include "cogl-matrix.h"
 #include "cogl-object-private.h"
 #include "cogl-profile.h"
+#include "cogl-queue.h"
 
 #include <glib.h>
 
@@ -259,11 +260,14 @@ typedef struct
 
 } CoglPipelineLayerBigState;
 
+typedef struct _CoglPipelineNode CoglPipelineNode;
+
+COGL_LIST_HEAD (CoglPipelineNodeList, CoglPipelineNode);
+
 /* Materials and layers represent their state in a tree structure where
  * some of the state relating to a given pipeline or layer may actually
  * be owned by one if is ancestors in the tree. We have a common data
  * type to track the tree heirachy so we can share code... */
-typedef struct _CoglPipelineNode CoglPipelineNode;
 struct _CoglPipelineNode
 {
   /* the parent in terms of class hierarchy, so anything inheriting
@@ -273,24 +277,15 @@ struct _CoglPipelineNode
   /* The parent pipeline/layer */
   CoglPipelineNode *parent;
 
+  /* The list entry here contains pointers to the node's siblings */
+  COGL_LIST_ENTRY (CoglPipelineNode) list_node;
+
+  /* List of children */
+  CoglPipelineNodeList children;
+
   /* TRUE if the node took a strong reference on its parent. Weak
    * pipelines for instance don't take a reference on their parent. */
   gboolean has_parent_reference;
-
-  /* As an optimization for creating leaf node pipelines/layers (the
-   * most common) we don't require any list node allocations to link
-   * to a single descendant. */
-  CoglPipelineNode *first_child;
-
-  /* Determines if node->first_child and node->children are
-   * initialized pointers. */
-  gboolean has_children;
-
-  /* Materials and layers are sparse structures defined as a diff
-   * against their parent and may have multiple children which depend
-   * on them to define the values of properties which they don't
-   * change. */
-  GList *children;
 };
 
 #define COGL_PIPELINE_NODE(X) ((CoglPipelineNode *)(X))
diff --git a/cogl/cogl-pipeline.c b/cogl/cogl-pipeline.c
index aba4d22..db9d29b 100644
--- a/cogl/cogl-pipeline.c
+++ b/cogl/cogl-pipeline.c
@@ -108,7 +108,7 @@ static void
 _cogl_pipeline_node_init (CoglPipelineNode *node)
 {
   node->parent = NULL;
-  node->has_children = FALSE;
+  COGL_LIST_INIT (&node->children);
 }
 
 static void
@@ -131,14 +131,7 @@ _cogl_pipeline_node_set_parent_real (CoglPipelineNode *node,
   if (node->parent)
     unparent (node);
 
-  if (G_UNLIKELY (parent->has_children))
-    parent->children = g_list_prepend (parent->children, node);
-  else
-    {
-      parent->has_children = TRUE;
-      parent->first_child = node;
-      parent->children = NULL;
-    }
+  COGL_LIST_INSERT_HEAD (&parent->children, node, list_node);
 
   node->parent = parent;
   node->has_parent_reference = take_strong_reference;
@@ -159,21 +152,9 @@ _cogl_pipeline_node_unparent_real (CoglPipelineNode *node)
   if (parent == NULL)
     return;
 
-  g_return_if_fail (parent->has_children);
+  g_return_if_fail (!COGL_LIST_EMPTY (&parent->children));
 
-  if (parent->first_child == node)
-    {
-      if (parent->children)
-        {
-          parent->first_child = parent->children->data;
-          parent->children =
-            g_list_delete_link (parent->children, parent->children);
-        }
-      else
-        parent->has_children = FALSE;
-    }
-  else
-    parent->children = g_list_remove (parent->children, node);
+  COGL_LIST_REMOVE (node, list_node);
 
   if (node->has_parent_reference)
     cogl_object_unref (parent);
@@ -186,11 +167,10 @@ _cogl_pipeline_node_foreach_child (CoglPipelineNode *node,
                                    CoglPipelineNodeChildCallback callback,
                                    void *user_data)
 {
-  if (node->has_children)
-    {
-      callback (node->first_child, user_data);
-      g_list_foreach (node->children, (GFunc)callback, user_data);
-    }
+  CoglPipelineNode *child, *next;
+
+  COGL_LIST_FOREACH_SAFE (child, &node->children, list_node, next)
+    callback (child, user_data);
 }
 
 /*
@@ -555,7 +535,7 @@ _cogl_pipeline_free (CoglPipeline *pipeline)
                                      destroy_weak_children_cb,
                                      NULL);
 
-  g_assert (!COGL_PIPELINE_NODE (pipeline)->has_children);
+  g_assert (COGL_LIST_EMPTY (&COGL_PIPELINE_NODE (pipeline)->children));
 
   _cogl_pipeline_fragend_free_priv (pipeline);
 
@@ -1334,7 +1314,7 @@ _cogl_pipeline_pre_change_notify (CoglPipeline     *pipeline,
   /* If there are still children remaining though we'll need to
    * perform a copy-on-write and reparent the dependants as children
    * of the copy. */
-  if (COGL_PIPELINE_NODE (pipeline)->has_children)
+  if (!COGL_LIST_EMPTY (&COGL_PIPELINE_NODE (pipeline)->children))
     {
       CoglPipeline *new_authority;
 
@@ -1764,7 +1744,7 @@ _cogl_pipeline_layer_pre_change_notify (CoglPipeline *required_owner,
 
   /* Identify the case where the layer is new with no owner or
    * dependants and so we don't need to do anything. */
-  if (COGL_PIPELINE_NODE (layer)->has_children == FALSE &&
+  if (COGL_LIST_EMPTY (&COGL_PIPELINE_NODE (layer)->children) &&
       layer->owner == NULL)
     goto init_layer_state;
 
@@ -1786,7 +1766,7 @@ _cogl_pipeline_layer_pre_change_notify (CoglPipeline *required_owner,
    * they have dependants - either direct children, or another
    * pipeline as an owner.
    */
-  if (COGL_PIPELINE_NODE (layer)->has_children ||
+  if (!COGL_LIST_EMPTY (&COGL_PIPELINE_NODE (layer)->children) ||
       layer->owner != required_owner)
     {
       CoglPipelineLayer *new = _cogl_pipeline_layer_copy (layer);