C makes it difficult to write generic code. Unlike C++, which gives you templates and virtual functions, C only has 3 mechanisms for writing generic code:

1. void* pointers
2. Preprocessor macros
3. Function pointers

void* pointers are far from ideal, since you lose all type safety provided by the compiler, which can result in hard-to-debug undefined behavior resulting from invalid type casts.

Preprocessor macros have well-noted drawbacks – preprocessor expansion is basically just a find/replace mechanism that happens before the compilation phase, which again can result in hard-to-debug errors. The archetypal example being something like: #define add(x) (x+x), where x can be incremented twice if you call add(i++). You can write template-style generic code entirely using C-macros, but the result is really hideous and difficult to maintain.

Function pointers provide a good way to write generic code, but unfortunately they don’t provide you with type generality – they merely provide the possibility of run-time polymorphism (which is why, for example, the standard library qsort still requires a function that takes void* pointers.)

You can also implement class hierarchies in C using structs, as is done in the GLib library which provides a generic GObject base class. But this suffers from similar problems as using void* pointers, since you still need to rely on potentially unsafe manual casting to up-cast and down-cast.

So yeah, C makes it hard to write code that is both generic AND safe/easy-to-maintain, which unfortunately can result in code duplication. Large C projects often use scripting languages to generate repetitive code during the build process.

I can not speak for others, but in my own personal experience with C, code duplication has not been much of an issue. Whether this is due to project sizes, or a charmed sample set I can not say. However, there are three rules of thumb that I follow that I think are applicable. In no particular order, they are …

1. Write for what is needed. Generality can come later IF it is needed.
2. If generality is needed, void pointers, function pointers and structure size can be invaluable. The routine qsort(), for example, makes use of all three.
3. Give weight to making your code clear.

It’s worth noting that you may not need a fully generic solution to reduce code duplication. Sometimes ordinary refactoring and a bit of method generalization is sufficient.

When writing a generalized solution for a broad audience, you have to consider:

1. What novel ways might the consumer use your code, and how do you accomodate them?
2. What errors do I need to catch? What errors should I not catch?
3. How robust does the API need to be? How many overloads do I need to provide?
4. What security measures do I have to put in place, so that the code cannot be used for evil purposes?

Eric Lippert wrote an entire article about a single design decision in the .NET framework code. All in all, it’s often simpler to just refactor.

I usually use a generic implementation, like glib’s, then if the casting ends up being too annoying, make a small type-specific wrapper for it. However, a lot of casting is expected in C, as is the use of a void* as a generic type, so what would be considered “messy” in another language is just typical C. Scarily enough, it will look a lot more natural when you get more experience in the language.

Your issue of reusability is not unique to C. However, some excellent and very reusable HashMap implementations are out there which you could base yours off of. One that’s been around for a decade or two is in Java:
http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html

All Java collections, including HashMap are being rewritten for Java 8 to get rid of the idea of an iterator, and instead require you to pass a function to the collection so it can iterate internally. This is a big win for writing concurrent code – the collection can manage concurrency internally so the client doesn’t have to. That said, most programmers are not used to passing function pointers. This does a good job explaining where HashMap is headed:
http://cr.openjdk.java.net/~briangoetz/lambda/collections-overview.html

The syntax of Scala may make it hard to translate something like this into C, but here’s an example of a collection that already works the way the Java 8 collections will – immutable by default, providing various tranformation methods, making use of function pointers and other cool stuff like partial application:
http://www.scala-lang.org/api/current/index.html#scala.collection.Map

If you are doing a lot of stuff with HashMaps and other more advanced data structures, you might want to look at a language that supports them.

Returning to the idea of code duplication in-general, you can code really fast by cutting and pasting, but it produces terrible code. I’d say it’s acceptable in throw-away code like one-time reports. It’s also OK sometimes when there is no code down-stream of it, like UI code that just builds a screen that nothing else depends on, but really that’s a very gray area at best.

