Skip to content

Instantly share code, notes, and snippets.

@DavidEGrayson
Last active June 26, 2025 21:13
Show Gist options
  • Save DavidEGrayson/44a54453af0ea0ec890c615b81dbbd0c to your computer and use it in GitHub Desktop.
Save DavidEGrayson/44a54453af0ea0ec890c615b81dbbd0c to your computer and use it in GitHub Desktop.
Limitations of _Generic in C make me need two different functions for hash lookups

I'm writing a general-purpose hash table library in C. Given a user-defined struct type named H whose first member is named key, I want the user to be able to use variables of type H* to represent an array of type H, with an associated hash table that allows quick lookups of elements in the array by the value of the key.

The key can be anything. Right now I'm supporting three types of keys:

  • arbitary data with a fixed byte size
  • a pointer to a null-terminated string
  • a size_t followed by a pointer to arbitary data with that size

The lookup function in my library has this signature:

void * _ahash_find(const void * hash, const void * key);

(The info about the key's type was already stored in the hash when it was created, so that info does not need to be passed here as an argument.)

Here is an example of a correct way to call this function:

typedef struct KVPair {
  int key;
  float value;
} KVPair;

KVPair * hash;

float lookup(int key) {
  KVPair * result = _ahash_find(hash, &key);
  return result->value;
}

However, I don't want typical users to call _ahash_find directly like this, because it is too easy to pass the wrong type of key in the second argument, causing tricky bugs in the program. (It's also too easy to assign the void * return value to an incorrect type, but that form of type mismatch is very easy to fix using a cast to typeof(hash).)

Also, requiring the user to provide a pointer to the key is overly cumbersome for cases where the key is an integer or string; I'd like them to just be able to write ahash_find(hash, 1) or ahash_find(hash, "foo") and have it work. This implies that the second argument might not have exactly the same type as the key. For example:

  • If the key member is any type of integer, we want to allow the second argument to be any integer as well. (This is familiar to C programmers, because they can pass any integer type to functions with signatures like void func(int).)
  • If the key member is const char *, we want to support the second argument being a string literal, which has type char *.

Here is my best attempt to write an ahash_find macro that behaves like this, allowing you to pass the key by pointer, by const pointer, or by value with a flexible type:

#define _AHASH_T_PTR(x, T) (_Generic((x), T *: (x), const T *: (x), default: ({T y = (x); y;})))
#define _AHASH_KEY_PTR(x, h) _AHASH_T_PTR((x), typeof_unqual((h)->key))
#define ahash_find(hash, key) ((typeof(hash))_ahash_find((hash), _AHASH_KEY_PTR((key), (hash))))

This would work perfectly, except there for one surprising fact about how _Generic works in C: the unused cases of the _Generic statement get type-checked, even if they will not be evaluated!

So if you write int k = 0; ahash_find(hash, &key);, that will be an error, because the code in the default case boils down to int y = &key;, which is incorrect.

Perhaps the answer is to have two separate macros for the two cases: we can have an ahash_find_p macro that will only accept pointers to keys, and an ahash_find macro that only accepts key values, which I suspect will be the more common case.

Are there any other solutions I'm missing, that work in C23?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment