generic containers in C
Author
I'm brushing up on my C, and I just realized I never saw something like a C++ std::vector in C. Since C doesn't have templates, I thought of two ways I could implement a vector on my own:
a) Implement a vector with element type pointer-to-void and do casting on the client side. Would it be possible to store integers directly as pointer-to-voids? Is (int)((void*)i) guaranteed to be i, assuming sizeof(void*) == sizeof(int)? Or could I only store pointers in such a vector?
b) Write a header file that relies on a macro ELEMENT_TYPE to be defined before the client includes the header. I'm not sure if multiple clients in distinct compilation units needing vectors of the same type would pose a problem for the linker though...
Surely there's an idiomatic C way to build "generic" data structures. Please enlighten me. Thanks!
[Edited by - DevFred on August 20, 2008 3:44:40 AM]
Quote:Original post by DevFredGeneric programming is not idiomatic in C :(
Surely there's an idiomatic C way to build "generic" data structures. Please enlighten me. Thanks!
Quote:a) Implement a vector with element type pointer-to-void and do casting on the client side. Would it be possible to store integers directly as pointer-to-voids? Is (int)((void*)i) guaranteed to be i, assuming sizeof(void*) == sizeof(int)? Or could I only store pointers in such a vector?This is the approach that I've seen used before. Obviously if everything is done via pointers then performance will be worse than the C++ template version. Your sizeof hack should work to allow you to avoid using pointers for primitive types, but again, this extra check does introduce a performance overhead that wouldn't be present in a C++ template version.
Quote:b) Write a header file that relies on a macro ELEMENT_TYPE to be defined before the client includes the header. I'm not sure if multiple clients in distinct compilation needing vectors of the same type would pose a problem for the linker though...This would allow you to tailor the container to the element type at compile time (like a template), but it is a bit messy.
I'm imagining something like this, and now that I think about it, it's not that bad seeing it does give you the power of templates:
#define ELEMENT_TYPE int#include "vector.h"#undef ELEMENT_TYPEvoid foo(){ vector_int myVector; vec_init( &myVector ); vec_push_back( &myVector, 42 );}------- vector.h -------#define vector vector_##ELEMENT_TYPEstruct vector{ ELEMENT_TYPE* data;};void vec_init( vector* v, unsigned int size ){ v->data = malloc( sizeof(ELEMENT_TYPE)*size );}void vec_push_back( vector* v, ELEMENT_TYPE data ){ ...}#undef vectorQuote:Original post by Hodgman
I'm imagining something like this, and now that I think about it, it's not that bad seeing it does give you the power of templates:
*** Source Snippet Removed ***
What if I want to use a vector of ints and a vector of floats in the same program?
Quote:Original post by Gage64In theory, this could be achieved by adding a namespacing prefix to every defined function, and including the header different times with different ELEMENT_TYPE values.
What if I want to use a vector of ints and a vector of floats in the same program?
In practice, as written right now, the substitution shouldn't happen (since substitutions never happen in preprocessor directives) and the header would always define a structure named vector_ELEMENT_TYPE.
I heard that the first edition of The C++ Programming Language suggested using macros this way (when templates didn't exist). I think my college library has that book so maybe I'll take a look...
Quote:Original post by Gage64
What if I want to use a vector of ints and a vector of floats in the same program?
in my example the structures would be named vector_int and vector_float. The vec_init and vec_push_back are overloaded for these two types.
Quote:Original post by HodgmanQuote:Original post by Gage64
What if I want to use a vector of ints and a vector of floats in the same program?
in my example the structures would be named vector_int and vector_float. The vec_init and vec_push_back are overloaded for these two types.
But the question was about C. Maybe C99 supports function overloading, but AFAIK most compilers don't support C99 so relying on it is probably not a good idea.
Author
Quote:Original post by ToohrVyk
this could be achieved by adding a namespacing prefix to every defined function
That's what I was thinking. The following first try obviously doesn't work, because ## can only be used in macro definitions (let's ignore parameters for now):
void push_##ELEMENT_TYPE(void){}The next step is to define a macro for the appending:
#define GENERIC(x,y) x##yvoid GENERIC(push_,ELEMENT_TYPE)(void){}The problem is that the function is now literally called push_ELEMENT_TYPE. I assume the reason for this is that while replacing GENERIC, its parameters are treated literally. So we need another macro:
#define SUBSTITUTE(x,y) x##y#define GENERIC(x,y) SUBSTITUTE(x,y)void GENERIC(push_,ELEMENT_TYPE)(void){}This works, but I'm not exactly sure in which order macros get expanded. Can anyone explain in detail why we need this one extra level?
Author
Quote:Original post by Hodgman
in my example the structures would be named vector_int and vector_float.
No, both would literally be named vector_ELEMENT_TYPE. Stupid preprocessor :)
It seems we need more macros to get the desired result:
#define ELEMENT_TYPE int#define APPEND(x,y) x##y#define SUBSTITUTE(x,y) APPEND(x,y)#define GENERIC(x) SUBSTITUTE(x,ELEMENT_TYPE)#define vector GENERIC(vector_)struct vector{ /* ... */};Quote:Original post by HodgmanQuote:Original post by Gage64
What if I want to use a vector of ints and a vector of floats in the same program?
in my example the structures would be named vector_int and vector_float. The vec_init and vec_push_back are overloaded for these two types.
Whether we are considering real overload or not, it will not help you here. Both those functions are referring to the same ELEMENT_TYPE. The "user" would have to redefine the same ELEMENT_TYPE for int and for float which would be not so easy to deal with... Aditionally, if the sizes of the types are different, push_back may not work.
[added: DevFred answered that first then me :)! he's fast :D ]
The approach I've seen most used is the first one
Quote:Original post by DevFred
a) Implement a vector with element type pointer-to-void and do casting on the client side. Would it be possible to store integers directly as pointer-to-voids? Is (int)((void*)i) guaranteed to be i, assuming sizeof(void*) == sizeof(int)? Or could I only store pointers in such a vector?
where you carry a structure for the vector arround in each function. Something in the lines of:
typedef struct { int sizeOfEachElement; int maxCapacity; int numberOfElements; void *data;}GenericVector;void genericVector_Init(GenericVector *vector, int maxElems, int sizeOfEachElement){ vector->sizeOfEachElement = sizeOfEachElement; vector->maxCapacity = maxElems; vector->numberOfElements = 0; vector->data = malloc(sizeOfEachElement * maxElems);}int genericVector_PushElement(GenericVector *vector, void *element){ if(vector->numberOfElements >= vector->maxCapacity) { /*Error condition. vector is full.*/ return ERROR_CODE; } else { memcpy(); memcpy(vector->data + vector->numberOfElements, element, vector->sizeOfEachElement); vector->numberOfElements ++; return 0; }}void genericVector_Destroy(){ vector->sizeOfEachElement = 0; vector->maxCapacity = 0; vector->numberOfElement = 0; free(vector->data); vector->data = NULL;}int main(){ GenericVector intVect, doubleVect, elephantVect; genericVector_Init(&intVect, 10, sizeof(int)); genericVector_Init(&doubleVect, 20, sizeof(double)); genericVector_Init(&elephantVect, 10, sizeof(Elephant)); ...}[Edited by - wolverine on August 20, 2008 6:35:33 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement