[pango/wip/baedert/for-master: 3/3] attrs: Save attribute list in a GPtrArray

[Timm Bäder <baedert src gnome org>]

commit 623bcee218cf6a62b432c04e3d20229aa20e4a76
Author: Timm Bäder <mail baedert org>
Date:   Fri Apr 17 17:08:32 2020 +0200

    attrs: Save attribute list in a GPtrArray

 pango/pango-attributes-private.h |   7 +-
 pango/pango-attributes.c         | 496 +++++++++++++++++----------------------
 2 files changed, 223 insertions(+), 280 deletions(-)
---
diff --git a/pango/pango-attributes-private.h b/pango/pango-attributes-private.h
index bf5bdade..660c1828 100644
--- a/pango/pango-attributes-private.h
+++ b/pango/pango-attributes-private.h
@@ -22,8 +22,13 @@
 
 struct _PangoAttrIterator
 {
+  GPtrArray *attrs; /* From the list */
+  guint n_attrs; /* Copied from the list */
+
   GSList *next_attribute;
   GPtrArray *attribute_stack;
+
+  guint attr_index;
   guint start_index;
   guint end_index;
 };
@@ -31,7 +36,7 @@ struct _PangoAttrIterator
 struct _PangoAttrList
 {
   guint ref_count;
-  GSList *attributes;
+  GPtrArray *attributes2;
 };
 
 void     _pango_attr_list_init         (PangoAttrList     *list);
diff --git a/pango/pango-attributes.c b/pango/pango-attributes.c
index c74ea17f..3969f1de 100644
--- a/pango/pango-attributes.c
+++ b/pango/pango-attributes.c
@@ -1310,7 +1310,7 @@ void
 _pango_attr_list_init (PangoAttrList *list)
 {
   list->ref_count = 1;
-  list->attributes = NULL;
+  list->attributes2 = NULL;
 }
 
 /**
@@ -1355,18 +1355,19 @@ pango_attr_list_ref (PangoAttrList *list)
 void
 _pango_attr_list_destroy (PangoAttrList *list)
 {
-  GSList *tmp_list;
+  guint i, p;
 
-  tmp_list = list->attributes;
-  while (tmp_list)
+  if (!list->attributes2)
+    return;
+
+  for (i = 0, p = list->attributes2->len; i < p; i++)
     {
-      PangoAttribute *attr = tmp_list->data;
-      tmp_list = tmp_list->next;
+      PangoAttribute *attr = g_ptr_array_index (list->attributes2, i);
 
       attr->klass->destroy (attr);
     }
 
-  g_slist_free (list->attributes);
+  g_ptr_array_free (list->attributes2, TRUE);
 }
 
 /**
@@ -1407,26 +1408,15 @@ PangoAttrList *
 pango_attr_list_copy (PangoAttrList *list)
 {
   PangoAttrList *new;
-  GSList *iter;
-  GSList *new_attrs;
 
   if (list == NULL)
     return NULL;
 
   new = pango_attr_list_new ();
+  if (!list->attributes2 || list->attributes2->len == 0)
+    return new;
 
-  iter = list->attributes;
-  new_attrs = NULL;
-  while (iter != NULL)
-    {
-      new_attrs = g_slist_prepend (new_attrs,
-                                  pango_attribute_copy (iter->data));
-
-      iter = g_slist_next (iter);
-    }
-
-  /* we're going to reverse the nodes, so head becomes tail */
-  new->attributes = g_slist_reverse (new_attrs);
+  new->attributes2 = g_ptr_array_copy (list->attributes2, (GCopyFunc)pango_attribute_copy, NULL);
 
   return new;
 }
