• ### Announcements

#### Archived

This topic is now archived and is closed to further replies.

# "templates" in old-school C?

## Recommended Posts

smitty1276    560
It''s hard to search for this topic, because a lot of sites concerning C++ templates use the word C... sorry. If I want to do something as (seemingly) simple as writing a reusable linked list implementation, how would I go about it in C? I realize that I could just use void* for all of my nodes, and just cast them, but is there some slick way using typedefs and macros, etc., to allow for an unknown type that can be determined at runtime?

##### Share on other sites
antareus    576
Don''t triple post. Delete the other ones.

No, void* is the way to do it. C has nothing really in the ways of tricks like C++ has.

##### Share on other sites
smitty1276    560
I didn''t see a delete button, but I saw it under edit (finally)... I deleted them, but I think they''re still there.

Sorry.

##### Share on other sites
Oluseyi    2103
What the hell, I''ll bite.

First off, unlike templates in C++, your system will be evaluated at runtime (templates are evaluated at compile time). The system will actually have a lot in common with implementing OO in C (so you might as well do it, too). Consider the following C++ fragment:
template < typename T >void SomeFunction( const T & t ){  t.generic_method();}
This application of templates requires a means for determining that the actual type instantiating the template (T) has the method generic_method. This is trivial in C++ because the code is fully expanded and then passed to the compiler, which simply looks into the symbol table. Since your system would be evaluated at runtime, you''d have to store an explicit symbol table which would be searched.

Furthermore, since neither C nor C++ is introspective (there is no way to programmatically query an entity as to its properties), you''ll need to use specific tokens as associative indices to indicate the existence of a certain function in an object''s interface. This could simply be the function name (an entry with the key "find" indicates the existence of a function find()).

C is not inherently object-oriented and doesn''t support inheritance, so all your objects must actually be of one type in C, but masquerade as being of different types. This is the hard part. You need to store a generic reference to all your objects (void *), but supply a conversion mechanism to recover the original object complete with type. This suggests typecasting, and would be easy if the function-style typecast could be assigned to a function pointer. Unfortunately it can''t, AFAICT.

This is such an intrinsic problem that I am unable to think of a workaround or solution. So you''re SOL.

Wasn''t that fun!

##### Share on other sites
smart_idiot    1298
I think you could probably use a macro to generate your class with whatever types you want, but wouldn''t using C++ be easier?

##### Share on other sites
smitty1276    560
I'm actually being forced to take C programming at school, only because it is a prerequisite for all of the other computer science classes I already have that are transferring (CSI, CSII, CSIII, etc...) You'd think since I have the classes that it is a prereq for... nevermind. In any case, I talked them into at least letting me skip to *ADVANCED* C, which is still a joke.

We are supposedly covering linked lists this week, and since I have already known how to do those for 10 years or so, I figured I would try to spice things up just for fun.

My point is, I CAN'T USE C++... I just wanted something "fun".

[edited by - smitty1276 on February 16, 2004 10:19:27 PM]

##### Share on other sites
If you don''t mind ugly...

//of course you know templated functions:#define Add(A,B) (A + B)//similarly, a templated class:#define ListNode(Type) \struct \{ \    Type  Value; \    void* Prev; \    void* Next; \} void main ( ){    ListNode(int) IntNode;    ListNode(float) FloatNode;     IntNode.Value = 4;    FloatNode.Value = 0.5;}

Cool, huh? Of course you can have trouble doing certain things... but it works. Only thing is you can''t name the struct, hence the void* pointers it uses. The reason you can''t name it is you can''t create different names for the different types, so you''d have multiple declarations of the same structure.

~CGameProgrammer( );

##### Share on other sites
davepermen    1047
you could, i guess, abuse __LINE__ :D for unique names, that is:D

If that''s not the help you''re after then you''re going to have to explain the problem better than what you have. - joanusdmentia

davepermen.net

##### Share on other sites
smitty1276    560
I tried the define thing, and I kept getting weird errors... maybe I''ll try again. It was just a quick attempt and I didn''t really do any trouble shooting.

Thanks for the responses.

##### Share on other sites
ironfroggy    122
why do you have to do this anyway? i could go the "c sucks" route, but ill be nice. however, you can also do hybrid (mostly c and toss in the c++ features you like)

