Re: Make yield_task_fair more efficient

[Balbir Singh <balbir@linux.vnet.ibm.com>]

Peter Zijlstra wrote:
> On Thu, 2008-02-21 at 15:12 +0530, Balbir Singh wrote:
>> Peter Zijlstra wrote:
>>> On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote:
>>>
>>>> I have an alternate approach in mind (that I need to find time for),
>>>> threaded-rbtrees. Walking the tree is really efficient, specially finding
>>>> successor of a node.
>>> Threading the rbtrees would be even more expensive, it would require a
>>> list_head in each node and a full list operation for every tree
>>> operation.
>>>
>> Peter, when I say threaded, I don't mean threaded as in tasks. Please see
>> http://www.nist.gov/dads/HTML/threadedtree.html and
>> http://datastructures.itgo.com/trees/tbt.htm
> 
> I'm quite aware of the meaning of threaded in the context of data
> structures.

Oh! I did not mean to assume anything. Just wanted to make sure we are talking
of the same thing

 They usually require additional list data and operations to
> implement.
> 

>From the definition
A Threaded Binary Tree is a binary tree in which every node that does not have a
right child has a THREAD (in actual sense, a link) to its INORDER successor.

You use the empty pointer (missing right child), so why do we need a list. May
be I am missing something.

> Look at how the latter link you provided grows the rb_node with one
> pointer to provide a single linked list.
> 

Yes, that's a bad example I suppose. Look at
http://www.cs.rutgers.edu/~kaplan/503/thread.html

-- 
	Warm Regards,
	Balbir Singh
	Linux Technology Center
	IBM, ISTL