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.

Comments

Post a Comment

Popular posts from this blog

The mysterious ORA-03111 error

Recently one of the applications that I developed started throwing exceptions, that had the following message: SQL state [72000]; error code [1013]; ORA-03111: break received on communication channel When I googled around, I couldn't come across anything useful. Sadly enough most of the sites just showed the documentation for that error, without any explanation from anyone experiencing that issues. So here you go, with the best possible explanation that I could come up with. My application sets two things on the connection that is throwing this exception: It sets the fetchSize to be 2500 rows It sets the query timeout to be 10 seconds The database server and the application are separated over a long latency network (actually there is a NetEm box that emulates the long latency between these two boxes) which has a latency characteristic of 50+/-5 milliseconds. This is the whole setup. It is important to understand how the timeout is handled by the Oracle client (in my case JDBC clien
Read more

Note on allocationSize parameter of @SequenceGenerator while using JPA

I ran into what I thought as an issue while I was using the sequence ID generation strategy in JPA. The JPA provider I am using is Hibernate. I think sharing my experience will save someone some time. To use a sequence (For e.g. Oracle sequence) to generate values and assign them to the ID field of your persistence object, you will following something like this: @Id @Column(name = "ITEM_ID") @GeneratedValue(strategy = GenerationType.SEQUENCE, generator="ItemIdSeqGenerator") @SequenceGenerator(name="ItemIdSeqGenerator", sequenceName="ITEM_ID_SEQ", allocationSize=1) private long itemId; This means the following things: The @Id annotation says that the field itemId is a primary key. The @Column annotation says that the corresponding column in the database is ITEM_ID. The @GeneratedValue says that the value that needs to be populated in the itemId should be generated, while that object is persisted. The strategy to generate the value is to
Read more

A note on Java's Calendar set() method

Remember that the Calendar's internal fields include year, month, date, hour, minutes, seconds, milliseconds and time zone. Whenever you are calling a set() method with multiple fields, like set(year, month, date), it will not affect the rest of the fields. Remember that there is no set() method with multiple fields available to set the milliseconds. If you would like to set the milliseconds, you must use set(Calendar.MILLISECOND, value). Likewise, if you are planning to set all the fields, its a good idea to reset all the fields using clear() method. This will clear milliseconds as well. Most of the times, millisecond field may not be of interest to you. But if you are going to use the UTC milliseconds, by calling getTimeInMillis(), then make sure you set the right values for milliseconds as well.
Read more