How could I implement a vector like container by pure C?

[stereomatching]

I found some implementation by macro
with the help of macro I may write something like

#define DEFINE_LIST(type) \
  typedef struct list_node_##type { \
    struct list_node_##type *next; \
    type data; \
  }

int main()
{
  DEFINE_LIST(int);     // defines struct list_node_int
  DEFINE_LIST(double);  // defines struct list_node_double
  IMPLEMENT_LIST_INSERT(int);    // defines list_int_insert
  IMPLEMENT_LIST_INSERT(double); // defines list_double_insert

  return 0;
}

looks like c could make generic programming come true but it could be very tedious
and much more harder to maintain than template
Do you have any ideas to make it more easy to read and maintain by pure C?
Thank you very much

[Narue]

looks like c could make generic programming come true but it could be very tedious

Not to mention type unsafe, which you can assign evilness to according to your beliefs about type safety. ;)

and much more harder to maintain than template

Clearly, which is why templates were added to C++ in the first place.

Do you have any ideas to make it more easy to read and maintain by pure C?

Ideas? Sure. There are a number of ways to implement a library interface such that it's easy to use, understand, and maintain. While not perfect (is that ever the case?), here's one such library I have on hand at the moment to show you.

First is the header file:

#ifndef GUARD_VECTOR_H
#define GUARD_VECTOR_H

#include <stddef.h>

/**
 * @brief Returns the value of an item at the specified index
 * @remarks This is a convenience wrapper around vector_at() for the average use case
 */
#define VECTOR_AT(T,v,i) *((T*)vector_at((v), (i)))

/**
 * @brief Inserts a value of type T into a vector at the specified index
 * @remarks This is a convenience wrapper to support rvalues.
 *          Note that VECTOR_INSERT() cannot be used as an expression
 */
#define VECTOR_INSERT(T, v, x, i) do {        \
    T __anon_var19781111 = x;                 \
    vector_insert(v, &__anon_var19781111, i); \
} while (0)

/**
 * @brief A structure representing the vector object
 */
typedef struct vector {
    void   *base;      /**< Raw memory for items */
    size_t  size;      /**< The number of inserted items */
    size_t  capacity;  /**< The number of potential items before a resize */
    size_t  item_size; /**< The number of bytes occupied by an item */
} vector;

extern vector *vector_create(size_t item_size, size_t capacity);
extern vector *vector_clone(vector *v);
extern void    vector_clear(vector *v);
extern int     vector_resize(vector *v, size_t capacity);
extern size_t  vector_size(vector *v);
extern void   *vector_at(vector *v, size_t index);
extern int     vector_insert(vector *v, void *item, size_t index);
extern int     vector_remove(vector *v, size_t index);
extern int     vector_remove_if(vector *v, int (*pred)(void *item));
extern size_t  vector_find(vector *v, void *value);
extern size_t  vector_find_if(vector *v, int (*pred)(void *item));

#endif

Then the implementation file:

#include <stdlib.h>
#include <string.h>
#include "vector.h"

static int auto_capacity(vector *v, size_t *new_capacity);

/**
 * @brief Creates a new vector object
 * @param[in] item_size The size of each element in bytes
 * @param[in] capacity Default number of items allocated to the vector
 * @return A pointer to the new vector object, or NULL on failure
 * @remarks If capacity is 0, an empty vector will be created
 */
extern vector *vector_create(size_t item_size, size_t capacity)
{
    vector *v = malloc(sizeof *v);
    
    if (v != NULL) {
        v->base = NULL;
        v->size = 0;
        v->capacity = capacity;
        v->item_size = item_size;
        
        if (capacity > 0) {
            /* Allocate the default capacity */
            v->base = malloc(capacity * item_size);
            
            if (v->base == NULL) {
                /* Clean up rather than leaving a zombie */
                free(v);
                v = NULL;
            }
        }
    }
    
    return v;
}

/**
 * @brief Creates an exact copy of vector object
 * @param[in] v The vector being copied
 * @return A pointer to the new vector object, or NULL on failure
 */
extern vector *vector_clone(vector *v)
{
    vector *p = vector_create(v->item_size, v->capacity);
    
    if (p != NULL) {
        /* Copy the parts that vector_create() didn't */
        memcpy(p->base, v->base, v->size * v->item_size);
        p->size = v->size;
    }
    
    return p;
}