##### Share on other sites
Zahlman    1682
quote:
Original post by CGameProgrammer
#define ListNode(Type) \struct \{ \    Type  Value; \    void* Prev; \    void* Next; \}

Cool, huh? Of course you can have trouble doing certain things... but it works. Only thing is you can''t name the struct, hence the void* pointers it uses.

Er, sure you can. Use token-pasting to create your own mangled names.

##### Share on other sites
quote:
Original post by smitty1276
I tried the define thing, and I kept getting weird errors... maybe I''ll try again. It was just a quick attempt and I didn''t really do any trouble shooting.

Thanks for the responses.

It compiled fine for me in Visual C++.

~CGameProgrammer( );

##### Share on other sites
RenderTarget    398
You could do something like this:

// templtype.h// note the lack of #ifndef/#define/#endif bracket#define TEMPLTYPELIST(x)    x##Liststruct{  TEMPLTYPE Value;  TEMPLTYPELIST( TEMPLTYPE ) * pPrev;  TEMPLTYPELIST( TEMPLTYPE ) * pNext;} TEMPLTYPELIST( TEMPLTYPE );

// main.c#define TEMPLTYPE int#include templtype.h#undef TEMPLTYPE#define TEMPLTYPE float#include templtype.h#undef TEMPLTYPEvoid main(){  intList il;  floatList fl;  ...}

I think that would work.

I like pie.

##### Share on other sites
Sneftel    1788
You could use CFront for processing templates into C code.

"Sneftel is correct, if rather vulgar." --Flarelocke

##### Share on other sites
RenderTarget    398
But that''s less fun.

I like pie.

##### Share on other sites
Nice trick RenderTarget, I didn''t know about ##blah; I only knew #blah converts the value to a string. For referencing, I still think ListNode(int) is better than ListNode_int, and of course ##blah doesn''t work for most types, like "unsigned int" or "char*" since that would result in invalid names.

~CGameProgrammer( );

##### Share on other sites
RenderTarget    398
quote:
Original post by CGameProgrammer
Nice trick RenderTarget, I didn''t know about ##blah; I only knew #blah converts the value to a string. For referencing, I still think ListNode(int) is better than ListNode_int, and of course ##blah doesn''t work for most types, like "unsigned int" or "char*" since that would result in invalid names.

You could always typedef those, if you really needed it to work. *shrug*

I like pie.

##### Share on other sites
Here''s a link: Faking Templates In C. Take note that there''s an error in the code, one of the declared functions is missing or something like that.

##### Share on other sites
Here''s another implementation, probably a better one too. The url that I had for it no longer works, so you''ll have to cut an paste. I tried to talk the author into using a different acronym then "sdl" but he was stubborn about it.

