[glib] New API: g_sequence_lookup() and g_sequence_lookup_iter()

[Xavier Claessens <xclaesse src gnome org>]

commit 4e309043311487d66157383991373107eac1f7b9
Author: Xavier Claessens <xclaesse gmail com>
Date:   Fri Apr 30 13:55:53 2010 +0200

    New API: g_sequence_lookup() and g_sequence_lookup_iter()
    
    Fixes bug #617254

 docs/reference/glib/glib-sections.txt |    2 +
 glib/gsequence.c                      |  132 ++++++++++++++++++++++++++++++++-
 glib/gsequence.h                      |    8 ++
 3 files changed, 141 insertions(+), 1 deletions(-)
---
diff --git a/docs/reference/glib/glib-sections.txt b/docs/reference/glib/glib-sections.txt
index 6540fe8..05ba4f8 100644
--- a/docs/reference/glib/glib-sections.txt
+++ b/docs/reference/glib/glib-sections.txt
@@ -2166,6 +2166,8 @@ g_sequence_remove_range
 g_sequence_move_range
 g_sequence_search
 g_sequence_search_iter
+g_sequence_lookup
+g_sequence_lookup_iter
 
 <SUBSECTION>
 g_sequence_get
diff --git a/glib/gsequence.c b/glib/gsequence.c
index 8b28ce7..5a55bee 100644
--- a/glib/gsequence.c
+++ b/glib/gsequence.c
@@ -133,6 +133,11 @@ static GSequenceNode *node_get_next      (GSequenceNode            *node);
 static gint           node_get_pos       (GSequenceNode            *node);
 static GSequenceNode *node_get_by_pos    (GSequenceNode            *node,
                                           gint                      pos);