I don’t think it’s too much of an over-simplification to say that any time you find yourself duplicating code, you should make a function. The bugs alone that you fix in one copy of the code and not the other are enough of a reason to make a function.

I’m wondering if code duplication is a necessary evil when it comes to
writing common data structures and C in general?

In C, absolutely for me, as someone who bounces between C and C++. I definitely duplicate more trivial things on a daily basis in C than in C++, but deliberately, and I don’t necessarily see it as “evil” because there are at least some practical benefits — I think it’s a mistake to consider all things as strictly “good” or “evil” — just about everything is a matter of trade-offs. Understanding those trade-offs clearly is the key to not avoid regrettable decisions in hindsight, and merely labeling things as “good” or “evil” generally ignores all such subtleties.

While the problem isn’t unique to C as others pointed out, it might be considerably more exacerbated in C due to the lack of anything more elegant than macros or void pointers for generics, awkwardness of non-trivial OOP, and the fact that the C standard library doesn’t come with any containers. In C++, a person implementing their own linked list might get an angry mob of people demanding why they aren’t using the standard library, unless they’re students. In C, you’d invite an angry mob if you can’t confidently roll out an elegant linked list implementation in your sleep since a C programmer is often expected to at least be able to do those types of things daily. It’s not due to some weird obsession on linked lists that Linus Torvalds used the implementation of SLL searching and removal using double indirection as a criteria to evaluate a programmer who understands the language and has “good taste”. It’s because C programmers might be required to implement such logic a thousand times over in their career. In this case for C, it’s like a chef evaluating a new cook’s skills by making them just prepare some eggs to see if they at least have mastery of the basic things they’ll be required to do all the time.

For example, I’ve probably implemented this basic “indexed free list” data structure a dozen times over in C locally for each site that uses this allocation strategy (almost all my linked structures to avoid allocating one node at a time and halve the memory costs of the links on 64-bit):

But in C it just takes a very small amount of code to realloc a growable array and pool some memory from it using an indexed approach to a free list when implementing a new data structure which uses this one.

Now I have the same thing implemented in C++ and there I only have it implemented once as a class template. But it’s a much, much more complex implementation on the C++ side with hundreds of lines of code and some external dependencies which also span hundreds of lines of code. And the main reason it’s much more complicated is because I have to code it against the idea that T could be any possible data type. It could throw at any given time (except when destroying it, which I have to do explicitly as with the standard library containers), I had to think about proper alignment to allocate memory for T (though fortunately this is made easier in C++11 onwards), it could be non-trivially constructible/destructible (requiring placement new and manual dtor invocations), I have to add methods that not everything will need but some things will need, and I have to add iterators, both mutable and read-only (const) iterators, and so
on and so forth.

Growable Arrays Aren’t Rocket Science

In C++ people make it sound like std::vector is the work of a rocket scientist, optimized to death, but it doesn’t perform any better than a dynamic C array coded against a specific data type which just uses realloc to increase array capacity on push backs with a dozen lines of code. The difference is that it takes a very complex implementation to make just a growable random-access sequence fully compliant with the standard, avoid invoking ctors on uninserted elements, exception-safe, provide both const and non-const random-access iterators, use type traits to disambiguate fill ctors from range ctors for certain integral types of T, potentially treat PODs different using type traits, etc. etc. etc. At that point you do, indeed, need a very complex implementation just to make a growable dynamic array, but only because it’s trying to handle every possible use case ever imaginable. On the plus side, you can get a whole lot of mileage out of all that extra effort if you do genuinely need to store both PODs and non-trivial UDTs, have use for generic iterator-based algorithms that work on any compliant data structure, benefit from exception-handling and RAII, at least sometimes override std::allocator with your own custom allocator, etc. etc. It definitely does pay off in the standard library when you consider how much benefit std::vector has had on the entire world of people who have used it, but that’s for something implemented in the standard library designed to target the entire world’s needs.