/* readme.txt */This document describes the "Small Define Library". It is a even smaller introduction to the API and usage as well as the "build instruction".I must add, that I gave up developing the lib any futher, because I ran intoseriously problems with implementing iterators generic and typesafe enoughto satisfy my standards. It seems not possible under C, so I left a smallvector-implementation of the stl''s std::vector.---------------------------API / Usage---------------------------I suggest you are familiar with the c++ stl.- include the correct header file - cvector.h#include <cvector.h>- declare the vectors type (or more than one, if you want different types).  If you want a vector of floats, do like this in one of your c-files (I  recommend to create a separate file for it):implement_vector(float)  And this in each file you want to use the vector_float:declare_vector(float)  These will expand a real huge macro and provide you with all functions   needed to access the floated vector.- create your container "object"vector_float myVec;vector_float_ctor(&myVec);  myVec will be a struct of some internal data which you should not touch. If  you _really_ have to touch beware, that these could change in any version  of the library unannounced.  Do not forget to call the ctor-function or your vector remain uninitialised.- function names are like this:vector_type_stlname(&container_variable, ...);  where:  "vector" is the container-type - means "vector" ;-)  "type" is the type you choose in the macro above   	(e.g. float)  "stlname" is the name of the function in the c++ standard template library,  	(e.g. push_back, empty, size or begin)  "container_variable" is the variable you named the container after   	(e.g. myVec)  "..." are other parameter which are similar to those in stl.   	(e.g. the value when adding to a vector with push_back)- iterators are just pointer to the elements, so you can increment, decrement  or dereference them like you wish- if you prefer to work with a simple c-array and only want vector to  build up the array and manage the memory stuff, call this:float* ptrToVec = 0;if (!vector_float_empty(&myVec)) ptrToVec = vector_float_begin(&myVec);  However, remember that some vector_* calls invalidate such pointers (since  the storage gets rearranged).- at end of usage, CALL THE DESTRUCTOR! There are no automatic ctors   and dtors in C, so you have to do it by yourself:vector_float_dtor(&myVec); See test.c for an example.---------------------------Build instructions---------------------------Up to now, there are no c-files but only the header required. This is most like the stl and because almost everything in here is either an inline (hope your compiler get inline correct?) or a #define.This means, there are no build instructions. Just copy the headers anywhereyou can access them and be happy. (Make sure, they are in your include path).Hint: If you try to compile the example (test.c) you will have to add thecurrent directory to your include path (for gcc use "gcc -I. test.c").Write me your opinion (you can flame as well, if you like ;-)sdl@kutzsche.netImmanuel Scholz @2002// ---------------------------------------------------------------------------What I want: (Objective)vector+ an implementation of a vector representing a continous memory block.+ the user can give any datatype to fill the vector with.+ the items in the block should not contain only of pointers to the required  data type, instead they should BE such a data type. This means, an vector of  int''s with the length of 10 should be accessible as an int[10].- the names of the vector''s function should be generic, and possible free of  the data types name (vector_size, vector_empty...)+ the user should not be able to access the structure of the vector. This  means, he only see a forward declaration (incomplete data type) of the  vector struct.+ the vector should be typesafe not to accept incompatible types instead of  those choosen initially by the user. This means, if you try to pass an int*   to an vector of int''s, it has to be rejected, best at compile time, but at  least at runtime.+ the implementation of the vector''s function should be efficient (if possible)// ---------------------------------------------------------------------------General questions (FAQ)Q: Is this library a good choice for me?A: Depends.  - If you are familar with c++ stl and look for a vector under C, then    maybe yes. It is, however, much smaller. - If you want a fast but generic array implementation, you are on it.   It surely fit your needs.   Like in c++, you can get the vector as an ordenary c-array and work on    this, if speed is an concern. - If you want a typesafe array implementation, and your compiler is   able to give an error on pointer assignments of different types, then SDL   might be what you are looking for. Make sure you turn compiler warnings    about incompatible pointer assignment into errors (e.g. -Werror with gcc).   Even without that support from your compiler, you get still an compiler(!)    error when you (as example) trying to add anything incompatible to an    integer into a vector of integers. - If you are interestet in generic programming or OOP under C it might a    good choice for you too. - But if you want a debugable, gdb-friendly library then sorry: SDL is    good at this. - If you dislike #defines in general, SDL is REALLY nothing for you. - Finally the size of the code generated by SDL can become quite big (if you   use more than one different type), compared to some tiny void* -   implementations so if you work in really small embedded systems, you may   break the code memory footprint. But remember, that usually the size   of the resulting vector is smaller than any void* - implementation.   Q: Why GPL? Can''t you make it LGPL or BSD?A: No. If you wan''t to use it under any lesser licences than GPL, write me,   I will sell you a seperate licence. But consider first to release your   project under GPL instead ;-).Q: Why you do such a stupid thing? Don''t you see that these whole #define   stuff is a real mess and fubar?A: It still proove a feasible way of generic programming under a language    like C. And I think it is usable of some kind (at least if you get used    to the debug-capabilities an "gcc -E -P | indent" will provide ;) )More questions? Write to sdl@kutzsche.netImmanuel Scholz @2002

