Skip to contentSkip to conversation

queue: Fix an l_queue_insert corner case

PATCH In review Andrew Zaborowski 2 participants 4 messages Mar 1, 2021 – Mar 2, 2021

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 queue: Fix an l_queue_insert corner case

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(-)
ell/queue.c +1 -1
index 86c52ed..b28eecf 100644
@@ -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) {
Signature · 1 line
2.27.0
#1 lore raw

Hi Andrew,

Quoted 6 lines · Andrew Zaborowski

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.

Quoted 3 lines

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?

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

Regards,
-Denis

#2 lore raw

Hi Denis,

Quoted 9 lines · Denis Kenzior
Quoted 6 lines · Andrew Zaborowski

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

Quoted 9 lines
Quoted 4 lines

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

#3 lore raw

Hi Andrew,

Quoted 7 lines

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.

Quoted 9 lines
Quoted 9 lines
Quoted 4 lines

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.

Quoted 3 lines

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

Sure.

Regards,
-Denis