[glib] sequence: add g_sequence_is_empty()

[Christian Hergert <chergert src gnome org>]

commit 8fccf8e4e3ae87f3c1069270daeb2a59a40bf89d
Author: Christian Hergert <chergert redhat com>
Date:   Thu Oct 15 12:54:09 2015 -0700

    sequence: add g_sequence_is_empty()
    
    This function provides an O(1) check to determine if a sequence is empty.
    Compare this to the two following alternatives to perform the same check.
    
    O(h):  if (0 == g_sequence_get_length (seq))
    O(2h): if (g_sequence_get_begin_iter(seq) == g_sequence_get_end_iter(seq))
    
    Where `h' is the height of the tree.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=756316

 glib/gsequence.c      |   20 ++++++++++++++++++++
 glib/gsequence.h      |    2 ++
 glib/tests/sequence.c |   26 ++++++++++++++++++++++++++
 3 files changed, 48 insertions(+), 0 deletions(-)
---
diff --git a/glib/gsequence.c b/glib/gsequence.c
index 76e24e7..475990a 100644
--- a/glib/gsequence.c
+++ b/glib/gsequence.c
@@ -1244,6 +1244,26 @@ g_sequence_get_length (GSequence *seq)
 }
 
 /**
+ * g_sequence_is_empty:
+ * @seq: a #GSequence
+ *
+ * Returns %TRUE if the sequence contains zero items.
+ *
+ * This function is functionally identical to checking the result of
+ * g_sequence_get_length() being equal to zero. However this function is
+ * implemented in O(1) running time.
+ *
+ * Returns: %TRUE if the sequence is empty, otherwise %FALSE.
+ *
+ * Since: 2.48
+ */
+gboolean
+g_sequence_is_empty (GSequence *seq)
+{
+  return (seq->end_node->parent == NULL) && (seq->end_node->left == NULL);
+}
+
+/**
  * g_sequence_get_end_iter:
  * @seq: a #GSequence
  *
diff --git a/glib/gsequence.h b/glib/gsequence.h
index 9939132..879bb04 100644
--- a/glib/gsequence.h
+++ b/glib/gsequence.h
@@ -59,6 +59,8 @@ GLIB_AVAILABLE_IN_ALL
 void           g_sequence_sort_iter          (GSequence                *seq,
                                               GSequenceIterCompareFunc  cmp_func,
                                               gpointer                  cmp_data);
+GLIB_AVAILABLE_IN_2_48
+gboolean       g_sequence_is_empty           (GSequence                *seq);
 
 
 /* Getting iters */
diff --git a/glib/tests/sequence.c b/glib/tests/sequence.c
index 27a7f5a..929f650 100644
--- a/glib/tests/sequence.c
+++ b/glib/tests/sequence.c
@@ -1356,6 +1356,31 @@ test_stable_sort (void)
   g_sequence_free (seq);
 }
 
+static void
+test_empty (void)
+{
+  GSequence *seq;
+  int i;
+
+  seq = g_sequence_new (NULL);
+  g_assert_cmpint (TRUE, ==, g_sequence_is_empty (seq));
+
+  for (i = 0; i < 1000; i++)
+    {
+      g_sequence_append (seq, GINT_TO_POINTER (i));
+      g_assert_false (g_sequence_is_empty (seq));
+    }
+
+  for (i = 0; i < 1000; i++)
+    {
+      GSequenceIter *end = g_sequence_get_end_iter (seq);
+      g_assert_false (g_sequence_is_empty (seq));
+      g_sequence_remove (g_sequence_iter_prev (end));
+    }
+
+  g_assert_true (g_sequence_is_empty (seq));
+}
+
 int
 main (int argc,
       char **argv)
@@ -1371,6 +1396,7 @@ main (int argc,
   g_test_add_func ("/sequence/iter-move", test_iter_move);
   g_test_add_func ("/sequence/insert-sorted-non-pointer", test_insert_sorted_non_pointer);
   g_test_add_func ("/sequence/stable-sort", test_stable_sort);
+  g_test_add_func ("/sequence/is_empty", test_empty);
 
   /* Regression tests */
   for (i = 0; i < G_N_ELEMENTS (seeds); ++i)