Saturday, June 16, 2007

Infnite loop while doing ++map.begin() on empty map

Look at this seemingly simple program:
int main(int argc, const char* argv[]) {
map mymap;
map::iterator it = mymap.begin();
++it;
return 0;
}
What do you think would happen when I compile and run this program? Infinite loop! I tried this program in two different versions of compilers: Sun Forte 6 suite on Solaris and gcc 3.4.6 on FreeBSD.

In most of the library distributions, maps and sets are implemented using red-black trees. The iterator above seem to have three links: parent, left and right. For some strange reason, when the map is empty, the iterator returned by begin() (and end() too) has parent as NULL and left and right to be pointing to itself!

(gdb) print it
$1 = {_M_node = 0xbfbfecd4}
(gdb) print *it._M_node
$2 = {_M_color = std::_S_red, _M_parent = 0x0, _M_left = 0xbfbfecd4, _M_right = 0xbfbfecd4}
You can have a look at the _M_increment function to know why this results in an infinite loop.

Now the history. One of our programs running in test region behaved very weird. What should have been processed in few mins wasn't processed even after an hour. So when I attached a debugger to the program and analyzed, I figured this was the issue. I accept that the program had a logical error that it didn't check for empty container. I think getting into an infinite loop is a big punishment. A core dump at least would have given a hint that something went wrong.

In his book "Writing Solid Code," Steve Maguire tells that code should be written such a way that every bug is forced to surface. I guess that's what is missing in this piece of library function.

No comments: