After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 698064 - Add g_ptr_array_contains()
Add g_ptr_array_contains()
Status: RESOLVED FIXED
Product: glib
Classification: Platform
Component: general
unspecified
Other Linux
: Normal enhancement
: ---
Assigned To: gtkdev
gtkdev
Depends on:
Blocks:
 
 
Reported: 2013-04-15 15:17 UTC by Xavier Claessens
Modified: 2017-05-02 15:57 UTC
See Also:
GNOME target: ---
GNOME version: ---


Attachments
Add g_ptr_array_contains() (2.18 KB, patch)
2013-04-15 15:17 UTC, Xavier Claessens
none Details | Review
Add g_ptr_array_contains() (2.27 KB, patch)
2014-06-17 09:35 UTC, Philip Withnall
none Details | Review
garray: Add g_ptr_array_find[_custom]() (4.09 KB, patch)
2014-06-17 14:49 UTC, Philip Withnall
none Details | Review
garray: Add g_ptr_array_find[_custom]() (4.58 KB, patch)
2014-06-18 22:23 UTC, Philip Withnall
none Details | Review
garray: Add g_ptr_array_find[_with_equal_func]() (4.64 KB, patch)
2017-03-23 16:45 UTC, Philip Withnall
none Details | Review
garray: Add g_ptr_array_find[_with_equal_func]() (4.77 KB, patch)
2017-03-23 16:46 UTC, Philip Withnall
committed Details | Review

Description Xavier Claessens 2013-04-15 15:17:09 UTC
I think it is useful function, tp-glib has it and when I code something that does not depend on tp-glib I always reimplement it.
Comment 1 Xavier Claessens 2013-04-15 15:17:59 UTC
Created attachment 241575 [details] [review]
Add g_ptr_array_contains()

Copied from telepathy-glib's tp_g_ptr_array_contains().
Comment 2 Allison Karlitskaya (desrt) 2013-04-16 12:36:57 UTC
One reason not to like this function: I might naturally expect to be able to do this:


g_ptr_array_append (array, g_strdup ("foo"));
g_ptr_array_append (array, g_strdup ("bar"));

if (g_ptr_array_contains (array, "foo"))
  {
    ... why does this not get run?
  }


I think that this would need to be explicitly spelled out in the docs, even though it's obvious when you think about it (because you know that GPtrArray has no concept of what is contained in it and you know that strings in C are essentially just untyped character pointers with no in-built comparison function).


Otherwise, I'm _mildly_ in favour of this, assuming that others don't yell too loud against it.
Comment 3 Xavier Claessens 2013-04-16 12:48:55 UTC
g_ptr_array_add (array, g_strdup ("foo"));
g_ptr_array_add (array, g_strdup ("bar"));
g_ptr_array_add (array, NULL);
if (g_strv_contains (array->pdata, "foo"))
  {
  }

If you agree on g_strv_contains() I've proposed as well. The doc could be more explicit I guess.
Comment 4 Philip Withnall 2014-06-17 09:35:48 UTC
Created attachment 278579 [details] [review]
Add g_ptr_array_contains()

