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:
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.
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.
Post a Comment