/**
 * @brief Clears a vector object created by vector_new() to an empty state
 * @param[in] v A pointer to the vector being destroyed
 */
extern void vector_clear(vector *v)
{
    v->size = 0;
    v->capacity = 0;
    free(v->base);
}

/**
 * @brief Resizes a vector object to the specified capacity
 * @param[in] v A pointer to the vector being resized
 * @param[in] capacity The new capacity
 * @return True/non-zero if the resize succeeded, false/zero otherwise
 * @remarks 1) The new capacity may be larger or smaller
 *          2) No-op if the capacity is unchanged, with a success return
 *          3) Resizing may invalidate pointers into the vector 
 */
extern int vector_resize(vector *v, size_t capacity)
{
    if (capacity == 0)
        return 0;
        
    if (capacity != v->capacity) {
        void *temp;
            
        v->capacity = capacity;
        
        /*
            If the vector is empty, realloc() depends on v->base 
            being initialized to NULL
        */
        temp = realloc(v->base, v->capacity * v->item_size);
        
        if (temp == NULL)
            return 0;
            
        v->base = temp;
    }
    
    return 1;
}

/**
 * @brief Returns the size of the specified vector
 * @param[in] v A pointer to the vector
 * @return The number of items inserted into the vector
 */
extern size_t vector_size(vector *v)
{
    return v->size;
}

/**
 * @brief Returns the item stored at the specified index of a vector
 * @param[in] v A pointer to the vector
 * @param[in] index The index of the requested item
 * @return A generic pointer to the item
 */
extern void *vector_at(vector *v, size_t index)
{
    return &((char*)v->base)[index * v->item_size];
}

/**
 * @brief Inserts a single item in a vector at the specified index
 * @param[in] v A pointer to the vector being inserted into
 * @param[in] item A pointer to the item being appended
 * @param[in] index The index where the item will be inserted
 * @return True/non-zero if the insert succeeded, false/zero otherwise
 * @remarks 1) The vector may be resized to make room
 *          2) The item pointed to is copied by value into the vector
 *          3) The size of the vector will increase by 1 on success
 *          4) The capacity of the vector may increase by more than 1
 *          5) All items from index to v->size may be shifted to make room
 */
extern int vector_insert(vector *v, void *item, size_t index)
{
    void *src, *dst;
    
    if (index > v->size)
        return 0;
    
    if (v->size == v->capacity) {
        /* Resize to the next auto-growth amount */
        size_t new_capacity;
        
        if (!auto_capacity(v, &new_capacity) || 
            !vector_resize(v, new_capacity))
        {
            return 0;
        }
            
        v->capacity = new_capacity;
    }
    
    src = vector_at(v, index + 1);
    dst = vector_at(v, index);
    
    /* Make room for a new item */
    memmove(src, dst, (v->size - index) * v->item_size);
    
    /* Insert the new item */
    memcpy(dst, item, v->item_size);
    ++v->size;
    
    return 1;
}

/**
 * @brief Removes the specified item within the a vector
 * @param[in] v A pointer to the vector
 * @param[in] index The index of the item
 * @return True/non-zero if the value was found and removed, false/zero otherwise
 * @remarks All items following the found value may be shifted to fill in the hole
 */
extern int vector_remove(vector *v, size_t index)
{
    if (index >= v->size)
        return 0;
    else if (index == v->size - 1) {
        /* Special case: no copy when removing the last item */
        --v->size;
    }
    else {
        void *dst = vector_at(v, index);
        void *src = vector_at(v, index + 1);
        
        /* Fill in the vacated slot */
        memmove(dst, src, (v->size - index - 1) * v->item_size);
        --v->size;
    }
    
    return 1;
}

/**
 * @brief Removes the specified item within the a vector
 * @param[in] v A pointer to the vector
 * @param[in] pred A predicate for determining the first matching item
 * @return True/non-zero if the value was found and removed, false/zero otherwise
 * @remarks All items following the found value may be shifted to fill in the hole
 */
extern int vector_remove_if(vector *v, int (*pred)(void *item))
{
    size_t index = vector_find_if(v, pred);
    
    if (index != -1)
        return vector_remove(v, index);
        
    return 0;
}

