Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

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.

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

share|improve this question
6  
The moral quandary you are describing is not unique to C. Anecdotally, I find that the bar for creating a generic implementation is quite high, unless you have an audience for it. The amount of effort required to create a good generic implementation far exceeds the point-solution, IME. –  Robert Harvey Jan 7 '13 at 19:49
3  
@RobertHarvey in my experience, re-usable code takes 3-4x times more efforts to write –  gnat Jan 7 '13 at 20:10
1  
@kevincline: Well, Java does have generics. Granted, it's the "don't pay attention to the man behind the curtain" type of generics. –  Robert Harvey Jan 7 '13 at 21:37
1  
And before generics, you could have passed in Object and passed in Float, Double, Integer and Long, respectively. –  tieTYT Jan 7 '13 at 22:13
3  
Deja vu is a code smell-check and a preference for DRY is at the root of all the best practices worth paying attention to IMO. But I've shot myself in the foot in OOP-oriented languages trying too hard to avoid duplication for its own sake. If you're not binding unrelated concerns to each other needlessly or destroying legibility for the sake of two similar functions becoming one, I'd go with the instinct in most any language. –  Erik Reppen Jan 8 '13 at 0:47

5 Answers 5

up vote 17 down vote accepted

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.

share|improve this answer
1  
One could also generate repetitive C code using external templating languages / tools or a shell script or using ant or ... –  Job Jan 7 '13 at 22:55
    
What is this Google-obfuscated Russian URL that you've placed in your answer? Clicking in it causes an "open" prompt to appear in my browser. Is this safe? –  Robert Harvey Jan 8 '13 at 19:46
2  
@RobertHarvey My antivirus and security scans think it is fine. It is a C language Header file, extension .h. It appears legit. –  maple_shaft Jan 8 '13 at 20:11
    
@maple_shaft: OK. I've removed the Googlization around the link. –  Robert Harvey Jan 8 '13 at 20:12
    
It's just a plain-text .h (C-header) file –  Charles Salvia Jan 9 '13 at 0:47

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.

share|improve this answer
    
"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." Ha, ha, ha! C has always been one of my favorite languages, but that's still pretty funny! –  GlenPeterson Jan 7 '13 at 21:08

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.

share|improve this answer
1  
--"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"-- In C that is an over simplification. Try making a Stack in C for integers, doubles, and strings without duplicating the push and pop functions for each data type. –  mike30 Jan 7 '13 at 20:55
    
@mike Isn't that possible using void pointers? –  faif Jan 7 '13 at 21:05
    
@mike - good point. But a counter-point would be that you could implement Stack for each data type in such a way that you don't need to implement Stack again. So the goal is not numberOfImplementations = 1, but more like 5. You might be able to make the int implementation work for chars... It's been so long since I've used C that I can't remember. –  GlenPeterson Jan 7 '13 at 21:05
1  
@faif. Yes, but the need to use void pointers makes the point for C. Casting pointers is slower and less elegant than alternatives found in C++. Duplicating the code ranks somewhat higher on the list of possible options when coding in C. –  mike30 Jan 7 '13 at 21:54
    
@mike30 Are there any proofs/references about: "Casting pointers in C is slower than alternatives found in C++?" –  faif Dec 11 '13 at 13:09

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.

share|improve this answer

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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.