## A recursive gdb script for Binary Trees

If we have a binary tree, how do we determine if a key is in the tree?Â Or another way, how do we know it was inserted correctly? We need toÂ visit every node.

This is a recursive problem and hard to do in gdb. TheÂ convenience variables are very simple and we can not implement a stack with them.Â Since they are effectively global, we can not even hide them inÂ stack frames. What we can do is use concatenation and a node-idÂ to generate uniqe names.

Note that you have to do all variable name declarations beforeÂ you do any recursion. That statement will make sense when youÂ violate it and wonder why your output looks strange.

```define indentby
printf "%*c", \$arg0+1, 0
end

define walk_btree
set \$node_\$arg0 = (\$arg1)
set \$fnum_\$arg0 = (\$arg2)
set \$branch_\$arg0 = (\$arg3)
set \$space_\$arg0 = (\$arg4)
set \$leftid_\$arg0 = \$arg0 + 1
set \$rightid_\$arg0 = \$arg0 + 2

indentby \$space_\$arg0
printf "%d %u (btree *)%p\n", \$branch_\$arg0, \$node_\$arg0->e_type[\$fnum_\$arg0].key, \$node_\$arg0

set \$space_\$arg0 = \$space_\$arg0 + 1
if \$node_\$arg0->e_type[\$fnum_\$arg0].left
walk_btree \$leftid_\$arg0 \$node_\$arg0->e_type[\$fnum_\$arg0].left \$fnum_\$arg0 0 \$space_\$arg0
end
if \$node_\$arg0->e_type[\$fnum_\$arg0].right
walk_btree \$rightid_\$arg0 \$node_\$arg0->e_type[\$fnum_\$arg0].right \$fnum_\$arg0 1 \$space_\$arg0
end
end
document walk_btree
NODE-ID NODE FNUM BRANCH INDENTBY
Recursively walk the binary tree printing out the key for the fnum'ed entry
end

define start_walk_btree
walk_btree 0 \$arg0 \$arg1 3 1
end
document start_walk_btree
NODE FNUM
Recursively walk the binary tree printing out the key for the fnum'ed entry
end```

Contrast that against a very simple algorithm to find if theÂ key is in the tree (with the assumption the tree is valid).

Recursion is not needed as we lop of a branch with eachÂ iteration.

```define find_btree
set \$node = \$arg0
set \$fnum = \$arg1
set \$key = \$arg2
set \$process = 1

while \$node && \$process
if \$key == \$node->e_type[\$fnum].key
set \$process = 0
else

if \$key < \$node->e_type[\$fnum].key
\$node = \$node->e_type[\$fnum].left
else
\$node = \$node->e_type[\$fnum].right
end
end
end

if \$node
printf "Found match on (btree *)%p\n", \$node
else
printf "No matching node in the binary tree\n"
end
end```

### 2 Responses to “A recursive gdb script for Binary Trees”

1. Moises Silva says:

Hello,

Thanks for sharing. This gave me the hint that I needed to find a solution to my problem (recursively printing a memory pool tree and finding corrupted nodes)

I suspected the solution would be using something similar to PHP variable variables (creating new variables out of a variable name)

There is one thing however that I had to do different from you, perhaps due to GDB version?

define indentby
printf “%*c”, \$arg0+1, 0
end

It did not work for me, what is the “*” supposed to do?

I had to do a while loop printing an space (with no line terminator) from 0 to \$arg0 to print the number of indentations I wanted, such as:

define __indentby
set \$indent_count = 0
while \$indent_count < \$arg0
printf “%4c”, ‘ ‘
set \$indent_count = \$indent_count + 1
end
end

2. Peter Backes says:

Note that this will work, though perhaps not quite in the way you intended it to. \$arg* are special, they will be replaced verbatim without evaluation (and that’s actually the only reason why you can construct variable names with them the way you do):

define walk_btree_x
set \$leftid_\$arg0 = \$arg0 + 1
set \$rightid_\$arg0 = \$arg0 + 2
print “\$arg0”
print “\$arg1”
if \$arg1 < 3
walk_btree_x \$leftid_\$arg0 (\$arg1+1)
walk_btree_x \$rightid_\$arg0 (\$arg1+1)
end
end
walk_btree_x 0 0

Thus, you are effectively constructing variables like \$leftid_\$leftid_\$leftid_0, not like \$leftid_3. You are simulating a stack by prefixing.

Thus, in fact,

set \$leftid_\$arg0 = \$arg0 + 1

and

set \$rightid_\$arg0 = \$arg0 + 2

are completely irrelvant and can be omitted. The values will never be used.

If you want \$leftid_3 (though I don't really see a reason why), you have to use eval. That will work only with a process to debug, however, not on a core file. (Might not bother you since you are already using printf, which has the same restrictions.)