{"id":108547,"date":"2023-08-04T07:00:00","date_gmt":"2023-08-04T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=108547"},"modified":"2023-08-04T06:39:24","modified_gmt":"2023-08-04T13:39:24","slug":"20230804-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20230804-00\/?p=108547","title":{"rendered":"Inside STL: The lists"},"content":{"rendered":"

The C++ standard library type list<\/code> represents a doubly-linked list, and forward_list<\/code> is a singly-linked list. Fortunately, the implementations of both of these lists are pretty much what you expect.<\/p>\n

Let’s start with the simpler forward_list<\/code>.<\/p>\n

template<typename T>\r\nstruct forward_list\r\n{\r\n    forward_list_node<T>* head;\r\n};\r\n\r\ntemplate<typename T>\r\nstruct forward_list_node\r\n{\r\n    forward_list_node<T>* next;\r\n    T value;\r\n};\r\n<\/pre>\n
The forward_list<\/code> itself is a pointer to the first element of the list, or nullptr<\/code> if the list is empty. Each subsequent element contains a pointer to the next element, or nullptr<\/code> if there is no next element.<\/p>\n
For example, a two-element list of integers 1 and 2 is laid out like this:<\/p>\n
\u00a0<\/div>\n\n\n\n\n\n
forward_list<\/td>\n <\/td>\nnode<\/td>\n <\/td>\nnode<\/td>\n<\/tr>\n
next<\/td>\n\u2192<\/td>\nnext<\/td>\n\u2192<\/td>\nnext = null<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\nvalue = 1<\/td>\n <\/td>\nvalue = 2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
The doubly-linked list list<\/code> is also pretty simple.<\/p>\n
template<typename T>\r\nstruct list\r\n{\r\n    list_node_base<T> head; \/\/ or \"list_node_base<T>* head;\"\r\n    size_t size;\r\n};\r\n\r\ntemplate<typename T>\r\nstruct list_node_base\r\n{\r\n    list_node<T>* next;\r\n    list_node<T>* prev;\r\n};\r\n\r\ntemplate<typename T>\r\nstruct list_node : list_node_base<T>\r\n{\r\n    T value;\r\n};\r\n<\/pre>\n
The list is actually circular, with a sentinel node (that has no value) marking the beginning and end of the list. Again, there are two patterns, depending on whether the sentinel is embedded or external.<\/p>\n
Here’s the version with an embedded sentinel:<\/p>\n\n\n\n\n\n\n
 <\/td>\n <\/td>\nlist<\/td>\n <\/td>\nnode 1<\/td>\n <\/td>\nnode 2<\/td>\n<\/tr>\n
node 2<\/td>\n <\/td>\nhead.next<\/td>\n\u2192<\/td>\nnext<\/td>\n\u2192<\/td>\nnext<\/td>\n\u2192<\/td>\nlist.head<\/td>\n<\/tr>\n
(wraparound)<\/td>\n\ufe0e\u2196<\/td>\nhead.prev<\/td>\n\ufe0e\u2196<\/td>\nprev<\/td>\n\ufe0e\u2196<\/td>\nprev<\/td>\n <\/td>\n(wraparound)<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\nsize = 2<\/td>\n <\/td>\nvalue = 1<\/td>\n <\/td>\nvalue = 2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
And here’s the version with an external sentinel:<\/p>\n\n\n\n\n\n\n\n\n\n
list<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
head<\/td>\n\u2192<\/td>\n\u2198<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
size = 2<\/td>\n <\/td>\n\u2193<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
 <\/td>\n <\/td>\nsentinel<\/td>\n <\/td>\nnode 1<\/td>\n <\/td>\nnode 2<\/td>\n<\/tr>\n
node 2<\/td>\n <\/td>\nnext<\/td>\n\u2192<\/td>\nnext<\/td>\n\u2192<\/td>\nnext<\/td>\n\u2192<\/td>\nsentinel<\/td>\n<\/tr>\n
(wraparound)<\/td>\n\ufe0e\u2196<\/td>\nprev<\/td>\n\ufe0e\u2196<\/td>\nprev<\/td>\n\ufe0e\u2196<\/td>\nprev<\/td>\n <\/td>\n(wraparound)<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n <\/td>\n <\/td>\nvalue = 1<\/td>\n <\/td>\nvalue = 2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
The Microsoft implementation uses an external sentinel, whereas clang and gcc use an embedded sentinel. This means that the Microsoft implementation incurs an extra allocation for empty lists. This is a minor annoyance because you have to worry about std::bad_alloc<\/code> exceptions at construction.<\/p>\n
The only complication is the usual one: Storing the allocator, which is done as a compressed pair with the head<\/code>.<\/p>\n
The Visual Studio debugger contains a visualizer for both forward_list<\/code> and list<\/code> but if you need to dig out the contents manually, here’s how you can do it with the Microsoft implementation of the standard library.<\/p>\n
First, the forward list:<\/p>\n
0:000> ?? l\r\nclass std::forward_list<int,std::allocator<int> >\r\n   +0x000 _Mypair          : std::_Compressed_pair<std::allocator<std::_Flist_node<int,void *> >,std::_Flist_val<std::_Flist_simple_types<int> >,1>\r\n0:000> ?? l._Mypair\r\nclass std::_Compressed_pair<std::allocator<std::_Flist_node<int,void *> >,std::_Flist_val<std::_Flist_simple_types<int> >,1>\r\n   +0x000 _Myval2          : std::_Flist_val<std::_Flist_simple_types<int> >\r\n0:000> ?? l._Mypair._Myval2\r\nclass std::_Flist_val<std::_Flist_simple_types<int> >\r\n   +0x000 _Myhead          : 0x000001b8`7b6106a0 std::_Flist_node<int,void *>\r\n0:000> ?? l._Mypair._Myval2._Myhead\r\nstruct std::_Flist_node<int,void *> * 0x000001b8`7b6106a0\r\n   +0x000 _Next            : 0x000001b8`7b6106e0 std::_Flist_node<int,void *>\r\n   +0x008 _Myval           : 0n42\r\n0:000> ?? l._Mypair._Myval2._Myhead->_Next\r\nstruct std::_Flist_node<int,void *> * 0x000001b8`7b6106e0\r\n   +0x000 _Next            : (null)\r\n   +0x008 _Myval           : 0n99\r\n<\/pre>\n
We have to dig through a bunch of wrappers until we get to the _Myhead<\/code>, but then it’s smooth sailing dumping each node and following the _Next<\/code> to the next node.<\/p>\n
The layout of the forward_list<\/code> nodes happens to match the Windows NT SINGLE_LIST_ENTRY<\/code> structures, so you can use the debugger list commands to view them.<\/p>\n
          head                max size\r\n          \u2193                   \u2193   \u2193\r\n0:000> dl 0x000001b8`7b6106a0 999 2\r\n000001b8`7b6106a0  000001b8`7b6106e0 baadf00d`0000002a\r\n000001b8`7b6106e0  00000000`00000000 baadf00d`00000063\r\n\u2191                  \u2191                 \u2191        \u2191\r\nnode address       _Next             padding  _Myval\r\n<\/pre>\n
We ask the debugger’s “dump list” command (dl<\/code>) to dump the linked list starting at our head<\/code> (0x000001b8`7b6106a0<\/code>), for a maximum of 999 nodes, where each node consists of two pointer-sized values. From that, we can quickly pull out the values 0x2a<\/code> (42) and 0x63<\/code> (99). If you are willing to be sloppy in the service of expediency, you could just dump the list object itself with dl<\/code>, with the understanding that the first entry is going to be garbage. (It’s trying to dump the list itself as a node.)<\/p>\n
0:000> ?? &l\r\nclass std::forward_list<int,std::allocator<int> > * 0000009c`379df8c0\r\n0:000> dl 0x0000009c`379df8c0 999 2\r\n0000009c`379df8c0  000001b8`7b6106a0 0x000063`0000002a \u2190 garbage first \"node\"\r\n000001b8`7b6106a0  000001b8`7b6106e0 baadf00d`0000002a\r\n000001b8`7b6106e0  00000000`00000000 baadf00d`00000063\r\n<\/pre>\n
You can do a little flex and do it all in one line:<\/p>\n
0:000> dl @@c++(&l) 999 2\r\n0000009c`379df8c0  000001b8`7b6106a0 0x000063`0000002a \u2190 garbage first \"node\"\r\n000001b8`7b6106a0  000001b8`7b6106e0 baadf00d`0000002a\r\n000001b8`7b6106e0  00000000`00000000 baadf00d`00000063\r\n<\/pre>\n
The @@c++(...)<\/code> notation tells the debugger that the enclosed expression is a C++ expression instead of a MASM expression.<\/p>\n
The dl<\/code> command stops when it reaches the maximum number of nodes, it encounters a null pointer, or the list loops back to the start.<\/p>\n
If you really want to get fancy, you can use the !list<\/code> command, which lets you customize even further how the elements are displayed.<\/p>\n
0:000> !list -t scratch!LIST_ENTRY.Flink -x \"? dwo(@$extret+8)\" 0000009c`379df8c0\r\nEvaluate expression: 42 = 00000000`0000002a \u2190 garbage first \"node\"\r\n\r\nEvaluate expression: 42 = 00000000`0000002a\r\n\r\nEvaluate expression: 99 = 00000000`00000063\r\n<\/pre>\n
Dumping a list<\/code> has a similar initial annoyance, followed by straightforward pointer-chasing. The only trick is knowing when to stop!<\/p>\n
0:000> ?? l\r\nclass std::list<int,std::allocator<int> >\r\n   +0x000 _Mypair          : std::_Compressed_pair<std::allocator<std::_List_node<int,void *> >,std::_List_val<std::_List_simple_types<int> >,1>\r\n0:000> ?? l._Mypair\r\nclass std::_Compressed_pair<std::allocator<std::_List_node<int,void *> >,std::_List_val<std::_List_simple_types<int> >,1>\r\n   +0x000 _Myval2          : std::_List_val<std::_List_simple_types<int> >\r\n0:000> ?? l._Mypair._Myval2\r\nclass std::_List_val<std::_List_simple_types<int> >\r\n   +0x000 _Myhead          : 0x0000017f`a63cf020 std::_List_node<int,void *>\r\n   +0x008 _Mysize          : 2\r\n0:000> ?? l._Mypair._Myval2._Myhead\r\nstruct std::_List_node<int,void *> * 0x0000017f`a63cf020\r\n   +0x000 _Next            : 0x0000017f`a63d2730 std::_List_node<int,void *>\r\n   +0x008 _Prev            : 0x0000017f`a63d2780 std::_List_node<int,void *>\r\n   +0x010 _Myval           : 0n-1163005939\r\n0:000> ?? l._Mypair._Myval2._Myhead->_Next\r\nstruct std::_List_node<int,void *> * 0x0000017f`a63d2730\r\n   +0x000 _Next            : 0x0000017f`a63d2780 std::_List_node<int,void *>\r\n   +0x008 _Prev            : 0x0000017f`a63cf020 std::_List_node<int,void *>\r\n   +0x010 _Myval           : 0n42\r\n0:000> ?? l._Mypair._Myval2._Myhead->_Next->_Next\r\nstruct std::_List_node<int,void *> * 0x0000017f`a63d2780\r\n   +0x000 _Next            : 0x0000017f`a63cf020 std::_List_node<int,void *>\r\n   +0x008 _Prev            : 0x0000017f`a63d2730 std::_List_node<int,void *>\r\n   +0x010 _Myval           : 0n99\r\n<\/pre>\n
At this point, we stop because the _Next<\/code> value matches our sentinel value. If we didn’t recognize this, we would just follow the _Next<\/code> pointer which takes us back to the sentinel:<\/p>\n
0:000> ?? l._Mypair._Myval2._Myhead->_Next->_Next->_Next\r\nstruct std::_List_node<int,void *> * 0x0000017f`a63cf020\r\n   +0x000 _Next            : 0x0000017f`a63d2730 std::_List_node<int,void *>\r\n   +0x008 _Prev            : 0x0000017f`a63d2780 std::_List_node<int,void *>\r\n   +0x010 _Myval           : 0n-1163005939\r\n<\/pre>\n
The layout of the list<\/code> matches the Windows NT LIST_ENTRY<\/code>, so the dl<\/code> command can once again be pressed into service.<\/p>\n
0:000> dl 0x0000017f`a63cf020 999 3\r\n0000017f`a63cf020  0000017f`a63d2730 0000017f`a63d2780\r\n0000017f`a63cf030  baadf00d`baadf00d \u2190 garbage value in sentinel\r\n0000017f`a63d2730  0000017f`a63d2780 0000017f`a63cf020\r\n0000017f`a63d2740  baadf00d`0000002a \u2190 value 42\r\n0000017f`a63d2780  0000017f`a63cf020 0000017f`a63d2730\r\n0000017f`a63d2790  baadf00d`00000063 \u2190 value 99\r\n<\/pre>\n
The nodes are a little harder to read since they spill over two lines. The first line of each node shows the _Next<\/code> and _Prev<\/code> pointers. The second line of each node shows the value.<\/p>\n
As a parlor trick, you can use the dlb<\/code> command to dump the doubly-linked list backward<\/i>.<\/p>\n
0:000> dlb 0x0000017f`a63cf020 999 3\r\n0000017f`a63cf020  0000017f`a63d2730 0000017f`a63d2780\r\n0000017f`a63cf030  baadf00d`baadf00d \u2190 garbage value in sentinel\r\n0000017f`a63d2780  0000017f`a63cf020 0000017f`a63d2730\r\n0000017f`a63d2790  baadf00d`00000063 \u2190 value 99\r\n0000017f`a63d2730  0000017f`a63d2780 0000017f`a63cf020\r\n0000017f`a63d2740  baadf00d`0000002a \u2190 value 42\r\n<\/pre>\n
Since the nodes are so clumsy to read, this is a case where the !list<\/code> command comes in handy.<\/p>\n
0:000> !list -t scratch!LIST_ENTRY.Flink -x \"? dwo(@$extret+0x10)\" 0000009c`379df8c0\r\nEvaluate expression: 3131961357 = 00000000`baadf00d \u2190 garbage value in sentinel\r\n\r\nEvaluate expression: 42 = 00000000`0000002a\r\n<\/pre>\n
I’m not sure why the debugger gives up just before reaching the last node.<\/p>\n
Okay, so the list<\/code> and forward_list<\/code> aren’t particularly tricky, but we’ll need them later. Stay tuned.<\/p>\n
\n