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