Reports from above were mixed. I had no idea what was going on up near the surface, or in nearby space. For all I knew, the Asians could have taken over already; all I knew was that I hadn't seen them here.
Jeannine and I were now working exclusively within the underground alien city. It was a wonderful, dark, cold arcology buried deep below the ice, immense buildings full of silent hallways and chambers with purposes ranging from the obvious (oddly arranged toilet facilities) to the mystifying (a huge room empty but for three ten-foot-diameter metallic balls suspended in midair by unknown means). The latter probably indicated that some power source was active somewhere, but little else seemed to function, and the artifacts we were investigating rarely showed signs of life.
Within that realm of old and dark silence, we humans moved carefully, huddled always near to the white glow of our lamps and work areas. Though there was no need to be quiet, we found ourselves speaking nearly always in subdued tones for no discernible reason beyond respect, tinged perhaps with awe, or at times even fear.
The whole team knew we were close to a breakthrough. What's more, the officers knew it too, which was why they had us working around the clock.
Jeannine hooked up the power leads to the artifact we were investigating and ran another test. She watched the monitor; there was a spike, then nothing. She flung her hands up in frustration. "What's wrong now! What a temperamental piece of—" She stopped herself and then sighed in exasperation.
"At least it's responding. That's something," I mused. "Let me have a go. Where's that power source we were trying yesterday?"
She waved. "Over there. The chances are nil that we can use it directly, even with adapters. This thing might work with a different form of energy, if not a completely different principle altogether."
"It's responding," I repeated. "We've got to be close. Sometimes you can take the old and mate it with the new and get it to work, if you can just make the right adapter. Or sometimes you can reimplement..."
I was in a code review with the Guru. While we were working through the code, we heard an unusual sound — unusual, at least for the office. I looked at the Guru. "That sounded like..."
"... a baby!" we chimed. I gophered up. Scanning the area, I spotted Wendy's curly brown hair approaching my cubicle. As she came around the corner, I could see her pushing a baby stroller. We made appropriate oohing and aahing noises over little Jeannine, who was a month old now. I normally didn't care much for babies, but Wendy was my buddy, so I made an exception.
Even Bob joined the gathering crowd. "Well, well," he said, puffed out as though he were the father. "I always say babies look like either Winston Churchill or Yoda. How's she lookin'?" He set his latte down on some printouts on my desk and took Jeannine from Wendy. He peered at the baby's scrunched up face. "Hmmm... must be the exception that proves the rule. Give her twenty years and she'll be quite the babe." Just then, Jeannine squirmed and grunted. Bob sniffed, handed the baby back to Wendy, and left abruptly without his latte.
I arched an eyebrow. "I see you've already taught her how to deal with Bob."
Wendy laughed. "I'd better go change her."
With the main attraction gone, the crowd dispersed, and the Guru and I returned to our code review. I carefully moved Bob's latte to a less dangerous spot. All went well, until we reached a parsing function that used strtok. The Guru looked at me askance.
"Isn't there a better choice than strtok, my child?" she asked.
"But strtok does exactly what I need it to do. Aren't you the one who's always reminding me that the C library is also part of the C++ Standard?"
"That is true, my apprentice. But remember also the disclaimers that the C Standard makes about the library functions."
"Well, if you're talking about multithreaded issues..."
"No, my child," the Guru interrupted. "That is not what I am referring to. The blessed C Standard explicitly states that strtok — indeed none of the Standard C functions — is reentrant. Worse, in your case, is that strtok maintains global state across calls. Consider the context in which your function is used — it is used within another parsing function which could also use strtok."
I used my favorite deer-in-the-headlights stare to let her know I didn't follow.
The Guru nodded. "Then consider this parable," she said as she picked up the dry-erase marker and wrote on my whiteboard:
void f()
{
// ...
strtok( charPtrA, delimiters );
// ...
strtok( 0, delimiters );
// ...
}
void g()
{
strtok( charPtrB, otherDelimiters );
// ...
f();
// ...
strtok( 0, otherDelimiters );
}
"When f() terminates, it will have turned to evil the internal state of strtok, and g() will no longer be able to use it predictably."
"I see," I said. "So the solution is ...?" I left the question hanging.
"Write your own algorithm, and introduce the changes necessary. For example, here is the basic strtok function, implemented to operate on std::strings instead of C-style strings and modified to not change the source string."
std::string StringTok(
const std::string* newSeq,
const std::string& delim )
{
// like the standard strtok,
// maintain global state across calls
// sequence being searched
static const std::string* seq = 0;
// current position
static std::string::size_type pos = 0;
if( newSeq )
{
seq = newSeq;
pos = 0;
}
std::string token;
if( seq && pos != std::string::npos )
{
pos = seq->find_first_not_of
( delim.c_str(), pos );
if( pos != std::string::npos )
{
std::string::size_type next =
seq->find_first_of( delim.c_str(), pos );
token = seq->substr( pos, next-pos );
pos = next;
if( pos != std::string::npos ) ++pos;
if( pos >= seq->size() ) pos =
std::string::npos;
}
}
return token;
}
(Well, okay, I admit that's not exactly what she wrote — I had to clean up a couple of minor typos and logic errors. But back to my story...)
"This implementation," the Guru continued, "suffers from most of the same limitations as the Standard C strtok function we discussed earlier and introduces additional concerns, such as the overhead of creating a copy of the token string."
"But what about copy-on-write? Aren't there some string implementations that would store the fact that the return value is a substring of the existing string, and only make a copy on write?"
"Some implementations may, although it is written: 'It is difficult to make a thread-safe implementation of copy-on-write [2].' Today, more implementers are heeding this instruction and are removing such optimizations. Besides, that is not the only issue: this function is also not strongly exception-safe, for example in the case when the substring assignment to token throws."
"So," I so'd, "how do I overcome these various problems?"
A wry smile crossed the Guru's lips. "My child, if you are to progress beyond the apprentice stage, you must do some work yourself. Overcoming these problems is, as I am sure your university textbooks used to say, an exercise left to the learner. Write a version of StringTok that removes the reentrancy and nesting problems, that corrects the exception-safety problem, and that remains as efficient as possible by avoiding string copying. Show me your writings this afternoon."
She went away, and I got to work. It didn't take me long to realize that the need to maintain state practically screamed for having an object. I wrote my test cases and coded my solution, fixed a few bugs, and went looking for the Guru. I ended up showing her the following code:
template<class T>
class StringTok
{
public:
StringTok( const T& seq,
typename T::size_type pos = 0 )
: seq_( seq ) , pos_( pos ) { }
T operator()( const T& delim );
private:
const T& seq_;
typename T::size_type pos_;
};
template<class T>
T StringTok<T>::operator()
( const T& delim )
{
T token;
if( pos_ != T::npos )
{
// start of found token
typename T::size_type first =
seq_.find_first_not_of
( delim.c_str(), pos_ );
if( first != T::npos )
{
// length of found token
typename T::size_type num =
seq_.find_first_of
( delim.c_str(), first ) - first;
// do all the work off to the side
token = seq_.substr( first, num );
// done; now commit using
// nonthrowing operations only
pos_ = first+num;
if( pos_ != T::npos ) ++pos_;
if( pos_ >= seq_.size() ) pos_ = T::npos;
}
}
return token;
}
"This way," I explained, "the code is simpler because I don't have to worry about starting new sequences; if the user wants that, he just creates a new tokenizer object. The exception-safety bug is gone too, now, because I 'do all the work off to the side and then commit using non-throwing operations only.' Oh, and I thought I'd template it... it wasn't any more work, except for writing typename a couple of times, and this way we can use it with our wide strings too."
The Guru pushed a graying lock behind one ear. "I see," she said with an air of slyness, "that StringTok uses the default copy constructor and assignment operator."
I smiled; this time I was ready for the bait and not caught off guard. "Indeed," I replied smoothly. "I deliberately allowed the default copying and assignment semantics because they work like bookmarks: this way the user can take a copy of the StringTok object at any point during tokenization and explore alternative tokenizations from that point forward. In fact, it works well with your original problem example, even if the problem is made harder by having f and g independently parse the very same string:"
void f()
{
// ...
StringTok<std::string> x( stringA );
// ...
x( delimiters );
// ...
}
void g()
{
// ...
// same string this time
StringTok<std::string> y( stringA );
// ...
f();
// ...
// remember where we are
StringTok<std::string> z( y );
y( otherDelimiters );
if( DidntWork() )
// retry from the same point
z( yetOtherDelimiters );
}
"Not only can the tokenizing operations overlap, but they can work independently on the same strings. All this," I concluded, "without incurring any overhead, because the sequence string is never physically copied." I crossed my arms and sat back.
"Well said," the Guru smiled, nodding. "While you are at it, you might consider adding more powerful features, such as the ability to use a vector<string> for the delimiters, so you are not restricted to single-character delimiters."
"Or," I jumped in, warming to the idea, "allow the capability of recognizing empty fields. I've tried to use strtok before, to parse out a comma-delimited field, but empty fields, such as A,B,,,C really mess it up. strtok will skip the two empty fields."
We quickly concluded the code review, and I began working on my revised parsing function.
"There sure still is work left for the reader on this one," Jeannine shook her head.
"Well, we got something when we tickled it last time. What aspects of the energy input haven't we tried varying yet?"
Jeannine nodded. "I know. I know. Let's try it again."
References
[1] To the tune of "I've Got Rhythm."
[2] H. Sutter. More Exceptional C++, Items 15 and 16 (Addison-Wesley, 2001).
Jim Hyslop is a senior software designer at Leitch Technology International Inc. He can be reached at [email protected].
Herb Sutter is an independent consultant and secretary of the ISO/ANSI C++ standards committee. He is also one of the instructors of The C++ Seminar (<www.gotw.ca/cpp_seminar>). Herb can be reached at [email protected].