/* cvector.h *//* August 2, 2002 *//* * This library is provided under GPL v2.0 * See http://www.gnu.org/copyleft/gpl.html * * copyright Immanuel Scholz @2002 */#ifndef SDL_CVECTOR_H__#define SDL_CVECTOR_H__/*----------------------------------------------------------------------*//* * Use this macro to declare the functions only but not to implement * them. You have to call this in every compile unit you are using vector * (instead of implement_vector, which has to be only declared once) */#define declare_vector(type)						\/* * The vector structure consist of a pointer to the begin, to the * point in memory after the last item and to the end of the * currently maximum allocated storage. Since the memory is allocated * in one block, it is guaranteed to be continuous. *  * Note: you should use the typedef vector_##type instead of the * structure. */									\struct vector_##type##_t;						\typedef struct vector_##type##_t vector_##type;				\									\/* * User _have_ to call the constructor before doing anything with the * vector. */									\void vector_##type##_ctor(vector_##type* v);				\									\/*  * If user stores pointers in the vector he has to make sure they are * deleted before calling the destructor. vector will not delete the * contens of itself - only the container (much like c++-stl) */									\void vector_##type##_dtor(vector_##type* v);				\									\/* Return the size of the vector as integer */				\int vector_##type##_size(const vector_##type* v);			\									\/* Return the current capacity of the vector */				\int vector_##type##_capacity(const vector_##type* v);			\									\/* Return 0 if vector has at least one element in it */			\int vector_##type##_empty(const vector_##type* v);			\									\/* * Reserves enough space for the vector to hold new_capacity items. If * the vector had already enough space, nothing is done. This call can * made any pointer to members invalid. */									\void vector_##type##_reserve(vector_##type* v, int new_capacity);	\									\/* * Resizes the vector so that his new size become "new_size". if it was * smaller before, new memory will be allocated (and zeroed), if it was * larger, the last positions are removed (but not free()''d!). If the * size is euqal to new_size, nothing happens. */									\void vector_##type##_resize(vector_##type* v, int new_size);		\									\/*  * Return a pointer to the item at "index". Does range check  * (via assertion).  */									\type* vector_##type##_at(const vector_##type* v, int index);		\									\/*  * Return an pointer to the first element (or end() if empty) Note, * that since the memory is continous, the pointer you get can be used * to access the vector like an ordenary c-array! (I am very proud of * this feature of sdl) */									\type* vector_##type##_begin(const vector_##type* v);			\									\/* Return a pointer to the place after the last element in list */	\type* vector_##type##_end(const vector_##type* v);			\									\/* * Inserts the data on back of the vector. If new memory has to be * allocated, it will be (all pointers to elements of the list looses * validity). */									\void vector_##type##_push_back(vector_##type* v, type data);		\									\/* * Removes the last element from the vector. (Does not change the  * capacity) */									\void vector_##type##_pop_back(vector_##type* v);/*----------------------------------------------------------------------*//* * Call to this macro once in any c-file you use to generate all the * functions and declarations you need */#define implement_vector(type)						\									\									\									\/* * The rest is for internal use of sdl. Do not even look at this  * directly (except sending me bug reports to sdl@kutzsche.net ;-) */									\									\									\									\/* first thing to do is to declare all vector-functions */		\declare_vector(type)							\									\/* * The vector structure consist of a pointer to the begin, to the * point in memory after the last item and to the end of the * currently maximum allocated storage. Since the memory is allocated * in one block, it is guaranteed to be continuous. * * Note: you should use the typedef vector_##type instead of this * structure. */                                                                     \struct vector_##type##_t {                                              \    type* begin;                                                        \    type* end;                                                          \    type* capacity;                                                     \};                                                                      \									\/* * User _have_ to call the constructor before doing anything with the * vector. */									\inline void vector_##type##_ctor(vector_##type* v)			\{									\  v->begin = 0;								\  v->end = 0;								\  v->capacity = 0;							\}									\									\/*  * If user stores pointers in the vector he has to make sure they are * deleted before calling the destructor. vector will not delete the * contens of itself - only the container (much like c++-stl) */									\inline void vector_##type##_dtor(vector_##type* v)			\{ free(v->begin); }							\									\/* Return the size of the vector as integer */				\inline int vector_##type##_size(const vector_##type* v)			\{ return v->end - v->begin; }						\									\/* Return the current capacity of the vector */				\inline int vector_##type##_capacity(const vector_##type* v)		\{ return v->capacity - v->begin; }					\									\/* Return 0 if vector has at least one element in it */			\inline int vector_##type##_empty(const vector_##type* v)		\{ return v->begin == v->end; }						\									\/* * Reserves enough space for the vector to hold new_capacity items. If * the vector had already enough space, nothing is done. This call can * made any pointer to members invalid. */									\inline void vector_##type##_reserve(vector_##type* v, int new_capacity) \{									\  type* new_place;							\  int old_capacity = vector_##type##_capacity(v);			\  int old_size = vector_##type##_size(v);				\  if (new_capacity > old_capacity) {					\      new_place = 							\	(type*)malloc(sizeof(type)*new_capacity);			\      if (old_size > 0)							\	memcpy(new_place, v->begin, sizeof(type)*old_size);		\      free(v->begin);							\      v->begin = new_place;						\      v->end = new_place+old_size; /* size does not change */		\      v->capacity = new_place+new_capacity;				\  }									\}      									\									\/* * Resizes the vector so that his new size become "new_size". if it was * smaller before, new memory will be allocated (and zeroed), if it was * larger, the last positions are removed (but not free()''d!). If the * size is euqal to new_size, nothing happens. */									\inline void vector_##type##_resize(vector_##type* v, int new_size)	\{									\  int old_size = vector_##type##_size(v);				\  vector_##type##_reserve(v,new_size);					\  if (old_size < new_size)						\    memset(v->begin + old_size, 0,					\	sizeof(type)*(new_size - old_size));				\  v->end = v->begin + new_size;						\}									\									\/*  * Return a pointer to the item at "index". Does range check  * (via assertion).  */									\inline type* vector_##type##_at(const vector_##type* v, int index)	\{									\  assert (index >= 0 && index < vector_##type##_size(v));		\  return &(v->begin[index]);						\}									\									\/* Return an pointer to the first element (or end() if empty) */	\inline type* vector_##type##_begin(const vector_##type* v)		\{ return v->begin; }							\									\/* Return an iterator to the place after the last element in list */	\inline type* vector_##type##_end(const vector_##type* v)		\{ return v->end; }							\									\/* * Inserts the data on back of the vector. If new memory has to be * allocated, it will be (all pointers to elements of the list looses * validity). */									\inline void vector_##type##_push_back(vector_##type* v, type data)	\{									\  if (v->end == v->capacity)						\    vector_##type##_reserve(v,(vector_##type##_capacity(v) == 0)?	\	1:2*vector_##type##_capacity(v));				\  *(v->end++) = data;							\}									\									\/* * Removes the last element from the vector. (Does not change the  * capacity) */									\inline void vector_##type##_pop_back(vector_##type* v)			\{									\  assert(!vector_##type##_empty(v));					\  v->end--;								\};#endif

