Dynamic hash->class tag

Question

I have:

const unsigned int hash_1 = 0xaf019b0c;
const unsigned int hash_2 = 0xf864e55c;  
const unsigned int hash_3 = 0xfaea8ed5;

Hashes come from an automatically generated header. These hashes are indirectly associated with tags 1, 2, 3. The tags are associated with classes through a simple compile-time generated id. That way I can GetTag<Class1>() and get my int-tag for Class1.

My goal is to simplify the hash->tag association. Preferably this should be compile-time generated and O(1) access time. Memory in this case is not an issue. I can not use any third-party software.

I have tried the following:

template<uint32 t>  size_t GetTagByHash() { return 0; }

with specific implementations like:

template<> size_t GetTagByHash<hash_1>() { return GetTag<Class1>(); }

but that kind of implementation is difficult to use since if I have a local variable uint32 my_hash; that the compiler can't determine what value it has in compile-time then the compiler is unable to resolve the correct implementation of GetTagByHash() to call.

Answer 1

As I understand it, your problem is how to do this lookup with run-time values as well as compile-time ones.

You've really got two questions. First, what algorithm do you want to use to do the lookup, and second, how do you tell C++ to implement that?

The algorithm to use is somewhat of a non-obvious question; you've got a list of effectively-random numbers, and you want to look up something in that list and return an associated tag. Probably you want some sort of hashtable, but to start with, I'll show some examples with something simpler -- and likely better for small numbers of hashes: A simple O(N) lookup, in pseudocode:

if i = N return tag_N
else if i = N-1 ...
...
else if i = 1 return tag_1
else return tag_0

Now, how do you tell C++ to do this? You've got to create a list of all your hash tags, and instructions for doing that. Here's a simple way:

template<int i> struct lookup
{
  int result(int j) { return 0; }
};

const unsigned int hash_1 = 0xaf019b0c;
template<> struct lookup<1>
{
  int result(int j)
  {
    if (j == hash_1)
      return GetTag<Class1>();
    return lookup<0>::result(j);
  }
};

const unsigned int hash_2 = 0xf864e55c;
template<> struct lookup<2>
{
  int result(int j)
  {
    if (j == hash_2)
      return GetTag<Class2>();
    return lookup<1>::result(j);
  }
};

And so forth. Then, at the end, you can have

int hash_lookup(int j)
{
  return lookup<last_hash_number>::result(j);
}

Writing out all those identical definitions is a pain, though, so it's best to let C++ do that -- and, to do that, you need to define the hashes in such a way that they can be iterated over. Let's do that:

template<int> struct hash_tag {
  static const int value = 0;
  typedef type void;
};

#define SET_HASH(I, VALUE, CLASS)   \
template<> struct hash_tag<(I)>     \
{                                   \
  static const int value = (VALUE); \
  typedef type (CLASS);             \
}

SET_HASH(1, 0xaf019b0c, Class1);
SET_HASH(2, 0xf864e55c, Class2);
SET_HASH(3, 0xfaea8ed5, Class3);

// Define a general recursive lookup struct.
template<int i> struct lookup
{
  int result(int j)
  {
    if (j == hash_tag<i>::value)
      return GetTag<hash_tag<i>::type>;
    return lookup<i-1>::result(j);
  }
};

// Make sure the recursion terminates.
template<> struct lookup<0>
{
  int result(int) { return 0; }
};

Then, you use this as before.

Now, let's return to that first question -- what algorithm do you actually want to use to do the lookup? The advantage of this iterative O(N) lookup is that it's easy to program, and it doesn't require any initialization of any data structures at run-time -- you can just call it. However, as noted, it's O(N). An alternate choice is to use a std::map object; you can use a similar recursive definition to initialize it at runtime, and then use it. That might look something like this:

// Make a typedef to save some typing.
typedef std::map<unsigned int, size_t> Map_type;
typedef std::pair<unsigned int, size_t> Map_value;

// Define a recursion to add hashes to the map.
template<int i> struct add_hash
{
  void add(Map_type& hashmap)
  {
    hashmap.insert(
      Map_value(hash_tag<i>::value, 
                GetTag<hash_tag<i>::type>));
    add_hash<i-1>::add(hashmap);
  }
};

// Make sure the recursion terminates.
template<> struct lookup<0>
{
  void add(Map_type&) {}
};

// Now, create a class to initialize the std::map and do lookup.
class Hash_lookup
{
  Hash_lookup() { add_hash<last_hash_number>(map_); }
  int result(unsigned int j) { return map_[j]; }
private:
  Map_type map_;
}

Personally, I would probably combine this with your GetTagByHash<> idea, and give the Hash_loop a "runtime-computed result" function as I described, as well as a "compile-time-computed result" function that takes a template argument rather than a function argument. But, in general, that's the basic idea for doing runtime lookup -- you put the values you want to look up into a set of templated classes that you can recursively iterate over at compile time, and then you use that recursive iteration to either define a lookup function or initialize a runtime structure that you can use for doing the lookup.