/**
 * @brief Searches for the specified value within the a vector
 * @param[in] v A pointer to the vector
 * @param[in] item A pointer to the value being searched for
 * @return The index of the found value, or (size_t)-1 if not found
 * @remarks A byte-by-byte comparison is used to test equality
 */
extern size_t vector_find(vector *v, void *value)
{
    size_t i;
    
    for (i = 0; i < v->size; i++) {
        if (memcmp(vector_at(v, i), value, v->item_size) == 0)
            return i;
    }
    
    return -1;
}

/**
 * @brief Searches for the specified value within the a vector
 * @param[in] v A pointer to the vector
 * @param[in] pred A predicate for determining the first matching item
 * @return The index of the found value, or (size_t)-1 if not found
 */
extern size_t vector_find_if(vector *v, int (*pred)(void *item))
{
    size_t i;
    
    for (i = 0; i < v->size; i++) {
        if (pred(vector_at(v, i)))
            return i;
    }
    
    return -1;
}

/**
 * @brief Calculates the auto-growth of a vector
 * @param[in] v A pointer to the vector
 * @param[out] new_capacity The calculated new capacity
 * @return True/non-zero if the vector can grow, false/zero otherwise
 */
static int auto_capacity(vector *v, size_t *new_capacity)
{
    if (v->capacity == -1)
        return 0;
    else if (v->capacity == 0) {
        /* Default to something reasonable for an empty vector */
        *new_capacity = 4;
    }
    else {
        /* Try to grow by 50% of the current capacity */
        *new_capacity = v->capacity * 1.5;
        
        if (*new_capacity < v->capacity) {
            /* Max out the capacity if 50% growth overflows (wraps) */
            *new_capacity = -1;
        }
    }
    
    return 1;
}

And finally a sample usage:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "vector.h"

void display(vector *v)
{
    size_t i;
    
    for (i = 0; i < vector_size(v); i++)
        printf("%-4d", VECTOR_AT(int, v, i));
        
    puts("");
}

int cmp(const void *a, const void *b)
{
    const int *ia = a;
    const int *ib = b;
    
    if (*ia < *ib)
        return -1;
    else if (*ia > *ib)
        return +1;
        
    return 0;
}

int main(void)
{
    vector *v = vector_create(sizeof(int), 0);
    int i;
    
    srand((unsigned)time(0));
    
    for (i = 0; i < 15; i++)
        VECTOR_INSERT(int, v, rand() % 100, v->size);
    
    display(v);
    qsort(v->base, v->size, v->item_size, cmp);
    display(v);
    
    vector_clear(v); /* "Destructor" */

    return 0;
}

[stereomatching]

Thanks a lot, your example is a big help for me.
I would try my best to generate some generic codes by c
since there are no C++ could be used

ps : my boss believe that the code developed by C++ would be inferior
than C if you want to develop embedded program.
No matter what, the boss is the boss.

[Narue]

I would try my best to generate some generic codes by c

Be sure to first ask yourself why you want it to be generic. A lot of the time genericity isn't needed in C, and only complicates things.

ps : my boss believe that the code developed by C++ would be inferior than C if you want to develop embedded program.

Only if there's not a good C++ implementation for the target platform. C++ is actually well suited to embedded development, but acceptance was hindered by crappy compilers. Things have improved drastically in the last decade or so, and C++ is now quite competitive with C.

No matter what, the boss is the boss.

Indeed.

[stereomatching]

Be sure to first ask yourself why you want it to be generic. A lot of the time genericity isn't needed in C, and only complicates things.

I need some generic containers and algorithms(maybe the best way is finding some
open source and free resource).
I seldom try to implement generic programming by pure C
This would be a good challenge for me(could have some fun)
If generic programming would complicates things in C, I would give up

[alwaysLearning0]

Hi,

Narue's example doesn't have polymorphic/virtual methods.
If you want to develop any robust C project, you need to use struct in such a way that you can write generic codes.

Here is an example using the vector(as we are talking about vector)
I wrote it hurriedly and haven't been writing any C code for a long time, so it can be improved a lot. But I hope it conveys the basic example of how to use C to develop polymorphic and generic object.

In C you can do this using function pointer.
I have written a vector struct which also holds the relative function pointers.

