Created attachment 117051 [details] [review]
Path to add g_sequence_find and g_sequence_find_iter

glib/tests/gsequence-test.c seems to be missing

Created attachment 118293 [details] [review]
Updated patch with test added

I've also removed the autofoo changes to get glib to work with libtool 2.2. I'll attach these in another bug.

Forgive me if I'm just too stupid, but where the testcase part in this patch? It still only contains the glib/tests/Makefile.am changes and not the actual testcase.

oh, hmm, you're quite right, I must have been stupid when removing the autofoo from the diff. 

Created attachment 118332 [details] [review]
Really with the testcase this time, I hope

The obvious first question is why can't you just dereference the iter returned from g_sequence_search() and see if it contains the data in question?

g_sequence_search() returns a pointer to the first position *after* the searched-for data (this fact could be documented and added to the test suite), so g_sequence_find() can be written like this:

GSequenceIter *
g_sequence_find ()
{
    iter = g_sequence_search()
   
    iter = g_sequence_prev()

    if (compare (iter, needle) == 0)
        return iter;

    return NULL;
}

Hence, applications can do it themselves.

No, that doesn't work. Maybe it should, but it doesn't.

if you don't believe me, try it..

I'll reply with more technical details of why this doesn't work when I have more time and brain.

Right, more time and brain now :)

The case where this doesn't work is if your sort function is not totally ordered - i.e. if multiple items compare as identical (cmp_func returns 0). One common use case here is sorting on date or string.

I guess its possible to iterate the g_sequence_priv, using the compare function to check that the items are compare-function-wise-identical, but that's starting to get a bit non-obvious IMHO.

If multiple items compare equal to the item passed in, they will be stored next to each other in the sequence, so the pseudo-code I wrote above will still work because g_sequence_search() returns a pointer to the first position after the set of items that compare equal.

To save me arguing, I'm attaching a testcase that shows the issue with your suggestion.

Created attachment 119944 [details]
Testcase

This testcase mixes two comparison functions: strncmp() and ==, which can't work. 

When you use your "sorter" function, the GSequence has no way of telling the difference between "test1_1" and "test1_2", so you can't expect to find any particular one of them when you search for "test1_1". The sequence_find() in your patch wouldn't work either because it doesn't walk all the items that compared equal.

For what it sounds like you are trying to do, you will need to take the actual pointer into account in the sorting function. Ie., something like this (uncompiled) code:

static gint sorter (gconstpointer a, gconstpointer b, gpointer user_data)
{
        int c;
	const char *str1 = a;
	const char *str2 = b;
	printf ("comparing %s (%p) to %s (%p)\n", str1, str1, str2,str2);
	c = strncmp (str1, str2,5);

        if (c == 0)
        {
            gssize ia = (gssize)a;
            gssize ib = (gssize)b;

            if (ia == ib) return 0;
            else if (ia > ib) return 1;
            else return -1;
        }
        else return c;
}

This will sort by the string value, but if the string value is identical, it will compare the pointers.

Ah, that makes sense. I'll close the bug.

I wonder if we should add some documentation about these things. If Sven and myself both got the wrong end of the stick, then I'm sure someone else will ;)

I would make sense to document and test in sequence-test.c that 

    g_sequence_insert_sorted()
    g_sequence_insert_sorted_ite()
    g_sequence_search() 
    etc.

all insert after the last item that compares equal to the one that is being inserted. It's not a coincidence that the code does this already: it makes repeatedly calling g_sequence_insert_sorted() a stable sort.