+static GSequenceNode *node_find          (GSequenceNode            *haystack,
+                                          GSequenceNode            *needle,
+                                          GSequenceNode            *end,
+                                          GSequenceIterCompareFunc  cmp,
+                                          gpointer                  user_data);
 static GSequenceNode *node_find_closest  (GSequenceNode            *haystack,
                                           GSequenceNode            *needle,
                                           GSequenceNode            *end,
@@ -780,6 +785,46 @@ g_sequence_search (GSequence        *seq,
 }
 
 /**
+ * g_sequence_lookup:
+ * @seq: a #GSequence
+ * @data: data to lookup
+ * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It
+ *     is called with two items of the @seq and @user_data. It should
+ *     return 0 if the items are equal, a negative value if the first
+ *     item comes before the second, and a positive value if the second
+ *     item comes before the first.
+ * @cmp_data: user data passed to @cmp_func.
+ *
+ * Returns an iterator pointing to the position of the first item found
+ * equal to @data according to @cmp_func and @cmp_data. If more than one item
+ * is equal, it is not guaranteed that it is the first which is returned.
+ * In that case, you can use g_sequence_iter_next() and g_sequence_iter_prev()
+ * to get others.
+ *
+ * Return value: an #GSequenceIter pointing to the position of the first item
+ * found equal to @data according to @cmp_func and @cmp_data.
+ *
+ * Since: 2.26
+ **/
+GSequenceIter *
+g_sequence_lookup (GSequence *seq,
+                   gpointer data,
+                   GCompareDataFunc cmp_func,
+                   gpointer cmp_data)
+{
+  SortInfo info;
+
+  g_return_val_if_fail (seq != NULL, NULL);
+
+  info.cmp_func = cmp_func;
+  info.cmp_data = cmp_data;
+  info.end_node = seq->end_node;
+  check_seq_access (seq);
+
+  return g_sequence_lookup_iter (seq, data, iter_compare, &info);
+}
+
+/**
  * g_sequence_sort_iter:
  * @seq: a #GSequence
  * @cmp_func: the #GSequenceItercompare used to compare iterators in the
@@ -1007,6 +1052,57 @@ g_sequence_search_iter (GSequence                *seq,
 }
 
 /**
+ * g_sequence_lookup_iter:
+ * @seq: a #GSequence
+ * @data: data to lookup
+ * @iter_cmp: the #GSequenceIterCompare function used to compare iterators
+ *     in the sequence. It is called with two iterators pointing into @seq.
+ *     It should return 0 if the iterators are equal, a negative value if the
+ *     first iterator comes before the second, and a positive value if the
+ *     second iterator comes before the first.
+ * @cmp_data: user data passed to @iter_cmp
+ *
+ * Like g_sequence_lookup(), but uses
+ * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
+ * the compare function.
+ *
+ * Return value: an #GSequenceIter pointing to the position of the first item
+ * found equal to @data according to @cmp_func and @cmp_data.
+ *
+ * Since: 2.26
+ **/
+GSequenceIter *
+g_sequence_lookup_iter (GSequence *seq,
+                        gpointer data,
+                        GSequenceIterCompareFunc iter_cmp,
+                        gpointer cmp_data)
+{
+  GSequenceNode *node;
+  GSequenceNode *dummy;
+  GSequence *tmp_seq;
+
+  g_return_val_if_fail (seq != NULL, NULL);
+
+  check_seq_access (seq);
+
+  seq->access_prohibited = TRUE;
+
+  tmp_seq = g_sequence_new (NULL);
+  tmp_seq->real_sequence = seq;
+
+  dummy = g_sequence_append (tmp_seq, data);
+
+  node = node_find (seq->end_node, dummy,
+                    seq->end_node, iter_cmp, cmp_data);
+
+  g_sequence_free (tmp_seq);
+
+  seq->access_prohibited = FALSE;
+
+  return node;
+}
+
+/**
  * g_sequence_iter_get_sequence:
  * @iter: a #GSequenceIter
  *
@@ -1549,6 +1645,40 @@ node_get_by_pos (GSequenceNode *node,
 }
 
 static GSequenceNode *
+node_find (GSequenceNode            *haystack,
+           GSequenceNode            *needle,
+           GSequenceNode            *end,
+           GSequenceIterCompareFunc  iter_cmp,
+           gpointer                  cmp_data)
+{
+  gint c;
+
+  haystack = find_root (haystack);
+
+  do
+    {
+      /* iter_cmp can't be passed the end node, since the function may
+       * be user-supplied
+       */
+      if (haystack == end)
+        c = 1;
+      else
+        c = iter_cmp (haystack, needle, cmp_data);
+
+      if (c == 0)
+        break;
+
+      if (c > 0)
+        haystack = haystack->left;
+      else
+        haystack = haystack->right;
+    }
+  while (haystack != NULL);
+
+  return haystack;
+}
+
+static GSequenceNode *
 node_find_closest (GSequenceNode            *haystack,
                    GSequenceNode            *needle,
                    GSequenceNode            *end,
@@ -1572,7 +1702,7 @@ node_find_closest (GSequenceNode            *haystack,
       else
         c = iter_cmp (haystack, needle, cmp_data);
 
-      /* In the following we don't break even if c == 0. Instaed we go on
+      /* In the following we don't break even if c == 0. Instead we go on
        * searching along the 'bigger' nodes, so that we find the last one
        * that is equal to the needle.
        */
diff --git a/glib/gsequence.h b/glib/gsequence.h
index fa79066..6a21c3e 100644
--- a/glib/gsequence.h
+++ b/glib/gsequence.h
@@ -99,6 +99,14 @@ GSequenceIter *g_sequence_search_iter        (GSequence                *seq,
                                               gpointer                  data,
                                               GSequenceIterCompareFunc  iter_cmp,
                                               gpointer                  cmp_data);
+GSequenceIter *g_sequence_lookup             (GSequence                *seq,
+                                              gpointer                  data,
+                                              GCompareDataFunc          cmp_func,
+                                              gpointer                  cmp_data);
+GSequenceIter *g_sequence_lookup_iter        (GSequence                *seq,
+                                              gpointer                  data,
+                                              GSequenceIterCompareFunc  iter_cmp,
+                                              gpointer                  cmp_data);
 
 
 /* Dereferencing */