Another dynamic array implementation in C

Question

I saw quite a few posts about making a dynamic array so I tried making my own for learning purposes.

Here it is:

#ifndef VECTOR_H #define VECTOR_H #include <stdlib.h> #include <stdbool.h> #include <string.h> #ifndef VECTOR_RESERVE_SIZE #define VECTOR_RESERVE_SIZE 4 #endif //Declaration typedef struct { int size_of_each; int reserved; int used; void* data; } vector_t; bool vector_init(vector_t *, int); void vector_append(vector_t *, void *); void* vector_get(vector_t *, int ); void vector_set(vector_t *, int, void *); void vector_free(vector_t *); //Implementation bool vector_init(vector_t *p, int s) { p->size_of_each = s; p->reserved = VECTOR_RESERVE_SIZE; p->used = 0; p->data = malloc(VECTOR_RESERVE_SIZE * p->size_of_each); if (p->data != NULL) { return false; } else { return true; } } void vector_append(vector_t *p, void *d) { if (p->used == p->reserved) { p->data = realloc(p->data, VECTOR_RESERVE_SIZE); //printf("reallocated \n"); p->reserved += VECTOR_RESERVE_SIZE; } memcpy((void*)((char*)p->data + p->size_of_each * p->used), // copy to back of the vector d, p->size_of_each); p->used += 1; } void* vector_get(vector_t *p, int i) { if (!(i > p->used)) { return (void*)((char*)p->data + p->size_of_each * i); } else { return NULL; } } void vector_set(vector_t *p, int i, void *d) { if (!(i > p->used)) { memcpy((void*)((char*)p->data + p->size_of_each * i), d, p->size_of_each); } } void vector_free(vector_t *p) { free(p->data); } #endif 

Here is an example of its usage:

#include <stdio.h> #define VECTOR_RESERVE_SIZE 3 #include "vector.h" int main() { int a = 321; int b = 45; int c = 21; int d = 31; int e = 71; vector_t v; vector_init(&v, sizeof (int)); vector_append(&v, &a); vector_append(&v, &b); vector_append(&v, &c); vector_append(&v, &d); vector_append(&v, &e); printf("1st element is %d \n", *(int*)vector_get(&v, 0)); printf("2nd element is %d \n", *(int*)vector_get(&v, 1)); printf("3th element is %d \n", *(int*)vector_get(&v, 2)); printf("4th element is %d \n", *(int*)vector_get(&v, 3)); printf("5th element is %d \n\n", *(int*)vector_get(&v, 4)); vector_set(&v, 4, &a); printf("4th element after setting is %d \n\n", *(int*)vector_get(&v, 4)); //contiguous printf("size of int is: %d \n", sizeof (int)); printf("address of 1st element: %p \n", vector_get(&v, 0)); printf("address of 2nd element: %p \n", vector_get(&v, 1)); printf("address of 3rd element: %p \n", vector_get(&v, 2)); printf("address of 4th element: %p \n", vector_get(&v, 3)); printf("address of 5th element: %p \n", vector_get(&v, 4)); vector_free(&v); } 

I've written some C++ before and this was one of my first few projects in C.

I'd like to know overall how good my code is and whether I'm using good practices / conventions.

Edit:

this: p->data = realloc(p->data, VECTOR_RESERVE_SIZE);

should be this: p->data = realloc(p->data, (p->reserved + VECTOR_RSERVE_SIZE) * P->size_of_each);

Edit: Maybe it's too late but, if people are still reviewing this I would really like to know how does this approach compare to std::vector.

Answer 1

Self document

Consider users do not want to see or may not have access to the implementation and are left to declarations.

These deserve parameters names and at least a comment about what each function does and how to use. (e.g. Call vector_init() first. It overwrites all vector_t members.)

// Deserve for documentation here. bool vector_init(vector_t *, int); void vector_append(vector_t *, void *); void* vector_get(vector_t *, int ); void vector_set(vector_t *, int, void *); void vector_free(vector_t *); 

Think big

Why limit to sizes up to INT_MAX when C readily handles sizes up to SIZE_MAX. That could be billions times more.

Use size_t for array indexing and sizing.

 // int size_of_each; // int used; size_t size_of_each; size_t used; // vector_get(vector_t *, int ); vector_get(vector_t *, size_t); 

Design: Smaller empty impact

Consider an app making 100s or 1,000,000s instance of this vector (e.g. a vector of vectors). Many of them will could be empty and never used. This is no advantage in doing that first malloc() at vector_init() time and a wasted allocation for all those unused instances. Allocate when needed. IMO, vector_init() should not allocate anything - it does make then that function error free - an important attribute to an initialization function.

Design: Slow Linear growth

Rather than linearly grow the array (incurring O(n*n) re-allocation time), scale the new size by maybe doubling (or some factor).

Design: Error handling

Detect and report (re-)allocation failures.

// void vector_append(vector_t *p, void *d) bool vector_append(vector_t *p, void *d) //return true on error 

Design: range check

vector_get(vector_t *p, int i), vector_set(vector_t *p, int i, void *d) perform no range check on i. Live as dangerously as you please, yet I'd definitely, at least, include parameters check on vector_set().

Design: const

I'd expect const to show that the data state has not changed.

// void* vector_get(vector_t *p, int i) void* vector_get(const vector_t *p, int i) 

Bug: Code in header file

Code is apparently designed for different VECTOR_RESERVE_SIZE depending on which .c includes it.

Unfortunately, if 2 .c files each include this, the there will be 2 vector_init(), vector_free(), etc, creating linker conflict.

Instead, divide code into vector.h and vector.c files. I suspect though this causes trouble with the VECTOR_RESERVE_SIZE scheme. IMO, VECTOR_RESERVE_SIZE is unnecessary.

Corner bug

No need to assume vector_free() is not called again. Leave data in a diminished, but correct state.

void vector_free(vector_t *p) { free(p->data); p->data = NULL; // add p->used = 0; // add } 

else not needed

 if (!(i > p->used)) { return (void*)((char*)p->data + p->size_of_each * i); } // else { return NULL; } return NULL; 

Odds & Ends

p->size_of_each * p->used may overflow int math leading to UB. Best to ensure at least size_t math.

void * not needed:

// memcpy((void*)((char*)p->data + p->size_of_each * p->used), d, p->size_of_each); memcpy((char*)p->data + (size_t)1 * p->size_of_each * p->used, d, p->size_of_each); // return (void*)((char*)p->data + p->size_of_each * i); return (char*)p->data + (size_t)1 * p->size_of_each * i; 

New functions

int vector_apply(vector, int (*function)(void *state, void *element), void *state) ⟶ Apply the function to each element in the vector. Return early if not zero returned from function.

vector_right_size(vector) ⟶ Shrink the vector to the minimum needed size.

Answer 2

In C, as in C++, object pointers can be freely converted to void*, so quite a few casts can be removed.

It's probably convenient to store data as a char*, since that's how we use it. We should still use void* as external interface, of course.

This is a dangerous anti-pattern:

 p->data = realloc(p->data, VECTOR_RESERVE_SIZE); 

If the realloc() fails, it returns a null pointer. By overwriting p->data before we check for null, we leak the old value of p->data, which is no longer accessible. And the null-check is also missing, so subsequent access is Undefined Behaviour.

Style-wise, I think I'd find (!(i > p->used)) easier to read as (i <= p->used). And if (p->data != NULL) { return false; } else { return true; } as return !p->data;.

The example code should set a good example, and check the return value of vector_init() (and also vector_append() once you realise it needs to indicate success/failure) and react appropriately. Otherwise, you'll find you're encouraging slapdash usage.