Simpler Implementations Handling Very Specific Use Cases

As a result of just handling very specific use cases with my “indexed free list”, in spite of implementing this free list a dozen times over on the C side and having some trivial code duplicated as a result, I’ve probably written less code total in C to implement that a dozen times than I had to implement it just one time in C++, and I had to spend less time maintaining those dozen C implementations than I had to maintain that one C++ implementation. One of the main reasons the C side is so simple is that I’m typically working with PODs in C whenever I use this technique and I generally don’t need more functions than insert and erase at the specific sites in which I implement this locally. Basically I can just implement the teeniest subset of the functionality the C++ version provides, since I’m free to make so many more assumptions about what I do and don’t need of the design when I’m implementing it for a very specific use case.

Now the C++ version is so much nicer and type-safe to use, but it was still a major PITA to implement and make exception-safe and bidirectional iterator-compliant, e.g., in ways where coming up with one general, reusable implementation probably costs more time than it actually saves in this case. And a lot of that cost of implementing it in a generalized way is wasted not only upfront, but repeatedly in the form of things like escalated build times paid over and over each day.

Not an Attack on C++!

But this is not an attack on C++ because I love C++, but when it comes to data structures, I’ve come to favor C++ mainly for the really non-trivial data structures that I want to spend the much extra time upfront to implement in a very generalized way, make exception-safe against all possible types of T, make standard-compliant and iterable, etc, where that type of upfront cost really pays off in the form of a ton of mileage.

Yet that also promotes a very different design mindset. In C++ if I want to make an Octree for collision detection, I have a tendency to want to generalize it to the nth degree. I don’t just want to make it store indexed triangle meshes. Why should I limit it to just one data type it can work with when I have a super powerful code generation mechanism at my fingertips which eliminates all abstraction penalties at runtime? I want it to store procedural spheres, cubes, voxels, NURBs surfaces, point clouds, etc etc etc and try to make it good for everything, because it’s tempting to want to design it that way when you have templates at your fingertips. I might not even want to limit it to collision detection — how about raytracing, picking, etc? C++ makes it initially look “sorta easy” to generalize a data structure to the nth degree. And that’s how I used to design such spatial indexes in C++. I tried to design them to handle the entire world’s hunger needs, and what I got in exchange was typically a “jack of all trades” with extremely complex code to balance it against all possible use cases imaginable.

Funnily enough though, I’ve gotten more reuse out of the spatial indexes I’ve implemented in C over the years, and at no fault of C++, but only mine in what the language tempts me to do. When I code something like an octree in C, I have a tendency to just make it work with points and be happy with just that, because the language makes it too difficult to even attempt to generalize it to the nth degree. But due to those tendencies, I’ve tended to design things over the years that are actually more efficient and reliable and really well-suited for certain tasks at hand, since they don’t bother with being general to the nth degree. They become aces in one specialized category instead of a jack of all trades. Again that comes at no fault of C++ but simply the human tendencies I have when I’m using it as opposed to C.

But anyway, I love both languages but there are different tendencies. In C I have a tendency to not generalize enough. In C++ I have a tendency to generalize too much. Using both has kind of helped me to balance myself out.

Are generic implementations a norm, or do you write different
implementations for each use case?

For trivial things like singly-linked 32-bit indexed lists using nodes from an array or an array that reallocates itself (analogical equivalent of std::vector in C++) or, say, an octree that just stores points and aims to do nothing more, I don’t bother to generalize to the point of storing any data type. I implement these to store a specific data type (though it may be abstract and use function pointers in some cases, but at least more specific than duck typing with static polymorphism).

And I’m perfectly happy with a little bit of redundancy in those cases provided that I unit test it thoroughly. If I don’t unit test, then redundancy starts to feel much more uncomfortable, because you might have redundant code that could be duplicating mistakes, e.g. Then even if the type of code you’re writing is unlikely to ever need design changes whatsoever, it might still need changes because it’s broken. I tend to write more thorough unit tests for C code I write as a reason.

