Debugging STL Containers with WinDbg Part 3: Map
For previous posts of this series, check out the following links:
Debugging STL Containers with WinDbg: Prolog
Debugging STL Containers with WinDbg Part 1: Vector
Debugging STL Containers with WinDbg Part 2: List
Let’s now look at maps. Like lists, a map container manages a varying-length sequence of elements but as a (nearly) balanced ordered tree of nodes, each storing one element. An element consists of a key, for ordering sequence, and a mapped value. Underneath it’s an implementation of an ordered red-black tree (a special type of binary tree) of {key, mapped} values. The source in Visual Studio 2012 can be found in C:\Program Files (x86)\Microsoft Visual Studio 11.0\VC\crt\src\map.
Before we delve into a map in WinDbg, it’s probably a good idea to understand the basic structure of a red-black tree so to make sense out of the output when you debug.
A red-black tree is a special kind of binary tree. In a red-black tree, a node is either red or black. These two "colors" are essentially used for balancing the tree over time when you insert and remove nodes. For tree traversal in this case, the "color" of a node is irrelevant so feel free to set it aside for now.
Each tree node has the following members that are of interest for our purpose:
_Left - Points to left subtree, or smallest element if head.
_Parent – Points to the node’s parent, or root of the tree if head.
_Right - Points to right subtree, or largest element if head.
_Myval - the stored key/value pair.
Just like binary trees, each node can have a left subtree and a right subtree. Left and right branches so to speak.
Each node stores the key and value of a node. Keys are not limited to numerical. You can have a comparison function or less-than operator defined for the key type you desire. When you dereference an iterator, you get back a pair - first corresponds to the key, and second to the value.
I hope it’ll make sense when you look into an instance of a map and draw a logical picture of it.
Take the following example:
C:\Projects\STL>type main.cpp
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
map<int, string> mymap;
mymap[1] = "Map1";
mymap[2] = "Map2";
mymap[3] = "Map3";
mymap[4] = "Map4";
mymap[5] = "Map5";
for (map<int,string>::iterator mi = mymap.begin(); mi != mymap.end(); ++mi)
cout << (*mi).first << ": " << (*mi).second << endl;
}
C:\Projects\STL>cl /EHsc /nologo /W4 /MTd /Zi main.cpp
main.cpp
C:\Projects\STL>main
1: Map1
2: Map2
3: Map3
4: Map4
5: Map5
In this example we have 5 nodes so it’s simple enough to traverse, yet it has enough nodes to let us see a tree structure that’s easy to understand.
Let’s start by looking at the map instance:
0:000> dt mymap
Local var @ 0xd2fb70 Type std::map<int,std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::less<int>,std::allocator<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > > > >
+0x000 _Myproxy : 0x00f56440 std::_Container_proxy
+0x004 _Myhead : 0x00f55428 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x008 _Mysize : 5
_Mysize is obvious, the number of nodes in the tree. _Myhead is a little trickier. _Myhead does not point to the root. _Myhead->_Parent does. Keep this in mind.
To start off the journey, let’s dump out the head node (it helps if you keep your eyes on the _Left/_Right/_Parent values):
0:000> dt 0x00f55428 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
main!std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x000 _Left : 0x00f56778 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x004 _Parent : 0x00f56830 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x008 _Right : 0x00f56a58 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x00c _Color : 1 ''
+0x00d _Isnil : 1 ''
+0x010 _Myval : std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >
As stated earlier, head node’s _Left points to the smallest element, and its _Right points to the largest element. _Left and _Right at this point are not really necessary for us to start the traversal, so ignore them for now. After we traversed the tree you can come back and double-check the values.
Head node’s _Parent points to the root of the tree, so let’s start there. Notice that you can specify which member of the type to display, so here we specified _Left, _Parent, _Right, and _Myval. For _Myval we want to drill down to the pair’s first and second values, and also one more level deeper into _Bx as well to see the string buffer, hence we used _Myval… (with three dots).
0:000> dt 0x00f56830 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *> _Left _Parent _Right _Myval...
main!std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x000 _Left : 0x00f56778 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x004 _Parent : 0x00f55428 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x008 _Right : 0x00f569a0 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x010 _Myval :
+0x000 first : 0n2
+0x004 second :
+0x000 _Myproxy :
+0x004 _Bx :
+0x000 _Buf : [16] "Map2"
+0x000 _Ptr : 0x3270614d "--- memory read error at address 0x3270614d ---"
+0x000 _Alias : [16] "Map2"
+0x014 _Mysize : 4
+0x018 _Myres : 0xf
=003d7440 npos : 0xffffffff
So the root node contains the <2,"Map2"> pair. From here you can dt _Left and _Right for each node. If you encounter a _Left or _Right value that is the same as the head node, that means there’s no more subtree there, and you’re done with that branch.
Here’s the complete output. I’ve added some debugger comments for you to follow.
0:000> dt 0x00f56830 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *> _Left _Parent _Right _Myval...
main!std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x000 _Left : 0x00f56778 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x004 _Parent : 0x00f55428 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x008 _Right : 0x00f569a0 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x010 _Myval :
+0x000 first : 0n2
+0x004 second :
+0x000 _Myproxy :
+0x004 _Bx :
+0x000 _Buf : [16] "Map2"
+0x000 _Ptr : 0x3270614d "--- memory read error at address 0x3270614d ---"
+0x000 _Alias : [16] "Map2"
+0x014 _Mysize : 4
+0x018 _Myres : 0xf
=003d7440 npos : 0xffffffff
0:000> * _Parent points to _Myhead, which is expected.
0:000> * Both _Left and _Right point to somewhere other than _Myhead,
0:000> * so they both have branches.
0:000> * Dump the left subtree.
0:000> dt 0x00f56778 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *> _Left, _Parent, _Right, _Myval...
main!std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x000 _Left : 0x00f55428 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x004 _Parent : 0x00f56830 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x008 _Right : 0x00f55428 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x010 _Myval :
+0x000 first : 0n1
+0x004 second :
+0x000 _Myproxy :
+0x004 _Bx :
+0x000 _Buf : [16] "Map1"
+0x000 _Ptr : 0x3170614d "--- memory read error at address 0x3170614d ---"
+0x000 _Alias : [16] "Map1"
+0x014 _Mysize : 4
+0x018 _Myres : 0xf
=003d7440 npos : 0xffffffff
0:000> * Here both _Left and _Right point to _Myhead, so we're done with this branch.
0:000> * Now dump the right subtree.
0:000> dt 0x00f569a0 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *> _Left, _Parent, _Right, _Myval...
main!std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x000 _Left : 0x00f568e8 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x004 _Parent : 0x00f56830 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x008 _Right : 0x00f56a58 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x010 _Myval :
+0x000 first : 0n4
+0x004 second :
+0x000 _Myproxy :
+0x004 _Bx :
+0x000 _Buf : [16] "Map4"
+0x000 _Ptr : 0x3470614d "--- memory read error at address 0x3470614d ---"
+0x000 _Alias : [16] "Map4"
+0x014 _Mysize : 4
+0x018 _Myres : 0xf
=003d7440 npos : 0xffffffff
0:000> * Both _Left and _Right point to somewhere other than _Myhead,
0:000> * so they both have branches.
0:000> * Dump the left subtree.
0:000> dt 0x00f568e8 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *> _Left, _Parent, _Right, _Myval...
main!std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x000 _Left : 0x00f55428 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x004 _Parent : 0x00f569a0 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x008 _Right : 0x00f55428 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x010 _Myval :
+0x000 first : 0n3
+0x004 second :
+0x000 _Myproxy :
+0x004 _Bx :
+0x000 _Buf : [16] "Map3"
+0x000 _Ptr : 0x3370614d "--- memory read error at address 0x3370614d ---"
+0x000 _Alias : [16] "Map3"
+0x014 _Mysize : 4
+0x018 _Myres : 0xf
=003d7440 npos : 0xffffffff
0:000> * Both _Left and _Right point to _Myhead, so we're done with this branch.
0:000> * Now dump the right subtree.
0:000> dt 0x00f56a58 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *> _Left, _Parent, _Right, _Myval...
main!std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x000 _Left : 0x00f55428 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x004 _Parent : 0x00f569a0 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x008 _Right : 0x00f55428 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>
+0x010 _Myval :
+0x000 first : 0n5
+0x004 second :
+0x000 _Myproxy :
+0x004 _Bx :
+0x000 _Buf : [16] "Map5"
+0x000 _Ptr : 0x3570614d "--- memory read error at address 0x3570614d ---"
+0x000 _Alias : [16] "Map5"
+0x014 _Mysize : 4
+0x018 _Myres : 0xf
=003d7440 npos : 0xffffffff
0:000> * Again both _Left and _Right point to _Myhead, so we're done with this branch as well.
0:000> * All branches traversed. We're done.
The diagram below provides a logical picture of the tree:
Unlike vectors, I don’t have a script to dump the nodes for map containers. Maybe I’ll find some time later to address this shortcoming. Until then, I hope the information presented so far is helpful to you.