Thursday, March 11, 2004

How to Walk an STL Map in GDB

Sometimes, you need to walk a map in GDB. Without a process running, you aren''t allowed to call functions on the structure, such as "find" or "[]". However, the data is still available, and can be retrieved if you know how to walk the tree structure.

This assumes that you are using GCC (may be version specific, I used 3.2.3).

The following code is used as an example:

#include <map>
#include <vector>
#include <iostream>

using namespace std;
map<int, int> map_to_walk;
vector<int> vector_to_walk;

int main() {

    cout << "Hello" << endl;

    map_to_walk[5] = 6;


   cout << "There" << endl;

Pretty basic stuff.

At the first cout, the map has been constructed. At that point, it looks like this:

(gdb) p map_to_walk 
$1 = {
    _M_t = {<_Rb_tree_base<std::pair<const int, int>,std::allocator<std::pair<const int, int> > >> = 
            {<_Rb_tree_alloc_base<std::pair<const int, int>,std::allocator<std::pair<const int, int> >,true>> = 
             {_M_header = 0x22e78}, 
             <No data fields>}, 
            _M_node_count = 0, 
            _M_key_compare = {<binary_function<int,int,bool>> = {<No data fields>}, <No data fields>}

I've changed the formatting a little to make it easier to see some things.

I'm guessing, but I think the fields are:

  • _M_t - the implementation of the tree
  • ._M_node_count - the number of nodes in the map.
  • ._M_header - the root node in the tree.
(gdb) p map_to_walk._M_t._M_header    
$3 = (_Rb_tree_node<std::pair<const int, int> > *) 0x22e78

The root node concept is borne out by the fact that it is a tree node, and it does exist. Looking at the node we see:

(gdb) p *map_to_walk._M_t._M_header
$4 = {<_Rb_tree_node_base> = {_M_color = _M_red, _M_parent = 0x0, 
    _M_left = 0x22e78, _M_right = 0x22e78}, _M_value_field = {first = 0, 
    second = 0}}

With both the left and right children pointing back to us.

Now, after inserting an element, we see the following:

(gdb) p *map_to_walk._M_t._M_header
$3 = {<_Rb_tree_node_base> = {_M_color = _M_red, _M_parent = 0x22e90, 
    _M_left = 0x22e90, _M_right = 0x22e90}, _M_value_field = {first = 0, 
    second = 0}}

The root node is still empty. The node count is now 1. The only thing that has changed is that the _M_left and _M_right pointers have moved to point to something else.

If we look at left/right, we see that they are _Rb_tree_node_base pointers. GDB doesn't do downcasts, so we don't get anything else. However, if we force the cast, we get the following:

(gdb) p *(_Rb_tree_node<std::pair<const int, int> > *)map_to_walk._M_t._M_header._M_left
$14 = {<_Rb_tree_node_base> = {_M_color = _M_black, _M_parent = 0x22e78, 
    _M_left = 0x0, _M_right = 0x0}, _M_value_field = {first = 5, second = 6}}

Woohoo, we see our value sitting right there! From there, I'm hoping that it is easy to track down.

STL vectors in GDB

STL vectors are even easier. The vector contains a single buffer of the elements. It contains a pointer to the start and the end of the elements, as well as a pointer to the end of the allocated space.

  • _M_start : The 0th element
  • _M_finish : The last+1 element (equals end())
  • _M_end_of_storage: The end of the currently allocated buffer.

So, to get at a specific element in the vector, you start with the _M_start pointer (0th) and then add the index of the value you are looking for:

(gdb) p vector_to_walk
$1 = {<_Vector_base<int,std::allocator<int> >> = {<_Vector_alloc_base<int,std::allocator<int>,true>> = {_M_start = 0x24c18, _M_finish = 0x24c1c, 
      _M_end_of_storage = 0x24c1c}, <No data fields>}, <No data fields>}
(gdb) p vector_to_walk._M_start 
$2 = (int *) 0x24c18
(gdb) p *vector_to_walk._M_start
$3 = 5
(gdb) p vector_to_walk._M_finish - vector_to_walk._M_start
$4 = 1

No comments: