"Compile-time hashtable" in C

Question

I'm implementing a piece of logic in C that goes something like this (for an interpreter):

if <input string> in <list of pre-defined constant strings>
  do_a_predefined_action()
else
  do_something_else(<input string>)

My first thought was a hashtable, but if the constant strings are known at compile-time it seems a bit wasteful to have to manually initialise a hashtable at runtime.

Other thoughts I had included statically initialising a hashtable structure with known hashes (ick...), then simply using it like normal. Another was a vast, nested switch block that would provide O(log n) lookup time (not as fast as a hashtable).

What is the best way of achieving lookup for a pre-defined set of strings? What is the solution I haven't seen yet? Elegance would be preferred to speed.

Answer 1

You can use something like gperf or Bob Jenkin's Minimal Perfect Hash code to generate a (possibly minimal) Perfect Hash Function, which will map strings to values, which you can later switch on.

Answer 2

I wouldn't be too worried about the cost of initializing a hashtable at program startup. This reeks of premature optimization. That said, ...

Since you do know all the strings, you could look into constructing a perfect hash for these strings. There are tools you can use to try many possible hashing algorithms and select the best fit for the data. This would lead to the static-initialization route. Although you've commented "ick" about this strategy. I encourage you to reconsider it if the speed issue is really so very important.

---

I have actually considered this very issue in the context of my postscript interpreter which initializes the systemdict hashtable at startup. Another route to consider would be to cache the table in a file. Pseudocode for initializing would then go something like this:

check for cached file
if file exists,
    load it.
if file does not exist,
    initialize table manually.
    save table to file.