Tuesday, February 21, 2017

Another gdb script to traverse a Binary Tree

I had a binary tree program i wanted to debug.
I looked for a gdb script that can print all the nodes of  a binary tree but could not find a working one.
So i wrote one myself.

Sample C program.

#include <stdio.h>
#include <malloc.h>

typedef struct node_ {
    int key;
    struct node_ *left;
    struct node_ *right;
} node_t;

node_t *insert_internal (node_t *root, node_t *new_node)
{
    if (NULL == root) return new_node;

    if (new_node->key > root->key) {
        root->right = insert_internal(root->right, new_node);
    } else {
        root->left = insert_internal(root->left, new_node);
    }

    return root;
}

node_t *insert (node_t *root, int key)
{
    node_t *new_node = (node_t *) malloc(sizeof(node_t));
    new_node->key = key;
    new_node->left = new_node->right = NULL;

    return insert_internal(root, new_node);
}

void printtree (node_t *root)
{
    if (NULL == root) return;

    printf("%d ", root->key);
    printtree(root->left);
    printtree(root->right);
}



int main()
{
    node_t *root = NULL;

    root = insert(root, 10);
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 90);
    root = insert(root, 70);
    root = insert(root, 40);
    root = insert(root, 20);

    printtree(root);
}

Gdb script to print nodes of a binary tree in preorder:
define gdbprinttree
    set $index = 0

    set $index = $index + 1
    eval "set $stack_%d = $arg0", $index

    while $index > 0
        eval "set $temp = $stack_%d", $index
        set $index = $index - 1
        print *$temp

        if $temp->right
            set $index = $index + 1
            eval "set $stack_%d = $temp->right", $index
        end

        if $temp->left
            set $index = $index + 1
            eval "set $stack_%d = $temp->left", $index
        end
    end
end

How to execute this script:
a) save the script in a file (say script.txt)
b) in gdb, source script.txt
c) gdbprinttree root  <-here root is pointer to root node, you break at printtree in above example program and execute this command to print the whole tree.