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

[Daniel Walker <dwalker@mvista.com>]

On Tue, 2005-12-20 at 21:31 +0300, Oleg Nesterov wrote:
> 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 ?

It seems correct, however Inaky's code had special cases for this .
Since the two iteration implementation are near identical, it's a bit
suspect. Maybe Inaky can shed some light on it .

Daniel