Jump to content
  • Advertisement
Sign in to follow this  
DevFred

generic containers in C

This topic is 3650 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by DevFred
Surely there's an idiomatic C way to build "generic" data structures. Please enlighten me. Thanks!
Generic programming is not idiomatic in C :(

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_TYPE

void foo()
{
vector_int myVector;
vec_init( &myVector );
vec_push_back( &myVector, 42 );
}

------- vector.h -------
#define vector vector_##ELEMENT_TYPE

struct 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 vector

Share this post


Link to post
Share on other sites
Quote:
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?

Share this post


Link to post
Share on other sites
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 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.

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.


Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by Hodgman
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.


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.

Share this post


Link to post
Share on other sites
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##y

void 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?

Share this post


Link to post
Share on other sites
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
{
/* ... */
};

Share this post


Link to post
Share on other sites
Quote:
Original post by Hodgman
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.


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]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!