First lets have a look at the main

/*main.c*/
#include "vector.h"
void GenericDisplay(vector *v){
	v->display(v);
}

void GenericFree(vector **v){
	free((*v)->data);
	free(*v);
	*v = NULL;
}

int main(void) {

	vector *intV = createIntgerVector(10);
	int i;


	for(i = 0; i < 10; i++){
		*(int *)(intV->at(intV,i)) = i; /*Initialization, I know it looks dirty. improve it :)*/
	}

	vector *doubleV = createDoubleVector(10);
	for(i = 0; i < 10; i++){
		*(double *)(doubleV->at(doubleV,i)) = i; /*Initialization, I know it looks dirty. improve it :)*/
	}


	GenericDisplay(intV);
	GenericDisplay(doubleV);

	GenericFree(&intV);
	GenericFree(&doubleV);

	return EXIT_SUCCESS;
}

It will print:

Int vector
0 1 2 3 4 5 6 7 8 9
Double vector
0.00 1.00 2.00 3.00 4.00 5.00 6.00 7.00 8.00 9.00

Now lets have a look at the vector.h

/*vector.h*/

#include <stdio.h>
#include <stdlib.h>

struct _vector;
typedef struct _vector vector;
typedef void *(*vector_method)(vector *v);
typedef void *(*vector_method_value)(vector *v,int index);

struct _vector{
	void *data;
	int size;
	vector_method display; //vector specific methods.
	vector_method reset;
	vector_method_value at;
};


void *display_int(vector *v){
	int size = v->size;
	int i;
	int *array = (int *)v->data;
	printf("Int vector \n");
	for(i=0; i < size; i++)
		printf("%d ", array[i]);

	printf("\n");
	return v;
}

void *reset_int(vector *v){
	int size = v->size;
	int i;
	int *array = (int *)v->data;

	for(i=0; i < size; i++)
		array[i] = 0;
	return v;
}

void *at_int(vector *v,int index){
	int *array = (int *)v->data;
	return array+index;
}

vector *createIntgerVector(int size){
	int i;
	vector *v = (vector *)malloc(sizeof(vector));
	v->size = size;
	v->data = (int *) malloc(sizeof(int) * size);
	v->display = display_int;
	v->reset = reset_int;
	v->at = at_int;
	return v;
}


void *display_double(vector *v){
	int size = v->size;
	int i;
	double *array = (double *)v->data;

	printf("Double vector \n");

	for(i=0; i < size; i++)
		printf("%.2lf ", array[i]);
	printf("\n");
	return v;
}

void *reset_double(vector *v){
	int size = v->size;
	int i;
	double *array = (double *)v->data;

	for(i=0; i < size; i++)
		array[i] = 0;
	return v;
}

void *at_double(vector *v,int index){
	double *array = (double *)v->data;
	return array+index;
}

vector *createDoubleVector(int size){
	int i;
	vector *v = (vector *)malloc(sizeof(vector));
	v->size = size;
	v->data = (double *) malloc(sizeof(double) * size);
	v->display = display_double;
	v->reset = reset_double;
	v->at = at_double;
	return v;
}

I hope it helps to understand how you can use C to write C++ like objects.
Actually any big projects (what ever i have seen so far) use this kind of struct.

Have fun.

[Narue]

Narue's example doesn't have polymorphic/virtual methods.

That's intentional. I have yet to see an implementation of proper polymorphism in C that isn't hideous. My example does indeed have a serious issue, but it's not lack of polymorphic/virtual methods. ;)

If you want to develop any robust C project, you need to use struct in such a way that you can write generic codes.

I beg to differ. Any robust project, regardless of language, benefits from simplicity. Shoehorning complexity in for the sake of being object oriented has historically proven to be a bad idea.

But I hope it conveys the basic example of how to use C to develop polymorphic and generic object.

The problem here being that the vector library itself handles the different types. This requires a lot of work on your part as the library author, but also pushes a lot of work onto the user of the library if they want to store user-defined types. A better approach is to require that the user of the library provide a few basic functions such as comparing two items, copying an item, and destroying an item. Then the library uses those in a generic way with pointers to void[1].

