Re: patch] Real-Time Preemption, plist fixes

[Esben Nielsen <simlo@phys.au.dk>]

On Sun, 5 Jun 2005, Thomas Gleixner wrote:

> [...] 
>   *
>   * Based on simple lists (include/linux/list.h).
> @@ -17,35 +22,50 @@
>   * a priority too (the highest of all the nodes), stored in the head
>   * of the list (that is a node itself).
>   *
> - * Addition is O(1), removal is O(1), change of priority of a node is
> - * O(1).
> + * Addition is O(N), removal is O(1), change of priority of a node is
> + * O(N).
>   *
> - * Addition and change of priority's order is really O(K), where K is
> - * a constant being the maximum number of different priorities you
> - * will store in the list. Being a constant, it means it is O(1).
> - *

What is N? The number of nodes in the list or the number of different
priorities? If it is the number of nodes in total this exercise is
worthless: You could just as well have a sorted list.

But I hope and also think that the original explanation was correct.

Esben

-
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/