Need hash: uthash?

[Kristaps Dzonsons <kristaps@bsd.lv>]

Hi,

mandoc is getting a `tr' implementation*, needed primarily for perlpod. 
  This is expensive as it involves iterating over each character in each 
text string, then each element in an array of `tr' characters (or escape 
sequences).  Expect it in the next few commits (now it's in polish phase).

For the time being, this is implemented with the same linear search of 
the `ds' and `de' macro keys.  This means O(mn) performance over the 
number of words/characters (!) and keys.  In practise, when profiling 
the code, libroff spends a lot of time running through these lists. 
-mdoc gets away without even touching this code, but -man (especially 
perlpod) is smacked hard.

In short, the `ds', `de', and now `tr' macros can really benefit from a 
hash table.  I'm settling on using uthash** due to its license---I can 
directly include it in the code.  Does anybody have any better 
suggestions or criticism?  Interfacing with it is very easy and clean, 
and I've had some good performance benefits on heavy -man manuals (e.g., 
gcc, cvs, etc.).

Thanks,

Kristaps

*Search for `.tr': 
http://developer.apple.com/library/mac/#documentation/Darwin/Reference/ManPages/man7/groff.7.html

**http://uthash.sourceforge.net/
--
 To unsubscribe send an email to tech+unsubscribe@mdocml.bsd.lv