Saturday, December 6, 2008

do { } while(0)

I was reading about hash tables organization this morning and checked how Ruby implements its internal symbol table. Investigating Ruby 1.9 source code I found st.c — general purpose hash table package by Peter Moore. The code is pretty clear, all standard hash table operations, some Ruby-specific preprocessor directives. And a couple of interesting things I didn't encounter before.

Some hash table operations in st.c, like finding and adding the entry, are defined as macros, not functions (probably to avoid function call overhead):

do {\
    st_table_entry *entry, *head;\
    if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
 rehash(table);\
        bin_pos = hash_val % table->num_bins;\
    }\
    \
    entry = alloc(st_table_entry);\
    \
    entry->hash = hash_val;\
    entry->key = key;\
    entry->record = value;\
    entry->next = table->bins[bin_pos];\
    if ((head = table->head) != 0) {\
 entry->fore = head;\
 (entry->back = head->back)->fore = entry;\
 head->back = entry;\
    }\
    else {\
 table->head = entry->fore = entry->back = entry;\
    }\
    table->bins[bin_pos] = entry;\
    table->num_entries++;\
} while (0)

So far so good, hash value modulo number of bins gives us fine distribution over bins and each bin is organized as a linked list. But what is that do { ... } while(0); thing? Looks strange from the first sight: the code will be executed only once, why not just disclose it in { .. } block or leave as is?

Fortunately I found very good explanation of this preprocessor trick in this FAQ entry. When this macro is substituted literally by preprocessor, it behaves like a code atom:

if (something)
  do {
     ...
  } while(0); /* Simple {...} block would conflict with the following else here */
else
  do_something();

do {...} while(0); construction not only creates a scope for local variables but also can be used everywhere as a single statement, without explicit { ... } around it. Nice technique!

2 comments:

Ruslan said...

do...while(0) used when programmer want to have transaction which can be broken everywhere:
do {
"action1"
if (something wrong)
break;
"actions2...5"
if (something wrong)
break;
"actions6...13"
if (something wrong)
break;
...
} while(0);
- but I think that procedure seems much more elegant.

Ruslan said...

I usually believe that in standard library all things optimized and rethougt 1000 times. In this particular example, I agree, user want to finish statement by ";", and to allow this, author used such not beautiful construction. He could also use if (1){...}else (without semicolon).
What is not good: I can't use such macro anywhere in my code:
for ( ;table->num_entries < MAX_ENTRIES; MACRO)
- will fail.