[gtk+/wip/css-bitmasks: 5/6] Store GtkBitmap data inline in the pointer

From: Alexander Larsson <alexl src gnome org>
To: commits-list gnome org
Cc:
Subject: [gtk+/wip/css-bitmasks: 5/6] Store GtkBitmap data inline in the pointer
Date: Wed, 8 Feb 2012 13:38:47 +0000 (UTC)
commit f9d9b26d980762baa6a259559792330f9783a748
Author: Alexander Larsson <alexl redhat com>
Date:   Wed Feb 8 14:27:29 2012 +0100

    Store GtkBitmap data inline in the pointer
    
    Bitmaps are often sparse in some way, which we can use by storing such
    bitmaps inside the actual GtkBitmap pointer, which we detect by looking at
    the least significant bit (which is never set for normal objects due to
    alignment rules).
    
    There are two basic approaches, you can store the bitmasks smaller than
    31/63 bits directly in the pointer, or you can use the pointer as a
    single bit number, considering that bit set.
    
    I did some measurements on this, and it turns out that 63 bits is enought
    for most bitmaps right now, but not 31bit, which means this is only efficient
    on 64bit arches. Additionally it doesn't scale well as the number of style
    classes and regions increase.
    
    Using the data to store a single bit number however was almost as good as 63
    bits always and sometimes better, and it will continue to scale as we
    add more classes and regions.
    
    With this change we use an additional 116KB ram in Nautilus after
    startup.

 gtk/gtkbitmask.c    |  305 ++++++++++++++++++++++++++++++++++++++++++++++----
 gtk/gtkwidgetpath.c |    2 -
 2 files changed, 280 insertions(+), 27 deletions(-)
---
diff --git a/gtk/gtkbitmask.c b/gtk/gtkbitmask.c
index a616c7a..2bd64f1 100644
--- a/gtk/gtkbitmask.c
+++ b/gtk/gtkbitmask.c
@@ -33,6 +33,12 @@ struct _GtkBitmask {
   VALUE_TYPE data[1];
 };
 
+typedef struct {
+  GtkBitmask bitmask;
+  VALUE_TYPE more_data[3];
+  const GtkBitmask *orig;
+} GtkBitmaskPrealloc;
+
 static GtkBitmask *
 _gtk_bitmask_allocate (guint size)
 {
@@ -73,12 +79,111 @@ _gtk_bitmask_resize (GtkBitmask **mask, guint len)
   (*mask)->len = len;
 }
 