For nontrivial things, that’s usually when I reach for C++, but if I was to implement it in C, I’d consider using just void* pointers, maybe accept a type size to know how much memory to allocate for each element, and possibly copy/destroy function pointers to deep copy and destroy the data if it’s not trivially constructible/destructible. Most of the times I don’t bother and don’t use so much C to create the most complex data structures and algorithms.

If you use one data structure frequently enough with a particular data type, you could also wrap a type-safe version over one that just works with bits and bytes and function pointers and void*, e.g., to reimpose the type safety through the C wrapper.

I could try to write a generic implementation for a hash map for
example, but I’m always finding the end result to be messy. I could
also write a specialized implementation just for this specific use
case, keep the code clear and easy to read and debug. The latter would
of course lead to some code duplication.

Hash tables are kind of iffy since it could be trivial to implement or really complex depending on how complex your needs are with respect to hashes, rehashes, if you need to automatically have the table grow on its own implicitly or can anticipate the table size in advance, whether you use open addressing or separate chaining, etc. But one thing to keep in mind is that if you tailored a hash table perfectly to the needs of a specific site, it often won’t be so complex in implementation and often won’t be so redundant when it’s tailored precisely for those needs. At least that’s the excuse I give myself if I implement something locally. If not you might just use the method described above with void* and function pointers to copy/destroy things and generalize it.

Often it doesn’t take much effort or much code to beat a very generalized data structure if your alternative is extremely narrowly applicable to your exact use case. As an example, it’s absolutely trivial to beat the performance of using malloc for each and every node (as opposed to pooling a bunch of memory for many nodes) once and for all with code you never have to revisit for a very, very exact use case even as newer implementations of malloc come out. It might take a lifetime to beat it and code no less complex that you have to devote a huge part of your life to maintaining and keeping it up-to-date if you want to match its generality.

As another example, I’ve often found it extremely easy to implement solutions that are 10 times faster or more than the VFX solutions offered by Pixar or Dreamworks. I can do it in my sleep. But that’s not because my implementations are superior — far, far from it. They’re downright inferior for most people. They’re only superior for my very, very specific use cases. My versions are far, far less generally applicable than Pixar’s or Dreamwork’s. It’s a ridiculously unfair comparison since their solutions are absolutely brilliant compared to my dumb-simple solutions, but that’s kind of the point. The comparison doesn’t need to be fair. If all you need is a few very specific things, you don’t need to make a data structure handle an endless list of things you don’t need.

Homogeneous Bits and Bytes

One thing to exploit in C since it has such an inherent lack of type safety is the idea of storing things homogeneously based on the characteristics of bits and
bytes. There’s more of a blur there as a result between memory allocator and data structure.

But storing a bunch of variable-sized things, or even things that merely could be variable-sized, like a polymorphic Dog and Cat, is difficult to do efficiently. You cannot go by the assumption that they could be variable-sized and store them contiguously in a simple random-access container because the stride to get from one element to the next could be different. As a result to store a list that contains both dogs and cats, you might have to use 3 separate data structure/allocator instances (one for dogs, one for cats, and one for a polymorphic list of base pointers or smart pointers, or worse, allocate each dog and cat against a general-purpose allocator and scatter them all over memory), which gets expensive and incurs its share of multiplied cache misses.

So one strategy to utilize in C, though it comes at reduced type richness and safety, is to generalize at the level of bits and bytes. You might be able to assume that Dogs and Cats require the same number of bits and bytes, have the same fields, the same pointer to a function pointer table. But in exchange you can then code fewer data structures, but just as importantly, store all these things efficiently and contiguously. You’re treating dogs and cats like analogical unions in that case (or you might just actually use a union).

