Genericity vs type-safety? Using void* in C_问答_开发者

Coming from OO (C#, Java, Scala) I value very highly the principles of both code reuse and type-safety. Type arguments in the above languages do the job and enable generic data structures which are both type-safe and don't 'waste' code.

As I get stuck into C, I'm aware that I have to make a compromise and I'd like it to be the right one. Either my data structures have a void * in each node / element and I lose type safety or I have to re-write my structures and code for each type I want to use them with.

The complexity of the code is an obvious factor: iterating through an array or a linked-list is trivial and adding a *next to a struct is no extra effort; in these cases it makes sense not to try and re-use structures and code. But for more complicated structures the answer isn't so obvious.

There's also modularity and testability: separating out the type and its operations from the code that uses the structure makes testing it easier. The inverse is also true: testing the iteration of some code over a structure whilst it's trying to do other things gets messy.

So what's your advice? void开发者_运维问答 * and reuse or type-safety and duplicated code? Are there any general principles? Am I trying to force OO onto procedural when it won't fit?

Edit: Please don't recommend C++, my question is about C!

I would say use void * so you can re-use the code. It's more work to re-implement e.g. a linked list, than to make sure you get/set the data in the list properly.

Take as many hints from glib as possible, I find their data structures very nice and easy to use, and have had little trouble because of the loss of type safety.

I think you'll have to strike a balance between the two, just as you suggest. If the code is only a few lines and trivial I would duplicate it but if it's more complex, I would consider working with void* to avoid having to do any potential bug fixing and maintenance in several places and also to reduce the code size.

If you look at the C runtime library, there's several "generic" functions that work with void*, one common example is sorting with qsort. It would be madness to duplicate this code for every type you'd like to sort.

There's nothing wrong with using void pointers. You don't even have to cast them when assigning them to a variable of type of pointer since the conversion is done internally. It migtht be worth having a look at this: http://www.cpax.org.uk/prg/writings/casting.php

The answer this question is the same as getting efficient templates for link list in C++.

a) Create an abstract version of the algorithm that uses void* or some Abstracted Type

b) Create a light weight public interface to call the Abstracted Type algorithms and caste between them.

For example.

typedef struct simple_list
  {
  struct simple_list* next;
  } SimpleList;

void add_to_list( SimpleList* listTop, SimpleList* element );
SimpleList* get_from_top( SimpleList* listTop );
// the rest

#define ListType(x) \
    void add_ ## x ( x* l, x* e ) \
        { add_to_list( (SimpleList*)l, (SimpleList*)x ); } \
    void get_ ## x ( x* l, x* e ) \
        { return (x*) get_from_to( (SimpleList*)l ); } \
   /* the rest */

typedef struct my_struct
  {
  struct my_struct* next;
  /* rest of my stuff */
  } MyStruct;

ListType(MyStruct)

MyStruct a;
MyStruct b;

add_MyStruct( &a, &b );
MyStruct* c = get_MyStruct(&a);

etc etc.

We use OO in C a lot here, but only for encapsulation and abstraction, no polymorphism or so.

Which means we have specific types, like FooBar(Foo a, ...) but, for our collection "classes", we use void *. Just use void * where multiple types could be used, BUT, by doing so, ensure you don't need the argument to be of a specific type. As per collection, having void * is alright, because the collection doesn't care about the type. But if your function can accept type a and type b but none other, make two variants, one for a and one for b.

The main point is to use a void * only when you don't care about the type.

Now, if you have 50 types with the same base structure (let's say, int a; int b; as first members of all types), and want a function to act upon those types, just make the common first members a type by itself, then make the function accept this, and pass object->ab or (AB*)object is your type is opaque, both will work if ab is the first field in your struct.

You can use macros, they will work with any type and the compiler will check statically the expanded code. The downside is that the code density (in the binary) will worsen and they are more difficult to debug.

I asked this question about generic functions some time ago and the answers could help you.

You can efficiently add type information, inheritance and polymorphism to C data structures, that's what C++ does. (http://www.embedded.com/97/fe29712.htm)

Definitely generic void*, never duplicate code!

Take into account that this dilemma was considered by many a C programmer, and many major C projects. All serious C projects I've ever encountered, whether open-source or commercial, picked the generic void*. When used carefully and wrapped into a good API, it is barely a burden on the user of the library. Moreover, void* is idiomatic C, recommended directly in K&R2. It is the way people expect code to be written, and anything else would be surprising and badly accepted.

You can build a (sort of) OO framework using C, but you miss out on a lot of the benefits ... like an OO type system that the compiler understands. If you insist on doing OO in a C-like language, C++ is a better choice. It is more complicated than vanilla C, but at least you get proper linguistic support for OO.

EDIT: Ok ... if you insist that we don't recommend C++, I recommend that you don't do OO in C. Happy? As far as your OO habits are concerned, you should probably think in terms of "objects", but leave inheritance and polymorphism out of your implementation strategy. Genericity (using function pointers) should be used sparingly.

EDIT 2: Actually, I think that use of void * in a generic C list is reasonable. It is just trying to build an mock OO framework using macros, function pointers, dispatching and that kind of nonsense that I think is a bad idea.

In Java all collections from java.util package in effect hold equivalent of void* pointer ( the Object ).

Yes, generics ( introduced in 1.5 ) add syntactic sugar and prevent you from coding unsafe assignments, however the storage type remains Object.

So, I think there is no OO crime commited when you use void* for generic framework type.

I would also add type-specific inlines or macro wrappers that assign/retrieve data from the generic structures if you do this often in your code.

P.S. The one thing that you should NOT do is to use void** to return allocated/reallocated generic types. If you check the signatures of malloc/realloc you will see that you can achieve correct memory allocations without dreaded void** pointer. I am only telling this because I've seen this in some open-source project, that I do not wish to name here.

A generic container can be wrapped with a little work so that it can be instantiated in type-safe versions. Here is an example, full headers linked below:

/* generic implementation */

struct deque *deque_next(struct deque *dq);

void *deque_value(const struct deque *dq);

/* Prepend a node carrying `value` to the deque `dq` which may
 * be NULL, in which case a new deque is created.
 * O(1)
 */
void deque_prepend(struct deque **dq, void *value);

From the header that can be used to instantiate specific wrapped types of deque

#include "deque.h"

#ifndef DEQUE_TAG
#error "Must define DEQUE_TAG to use this header file"
#ifndef DEQUE_VALUE_TYPE
#error "Must define DEQUE_VALUE_TYPE to use this header file"
#endif
#else

#define DEQUE_GEN_PASTE_(x,y) x ## y
#define DEQUE_GEN_PASTE(x,y) DEQUE_GEN_PASTE_(x,y)
#define DQTAG(suffix) DEQUE_GEN_PASTE(DEQUE_TAG,suffix)

#define DQVALUE DEQUE_VALUE_TYPE

#define DQREF DQTAG(_ref_t)

typedef struct {
    deque_t *dq;
} DQREF;

static inline DQREF DQTAG(_next) (DQREF ref) {
    return (DQREF){deque_next(ref.dq)};
}

static inline DQVALUE DQTAG(_value) (DQREF ref) {
    return deque_value(ref.dq);
}

static inline void DQTAG(_prepend) (DQREF *ref, DQVALUE val) {
    deque_prepend(&ref->dq, val);
}

deque.h: http://ideone.com/eDNBN
deque_gen.h: http://ideone.com/IkJRq