"templates" in old-school C?

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.

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.

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!

I think you could probably use a macro to generate your class with whatever types you want, but wouldn''t using C++ be easier?

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]

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( );

_{-- Post screenshots of your projects. There''s already 134 screenshot posts.}

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

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.

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)

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.

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( );

_{-- Post screenshots of your projects. There''s already 134 screenshot posts.}

You could do something like this:

// templtype.h

// note the lack of #ifndef/#define/#endif bracket


#define TEMPLTYPELIST(x)    x##List

struct
{
  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 TEMPLTYPE

void main()
{
  intList il;
  floatList fl;
  ...
}

I think that would work.

I like pie.

You could use CFront for processing templates into C code.

---

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

But that''s less fun.

I like pie.

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( );

_{-- Post screenshots of your projects. There''s already 134 screenshot posts.}

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.

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.

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 into
seriously problems with implementing iterators generic and typesafe enough
to satisfy my standards. It seems not possible under C, so I left a small
vector-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 anywhere
you 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 the
current 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.net

Immanuel 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.net

Immanuel 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)