@@ -1436,49 +1426,42 @@ pango_attr_list_insert_internal (PangoAttrList  *list,
                                 PangoAttribute *attr,
                                 gboolean        before)
 {
-  GSList *tmp_list, *prev, *link;
   const guint start_index = attr->start_index;
   PangoAttribute *last_attr;
 
-  if (!list->attributes)
+  if (G_UNLIKELY (!list->attributes2))
+    list->attributes2 = g_ptr_array_new ();
+
+  if (list->attributes2->len == 0)
     {
-      list->attributes = g_slist_prepend (NULL, attr);
+      g_ptr_array_add (list->attributes2, attr);
       return;
     }
 
-  last_attr = g_slist_last (list->attributes)->data;
+  g_assert (list->attributes2->len > 0);
+
+  last_attr = g_ptr_array_index (list->attributes2, list->attributes2->len - 1);
 
   if (last_attr->start_index < start_index ||
-       (!before && last_attr->start_index == start_index))
+      (!before && last_attr->start_index == start_index))
     {
-      list->attributes = g_slist_append (list->attributes, attr);
+      g_ptr_array_add (list->attributes2, attr);
     }
   else
     {
-      prev = NULL;
-      tmp_list = list->attributes;
-      while (1)
-       {
-         PangoAttribute *tmp_attr = tmp_list->data;
+      guint i, p;
 
-         if (tmp_attr->start_index > start_index ||
-             (before && tmp_attr->start_index == start_index))
-           {
-             link = g_slist_alloc ();
-             link->next = tmp_list;
-             link->data = attr;
-
-             if (prev)
-               prev->next = link;
-             else
-               list->attributes = link;
-
-             break;
-           }
+      for (i = 0, p = list->attributes2->len; i < p; i++)
+        {
+          PangoAttribute *cur = g_ptr_array_index (list->attributes2, i);
 
-         prev = tmp_list;
-         tmp_list = tmp_list->next;
-       }
+          if (cur->start_index > start_index ||
+              (before && cur->start_index == start_index))
+            {
+              g_ptr_array_insert (list->attributes2, i, attr);
+              break;
+            }
+        }
     }
 }
 