Using the "method" approach of storing pointers to functions in the object itself is a pointless waste of memory as the cost of each object doesn't justify the obj->method() syntax since you don't get the benefit of an implicit this argument as you would in C++. The object being acted upon still needs to be passed as an explicit argument (which you can hide through a macro, though preprocessor usage in general should be limited for maintainability purposes).

"Methods" in C should be reserved for behaviors that truly need to be object-specific, such as compare, copy, and destruction in otherwise generic algorithms, as described above.

I hope it helps to understand how you can use C to write C++ like objects.

While making C more like C++ is an enlightening exercise, you'd do well to consider that C doesn't make a good C++. If you want C++, use C++. Otherwise, use C properly instead of trying to turn it into an ugly and difficult to use C++.

[1] For examples of this approach, you can see the libraries on my website.

[nezachem]

Ideas? Sure. There are a number of ways to implement a library interface such that it's easy to use, understand, and maintain. While not perfect (is that ever the case?), here's one such library I have on hand at the moment to show you.

Questions and nitpicking:

1. What is the significance of __anon_var_19781111 identifier (I understand a need for a temporary - I am just curious about the choice of a name)?
2. Looks like vector_at() shall test the index the same way other functions do.
3. vector_remove() special cases a removal from the end. Are there memmove implementations which fail on size 0?
4. Probably most important. Removal an item gives a user no chance to act upon an item being removed. Did you consider adding a

vector_remove_with(vector * v, size_t index, int (*cleanup_action)(void * item))

interface?

[Narue]

1. What is the significance of __anon_var_19781111 identifier (I understand a need for a temporary - I am just curious about the choice of a name)?

Just something obviously intended to be unique. The double underscores are technically stomping on the implementation's name space, but since this isn't a production library, I didn't worry about it. The number is my birthday: November 11th, 1978.

2. Looks like vector_at() shall test the index the same way other functions do.

A design decision. Like arrays or C++'s operator[] on std::vector, the index is unchecked. Presumably the client code would check it explicitly if it's not trustworthy.

3. vector_remove() special cases a removal from the end. Are there memmove implementations which fail on size 0?

The first case handles situations where size is 0, so execution shouldn't get to memmove() there. All of the edge cases should be covered, unless my weekend muddled mind just isn't seeing something. ;)

4. Probably most important. Removal an item gives a user no chance to act upon an item being removed. Did you consider adding a

vector_remove_with(vector * v, size_t index, int (*cleanup_action)(void * item))

interface?

I'm not convinced that the library should provide this feature. What's wrong with cleanup_action(vector_at(v, i)) before removal? Further, if that's too verbose, what's wrong with the client defining vector_remove_with() if needed?

[nezachem]

Just something obviously intended to be unique. The double underscores are technically stomping on the implementation's name space, but since this isn't a production library, I didn't worry about it. The number is my birthday: November 11th, 1978.

Correct me if I am wrong, but it is scoped in the do-while clause, and therefore unique, regardless of the actual name.

A design decision. Like arrays or C++'s operator[] on std::vector, the index is unchecked. Presumably the client code would check it explicitly if it's not trustworthy.

Still... vector_remove() and vector_insert() do validate indices. vector_at() not validating them looks inconsistent.

The first case handles situations where size is 0, so execution shouldn't get to memmove() there. All of the edge cases should be covered, unless my weekend muddled mind just isn't seeing something. ;)

Again, there's an inconsistency. vector_insert() shouldn't go into a memmove when appending (that is, index == v->size ). OTOH, I don't think that the extra logic is justified at all (unless, as I said, it works around a hypothetical bug in memmove).

I'm not convinced that the library should provide this feature. What's wrong with cleanup_action(vector_at(v, i)) before removal? Further, if that's too verbose, what's wrong with the client defining vector_remove_with() if needed?

I suspect it kills the purpose of the library, especially considering vector_remove_if_with() .

[Narue]

Correct me if I am wrong, but it is scoped in the do-while clause, and therefore unique, regardless of the actual name.

Nope, you're absolutely correct. It's more of a readability thing.

Still... vector_remove() and vector_insert() do validate indices. vector_at() not validating them looks inconsistent.

True, though the average use case of this library has vector_at() being called vastly more often than vector_insert() or vector_remove(). I decided that the optimization was worth more than consistency. Originally the bounds check was there, so in this case I can definitely say it was a design decision.

