Messages in this thread | | | Subject | Re: [PATCH rc5-rt2 0/3] plist: alternative implementation | From | Daniel Walker <> | Date | Tue, 20 Dec 2005 09:29:33 -0800 |
| |
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
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |