This comes up again and again, and I’ve seen various bad advice given, even in textbooks, so I thought I’d write a quick post about it. People are increasingly familiar with OO languages and perhaps not so familiar with plain old C, so when faced with having to drop down to pure C for some reason it’s quite common to ask how to achieve some of the design patterns they’re familiar with from OO, such as encapsulation, data hiding and the like.

What do I mean? Well, the canonical example where this kind of thing is useful is data structures, so let’s imagine that we want to make a library of functions that implements a key-value map. We might start with a header file containing something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

typedef struct {
  unsigned size, count;
  kvmap_entry_t *entries;
  void          *userdata;
} kvmap_t;

typedef int (*kvmap_key_comparator_t)(const void *k1, const void *k2,
                                      void *userdata);

kvmap_t *kvmap_create (kvmap_key_comparator_t compare_keys, void *userdata);

void kvmap_destroy (kvmap_t *map);

void kvmap_set (kvmap_t *map, const void *key, const void *value);

void *kvmap_get (kvmap_t *map, void *key);

void *kvmap_remove (kvmap_t *map, void *key);

There are lots of possible objections to this, but perhaps the worst thing is that the actual data structure is visible to the user of these APIs. Looking at the above, it seems likely that the map is currently stored as a sorted list (which is a perfectly reasonable representation for small key-value maps, especially if look-ups dominate), but in the future we might want to use a more sophisticated structure—or even (and this is what Core Foundation does on the Mac) choose a structure based on the data we have. If we expose it to the user, we can’t.

Textbooks and articles you might have read in print often suggest the following “solution”:- use void *. Then our header looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

typedef void *kvmap_t;

typedef int (*kvmap_key_comparator_t)(const void *k1, const void *k2,
                                      void *userdata);

kvmap_t kvmap_create (kvmap_key_comparator_t compare_keys, void *userdata);

void kvmap_destroy (kvmap_t map);

void kvmap_set (kvmap_t map, const void *key, const void *value);

void *kvmap_get (kvmap_t map, void *key);

void *kvmap_remove (kvmap_t map, void *key);

Then in your implementation routines you’ll need to write something like

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include "kvmap.h"

typedef struct {
  unsigned size, count;
  kvmap_entry_t *entries;
  void          *userdata;
} kvmap_internal_t;

...

void *
kvmap_get (kvmap_t map, void *key)
{
   kvmap_internal_t *pmap = (kvmap_internal_t *)map;

   ...
}

Looks good, right? I mean, we can’t see the data any more.

Well…

It’s better, in the sense that you indeed cannot now see the implementation quite so obviously. Unfortunately, using void * means that there is no longer any useful type checking. We can pass any pointer into the map parameter of any of these functions, and we can probably pass the map pointer to any number of other functions accidentally also.

There is, however, a better way.

C supports pre-declarations of structured types, and will allow you to use a pointer to a structured type whose contents you have not specified yet. We can use this feature to write a better version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

typedef struct kvmap *kvmap_t;

typedef int (*kvmap_key_comparator_t)(const void *k1, const void *k2,
                                      void *userdata);

kvmap_t kvmap_create (kvmap_key_comparator_t compare_keys, void *userdata);

void kvmap_destroy (kvmap_t map);

void kvmap_set (kvmap_t map, const void *key, const void *value);

void *kvmap_get (kvmap_t map, void *key);

void *kvmap_remove (kvmap_t map, void *key);

Now in your implementation you can just define struct kvmap. You don’t need to do this in the header file, and you don’t need a typedef:

1
2
3
4
5
6
7

#include "kvmap.h"

struct kvmap {
   unsigned size, count;
   kvmap_entry_t *entries;
   void          *userdata;
};

then when you want to use it in your functions, you can just treat the map argument as a pointer.

The best part is that the C compiler will now complain if you try to pass anything that is not a kvmap_t as the map argument. And if you have other abstract data type implementations (maybe you have some list routines as well), it will complain if you pass your kvmap_t into one of them accidentally as well.

There’s loads more I could write on this topic, but for now, just remember that it’s OK in C to define, declare and use a pointer to a struct type that you haven’t defined. You can’t dereference it or do pointer arithmetic on it, but that’s kind of the point :-)