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)
"I thought what I'd do was, I'd pretend I was one of those deaf-mutes." - the Laughing Man