Copied from telepathy-glib's tp_g_ptr_array_contains().
Comment 5 Philip Withnall 2014-06-17 09:37:04 UTC
Here’s an updated version which documents the use of pointer comparisons more explicitly. I think this definitely is a useful function to have, since most of the uses of GPtrArray I’ve seen have been storing structs or objects, not strings, so pointer comparisons are appropriate.
Comment 6 Dan Winship 2014-06-17 13:50:18 UTC
could do g_ptr_array_find(array, element) and g_ptr_array_find_custom(array, element, compare_func), a la g_slist_find() / g_slist_find_custom().
Comment 7 Philip Withnall 2014-06-17 14:39:39 UTC
(In reply to comment #6)
> could do g_ptr_array_find(array, element) and g_ptr_array_find_custom(array,
> element, compare_func), a la g_slist_find() / g_slist_find_custom().

Yeah, I think that’s a better suggestion. A brief look in Devhelp gives loads of *_find[_custom]() APIs, and only a few *_contains() APIs. I think consistency might win in this case.
Comment 8 Philip Withnall 2014-06-17 14:49:53 UTC
Created attachment 278607 [details] [review]
garray: Add g_ptr_array_find[_custom]()

Partially based on telepathy-glib’s tp_g_ptr_array_contains(), and a
patch by Xavier Claessens <xavier.claessens@collabora.co.uk>.
Comment 9 Allison Karlitskaya (desrt) 2014-06-17 23:04:02 UTC
Review of attachment 278607 [details] [review]:

Seems a little strange that one of these returns only a boolean and the other one also an index (by reference).

Use of gsize is a bit weird as well: other index-based functions on GPtrArray operate on guint.  Also: the guint field is exposed as part of the public struct.

Also weird that we return the index by reference instead of using a signed value and "-1 for not found" as the return value.  I guess that might clash with the fact that we have a uint for the index in other places.

(just thinking aloud) on 32bit machines, it's impossible that using an int could ever land us in trouble because we could not possibly construct a GPtrArray containing enough items to overflow a signed int.  On 64bit, it's theoretically possible that we could have a monster GPtrArray -- but then gsize (and glong) are larger there.  I guess it might make sense to have these functions return 'glong'...  but that's ugly.  I guess returning-by-reference is not that awful after all.... but it should definitely be a guint -- not a gsize.

Next, we get into the discussion about if we should have a variant of this that works on sorted pointer arrays by doing a binary search.

All told, I think this is another one of those cases where I wonder if it's not just easier to open-code in most cases.... the one place I could see this commonly used is the custom function case with g_str_equal, but I'd consider that to be better handled under a dedicated 'string list builder' class that we've often discussed having.
Comment 10 Philip Withnall 2014-06-18 22:20:40 UTC
(In reply to comment #9)
> Review of attachment 278607 [details] [review]:
> 
> Seems a little strange that one of these returns only a boolean and the other
> one also an index (by reference).

Mmm. I was going along the lines of g_ptr_array_find_custom() being the ‘*_full()’ version of the method. But it would make just as much sense to return an index (by reference) from g_ptr_array_find() as well.

> but it should definitely be a guint -- not a
> gsize.

OK, I’ll change that in the next iteration.

> Next, we get into the discussion about if we should have a variant of this that
> works on sorted pointer arrays by doing a binary search.

I’ve never needed anything like that. Shall we take this one step at a time? :-)

> All told, I think this is another one of those cases where I wonder if it's not
> just easier to open-code in most cases.... the one place I could see this
> commonly used is the custom function case with g_str_equal, but I'd consider
> that to be better handled under a dedicated 'string list builder' class that
> we've often discussed having.

I don’t think open-coding it is any easier. It just creates messy code: you have to declare a ‘gboolean found’ somewhere, create a pointless loop which does the equality checks, sets found and bails out, and then do the check you actually wanted to after all that. The only advantage to open-coding that I see is that it can simplify the equality checks (and means you don’t have to move them out to a strcmp()-style function).
Comment 11 Philip Withnall 2014-06-18 22:23:54 UTC
Created attachment 278720 [details] [review]
garray: Add g_ptr_array_find[_custom]()

Partially based on telepathy-glib’s tp_g_ptr_array_contains(), and a
patch by Xavier Claessens <xavier.claessens@collabora.co.uk>.
Comment 12 Dan Winship 2014-06-18 23:45:45 UTC
I had been thinking it would return an index or -1, but I'm not sure there's precedent either way in glib
Comment 13 Allison Karlitskaya (desrt) 2017-03-23 12:51:56 UTC
Can we have a GEqualFunc instead of a GCompareFunc?  I'm gonna get this wrong all the time otherwise...
Comment 14 Allison Karlitskaya (desrt) 2017-03-23 12:56:03 UTC
I don't like _custom() either.  It's really only used on the G(S)List API (and consequently, GQueue).  They also all use comparefuncs, which is another inconsistency.

Also: _contains() here is not necessarily evil.

What if it was like:
  - _find()
  - _find_with_equal_func()

and maybe even these, which pass through a NULL index:
  - _contains()
  - _contains_with_equal_func()
Comment 15 Philip Withnall 2017-03-23 12:58:38 UTC
I’ll reply fully with my thoughts in a bit. Just a note about something else Allison mentioned: where we use GEqualFunc, we should document which order its arguments are passed in.
Comment 16 Philip Withnall 2017-03-23 15:57:25 UTC
(In reply to Philip Withnall from comment #15)
> where we use GEqualFunc, we should document which order
> its arguments are passed in.

⇒ b3362bb ghash: Document order of parameters in GEqualFunc usage
Comment 17 Philip Withnall 2017-03-23 16:13:51 UTC
(In reply to Allison Lortie (desrt) from comment #14)
> I don't like _custom() either.  It's really only used on the G(S)List API
> (and consequently, GQueue).  They also all use comparefuncs, which is
> another inconsistency.
> 
> Also: _contains() here is not necessarily evil.
> 
> What if it was like:
>   - _find()
>   - _find_with_equal_func()

I would be fine with this.

> and maybe even these, which pass through a NULL index:
>   - _contains()
>   - _contains_with_equal_func()

Those would be equivalent to:
   g_ptr_array_find (haystack, needle, NULL)
and
   g_ptr_array_find_custom (haystack, needle, equal_func, NULL)

which are so trivial that they could easily be open-coded by people; or we could put them in gptrarray.h as static inlines.

On this basis, I’ll update the patch to use GEqualFunc (good catch) and use find() and find_with_equal_func() naming — but I won’t add contains() and contains_with_equal_func(). They can be added as a follow-up commit if people want them.
Comment 18 Philip Withnall 2017-03-23 16:45:20 UTC
Created attachment 348585 [details] [review]
garray: Add g_ptr_array_find[_with_equal_func]()

Partially based on telepathy-glib’s tp_g_ptr_array_contains(), and a
patch by Xavier Claessens <xavier.claessens@collabora.co.uk>.
Comment 19 Philip Withnall 2017-03-23 16:46:29 UTC
Created attachment 348586 [details] [review]
garray: Add g_ptr_array_find[_with_equal_func]()

Partially based on telepathy-glib’s tp_g_ptr_array_contains(), and a
patch by Xavier Claessens <xavier.claessens@collabora.co.uk>.
Comment 20 Philip Withnall 2017-03-23 16:47:21 UTC
(In reply to Philip Withnall from comment #19)
> Created attachment 348586 [details] [review] [review]
> garray: Add g_ptr_array_find[_with_equal_func]()
> 
> Partially based on telepathy-glib’s tp_g_ptr_array_contains(), and a
> patch by Xavier Claessens <xavier.claessens@collabora.co.uk>.

Updated to change the function naming, use the latest ‘Since:’ lines, GEqualFunc, and mention the argument order to the GEqualFunc.
Comment 21 Emmanuele Bassi (:ebassi) 2017-05-02 15:15:19 UTC
Review of attachment 348586 [details] [review]:

Looks okay to me, with a minor nitpick (not blocking).

::: glib/garray.c
@@ +1584,3 @@
+  for (i = 0; i < haystack->len; i++)
+    {
+  return FALSE;

Bear with me for a second. What if `equal_func` was nullable, and this would be:

  if (equal_func == NULL)
    contains = g_ptr_array_index (haystack, i) == needle;
  else
    contains = equal_func (g_ptr_array_index (haystack, i), needle);

  if (contains)
    {
      if (index_ != NULL)
        *index_ = i;
      return TRUE;
    }

Then g_ptr_array_find() would just be:

  return g_ptr_array_find_with_equal_func (haystack, needle, NULL, index_);

instead of a copy-paste.
Comment 22 Philip Withnall 2017-05-02 15:57:08 UTC
Pushed with the suggested change, plus some additions to the documentation (to clarify what happens if an element appears twice in the array) and some unit tests.

Thanks all!

Attachment 348586 [details] pushed as f6f6b3d - garray: Add g_ptr_array_find[_with_equal_func]()