And that does come at a huge cost to type safety. If there’s one thing I miss more than anything else in C, it’s type safety. It’s getting closer to assembly level where the structures are just indicating how much memory allocate and how each data field is aligned. But that’s actually my number one reason to use C. If you’re really trying to control memory layouts and where everything is allocated and where everything is stored relative to each other, often it helps to just think about things at the level of bits and bytes, and how much bits and bytes you need to solve a particular problem. There the dumbness of C’s type system can actually become beneficial rather than a handicap. Typically that’ll end up resulting in much fewer data types to deal with, since the data types are no longer modeling abstract ideas so much as how many bits and bytes you need to solve a problem.

Illusory/Apparent Duplication

Now I’ve been using “duplication” in a loose sense for things that may not even be redundant. I’ve seen people distinguish terms like “incidental/apparent” duplication from “actual duplication”. The way I see it is that there’s no such clear distinction in many cases. I find the distinction more like “potential uniqueness” vs. “potential duplication” and it can go either way. It often depends on how you want your designs and implementations to evolve and how perfectly tailored they will be for a specific use case. But I have often found that what might appear to be code duplication later turns out to no longer be redundant after several iterations of improvements.

Take a simple growable array implementation using realloc, the analogical equivalent of std::vector<int>. Initially it might be redundant with, say, using std::vector<int> in C++. But you might find, through measuring, that it might be beneficial to preallocate 64 bytes in advance to allow sixteen 32-bit integers to be inserted without requiring a heap allocation. Now it’s no longer redundant, at least not with std::vector<int>. And then you might say, “But I could just generalize this to a new SmallVector<int, 16>, and you could. But then let’s say you find it’s useful because these are for very small, short-lived arrays to quadruple the array capacity on heap allocations instead of increasing by 1.5 (roughly the amount that many vector implementations use) while working off the assumption that the array capacity is always a power of two. Now your container is really different, and there’s probably no container like it. And maybe you could try to generalize such behaviors by adding more and more template parameters to customize preallocation heavior, customize reallocation behavior, etc. etc., but at that point you might find something really unwieldy to use compared to a dozen lines of simple C code.

And you might even reach a point where you need a data structure which allocates 256-bit aligned and padded memory, storing exclusively PODs for AVX 256 instructions, preallocates 128 bytes to avoid heap allocations for common-case small input sizes, doubles in capacity when full, and allows safe overwrites of trailing elements exceeding array size but not exceeding array capacity. At that point if you’re still trying to generalize a solution to avoid duplicating a small amount of C code, may the programming gods have mercy on your soul.

So there are also times like this where what initially starts out looking redundant starts to grow, as you tailor a solution to better and better and better fit a certain use case, into something wholly unique and not redundant at all. But that’s only for things where you can afford to tailor them perfectly to a specific use case. Sometimes we just need a “decent” thing that’s generalized for our purpose, and there I benefit the most from very generalized data structures. But for exceptional things perfectly made for a particular use case, the idea of “general purpose” and “made perfectly for my purpose” start to become too incompatible.

PODs and Primitives

Now in C, I often find excuses to store PODs and especially primitives into data structures whenever possible. That might seem like an anti-pattern but I’ve actually found it inadvertently helpful in improving the maintainability of code over the types of things I used to do more often in C++.

A simple example is interning short strings (as is typically the case with strings used for search keys — they tend to be very short). Why bother dealing with all these variable-length strings whose sizes vary at runtime, implying non-trivial construction and destruction (since we might need to heap allocate and free)? How about just store these things in a central data structure, like a thread-safe trie or hash table designed just for string interning, and then refer to those strings with a plain old int32_t or:

struct IternedString 
{
    int32_t index;
};

