Re: [PATCH rc5-rt2 0/3] plist: alternative implementation

[Oleg Nesterov <oleg@tv-sign.ru>]

Daniel Walker wrote:
> 
> On Tue, 2005-12-20 at 15:38 +0100, Ingo Molnar wrote:
> > * Oleg Nesterov <oleg@tv-sign.ru> wrote:
> >
> I think there is a bug in the new plist_add() , which was in the
> original code. It doesn't properly handle the new maximum node scenario,
> or INT_MAX .
> 
> If the list is 1 2 3 4
> 
> and you insert 5 , you'll end up with the list 1 2 3 5 4 . Or something
> like that .

I think you are not right, please look at the code.

The code under list_for_each_entry() can break the loop only
when node->prio <= iter->prio.

void plist_add(struct pl_node *node, struct pl_head *head)
{
	struct pl_node *iter;

	list_for_each_entry(iter, &head->prio_list, plist.prio_list)
		if (node->prio < iter->prio)
			goto lt_prio;
		else if (node->prio == iter->prio)
			...

	// So, node->prio is a new maximum, or the list was empty.

	// &iter.plist == head. We don't touch iter->prio, so it
	// is ok that this pl_node is fake, it is really pl_head.

	// We are doing list_add_tail(), this means that new node
	// will stay _after_ all other nodes.

	// In this case the code below is equal to:
	//
	//	list_add_tail(&node->plist.prio_list, &head->prio_list);
	//	list_add_tail(&node->plist.prio_list, &head->node_list);

lt_prio:
	list_add_tail(&node->plist.prio_list, &iter->plist.prio_list);
eq_prio:
	list_add_tail(&node->plist.node_list, &iter->plist.node_list);
}

Note that this also garantees FIFO ordering, which was documented
in plist.h, but was not true for plist_for_each().

Daniel, do you agree ?

Oleg.