Is there a way to pass a function pointer through more than 1 layer of polymorphic data structures in C

user_18530302 0
Viewed 55

I am currently working on a project in C that involves writing polymorphic data structures. I have already created a static hash table which just takes a void pointer to data void *data as input for insert, lookup and delete functions. In order to hash the data I have a function pointer typedef int (*hash_t)(size_t, void*); as a parameter when creating a new table. Initially I used the hash table to build a graph where it didn't really make sense to separate key and value, with a hash function like this:

int
hash_data(size_t size, void *graph_node) {
    return ((graph_node_t*)node)->id % size;
}

But now I was looking at reusing the hash table to record the frequencies of integers in a text file where <key, value> approach would make a lot more sense, so I'm trying to build a dictionary data structure which builds off the hash table by having a <key, value> struct:

typedef struct {
    void *key;
    void *value;
} key_value_t;

Where once again I'd have a function pointer typedef int (*hash_t)(size_t, void*); as a parameter when creating a new dictionary, where ideally I'd pass a function pointer to something like this to my hashtable:

int
hash_key_value(size_t size, void *key_value) {
    return hash_key(size, ((pair_t*)pair)->key);
}

The problem is I'm not sure how to have a function like this where it itself calls another function pointer, being called from within my hash table insert and lookup functions.

I have tried having the function pointer as a parameter such as:

int
hash_pair(size_t size, void *pair, hash_key_t hash_key) {
    return hash_key(size, ((pair_t*)pair)->key);
}

but this doesn't seem to be helpful as it requires the my hash code has a pointer to my hashKey function which is provided by code two layers less abstract.

I've considered having a 'fill in the blank' kind of function in my dictionary.c file like:

int
hash_key(size_t size, void *key) {
    /* some code */
}

But this seems less elegant than allowing the dictionary to be used without modifying the file at all, and is inconsistent with the function pointer approach I have already used.

Another alternative would be to make the dictionary only allow integer keys as perhaps I'm taking too much of an OOP approach to the problem.

function-pointers function dictionary hashtable c
1 Answers

The hash function approach is fine, but requires slight modifications!

Lets assume you have a dictionary; we'd add the pointer to the hash function there:

typedef struct dictionary
{
    struct pair* m_data;
    size_t m_capacity;
    HashFunction* m_hash;
}
dictionary;

The question is now how to correctly define the hash function type. At first: Why should such a hash function be aware of the size of the hash map? It should just return a value for a given object. The same value for the same object, same value for two objects considered equal, otherwise ideally differing. That's it. Why should the hash function care for mapping the object's hash value to some array bounds? That's the task of your insertion/lookup/deletion functions. So:

typedef size_t (HashFunction)(void*);

(OK, using alternative syntax, I prefer typedefing the signature and retain the pointer nature with the variables, as in the struct...)

Now lookup won't consider a pair, but the key:

void* lookup(dictionary* dict, void* key)
{
    // appropriate mapping done here!
    struct pair* p = dict->m_data + dict->m_hash(key) % dict->m_capacity;
    return dict->m_equal(p.key, key) ? p.value : NULL;
}

Insertion (including re-hashing on too high fill grade) and deletion then analogously.

Note, that you actually yet need an equality comparer as well to be able to detect key collisions for differing objects! And you might want to consider some appropriate collision handling on insertion (e.g. slots consisting of arrays or linked lists).

user_13123820
Related