… in our hash tables, red-black trees, skip lists, etc, if we don’t need lexicographical sorting? Now all of our other data structures which we coded to work with 32-bit integers can now store these interned string keys which are effectively just 32-bit ints. And I’ve found in my use cases at least (might just be my domain since I work in areas like raytracing, mesh processing, image processing, particle systems, binding to scripting languages, low-level multithreaded GUI kit implementations, etc — low-level things but not as low-level as an OS), that the code coincidentally happens to become more efficient and simpler just storing indices to things like this. That makes it so I’m often working, say 75% of the time, with just int32_t and float32 in my non-trivial data structures, or just storing things that are the same size (almost always 32-bit).

And naturally if that’s applicable for your case, you can avoid having a number of data structure implementations for different data types, since you’ll be working with so few in the first place.

Testing and Reliability

One last thing I’d offer, and it might not be for everyone, is to favor writing tests for those data structures. Make them really good at something. Make sure they’re ultra reliable.

Some minor code duplication becomes a lot more forgivable in those cases, since code duplication is only a maintenance burden if you have to make cascading changes to the duplicated code. You eliminate one of the prime reasons for such redundant code to change by making sure it’s ultra reliable and really well-suited for what it’s’trying to do.

My sense of aesthetics have changed over the years. I no longer get irritated because I’m seeing one library implement dot product or some trivial SLL logic that is already implemented in another. I only get irritated when things are poorly tested and unreliable, and I’ve found that a much more productive mindset. I have genuinely dealt with code bases that duplicated bugs through duplicated code, and have seen the worst cases of copy-and-paste coding making what should have been a trivial change to one central place turn into an error-prone cascading change to many. Yet many of those times, it was the result of poor testing, of the code failing to become reliable and good at what it was doing in the first place. Before when I was working in buggy legacy codebases, my mind associated all forms of code duplication as having a very high probability of duplicating bugs and requiring cascading changes. Yet a miniature library which does one thing extremely well and reliably will find very few reasons to change in the future, even if it has some redundant-looking code here and there. My priorities were off back then when the duplication irritated me more than the poor quality and lack of testing. These latter things should be the top priority.

Code Duplication For Minimalism?

This is a funny thought that popped in my head, but consider a case where we might encounter a C and C++ library which roughly do the same thing: both have roughly the same functionality, the same amount of error handling, one isn’t significantly more efficient than the other, etc. And most importantly, both are competently implemented, well-tested, and reliable. Unfortunately I have to speak hypothetically here since I’ve never found anything close to a perfect side-by-side comparison. But the closest things I’ve ever found to this side-by-side comparison often had the C library being much, much smaller than the C++ equivalent (sometimes 1/10th of its code size).

And I believe the reason for that is because, again, to solve a problem in a general way that handles the widest range of use cases instead of one exact use case might require hundreds to thousands of lines of code, while the latter might only require a dozen. In spite of the redundancy, and in spite of the fact that the C standard library is abysmal when it comes to providing standard data structures, it often ends up producing less code in human hands to solve the same problems, and I think that’s primarily due to the differences in human tendencies between these two languages. One promotes solving things against a very specific use case, the other tends to promote more abstract and generic solutions against the widest range of use cases, but the end result of these doesn’t necessarily favor less overall code to maintain on the side that solves things at the most general level against the widest range of needs to produce the minimum amount of redundancy.

I was looking at someone’s raytracer on github the other day and it was implemented in C++ and required so, so much code for a toy raytracer. And I didn’t spend that much time looking at the code but there were a boatload of general-purpose structures in there that were handling way, way more than what a raytracer would need. And I recognize that style of coding because I used to use C++ the same way in a kind of super bottom-up fashion, focusing on making a full-blown library of very general-purpose data structures first that go way above and beyond the immediate problem at hand and then tackling the actual problem second. But while those general structures might eliminate some redundancy here and there and enjoy a lot of reuse in new contexts, in exchange they inflate the project enormously by exchanging a little bit of redundancy with a boatload of unnecessary code/functionality, and the latter isn’t necessarily easier to maintain than the former. To the contrary I often find it harder to maintain, since it’s hard to maintain a design of something general which has to tightrope balance design decisions against the widest range of needs possible.