[gtk+/wip/css-bitmasks: 1/6] Add various new functions to gtkbitmask

[Alexander Larsson <alexl src gnome org>]

commit c18d21f312a6e46a2c77188a96e5e8e8635c88e3
Author: Alexander Larsson <alexl redhat com>
Date:   Tue Feb 7 23:35:56 2012 +0100

    Add various new functions to gtkbitmask
    
    These are needed for later commits

 gtk/gtkbitmask.c        |  135 +++++++++++++++++++++++++++++++++++++++++++++++
 gtk/gtkbitmaskprivate.h |    9 +++
 gtk/tests/bitmask.c     |   57 ++++++++++++++++++++
 3 files changed, 201 insertions(+), 0 deletions(-)
---
diff --git a/gtk/gtkbitmask.c b/gtk/gtkbitmask.c
index a47d755..ae64f70 100644
--- a/gtk/gtkbitmask.c
+++ b/gtk/gtkbitmask.c
@@ -277,3 +277,138 @@ _gtk_bitmask_intersects (const GtkBitmask *mask,
   return FALSE;
 }
 
+void
+_gtk_bitmask_clear (GtkBitmask *mask)
+{
+  int i;
+
+  g_return_if_fail (mask != NULL);
+
+  for (i = mask->len - 1; i >= 0; i--)
+    g_array_index (mask, VALUE_TYPE, i) = 0;
+}
+
+guint
+_gtk_bitmask_get_uint (const GtkBitmask  *mask,
+		       guint              index_)
+{
+  guint array_index, bit_index;
+  VALUE_TYPE value1, value2;
+
+  g_return_val_if_fail (mask != NULL, FALSE);
+
+  gtk_bitmask_indexes (index_, &array_index, &bit_index);
+
+  value1 = value2 = 0;
+  if (array_index < mask->len)
+    value1 = g_array_index (mask, VALUE_TYPE, array_index);
+  if (array_index + 1 < mask->len)
+    value2 = g_array_index (mask, VALUE_TYPE, array_index + 1);
+
+  value1 >>= bit_index;
+  if (bit_index != 0)
+    value2 <<= VALUE_SIZE_BITS - bit_index;
+  else
+    value2 = 0;
+
+  return (guint)(value1 | value2);
+}
+
+void
+_gtk_bitmask_set_uint (GtkBitmask  *mask,
+		       guint        index_,
+		       guint        bits)
+{
+  guint array_index, bit_index;
+  VALUE_TYPE value1, value2;
+  VALUE_TYPE new_value1, new_value2;
+
+  g_return_if_fail (mask != NULL);
+
+  gtk_bitmask_indexes (index_, &array_index, &bit_index);
+
+  value1 = value2 = 0;
+  if (array_index < mask->len)
+    value1 = g_array_index (mask, VALUE_TYPE, array_index);
+  if (array_index + 1 < mask->len)
+    value2 = g_array_index (mask, VALUE_TYPE, array_index + 1);
+
+  /* Mask out old uint value */
+  new_value1 = ((VALUE_TYPE)G_MAXUINT) << bit_index;
+  if (bit_index != 0)
+    new_value2 = ((VALUE_TYPE)G_MAXUINT) >> (VALUE_SIZE_BITS - bit_index);
+  else
+    new_value2 = 0;
+  value1 &= ~new_value1;
+  value2 &= ~new_value2;
+
+  /* merge in new uint value */
+  new_value1 = ((VALUE_TYPE)bits) << bit_index;
+  if (bit_index != 0)
+    new_value2 = ((VALUE_TYPE)bits) >> (VALUE_SIZE_BITS - bit_index);
+  else
+    new_value2 = 0;
+  value1 |= new_value1;
+  value2 |= new_value2;
+
+  /* Ensure there is space to write back */
+  g_array_set_size (mask, MAX (mask->len, array_index + 2));
+
+  g_array_index (mask, VALUE_TYPE, array_index) = value1;
+  g_array_index (mask, VALUE_TYPE, array_index + 1) = value2;
+
+  gtk_bitmask_shrink (mask);
+}
+
+guint
+_gtk_bitmask_hash (const GtkBitmask *mask)
+{
+  int i;
+  VALUE_TYPE value, hash;
+
+  g_return_val_if_fail (mask != NULL, FALSE);
+
+  hash = 0;
+
+  for (i = mask->len - 1; i >= 0; i--)
+    {
+      value = g_array_index (mask, VALUE_TYPE, i);
+      hash = hash ^ value;
+    }
+
+  if (sizeof (hash) > sizeof (guint))
+    hash = hash ^ (hash >> 32);
+
+  return hash;
+}
+
+gboolean
+_gtk_bitmask_find_next_set (const GtkBitmask  *mask,
+			    guint             *pos)
+{
+  guint array_index, bit_index;
+  VALUE_TYPE value;
+
+  gtk_bitmask_indexes (*pos, &array_index, &bit_index);
+
+  while (array_index < mask->len)
+    {
+      value = g_array_index (mask, VALUE_TYPE, array_index);
+
+      /* TODO: This could use ffsl if bit_index == 0 */
+      while (bit_index < VALUE_SIZE_BITS)
+	{
+	  if (value & VALUE_BIT (bit_index))
+	    {
+	      *pos = array_index * VALUE_SIZE_BITS + bit_index;
+	      return TRUE;
+	    }
+	  bit_index++;
+	}
+      array_index++;
+      bit_index = 0;
+    }
+
+  return FALSE;
+}
+
diff --git a/gtk/gtkbitmaskprivate.h b/gtk/gtkbitmaskprivate.h
index adb65cf..9c699a8 100644
--- a/gtk/gtkbitmaskprivate.h
+++ b/gtk/gtkbitmaskprivate.h
@@ -52,6 +52,12 @@ gboolean       _gtk_bitmask_get                  (const GtkBitmask  *mask,
 void           _gtk_bitmask_set                  (GtkBitmask        *mask,
                                                   guint              index_,
                                                   gboolean           value);
+void           _gtk_bitmask_clear                (GtkBitmask        *mask);
+guint          _gtk_bitmask_get_uint             (const GtkBitmask  *mask,
+                                                  guint              index_);
+void           _gtk_bitmask_set_uint             (GtkBitmask        *mask,
+                                                  guint              index_,
+						  guint              bits);
 
 void           _gtk_bitmask_invert_range         (GtkBitmask        *mask,
                                                   guint              start,
@@ -62,6 +68,9 @@ gboolean       _gtk_bitmask_equals               (const GtkBitmask  *mask,
                                                   const GtkBitmask  *other);
 gboolean       _gtk_bitmask_intersects           (const GtkBitmask  *mask,
                                                   const GtkBitmask  *other);
+guint          _gtk_bitmask_hash                 (const GtkBitmask  *mask);
+gboolean       _gtk_bitmask_find_next_set        (const GtkBitmask  *mask,
+						  guint             *pos);
 
 G_END_DECLS
 
diff --git a/gtk/tests/bitmask.c b/gtk/tests/bitmask.c
index 71a3c97..4bbfa96 100644
--- a/gtk/tests/bitmask.c
+++ b/gtk/tests/bitmask.c
@@ -156,6 +156,61 @@ test_set (void)
 }
 
 static void
+test_set_uint (void)
+{
+  guint i, j, k;
+  guint index;
+  GtkBitmask *copy;
+  GtkBitmask *mask;
+  guint val;
+
+  for (i = 0; i < N_RUNS; i++)
+    {
+      mask = _gtk_bitmask_copy (masks[g_test_rand_int_range (0, G_N_ELEMENTS (tests))]);
+      val = g_test_rand_int ();
+      copy = _gtk_bitmask_copy (mask);
+
+      for (j = 0; j < N_TRIES; j++)
+        {
+	  index = g_test_rand_int_range (0, MAX_INDEX);
+
+	  _gtk_bitmask_set_uint (copy, index, val);
+
+	  for (k = 0; k < sizeof (guint) * 8; k++)
+	    _gtk_bitmask_set (mask, index + k, val & (1<<k));
+
+	  assert_cmpmasks (copy, mask);
+        }
+
+      _gtk_bitmask_free (copy);
+    }
+}
+
+static void
+test_get_uint (void)
+{
+  guint i, j, k;
+  guint index;
+  GtkBitmask *mask;
+  guint val;
+
+  for (i = 0; i < N_RUNS; i++)
+    {
+      mask = masks[g_test_rand_int_range (0, G_N_ELEMENTS (tests))];
+
+      for (j = 0; j < N_TRIES; j++)
+        {
+	  index = g_test_rand_int_range (0, 100);
+
+	  val = _gtk_bitmask_get_uint (mask, index);
+
+	  for (k = 0; k < sizeof (guint) * 8; k++)
+	    g_assert_cmpint (!!_gtk_bitmask_get (mask, index + k), ==, !!(val & (1<<k)));
+        }
+    }
+}
+
+static void
 test_union (void)
 {
   GtkBitmask *left, *right, *expected;
@@ -328,6 +383,8 @@ main (int argc, char *argv[])
   g_test_add_func ("/bitmask/is_empty", test_is_empty);
   g_test_add_func ("/bitmask/equals", test_equals);
   g_test_add_func ("/bitmask/set", test_set);
+  g_test_add_func ("/bitmask/set_uint", test_set_uint);
+  g_test_add_func ("/bitmask/get_uint", test_get_uint);
   g_test_add_func ("/bitmask/union", test_union);
   g_test_add_func ("/bitmask/intersect", test_intersect);
   g_test_add_func ("/bitmask/invert_range", test_invert_range);