+static gboolean
+gtk_bitmask_is_bit (const GtkBitmask *mask)
+{
+  return (((gsize)mask) & 1);
+}
+
+static GtkBitmask *
+gtk_bitmask_for_bit (guint bit)
+{
+  gsize mask;
+
+  mask = bit;
+  mask <<= 1;
+  mask |= 1;
+  return (GtkBitmask *)mask;
+}
+
+static guint
+gtk_bitmask_get_bit (const GtkBitmask *mask)
+{
+  return ((gsize)mask) >> 1;
+}
+
+static gboolean
+gtk_bitmask_is_inline (const GtkBitmask *mask)
+{
+  return mask == NULL || gtk_bitmask_is_bit (mask);
+}
+
+static void
+gtk_bitmask_realize_for_write (GtkBitmask **mask, guint size_hint)
+{
+  GtkBitmask *realized;
+
+  if (*mask == NULL)
+    {
+      realized = _gtk_bitmask_allocate (MAX (size_hint, 1));
+      realized->len = 0;
+      *mask = realized;
+    }
+  else if (gtk_bitmask_is_bit (*mask))
+    {
+      guint bit = gtk_bitmask_get_bit (*mask);
+      guint len = (bit / VALUE_SIZE_BITS) + 1;
+      int i;
+
+      realized = _gtk_bitmask_allocate (MAX (len, size_hint));
+      realized->len = len;
+      for (i = 0; i < len; i++)
+	realized->data[i] = 0;
+
+      _gtk_bitmask_set (&realized, bit, TRUE);
+
+      *mask = realized;
+    }
+}
+
+
+static void
+gtk_bitmask_realize (const GtkBitmask **mask, GtkBitmaskPrealloc *prealloc)
+{
+  prealloc->orig = *mask;
+  if (*mask == NULL)
+    {
+      prealloc->bitmask.len = 0;
+      prealloc->bitmask.alloc = 4;
+      *mask = &prealloc->bitmask;
+    }
+  else if (gtk_bitmask_is_bit (*mask))
+    {
+      GtkBitmask *realized;
+      int i;
+      guint bit = gtk_bitmask_get_bit (*mask);
+      guint len = (bit / VALUE_SIZE_BITS) + 1;
+
+      if (len <= 4)
+	{
+	  prealloc->bitmask.alloc = 4;
+	  realized = &prealloc->bitmask;
+	}
+      else
+	realized = _gtk_bitmask_allocate (len);
+
+      for (i = 0; i < len; i++)
+	realized->data[i] = 0;
+      realized->len = len;
 
+      _gtk_bitmask_set (&realized, bit, TRUE);
+
+      *mask = realized;
+    }
+}
+
+static void
+gtk_bitmask_unrealize (const GtkBitmask *mask, GtkBitmaskPrealloc *prealloc)
+{
+  if (mask != prealloc->orig &&
+      mask != &prealloc->bitmask)
+    g_free ((GtkBitmask *)mask);
+}
 
 GtkBitmask *
 _gtk_bitmask_new (void)
 {
-  return _gtk_bitmask_allocate (1);
+  return NULL;
 }
 
 GtkBitmask *
