Skip to main content

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.

Comments

Popular posts from this blog

Understanding Function Call Stack

Understanding Function Call Stack This writeup shows stack operations and behavior with a simple C Program, Assembly code and a dump of stack memory. Contents : Code Analysis of Stack Operations Analysis of Stack memory dump Full C Code Full Objdump C Code Assembly Code int main() { int a = 1; int b = 2; int c = 3; int d = 4; int e = 5; int f = 6; int g = 7; int h = 8; int ret = 0; ret = fun1(a, b, c, d, e, f, g, h); printf("output is %d", ret); } 0000000000400868 : 400868: push %rbp 400869: mov %rsp,%rbp 40086c: sub $0x30,%rsp 400870: movl $0x1,-0x4(%rbp) 400877: movl $0x2,-0x8(%rbp) 40087e: movl $0x3,-0xc(%rbp) 400885: movl $0x4,-0x10(%rbp) 40088c: movl $0x5,-0x14(%rbp) 400893: movl $0x6,-0x18(%rbp) 40089a: movl $0x7,-0x1c(%rbp) 4008a1: movl $0x8,-0x20(%rbp) 4008a8: movl $0x0,-0x24(%rbp) 4008af: mov -0x18(%rbp),%r9d...