[Crash-utility] Adding a new command rbtree

[HATAYAMA Daisuke]

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

Thanks.
HATAYAMA, Daisuke