@@ -1533,7 +1516,7 @@ pango_attr_list_insert_before (PangoAttrList  *list,
  * and be merged with any adjoining attributes that are identical.
  *
  * This function is slower than pango_attr_list_insert() for
- * creating a attribute list in order (potentially much slower
+ * creating an attribute list in order (potentially much slower
  * for large lists). However, pango_attr_list_insert() is not
  * suitable for continually changing a set of attributes
  * since it never removes or combines existing attributes.
@@ -1542,7 +1525,7 @@ void
 pango_attr_list_change (PangoAttrList  *list,
                        PangoAttribute *attr)
 {
-  GSList *tmp_list, *prev, *link;
+  guint i, p;
   guint start_index = attr->start_index;
   guint end_index = attr->end_index;
 
@@ -1554,168 +1537,120 @@ pango_attr_list_change (PangoAttrList  *list,
       return;
     }
 
-  tmp_list = list->attributes;
-  prev = NULL;
-  while (1)
+  if (!list->attributes2 || list->attributes2->len == 0)
     {
-      PangoAttribute *tmp_attr;
-
-      if (!tmp_list ||
-         ((PangoAttribute *)tmp_list->data)->start_index > start_index)
-       {
-         /* We need to insert a new attribute
-          */
-         link = g_slist_alloc ();
-         link->next = tmp_list;
-         link->data = attr;
+      pango_attr_list_insert (list, attr);
+      return;
+    }
 
-         if (prev)
-           prev->next = link;
-         else
-           list->attributes = link;
+  for (i = 0, p = list->attributes2->len; i < p; i++)
+    {
+      PangoAttribute *tmp_attr = g_ptr_array_index (list->attributes2, i);
 
-         prev = link;
-         tmp_list = prev->next;
-         break;
-       }
+      if (tmp_attr->start_index > start_index)
+        {
+          g_ptr_array_insert (list->attributes2, i, attr);
+          break;
+        }
 
-      tmp_attr = tmp_list->data;
+      if (tmp_attr->klass->type != attr->klass->type)
+        continue;
 
-      if (tmp_attr->klass->type == attr->klass->type &&
-         tmp_attr->end_index >= start_index)
-       {
-         /* We overlap with an existing attribute */
-         if (pango_attribute_equal (tmp_attr, attr))
-           {
-             /* We can merge the new attribute with this attribute
-              */
-             if (tmp_attr->end_index >= end_index)
-               {
-                 /* We are totally overlapping the previous attribute.
-                  * No action is needed.
-                  */
-                 pango_attribute_destroy (attr);
-                 return;
-               }
-             tmp_attr->end_index = end_index;
-             pango_attribute_destroy (attr);
+      if (tmp_attr->end_index < start_index)
+        continue; /* This attr does not overlap with the new one */
 
-             attr = tmp_attr;
+      g_assert (tmp_attr->end_index >= start_index);
+      g_assert (start_index < tmp_attr->end_index);
 
-             prev = tmp_list;
-             tmp_list = tmp_list->next;
+      if (pango_attribute_equal (tmp_attr, attr))
+        {
+          /* We can merge the new attribute with this attribute
+           */
+          if (tmp_attr->end_index >= end_index)
+            {
+              /* We are totally overlapping the previous attribute.
+               * No action is needed.
+               */
+              g_ptr_array_remove_index (list->attributes2, i);
+              pango_attribute_destroy (attr);
+              return;
+            }
 
-             break;
-           }
-         else
-           {
-             /* Split, truncate, or remove the old attribute
-              */
-             if (tmp_attr->end_index > attr->end_index)
-               {
-                 PangoAttribute *end_attr = pango_attribute_copy (tmp_attr);
+          tmp_attr->end_index = end_index;
+          /*g_ptr_array_remove_index (list->attributes2, i);*/
+          pango_attribute_destroy (attr);
 
-                 end_attr->start_index = attr->end_index;
-                 pango_attr_list_insert (list, end_attr);
-               }
+          attr = tmp_attr;
+          break;
+        }
+      else
+        {
+          /* Split, truncate, or remove the old attribute
+           */
+          if (tmp_attr->end_index > attr->end_index)
+            {
+              PangoAttribute *end_attr = pango_attribute_copy (tmp_attr);
 
-             if (tmp_attr->start_index == attr->start_index)
-               {
-                 pango_attribute_destroy (tmp_attr);
-                 tmp_list->data = attr;
+              end_attr->start_index = attr->end_index;
+              pango_attr_list_insert (list, end_attr);
+            }
 
-                 prev = tmp_list;
-                 tmp_list = tmp_list->next;
-                 break;
-               }
-             else
-               {
-                 tmp_attr->end_index = attr->start_index;
-               }
-           }
-       }
-      prev = tmp_list;
-      tmp_list = tmp_list->next;
+          if (tmp_attr->start_index == attr->start_index)
+            {
+              pango_attribute_destroy (tmp_attr);
+              g_ptr_array_remove_index (list->attributes2, i);
+              break;
+            }
+          else
+            {
+              tmp_attr->end_index = attr->start_index;
+            }
+        }
     }
-  /* At this point, prev points to the list node with attr in it,
-   * tmp_list points to prev->next.
-   */
-
-  g_assert (prev->data == attr);
-  g_assert (prev->next == tmp_list);
 
   /* We now have the range inserted into the list one way or the
-   * other. Fix up the remainder
-   */
-  while (tmp_list)
+   * other. Fix up the remainder */
+  /* Attention: No i = 0 here. */
+  for (i = i + 1, p = list->attributes2->len; i < p; i++)
     {
-      PangoAttribute *tmp_attr = tmp_list->data;
+      PangoAttribute *tmp_attr = g_ptr_array_index (list->attributes2, i);
 
       if (tmp_attr->start_index > end_index)
-       break;
-      else if (tmp_attr->klass->type == attr->klass->type)
-       {
-         if (tmp_attr->end_index <= attr->end_index ||
-             pango_attribute_equal (tmp_attr, attr))
-           {
-             /* We can merge the new attribute with this attribute.
-              */
-             attr->end_index = MAX (end_index, tmp_attr->end_index);
-
-             pango_attribute_destroy (tmp_attr);
-             prev->next = tmp_list->next;
-
-             g_slist_free_1 (tmp_list);
-             tmp_list = prev->next;
-
-             continue;
-           }
-         else
-           {
-             /* Trim the start of this attribute that it begins at the end
-              * of the new attribute. This may involve moving
-              * it in the list to maintain the required non-decreasing
-              * order of start indices
-              */
-             GSList *tmp_list2;
-             GSList *prev2;
-
-             tmp_attr->start_index = attr->end_index;
-
-             tmp_list2 = tmp_list->next;
-             prev2 = tmp_list;
-
-             while (tmp_list2)
-               {
-                 PangoAttribute *tmp_attr2 = tmp_list2->data;
+        break;
 
-                 if (tmp_attr2->start_index >= tmp_attr->start_index)
-                   break;
+      if (tmp_attr->klass->type != attr->klass->type)
+        continue;
 
-                 prev2 = tmp_list2;
-                 tmp_list2 = tmp_list2->next;
-               }
-
-             /* Now remove and insert before tmp_list2. We'll
-              * hit this attribute again later, but that's harmless.
-              */
-             if (prev2 != tmp_list)
-               {
-                 GSList *old_next = tmp_list->next;
-
-                 prev->next = old_next;
-                 prev2->next = tmp_list;
-                 tmp_list->next = tmp_list2;
+      if (tmp_attr->end_index <= attr->end_index ||
+          pango_attribute_equal (tmp_attr, attr))
+        {
+          /* We can merge the new attribute with this attribute. */
+          attr->end_index = MAX (end_index, tmp_attr->end_index);
+          pango_attribute_destroy (tmp_attr);
+          g_ptr_array_remove_index (list->attributes2, i);
+          i--;
+          p--;
+          continue;
+        }
+      else
+        {
+          /* Trim the start of this attribute that it begins at the end
+           * of the new attribute. This may involve moving
+           * it in the list to maintain the required non-decreasing
+           * order of start indices
+           */
+          int k, m;
 
-                 tmp_list = old_next;
+          tmp_attr->start_index = attr->end_index;
 
-                 continue;
-               }
-           }
-       }
+          for (k = i + 1, m = list->attributes2->len; k < m; k++)
+            {
+              PangoAttribute *tmp_attr2 = g_ptr_array_index (list->attributes2, k);
 
-      prev = tmp_list;
-      tmp_list = tmp_list->next;
+              if (tmp_attr2->start_index >= tmp_attr->start_index)
+                break;
+            }
+        }
     }
 }
 
@@ -1751,52 +1686,41 @@ pango_attr_list_update (PangoAttrList *list,
                         int             remove,
                         int             add)
 {
-  GSList *l, *prev, *next;
+  guint i, p;
 
-   prev = NULL;
-   l = list->attributes;
-   while (l)
+  for (i = 0, p = list->attributes2->len; i < p; i++)
     {
-      PangoAttribute *attr = l->data;
-      next = l->next;
+      PangoAttribute *attr = g_ptr_array_index (list->attributes2, i);
 
       if (attr->start_index >= pos &&
           attr->end_index < pos + remove)
         {
           pango_attribute_destroy (attr);
-          if (prev == NULL)
-            list->attributes = next;
-          else
-            prev->next = next;
+          g_ptr_array_remove_index (list->attributes2, i);
+          i--; /* Look at this index again */
+          p--;
+          continue;
+        }
 
-          g_slist_free_1 (l);
+      if (attr->start_index >= pos &&
+          attr->start_index < pos + remove)
+        {
+          attr->start_index = pos + add;
         }
-      else
+      else if (attr->start_index >= pos + remove)
         {
-          prev = l;
-
-          if (attr->start_index >= pos &&
-              attr->start_index < pos + remove)
-            {
-              attr->start_index = pos + add;
-            }
-          else if (attr->start_index >= pos + remove)
-            {
-              attr->start_index += add - remove;
-            }
-
-          if (attr->end_index >= pos &&
-              attr->end_index < pos + remove)
-            {
-              attr->end_index = pos;
-            }
-          else if (attr->end_index >= pos + remove)
-            {
-              attr->end_index += add - remove;
-            }
+          attr->start_index += add - remove;
         }
 
-      l = next;
+      if (attr->end_index >= pos &&
+          attr->end_index < pos + remove)
+        {
+          attr->end_index = pos;
+        }
+      else if (attr->end_index >= pos + remove)
+        {
+          attr->end_index += add - remove;
+        }
     }
 }
 
@@ -1826,7 +1750,7 @@ pango_attr_list_splice (PangoAttrList *list,
                        gint           pos,
                        gint           len)
 {
-  GSList *tmp_list;
+  guint i, p;
   guint upos, ulen;
 
   g_return_if_fail (list != NULL);
@@ -1842,10 +1766,9 @@ pango_attr_list_splice (PangoAttrList *list,
  */
 #define CLAMP_ADD(a,b) (((a) + (b) < (a)) ? G_MAXUINT : (a) + (b))
 
-  tmp_list = list->attributes;
-  while (tmp_list)
+  for (i = 0, p = list->attributes2->len; i < p; i++)
     {
-      PangoAttribute *attr = tmp_list->data;
+      PangoAttribute *attr = g_ptr_array_index (list->attributes2, i);;
 
       if (attr->start_index <= upos)
        {
@@ -1861,15 +1784,15 @@ pango_attr_list_splice (PangoAttrList *list,
           */
          attr->start_index = CLAMP_ADD (attr->start_index, ulen);
          attr->end_index = CLAMP_ADD (attr->end_index, ulen);
-       }
-
-      tmp_list = tmp_list->next;
+        }
     }
 
-  tmp_list = other->attributes;
-  while (tmp_list)
+  if (!other->attributes2 || other->attributes2->len == 0)
+    return;
+
+  for (i = 0, p = other->attributes2->len; i < p; i++)
     {
-      PangoAttribute *attr = pango_attribute_copy (tmp_list->data);
+      PangoAttribute *attr = pango_attribute_copy (g_ptr_array_index (other->attributes2, i));
       attr->start_index = CLAMP_ADD (attr->start_index, upos);
       attr->end_index = CLAMP_ADD (attr->end_index, upos);
 
@@ -1877,8 +1800,6 @@ pango_attr_list_splice (PangoAttrList *list,
        * pango_attr_list_change() will take care of deleting it.
        */
       pango_attr_list_change (list, attr);
-
-      tmp_list = tmp_list->next;
     }
 #undef CLAMP_ADD
 }
@@ -1899,15 +1820,28 @@ pango_attr_list_splice (PangoAttrList *list,
 GSList *
 pango_attr_list_get_attributes (PangoAttrList *list)
 {
+  GSList *result = NULL;
+  guint i, p;
+
   g_return_val_if_fail (list != NULL, NULL);
 
-  return g_slist_copy_deep (list->attributes, (GCopyFunc)pango_attribute_copy, NULL);
+  if (!list->attributes2 || list->attributes2->len == 0)
+    return NULL;
+
+  for (i = 0, p = list->attributes2->len; i < p; i++)
+    {
+      PangoAttribute *attr = g_ptr_array_index (list->attributes2, i);
+
+      result = g_slist_prepend (result, pango_attribute_copy (attr));
+    }
+
+  return g_slist_reverse (result);
 }
 
 gboolean
 _pango_attr_list_has_attributes (const PangoAttrList *list)
 {
-  return (list->attributes != NULL);
+  return (list->attributes2 != NULL && list->attributes2->len > 0);
 }
 
 G_DEFINE_BOXED_TYPE (PangoAttrIterator,
@@ -1919,9 +1853,11 @@ void
 _pango_attr_list_get_iterator (PangoAttrList     *list,
                                PangoAttrIterator *iterator)
 {
-  iterator->next_attribute = list->attributes;
   iterator->attribute_stack = NULL;
+  iterator->attrs = list->attributes2;
+  iterator->n_attrs = iterator->attrs ? iterator->attrs->len : 0;
 
+  iterator->attr_index = 0;
   iterator->start_index = 0;
   iterator->end_index = 0;
 
@@ -1992,7 +1928,7 @@ pango_attr_iterator_next (PangoAttrIterator *iterator)
 
   g_return_val_if_fail (iterator != NULL, FALSE);
 
-  if (!iterator->next_attribute &&
+  if (iterator->attr_index >= iterator->n_attrs &&
       (!iterator->attribute_stack || iterator->attribute_stack->len == 0))
     return FALSE;
 
@@ -2017,22 +1953,37 @@ pango_attr_iterator_next (PangoAttrIterator *iterator)
         }
     }
 
-  while (iterator->next_attribute &&
-         ((PangoAttribute *)iterator->next_attribute->data)->start_index == iterator->start_index)
+  while (1)
     {
-      if (((PangoAttribute *)iterator->next_attribute->data)->end_index > iterator->start_index)
+      PangoAttribute *attr;
+
+      if (iterator->attr_index >= iterator->n_attrs)
+        break;
+
+      attr = g_ptr_array_index (iterator->attrs, iterator->attr_index);
+
+      if (attr->start_index != iterator->start_index)
+        break;
+
+      if (attr->end_index > iterator->start_index)
         {
           if (G_UNLIKELY (!iterator->attribute_stack))
             iterator->attribute_stack = g_ptr_array_new ();
 
-          g_ptr_array_add (iterator->attribute_stack, iterator->next_attribute->data);
-          iterator->end_index = MIN (iterator->end_index, ((PangoAttribute 
*)iterator->next_attribute->data)->end_index);
+          g_ptr_array_add (iterator->attribute_stack, attr);
+
+          iterator->end_index = MIN (iterator->end_index, attr->end_index);
         }
-      iterator->next_attribute = iterator->next_attribute->next;
+
+      iterator->attr_index++; /* NEXT! */
     }
 
-  if (iterator->next_attribute)
-    iterator->end_index = MIN (iterator->end_index, ((PangoAttribute 
*)iterator->next_attribute->data)->start_index);
+  if (iterator->attr_index < iterator->n_attrs)
+      {
+      PangoAttribute *attr = g_ptr_array_index (iterator->attrs, iterator->attr_index);
+
+      iterator->end_index = MIN (iterator->end_index, attr->start_index);
+    }
 
   return TRUE;
 }
@@ -2311,44 +2262,31 @@ pango_attr_list_filter (PangoAttrList       *list,
 
 {
   PangoAttrList *new = NULL;
-  GSList *tmp_list;
-  GSList *prev;
+  guint i, p;
 
   g_return_val_if_fail (list != NULL, NULL);
 
-  tmp_list = list->attributes;
-  prev = NULL;
-  while (tmp_list)
+  if (!list->attributes2 || list->attributes2->len == 0)
+    return NULL;
+
+  for (i = 0, p = list->attributes2->len; i < p; i++)
     {
-      GSList *next = tmp_list->next;
-      PangoAttribute *tmp_attr = tmp_list->data;
+      PangoAttribute *tmp_attr = g_ptr_array_index (list->attributes2, i);
 
       if ((*func) (tmp_attr, data))
-       {
-         if (prev)
-           prev->next = tmp_list->next;
-         else
-           list->attributes = tmp_list->next;
-
-         tmp_list->next = NULL;
-
-         if (!new)
-           {
-             new = pango_attr_list_new ();
-             new->attributes = tmp_list;
-           }
-         else
-           {
-              g_slist_last (new->attributes)->next = tmp_list;
-           }
-
-         goto next_attr;
-       }
+        {
+          g_ptr_array_remove_index (list->attributes2, i);
+          i--; /* Need to look at this index again */
+          p--;
 
-      prev = tmp_list;
+          if (G_UNLIKELY (!new))
+            {
+              new = pango_attr_list_new ();
+              new->attributes2 = g_ptr_array_new ();
+            }
 
-    next_attr:
-      tmp_list = next;
+          g_ptr_array_add (new->attributes2, tmp_attr);
+        }
     }
 
   return new;