[Crash-utility] Adding a new command rbtree

[qiaonuohan]

At 2012-5-10 9:31, HATAYAMA Daisuke wrote:
> From: qiaonuohan<qiaonuohan at cn.fujitsu.com>
> Subject: [Crash-utility] Adding a new command rbtree
> Date: Wed, 09 May 2012 16:47:58 +0800
>
>> Hello HATAYAMA,
>>
>> I am trying to add a new command can be used to display rbtree and
>> radix tree. After some investigation, I find they are similar to the
>> build-in command "list". So I send this mail to ask your opinion about
>> making cmd_list to be similar to the command "struct/union/*".
>>
>> Another thing needed to be inquired is about the style of displaying
>> tree. I will list some of my thought, and some suggestion will be glad
>> to get from you.
>>
>> 1.
>> NODE ... : ...
>>    NODE ... : ...
>>      NODE ... : ...
>>        NODE ... : ...
>>      NODE ... : ...
>>    NODE ... : ...
>>
>> This style can not indicate whether the leaf is left or right. And
>> with
>> a big depth, the output may be ugly. So I do not like it.
>>
>> 2.
>> l - left child
>> r - right child
>>
>> root NODE ... : ...
>> l    NODE ... : ...
>> ll   NODE ... : ...
>> lll  NODE ... : ...
>> lr   NODE ... : ...
>> r    NODE ... : ...
>>
>> Of course, in radix tree, l&  r will be changed to some string that
>> can
>> indicate the child of a node. Still, with a big depth, the line will
>> be
>> too long and ugly.
>>
>> 3.
>> root    NODE addr1 : ...
>> addr1 l NODE addr2 : ...
>> addr2 l NODE addr3 : ...
>> addr3 l NODE addr4 : ...
>> addr2 r NODE addr5 : ...
>> addr1 r NODE addr6 : ...
>>
>> (l&  r have the same meaning with the one in the 2.)
>>
>> Surely, I prefer the the third one. What do you think? Or eliminating
>> the information indicating position is acceptable?
>>
>
> Hello Qiaon,
>
> It seems natural to me to make output format of both new commands
> compatible to list as much as possible. For example, list command
> outputs list of address for each nodes at default. rbtree and rdtree
> should do like this at defalt?
>
> Other information specific to individual tree structures such as
> position of node within the tree could be useful if given. But the
> output examples you're showing above can easily violate 80 column
> rule. Instead, how about splitting the feature of indicating position
> from the default output?
>
> My quick idea here: First, given address of starting node, list all
> the nodes addresses connected to the starting node.
>
> crash>  list 0xffff88003ef1f908
> ffff88003ef1f908
> ffff88003ef1eec8
> ffff88003ef1e488
> ffff88003ef2b948
> ffff88003ef2af08
> ffff88003ef2a4c8
> ffff88003ef55988
> ffff88003ef54f48
> ffff88003ef899c8
>
> Suppose that user wants to know where the node with ffff88003ef2a4c8
> positions in the tree starting from 0xffff88003ef1f908; in other
> words, position of node ffff88003ef2a4c8 relative to
> 0xffff88003ef1f908. Then:
>
>    crash>  rbtree -p 0xffff88003ef1f908 ffff88003ef2a4c8
>    rlr
>
> where I choosed -p at random intending "p"osition.
>
> Maybe there's case where user wants to know many positions at the same
> time. It might be better to use "<" operator? like
>
>    crash>  list 0xffff88003ef1f908>  ADDRESS_list.txt
>    crash>  rbtree -p 0xffff88003ef1f908<  ADDRESS_list.txt

Hello HATAYAMA,

Hmm, your idea seems not that good to me. As you said, it needs to 
search the tree to get the information of position one by one. It will 
waste time and effort. But you inspired me. Take look at the following 
style.

crash> rbtree ...
NODE addr1
   ...
NODE addr2
   ...
NODE addr3
   ...
NODE addr4
   ...
NODE addr5
   ...
NODE addr6
   ...

crash> rbtree -p ...
NODE addr1
   (position information)
   ...
NODE addr2
   (position information)
   ...
NODE addr3
   (position information)
   ...
NODE addr4
   (position information)
   ...
NODE addr5
   (position information)
   ...
NODE addr6
   (position information)
   ...

-p option will make the command to output position information.


>
> Thanks.
> HATAYAMA, Daisuke
>
>
>


-- 
--
Regards
Qiao Nuohan