Again, there's an inconsistency. vector_insert() shouldn't go into a memmove when appending (that is, index == v->size ).

Oh, I see where you were going with that now. That's a good point, I have no defense beyond this not being a serious library (hoping you'll buy that excuse). :)

I suspect it kills the purpose of the library, especially considering vector_remove_if_with() .

Also a good point, though I'd lean more toward excluding vector_remove_if() than let the smell propagate into an awkward interface.

[nezachem]

(hoping you'll buy that excuse). :)

All points well taken.

though I'd lean more toward excluding vector_remove_if() than let the smell propagate into an awkward interface.

Now it begins to sound interesting. Why do you think it is awkward (no I am not an analyst; I am genuinely curious)? Just look at libbfd. That is awkward.

PS: I didn't even started on map() and fold().

[alwaysLearning0]

Hi,

I was just trying to show how type specific methods can be passed to generic codes in C.

Using the "method" approach of storing pointers to functions in the object itself is a pointless waste of memory as the cost of each object doesn't justify the obj->method() syntax since you don't get the benefit of an implicit this argument as you would in C++.

I beg to differ on this one, I agree that we need to pass the obj to every method calls, but when ever you want to write a server which will load dynamically loaded modules, you need this approach. As server has to be generic as much as possible.

I have seen fair amount of server side open source in my relatively short career ( :) ), and each of them use this approach to load modules on basis of the C++ object like struct.

While making C more like C++ is an enlightening exercise, you'd do well to consider that C doesn't make a good C++. If you want C++, use C++. Otherwise, use C properly instead of trying to turn it into an ugly and difficult to use C++.

I 100% agree on this and thats why I don't code on C any more. :)

[Narue]

Why do you think it is awkward (no I am not an analyst; I am genuinely curious)?

remove_if_with() should extend the functionality of remove_if(), not correct a fundamental flaw. The fundamental flaw is that remove_if() doesn't give users the capability of performing cleanup on a per item basis that would be accomplished with a combination of find_if()/remove(). If remove_if() doesn't do the same thing (which was the intention), that's an awkward smell. Adding remove_if_with() doesn't fix the smell, it just works around it, which suggests that the problem is in remove_if().

I took for granted that after writing find_if(), remove_if() should be there without question. Since you brought it up, I've given it more consideration and concluded that remove_if() should either go away, or be modified to work like C++'s remove_if() algorithm where removed items are swapped to the end rather than physically removed. But because swapping to the end may be unexpected behavior that complicates use of the library, I'd probably go with cutting it.

PS: I didn't even started on map() and fold().

There's a fine line between providing enough of a base to make as many people happy as possible, and including the kitchen sink. ;)

[stereomatching]

Researching and testing both of your codes.

The codes of alwaysLearning0 have to maintain many similar codes
To solve that kind of problems I have to define a lot of macro
But if I also define a macro for struct _vector

#define VECTOR(type)\
struct _vector\
{\
	type *data;\
	size_t size;\
	vector_cmethod display;\
	vector_method reset;\
	vector_method_value at;\
};

I would not need to perform those type casting anymore
But those macros are very horrible to look at

The codes of Narue don't need to define a lot of macros
but have to deal with a lot of void*

I think the version of Narue would be easier to maintain
But the version of alwaysLearning0(with the helps of macro) maybe
would be faster since it don't need to do any type casting

Thanks to both of you.
Besides, did any rtos developed by C++?

Where could I find some useful data if I want to do some embedded development by C++?
I am not sure that C++ could be compete with C or not
Although I found out that on pc it is always a better choice than C for me
if you use it carefully.But embedded is a brain new area for me.
If I want to prove that it could be compete with C, I would need some
examples.

[nezachem]

Since you brought it up, I've given it more consideration and concluded that remove_if() should either go away, or be modified to work like C++'s remove_if() algorithm where removed items are swapped to the end rather than physically removed.

Oops. Is swapping (I thought about that possibility and discarded it as frivolous) mandated by stl? (Disclamer: I am not good in C++, I honestly do not know).

There's a fine line between providing enough of a base to make as many people happy as possible, and including the kitchen sink. ;)

Granted.

The only time in my career I needed the generic C vectors, I actually needed them for map() and his uncles. I do not think its existence is justified otherwise.