Hash specialization for table of function pointer

Question

Updates in bold

I am writing a hash function for a table of function pointers with the limitation that the structure of the function pointers and function table cannot be modified (i.e. they have been published to third-parties). Based on Can std::hash be used to hash function pointers?, std::hash can be used for function pointers. Adopting that, it yields the following solution.

The tedious part about this solution is that every time we add new APIs to FuncPointers struct, we'd have to modify the hash specialization to add the corresponding change (i.e. hashFunc(hashedValue, pFuncs->func3) ).

I am wondering if there's a better way to implement this hashing of function pointers so continuous modification to the hash specialization can be avoided?

typedef void (*func_type1) (int);
typedef void (*func_type2) (double);

typedef struct FuncPointers
{
    func_type1 func1;
    func_type2 func2;
    ...
} FuncPointers;

template <typename T> void hashFunc (size_t & HashedValue, T funcPointer)
{
    std::hash<T> hash;
    HashedValue ^= hash(funcPointer); // the XOR operator is randomly picked
}

namespace std
{
    template<> struct hash<FuncPointers>
    {
        size_t operator()(FuncPointers *pFuncs)
        {
            size_t hashedValue = 0;
            hashFunc(hashedValue, pFuncs->func1);
            hashFunc(hashedValue, pFuncs->func2);
            ...

            return hashedValue;
        }
    };
}

Here is a solution for `std::tuple` that is standard compliant: http://stackoverflow.com/a/7115547/1774667 (the second part of the answer, the first part violates C++11 standard) — Yakk - Adam Nevraumont, May 14 '14 at 14:22

score 0 · Answer 1 · edited May 23 '17 at 11:57

Start with this: https://stackoverflow.com/a/7115547/1774667

It provides a hash_tuple::hash<Tuple> that is a valid decent quality hasher (with combining and recursion support!) for a std::tuple.

Next, change FuncPointers as follows:

struct FuncPointers:std::tuple<func_type1, func_type2 /*, ...*/> {

  // optional:
  func_type1 func1() const { return std::get<0>(*this); }
  func_type1& func1() { return std::get<0>(*this); }
  //...
};
namespace std {
  template<>
  struct hash<FuncPointers> {
    template<typename... Ts>
    std::size_t operator()( std::tuple<Ts...> const& funcs ) const {
      return hash_tuple::hash<std::tuple<Ts...>>{}(funcs);
    }
  };
}

which redirects your std::hash<FuncPointers> to invoke hash_tuple::hash<std::tuple<...>> on the parent of FuncPointers. If you do not want to inherit from std::tuple, changing it to a has-a instead of an is-a relationship should be easy.

The optional func() accessors give you closer to the old interface (just requires a () added), but also adds boilerplate.

An alternative would be:

template<unsigned N>
auto func() const->decltype( std::get<N>(*this) ){ return std::get<N>(*this); }
template<unsigned N>
auto& func()->decltype( std::get<N>(*this) ){ return std::get<N>(*this); }

which changes funcPointers.func1 to funcPointers.func<1>(), but gets rid of tonnes of boilerplate when you add a new func, and stays pretty similar to the old interface of funcPointers.

If there is not much code that is using the old interface, using std::get<N>() makes some sense.

If your names are more descriptive than func1 and you only used that for the example, an enumeration of the function names can be used with std::get or func<X> above. If you go with func<X> you can even make it typesafe (force the use of the named functions).

Thanks Yakk. One limitation I didn't mention (my bad) is that I cannot change the structure of the function pointers as well as the function table (i.e. these structures have been published to third-parties so we cannot modify them). I will take a closer look at your suggestion to see if I can rationalize it with that limitation. — lancery, May 14 '14 at 19:28
@lancery you can write a `get_tie` method that wraps up each of the variables into a `std::tie` (which is about the same code as manually maintaining the `hash`), or you can wait for reflection to arrive, possibly before C++17. A `static_assert` that (number of functions you handle) * `sizeof(` function pointer `)` `==` `sizeof(FuncPointers)` might be useful. — Yakk - Adam Nevraumont, May 14 '14 at 19:38
since this is a table of function pointers, can we make some simplifying assumption that they are all of the same size (i.e. via using size_t) and iterate through them somehow? — lancery, May 15 '14 at 18:01
@lancery `auto begin = reinterpret_cast(&fp); auto end = begin+sizeof(fp)/sizeof(void const*);` then do a cumulative hash on the range `begin` to `end`? Dangers would include: padding between members, extra crap at front (go for POD), extra crap or padding at end. We can make this a bit less quirky with some anonymous `struct` and `union` action -- willing to restrict which compiler you are using? — Yakk - Adam Nevraumont, May 15 '14 at 18:13
This is being compiled using VC++ Compiler. Do we have to worry about padding? My understanding is that given it's a direct struct definition (not member struct so don't have to worry about fat pointers) and that function pointers are either 4 bytes or 8 bytes so they are naturally aligned. — lancery, May 15 '14 at 22:21

score -1 · Answer 2 · edited May 23 '17 at 12:05

-1

You'd be better off making your FuncPointers a std::tuple<func_type1, func_type2>. Then see this answer on hashing.

BTW, typedef struct FuncPointers { } FuncPointers is a C-ism which has never been necessary in C++.

edited May 23 '17 at 12:05

Community

1
1

answered May 14 '14 at 09:50

MSalters

173,980
10
155
350

Specializing `hash` for `std::tuple` is undefined behavior. The linked answer uses a symmetric `^`, which is a bad idea when hashing. – Yakk - Adam Nevraumont May 14 '14 at 14:16
@Yakk: I didn't state that you should specialize `std::hash`, just provide your own hash as the second argument to `std::unordered_set`. You're right that plain `^` is a bad idea, but the relevant idea of the linked answer is to enumerate the tuple members. – MSalters May 14 '14 at 14:24
The OP specializes `std::hash` -- replacing `FuncPointers` with `std::tuple` makes that not possible (well, possible, but no longer legal!). The answer you linked to specializes `std::hash>`, which is undefined behavior (no diagnosic required), and what is worse usually works. I'm just saying your answer will lead the OP (or someone else reading it) down the wrong path in 2-3 different ways at once. – Yakk - Adam Nevraumont May 14 '14 at 14:36

Hash specialization for table of function pointer

2 Answers2