…or something like that.

I’ve been toying and experimenting with different data structures to represent the domain name cache in mdnsd.

These are the structures I’ve seriously considered

• Radix tree/trie – It’s attractive to do lookup in O(k), but with a key length of 255 bytes (utf8) the tree would be huge, 2040 bits. Not sure it would be effective even with all the compression techniques in the book.
• Splay tree (self-balancing binary tree), scales well but key comparisons must be strcmp().
• Hash table, well obviously fast but there could be scaling problems as collisions become lager.
• “Chained” hash table – Use the fact that domain names are separated in labels (label1.label2.tld) and use one hash table on each level.

Read the rest of this entry »

Last night (local time) I submitted my initial mDNS stack to p4, it forms the foundation of the responder daemon (mdnsd). The stack is more or less complete, but I’ll see how it works out once I integrate it with the rest of the application, there will probably be some more code re-factoring (and bug fixing). Read the rest of this entry »