When I learned programming, I learned C about 4-6 months before C++ (and Java about 2 years before both as I've mentioned previously). I never really noticed, but this had some hand in shaping how I look at problems: I'm more liable to stick to imperative, light-OO programs, more comfortable with dealing with raw memory, and more familiar with rolling my own...well...everything. Essentially, I program to whatever higher-level functionality is present, but don't miss a beat when something's missing.

It can also make me bite off a lot more than I can chew at times.

Consider an example. In a Computer Networks course I took this summer, we were assigned to implement a client-server protocol ontop of some (not very performant) infrastructure. The details aren't important, save for one: all of the backing code, including the test code we had to link against, was in C. A smart, sane programmer might go, "Oh, I definitely need some more complex data structures, let's just extern "C" the code and write some wrappers and use C++ like a normal person."

We didn't do that.

In a move lauded by many as "crazy" and "idiotic", we decided to write the code in C. This could have turned out far worse (most of our bugs actually resulted in starting the assingment late, rather than "We could do this better in C++"), but did leave us with one problem: for a surprising number of parts of the system, we needed a map. Now, most people would stop here and switch to C++, foreseeing the sheer number of type-incompatibilities, segfaults, and other horrendous yet subtle bugs that would be completely avoided using a std::map.

I am not most people.

OO in C

In C++, object-oriented programming is straightforward, which makes sense given it's the reason for C++'s existence. You might have a class declaration like so:

class Foo {
public:
  Foo(int&);
  int func(int i);
  ~Foo();
private:
  int * k;
};

and a definition like so:

Foo::Foo(int &k) {
  this->k = new int(k);
}
int Foo::func(int i) {
  return i + *k;
}
Foo::~Foo() {
  delete k;
}

(This is a bad example. Don't do this.)

Now, in C, you don't have any of that fancy-shmancy constructor/destructor/assignment-operator/definite lifespan stuff. Instead you have functions! And pointers! And misery!

typedef struct {
   int * k;
} Foo;

int Foo_init(Foo * f, int k) {
   if (f == NULL) { // You fucked up
     return -1;
   }
   f->k = malloc(sizeof k);
   if (f->k == NULL) { // Yes this happens
     return -1;
   }
   *(f->k) = k;
   return 0;
}

int Foo_func(Foo * f, int i, int * ret) {
  if (f == NULL || ret == NULL) { // Reconsider your life choices
    return -1;
  }
  *ret = i + *(f->k);
  return 0;
}

int Foo_destroy(Foo * f) {
  if (f == NULL) { // No seriously, something's wrong with you
    return -1;
  }
  free(f->k);
  return 0;
}

Notice all the differences:

• No member functions. This one's actually pretty tame, as far as problems go, but it does mean you have to verify each and every time that your object actually exists.
• No access control. I mean, sure, using a private implementation idiom might be a good idea, but then you have to constantly have one more layer of indirection, and that's just messy.
• No scope-based lifespan. Every time you want to use a Foo, you have to manually call Foo_init before using it, and Foo_destroy after it leaves scope. If you don't, well, you might never know! It might still work. Or not. It depends on what's in the garbage memory you're writing to, which is a source of most of the bugs in C and C++ programs.
• No real exceptions. Notice how every function that does something returns an int? That's error handling. And it's all you've got. Sure, you can dress it up pretty by using Unix error codes or a custom enum, but at the core of it you're still passing a number around that says in some cryptic way whether or not your program is actually working, and you can't verify if anyone is actually reading the value or just assuming it's okay.

Still with me? Good. We have eight more circles to pass through.

Another feature present C++ provides you with, besides automatic lifespan and proper exception-handling (ish), is template programming. Suppose you had some kind of container object Bar, which just held a single field of that type. (Don't ask why you'd want this. You wouldn't.) In C++, you could do this:

template class Bar { public: Bar(T t); T getItem(); private: T item; };

You could also do things like make item a reference, make getItem const, or a bunch of other options. If you wanted to do the same in C, you'd have to write something like this (skipping error-handling for now):

struct Bar {
  void * item;
}
int Bar_init(Bar * b, void * value) {
  // ...
  b->item = value;
  // ...
}
int Bar_getItem(Bar * b, void ** ret) {
  // ...
  *ret = b->item;
  // ...
}

Welp, there goes type-safety. And scope-checking. If you didn't know for sure that value and your Bar would stay in the same scope, you'd have to do this:

int Bar_init (Bar * b, void * value, size_t item_size) {
  // ...
  b->item = malloc(item_size);
  // ...
  memcpy(b->item, value, item_size);
  //...
}

// Bar_getItem is the same for now

int Bar_destroy(Bar * b) {
  // ...
  free(b->item);
  // ...
}

Oddly enough: this also shows the first steps along the way to type-checking: checking the size of elements at runtime. It's more-or-less the only thing we can do, short of some twisted form of hell involving macros and cryptic compiler errors and drinking until you can forget you ever tried. Sure, this code is ugly, but it works. Most of the time. Onto the actual example...

Maps to Hell and Back Again

If you don't need iteration or deletion, a map has a pretty simple interface:

• Initialize with a set type of key and type of value (duh)
• put a value into the map for a specified key
• find a value (if it exists) put into the map for a given key
• destroy a map (also duh)

Written out in C, this might look something like this:

struct Map;

int Map_init(struct Map * m, size_t key_size, size_t value_size);
int Map_put(struct Map * m, void * key, void * value);
int Map_get(struct Map * m, void * key, void ** ret);
int Map_destroy(struct Map * m);

Hey, notice the key_size and value_size? Remember what I said about type-checking? This is how you know how big your passed-in memory blocks will be. Or this is how big you hope they'll be. (More on that later.)

Sample usage (ignoring error checking for brevity) would be something like this:

Map map;
Map_init(&map, sizeof(KEY_TYPE), sizeof(VALUE_TYPE));
KEY_TYPE k = /*...*/;
VALUE_TYPE v = /*...*/;
Map_put(&map, &k, &v);
VALUE_TYPE * ret = NULL;
Map_get(&map, &k, (void**)&ret);
/* Do Other Stuff */
Map_destroy(&map);

I'll skip the actual implementation for brevity's sake, but in our case I used a double-hashing-based open-addressing map using two hash functions based on Java's hashCode. (Good programming is lazy programming. If I'd taken this into account earlier, we wouldn't be writing C.) The primary reason you need key_size and value_size here is that both the keys and values are stored in an array, and you need to know how to index that array, and how big it should be. Adding a key to the map at an index boiled down to:

memcpy(m->key_array + (index * m->key_size), key, m->key_size);

and adding a value for the key was very similar. Getting a value at an index turned out to be really simple as well:

*ret = m->value_array + (index * m->value_size);

(This does introduce a bug later on. Try and guess how while you read the next few paragraphs.)

If you want to make this threadsafe, you can even do that easily: since you're implementing it yourself, add a reader-writer lock, read-lock it on getting a value, and write-lock it when adding a key. (This also becomes important.)

And that's it. Everything works. Maps are solved, and as this tweet clearly shows, I've outperformed Bjarne himself at making a generic hash map. Close the shop, write the rest, and go home, right?

Well, not exactly.

Let's say you have a Map with key-type K and value-type V. Suppose, instead of passing a V* to Map_put, a client passes a V**. When you try to use the V* later on (or possibly anything else in the map), something is bound to go horribly wrong. So you think to yourself, "I want type-checking, but void *s don't know how big they are. If only there were a way to know how big the original memory was..." And then you take another shot of vodka, because you realize that you need a function to act in local scope to the caller, and the only way to do this is macros.

Let's start by changing some definitions:

int Map_put(struct Map * m, void * key, size_t key_size, void * value, size_t value_size);
int Map_get(struct Map * m, void * key, size_t key_size, void ** ret, size_t ret_size);

The implementation changes are pretty simple: they check that key_size and value_size match those of the Map passed in, return an error if they don't, and then continue along in the way that the original implementation did. However, we can't rely on the user to actually use them right, because they were reckless enough to use a C-based map in the first place, so we add macros to call them:

#define MAP_PUT(m, key, value) Map_put(m, key, sizeof(*key), value, sizeof(*value))
#define MAP_GET(m, key, ret) Map_get(m, key, sizeof(*key), &ret, sizeof(*ret))

We also pass in ret as a single-indirection pointer instead, so we can actually retrieve the defined type. Doing a simple grep for the original functions and swapping them for their disfigured preprocessor cousins is quick if not painless, and bam: type-checking. It might be an ugly way to do it, but hell, it's the only way to do it...short of some scary, using-macros-to-build-custom-types kind of solution that flashed through my mind the moment I said the other one was the only way. Excuse me, I need a cold shower.

(Note: this obviously falls apart if sizeof(T) and sizeof(T*) are the same. Just don't store pointers or ints.)

Now that you've had 5 paragraphs to think about it, have you found the other bug? I'll give you a hint: it involves the paragraph right after I mention it.

See, thread-safety is good and all, but when you return raw references to locations in the array as part of your API, it's pretty much useless. In a system where we had around 5 threads per client/server combination, and each thread potentially had a pointer to the same Map, it wouldn't be inconceivable that they would all call Map_get for the same key. And then operate using the pointed-to value. And then try to manipulate it. All at once. And all the threads would go, "It's okay, I had the reader lock, so I can't be causing concurrency errors," calling pthread_chortle and pthread_grin_smugly as they look with disdain over the broken mess that they see the rest of the program to be, none the wiser that they are the bane of the client programmers, and the source of the "l'esprit de l'escalier"-esque frustration I experienced realizing my error long after the deadline had passed.

Solving this problem would be pretty trivial (having a mutex for each key or value or index or whatever, adding a method to acquire and free the value for a key), but it just goes to remind one of the foolishness on which this endeavour is based. Programming threadsafe generics in C is best left to the most quixotic of programmers, who waste time tilting at windmills while there are actual dragons to slay. To sum up the lessons learned:

• If you need a container type, consider C++ instead. If you decide to still use C, reconsider. Repeat ad infinitum.
• Concurrency is a fickle beast, but pointers tend to make things worse.
• This is mostly unrelated, but don't assume you can implement something just because you learned about it in class. I was reminded the hard way that a fixed-length closed-hashing hash-map needed to have a prime size to ensure it's actually filled.

To all the people that called us idiots for doing this...well, you had a point. Still, I like to think that I gained something from all those hours spent staring at pointers and structs to find the one function where the wrong variable was passed by value. I mean, I don't know what it was that I gained.

I'll just have to dereference it and find out.

J