@@ -86,7 +191,8 @@ _gtk_bitmask_copy (const GtkBitmask *mask)
 {
   GtkBitmask *copy;
 
-  g_return_val_if_fail (mask != NULL, NULL);
+  if (gtk_bitmask_is_inline (mask))
+    return (GtkBitmask *)mask;
 
   copy = _gtk_bitmask_new ();
   _gtk_bitmask_union (&copy, mask);
@@ -97,18 +203,19 @@ _gtk_bitmask_copy (const GtkBitmask *mask)
 void
 _gtk_bitmask_free (GtkBitmask *mask)
 {
-  g_return_if_fail (mask != NULL);
-
-  g_free (mask);
+  if (!gtk_bitmask_is_inline (mask))
+    g_free (mask);
 }
 
 void
 _gtk_bitmask_print (const GtkBitmask *mask,
 		    GString          *string)
 {
+  GtkBitmaskPrealloc mask_prealloc;
   int i;
 
-  g_return_if_fail (mask != NULL);
+  gtk_bitmask_realize (&mask, &mask_prealloc);
+
   g_return_if_fail (string != NULL);
 
   for (i = mask->len * VALUE_SIZE_BITS - 1; i >= 0; i--)
@@ -120,6 +227,7 @@ _gtk_bitmask_print (const GtkBitmask *mask,
   if (i < 0)
     {
       g_string_append_c (string, '0');
+      gtk_bitmask_unrealize (mask, &mask_prealloc);
       return;
     }
 
@@ -127,6 +235,8 @@ _gtk_bitmask_print (const GtkBitmask *mask,
     {
       g_string_append_c (string, _gtk_bitmask_get (mask, i) ? '1' : '0');
     }
+
+  gtk_bitmask_unrealize (mask, &mask_prealloc);
 }
 
 char *
@@ -148,58 +258,129 @@ gtk_bitmask_shrink (GtkBitmask **mask)
 {
   guint i;
 
+  if (gtk_bitmask_is_inline (*mask))
+    return;
+
   for (i = (*mask)->len; i; i--)
     {
       if ((*mask)->data[i - 1])
 	break;
     }
 
-  (*mask)->len = i;
+  if (i == 0)
+    {
+      g_free (*mask);
+      *mask = NULL;
+    }
+  else
+    (*mask)->len = i;
 }
 
 void
 _gtk_bitmask_intersect (GtkBitmask      **mask,
 			const GtkBitmask *other)
 {
+  GtkBitmaskPrealloc other_prealloc;
   guint i;
 
   g_return_if_fail (mask != NULL);
-  g_return_if_fail (other != NULL);
+
+  if (gtk_bitmask_is_inline (*mask) &&
+      gtk_bitmask_is_inline (other))
+    {
+      if (mask == NULL || other == NULL)
+	*mask = NULL;
+      else
+	{
+	  /* Different bits, the intersection is empty */
+	  if (*mask != other)
+	    *mask = NULL;
+	  /* If same bit, the value is already right */
+	}
+
+      return;
+    }
+
+  gtk_bitmask_realize (&other, &other_prealloc);
+  gtk_bitmask_realize_for_write (mask, 0);
 
   _gtk_bitmask_resize (mask, MIN ((*mask)->len, other->len));
   for (i = 0; i < (*mask)->len; i++)
     (*mask)->data[i] &= other->data[i];
 
   gtk_bitmask_shrink (mask);
+
+  gtk_bitmask_unrealize (other, &other_prealloc);
 }
 
 void
 _gtk_bitmask_union (GtkBitmask      **mask,
 		    const GtkBitmask *other)
 {
+  GtkBitmaskPrealloc other_prealloc;
   guint i;
 
   g_return_if_fail (mask != NULL);
-  g_return_if_fail (other != NULL);
+
+  if (gtk_bitmask_is_inline (*mask) &&
+      gtk_bitmask_is_inline (other))
+    {
+      /* Union nothing with something is something  */
+      if (*mask == NULL)
+	{
+	  *mask = (GtkBitmask *)other;
+	  return;
+	}
+
+      /* Union with nothing or same is same */
+      if (other == NULL ||
+	  *mask == other)
+	return;
+    }
+
+  gtk_bitmask_realize (&other, &other_prealloc);
+  gtk_bitmask_realize_for_write (mask, other->len);
 
   _gtk_bitmask_resize (mask, MAX ((*mask)->len, other->len));
   for (i = 0; i < other->len; i++)
     (*mask)->data[i] |= other->data[i];
+
+  gtk_bitmask_unrealize (other, &other_prealloc);
 }
 
 void
 _gtk_bitmask_subtract (GtkBitmask      **mask,
 		       const GtkBitmask *other)
 {
+  GtkBitmaskPrealloc other_prealloc;
   guint i;
 
   g_return_if_fail (mask != NULL);
-  g_return_if_fail (other != NULL);
+
+  if (gtk_bitmask_is_inline (*mask) &&
+      gtk_bitmask_is_inline (other))
+    {
+      /* Subtract from nothing, or subtract nothing => no change */
+      if (*mask == NULL ||
+	  other == NULL)
+	return;
+
+      /* Subtract the same bit => nothing */
+      if (*mask == other)
+	*mask = NULL;
+      /* Subtract other bit => no change */
+      return;
+    }
+
+  gtk_bitmask_realize (&other, &other_prealloc);
+  gtk_bitmask_realize_for_write (mask, 0);
 
   for (i = 0; i < other->len; i++)
     (*mask)->data[i] &= ~(other->data[i]);
 
   gtk_bitmask_shrink (mask);
+
+  gtk_bitmask_unrealize (other, &other_prealloc);
 }
 
 static void
@@ -217,7 +398,17 @@ _gtk_bitmask_get (const GtkBitmask *mask,
 {
   guint array_index, bit_index;
 
-  g_return_val_if_fail (mask != NULL, FALSE);
+  if (mask == NULL)
+    return FALSE;
+
+  if (gtk_bitmask_is_bit (mask))
+    {
+      guint bit = gtk_bitmask_get_bit (mask);
+      if (bit == index_)
+	return TRUE;
+      else
+	return FALSE;
+    }
 
   gtk_bitmask_indexes (index_, &array_index, &bit_index);
 
@@ -236,6 +427,23 @@ _gtk_bitmask_set (GtkBitmask **mask,
 
   g_return_if_fail (mask != NULL);
 
+  if (*mask == NULL)
+    {
+      if (value)
+	*mask = gtk_bitmask_for_bit (index_);
+      return;
+    }
+
+  if (gtk_bitmask_is_bit (*mask) &&
+      gtk_bitmask_get_bit (*mask) == index_)
+    {
+      if (!value)
+	*mask = NULL;
+      return;
+    }
+
+  gtk_bitmask_realize_for_write (mask, 0);
+
   gtk_bitmask_indexes (index_, &array_index, &bit_index);
 
   if (value)
@@ -274,19 +482,23 @@ _gtk_bitmask_invert_range (GtkBitmask **mask,
 gboolean
 _gtk_bitmask_is_empty (const GtkBitmask *mask)
 {
-  g_return_val_if_fail (mask != NULL, FALSE);
-
-  return mask->len == 0;
+  return mask == NULL;
 }
 
 gboolean
 _gtk_bitmask_equals (const GtkBitmask  *mask,
 		     const GtkBitmask  *other)
 {
+  GtkBitmaskPrealloc mask_prealloc;
+  GtkBitmaskPrealloc other_prealloc;
   guint i;
 
-  g_return_val_if_fail (mask != NULL, FALSE);
-  g_return_val_if_fail (other != NULL, FALSE);
+  if (gtk_bitmask_is_inline (mask) &&
+      gtk_bitmask_is_inline (other))
+    return mask == other;
+
+  gtk_bitmask_realize (&mask, &mask_prealloc);
+  gtk_bitmask_realize (&other, &other_prealloc);
 
   if (mask->len != other->len)
     return FALSE;
@@ -297,6 +509,9 @@ _gtk_bitmask_equals (const GtkBitmask  *mask,
 	return FALSE;
     }
 
+  gtk_bitmask_unrealize (mask, &mask_prealloc);
+  gtk_bitmask_unrealize (other, &other_prealloc);
+
   return TRUE;
 }
 
@@ -304,36 +519,58 @@ gboolean
 _gtk_bitmask_intersects (const GtkBitmask *mask,
 			 const GtkBitmask *other)
 {
+  GtkBitmaskPrealloc mask_prealloc;
+  GtkBitmaskPrealloc other_prealloc;
   int i;
+  gboolean res;
 
-  g_return_val_if_fail (mask != NULL, FALSE);
-  g_return_val_if_fail (other != NULL, FALSE);
+  if (gtk_bitmask_is_inline (mask) &&
+      gtk_bitmask_is_inline (other))
+    {
+      if (mask == NULL || other == NULL)
+	return FALSE;
+
+      if (mask == other)
+	return TRUE;
 
+      return FALSE;
+    }
+
+  gtk_bitmask_realize (&mask, &mask_prealloc);
+  gtk_bitmask_realize (&other, &other_prealloc);
+
+  res = FALSE;
   for (i = MIN (mask->len, other->len) - 1; i >= 0; i--)
     {
       if (mask->data[i] & other->data[i])
-	return TRUE;
+	{
+	  res = TRUE;
+	  break;
+	}
     }
 
-  return FALSE;
+  gtk_bitmask_unrealize (mask, &mask_prealloc);
+  gtk_bitmask_unrealize (other, &other_prealloc);
+
+  return res;
 }
 
 void
 _gtk_bitmask_clear (GtkBitmask **mask)
 {
-  g_return_if_fail (mask != NULL);
-
-  (*mask)->len = 0;
+  _gtk_bitmask_free (*mask);
+  *mask = NULL;
 }
 
 guint
 _gtk_bitmask_get_uint (const GtkBitmask  *mask,
 		       guint              index_)
 {
+  GtkBitmaskPrealloc mask_prealloc;
   guint array_index, bit_index;
   VALUE_TYPE value1, value2;
 
-  g_return_val_if_fail (mask != NULL, FALSE);
+  gtk_bitmask_realize (&mask, &mask_prealloc);
 
   gtk_bitmask_indexes (index_, &array_index, &bit_index);
 
@@ -349,6 +586,8 @@ _gtk_bitmask_get_uint (const GtkBitmask  *mask,
   else
     value2 = 0;
 
+  gtk_bitmask_unrealize (mask, &mask_prealloc);
+
   return (guint)(value1 | value2);
 }
 
@@ -363,6 +602,8 @@ _gtk_bitmask_set_uint (GtkBitmask  **mask,
 
   g_return_if_fail (mask != NULL);
 
+  gtk_bitmask_realize_for_write (mask, 0);
+
   gtk_bitmask_indexes (index_, &array_index, &bit_index);
 
   value1 = value2 = 0;
@@ -401,10 +642,14 @@ _gtk_bitmask_set_uint (GtkBitmask  **mask,
 guint
 _gtk_bitmask_hash (const GtkBitmask *mask)
 {
+  GtkBitmaskPrealloc mask_prealloc;
   int i;
   VALUE_TYPE value, hash;
 
-  g_return_val_if_fail (mask != NULL, FALSE);
+  if (mask == NULL)
+    return 0;
+
+  gtk_bitmask_realize (&mask, &mask_prealloc);
 
   hash = 0;
 
@@ -417,6 +662,8 @@ _gtk_bitmask_hash (const GtkBitmask *mask)
   if (sizeof (hash) > sizeof (guint))
     hash = hash ^ (hash >> 32);
 
+  gtk_bitmask_unrealize (mask, &mask_prealloc);
+
   return hash;
 }
 
@@ -424,9 +671,15 @@ gboolean
 _gtk_bitmask_find_next_set (const GtkBitmask  *mask,
 			    guint             *pos)
 {
+  GtkBitmaskPrealloc mask_prealloc;
   guint array_index, bit_index;
   VALUE_TYPE value;
 
+  if (mask == NULL)
+    return FALSE;
+
+  gtk_bitmask_realize (&mask, &mask_prealloc);
+
   gtk_bitmask_indexes (*pos, &array_index, &bit_index);
 
   while (array_index < mask->len)
@@ -447,5 +700,7 @@ _gtk_bitmask_find_next_set (const GtkBitmask  *mask,
       bit_index = 0;
     }
 
+  gtk_bitmask_unrealize (mask, &mask_prealloc);
+
   return FALSE;
 }
diff --git a/gtk/gtkwidgetpath.c b/gtk/gtkwidgetpath.c
index b63d191..5247936 100644
--- a/gtk/gtkwidgetpath.c
+++ b/gtk/gtkwidgetpath.c
@@ -736,7 +736,6 @@ _gtk_widget_path_iter_add_classes (GtkWidgetPath *path,
 
   g_return_if_fail (path != NULL);
   g_return_if_fail (path->elems->len != 0);
-  g_return_if_fail (classes != NULL);
 
   if (pos < 0 || pos >= path->elems->len)
     pos = path->elems->len - 1;
@@ -975,7 +974,6 @@ _gtk_widget_path_iter_add_regions (GtkWidgetPath  *path,
 
   g_return_if_fail (path != NULL);
   g_return_if_fail (path->elems->len != 0);
-  g_return_if_fail (regions != NULL);
 
   if (pos < 0 || pos >= path->elems->len)
     pos = path->elems->len - 1;
[Date Prev][Date Next] [Thread Prev][Thread Next] [Thread Index] [Date Index] [Author Index]