[PATCH] queue: Fix an l_queue_insert corner case

[PATCH] queue: Fix an l_queue_insert corner case

[Andrew Zaborowski]

[-- Attachment #1: Type: text/plain, Size: 910 bytes --]

The comment doc for the function says:

 * Inserts @data pointer at a position in the queue determined by the
 * compare @function.  @function should return > 0 if the @data (first
 * parameter) should be inserted after the current entry (second parameter).

however the function would insert @data after entries for which
@function returned a >= 0 value.  Change the check to > 0 to align with
the docs.
---
 ell/queue.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/ell/queue.c b/ell/queue.c
index 86c52ed..b28eecf 100644
--- a/ell/queue.c
+++ b/ell/queue.c
@@ -299,7 +299,7 @@ LIB_EXPORT bool l_queue_insert(struct l_queue *queue, void *data,
 	for (prev = NULL, cur = queue->head; cur; prev = cur, cur = cur->next) {
 		cmp = function(entry->data, cur->data, user_data);
 
-		if (cmp >= 0)
+		if (cmp > 0)
 			continue;
 
 		if (prev == NULL) {
-- 
2.27.0

Re: [PATCH] queue: Fix an l_queue_insert corner case

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 981 bytes --]

Hi Andrew,

On 3/1/21 4:57 PM, Andrew Zaborowski wrote:
> The comment doc for the function says:
> 
>   * Inserts @data pointer at a position in the queue determined by the
>   * compare @function.  @function should return > 0 if the @data (first
>   * parameter) should be inserted after the current entry (second parameter).
> 

Right.  But the docs don't say anything about treatment of 0 returns.

> however the function would insert @data after entries for which
> @function returned a >= 0 value.  Change the check to > 0 to align with
> the docs.

The intent is that values that are 'equal' (@function returns 0) are inserted 
_after_ any entries already in the queue.  While not documented explicitly, I'm 
pretty sure that this is the only sensible behavior (and likely something we 
implicitly rely on).  So, I'm not sure this is the right fix?

> ---
>   ell/queue.c | 2 +-
>   1 file changed, 1 insertion(+), 1 deletion(-)
> 

Regards,
-Denis

Re: [PATCH] queue: Fix an l_queue_insert corner case

[Andrew Zaborowski]

[-- Attachment #1: Type: text/plain, Size: 1276 bytes --]

Hi Denis,

On Tue, 2 Mar 2021 at 16:03, Denis Kenzior <denkenz@gmail.com> wrote:
> On 3/1/21 4:57 PM, Andrew Zaborowski wrote:
> > The comment doc for the function says:
> >
> >   * Inserts @data pointer at a position in the queue determined by the
> >   * compare @function.  @function should return > 0 if the @data (first
> >   * parameter) should be inserted after the current entry (second parameter).
> >
>
> Right.  But the docs don't say anything about treatment of 0 returns.

Right, or about the treatment of any other value.

With this wording I'm pretty sure anyone you ask is going to interpret this as:

 - insert after current entry if returned value > 0
 - insert before current entry otherwise

>
> > however the function would insert @data after entries for which
> > @function returned a >= 0 value.  Change the check to > 0 to align with
> > the docs.
>
> The intent is that values that are 'equal' (@function returns 0) are inserted
> _after_ any entries already in the queue.  While not documented explicitly, I'm
> pretty sure that this is the only sensible behavior (and likely something we
> implicitly rely on).  So, I'm not sure this is the right fix?

We can change the docs to much that intent then...

Best regards

Re: [PATCH] queue: Fix an l_queue_insert corner case

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 1399 bytes --]

Hi Andrew,

> Right, or about the treatment of any other value.
> 
> With this wording I'm pretty sure anyone you ask is going to interpret this as:
> 
>   - insert after current entry if returned value > 0
>   - insert before current entry otherwise
> 
Just FYI, this is class modeled on the Gnome API:
https://developer.gnome.org/glib/stable/glib-Singly-Linked-Lists.html#g-slist-insert-sorted

I don't recall whether it actually works the same way as you interpret it.  They 
do document GCompareFunc, which might make things more or less ambiguous.

>>
>>> however the function would insert @data after entries for which
>>> @function returned a >= 0 value.  Change the check to > 0 to align with
>>> the docs.
>>
>> The intent is that values that are 'equal' (@function returns 0) are inserted
>> _after_ any entries already in the queue.  While not documented explicitly, I'm
>> pretty sure that this is the only sensible behavior (and likely something we
>> implicitly rely on).  So, I'm not sure this is the right fix?

This change:
'git show 13225cb2efd070618122abbae3c1b23600527658'

came about because someone came to a different conclusion and assumed the entry 
would be inserted afterwards.  I'm fuzzy now on the details, likely it was the 
scanning code in iwd.

> 
> We can change the docs to much that intent then...
> 

Sure.

Regards,
-Denis