/* test.c *//* * This library is provided under GPL v2.0 * See http://www.gnu.org/copyleft/gpl.html * * copyright Immanuel Scholz @2002 */#include <assert.h>#include <cvector.h>implement_vector(int)int main(void) {    int i;    vector_int v;    int* it;        /* ctor */    vector_int_ctor(&v);    /* empty and size */    assert(vector_int_empty(&v));    assert(vector_int_size(&v) == 0);    /* at, resize, capacity, size and reserve */    vector_int_resize(&v,10);    assert(!vector_int_empty(&v));    assert(vector_int_size(&v) == 10);    assert(vector_int_capacity(&v) >= 10);    for (i = 0; i < 10; ++i) {      assert(vector_int_at(&v,i) != 0); /* no NULL pointer returned */      assert(*vector_int_at(&v,i) == 0); /* initialized to 0 by resize */    }        vector_int_reserve(&v,20);    assert(vector_int_capacity(&v) >= 20);    vector_int_reserve(&v,30);    assert(vector_int_capacity(&v) >= 30);    vector_int_resize(&v,0);    assert(vector_int_empty(&v));    /* begin, end, iterator_equal */    assert( vector_int_begin(&v) == vector_int_end(&v) );    /* push_back */    for (i = 0; i < 50; ++i)      vector_int_push_back(&v,i);    /* iterator_incr, iterator_decr, iterator_deref */    i = 0;    for (it = vector_int_begin(&v); 	it != vector_int_end(&v); 	++it) {	assert(*it == i++);    }    it = vector_int_begin(&v) + 10;    assert(*it == 10);    for (i = 10; i > 0; --i) {	assert(*it == i);	--it;    }        /* pop_back */    for (i = 0; i < 50; ++i)      vector_int_pop_back(&v);    assert(vector_int_size(&v) == 0);       /* dtor */    vector_int_dtor(&v);        return 0;}

To make sense of cvector.h it helps to examine the preprocessor output. Consult the docs for your compiler regarding which switches to use for that.

Here''s a dummy source file that I used to do that with. Put this into the same directory as cvector.h and direct your compiler to generate preprocessor output for it. It won''t compile, so don''t bother trying. It''s purpose is to examine the token substitution pattern of the various macros in the header.

/* macro.c */#include "cvector.h"implement_vector(USER_DEFINED_TYPE)