Vector Implementation in C

Question

I made a somewhat simple vector implementation in C. Right now I only have around 5 features (making a vector, adding elements, removing elements, changing elements, deleting the vector). I'm proud of it but I know it needs a lot of work so I came here to see what you think I could improve. There are 3 files, main.c (tests), Arr.h (function definitions, macros and structs) and Arr.c. Here is the code for all 3 files:

Arr.h

//Arr.h #ifndef ARR_H #define ARR_H #define growCapacity(capacity) \ (capacity < 8) ? 8 : capacity*2 typedef struct{ int count; int capacity; int* Array; }Vect; void initVect(Vect* vect); Vect* constructVect(int array[], int count, int capacity); void addVect(Vect* vect, int data); void changeVect(int data, int index, Vect* vect); void removeVect(Vect* vect, int count); #endif 

Arr.c

//Arr.c #include "Arr.h" #include <stdio.h> #include <stdlib.h> #include <string.h> void* reallocate(Vect* vect, size_t oldSize, size_t newSize){ if(newSize == 0){ free(vect->Array); return NULL; } void* result = realloc(vect->Array, newSize); if(result == NULL){ printf("There is not enough memory to reallocate array. Exiting"); exit(1); } return result; } void initVect(Vect* vect){ vect->count = 0; vect->capacity = 0; vect->Array = NULL; } Vect* constructVect(int array[], int count, int capacity){ //Find a way to get the count and size of an array by using a function rather than having it as a parameter Vect* vect = (Vect*)malloc(sizeof(Vect)); vect->capacity = capacity; vect->count = count; vect->Array = (int*)malloc(capacity); memcpy(vect->Array, array, capacity); return vect; } void addVect(Vect* vect, int data){ if(vect->capacity < (vect->count*4)+1){ int oldCapacity = vect->capacity; vect->capacity = growCapacity(oldCapacity); vect->Array = (int*)reallocate(vect, oldCapacity, vect->capacity); } vect->Array[vect->count] = data; vect->count++; } void changeVect(int data, int index, Vect* vect){ if(index > vect->count){ fprintf(stderr, "ERR: element does not exist..."); exit(-1); } vect->Array[index] = data; } void removeVect(Vect* vect, int count){ vect->count -= count; //Removes amount of vectors specified in count, the data is not fully deleted but it is no longer accessible } 

main.c

#include <stdio.h> #include <stdlib.h> #include "Arr.h" int main(){ int array[] = {1, 2, 3, 4 , 5}; int count = sizeof(array)/sizeof(array[0]); int capacity = sizeof(array); Vect* vecto = constructVect(array, count, capacity); for(int i = 0; i<vecto->count; i++){ //Write elements printf("Count: %d Capacity: %d Element: %d\n", vecto->count, vecto->capacity, vecto->Array[i]); } printf("\n\n Updated after adding 2 elements\n\n"); addVect(vecto, 7); addVect(vecto, 9); for(int i = 0; i<vecto->count; i++){ //Write elements printf("Count: %d Capacity: %d Element: %d\n", vecto->count, vecto->capacity, vecto->Array[i]); } printf("\n\n Changed element\n\n"); changeVect(54, 0, vecto); for(int i = 0; i<vecto->count; i++){ //Write elements printf("Count: %d Capacity: %d Element: %d\n", vecto->count, vecto->capacity, vecto->Array[i]); } printf("\n\n Update after removing 2 elements\n\n"); removeVect(vecto, 2); for(int i = 0; i<vecto->count; i++){ printf("Count: %d Capacity: %d Element: %d\n", vecto->count, vecto->capacity, vecto->Array[i]); } return 0; } 

Answer 1

#define growCapacity(capacity) \ (capacity < 8) ? 8 : capacity*2 

I don't think this should be in the header, as it's not useful to the user of our vector. Consider moving it to the implementation file.

int count; int capacity; int* Array; 

count and capacity would be better as size_t values - especially as we use size_t arithmetic with them. Converting to int can cause problems.

void* reallocate(Vect* vect, size_t oldSize, size_t newSize){ 

This is internal to the implementation, so declare it with static linkage, so that you won't get link conflicts with any other reallocate() declared in other files.

Why do we have to pass oldSize? That information isn't needed.

void* result = realloc(vect->Array, newSize); 

It looks like we're confused about number of elements and size in chars here - we're called with the number of elements required, so we should be allocating sizeof (int) * newSize here.

if(result == NULL){ printf("There is not enough memory to reallocate array. Exiting"); exit(1); } 

It's good that you have considered what happens when allocation returns a null pointer. However, exiting the program becomes progressively less useful as program size increases, and in a library it's better to pass an error indication to the caller to decide whether to give up or to take some other action.

Also, when printing, be sure to write a complete line (ending in \n).

Vect* vect = (Vect*)malloc(sizeof(Vect)); vect->capacity = capacity; 

Oops - vect may be null, so we need to test for that before accessing vect->capacity. Also, malloc() returns void*, so there's no need to cast to Vect* like that:

Vect* vect = malloc(sizeof *vect); if (!vect) { return vect; /* caller must deal with null result */ } vect->capacity = capacity; 

vect->Array = (int*)malloc(capacity); memcpy(vect->Array, array, capacity); 

Again, no need to cast void* to other object pointer types, and we need to check whether it was successful before writing to vect->Array.

if(vect->capacity < (vect->count*4)+1){ 

Why are we multiplying by 4 here? If our new count is going to exceed the capacity, then we'll need to extend the allocation.

Finally, we're missing a function to free the vector storage. Without that, there's no way to avoid leaking memory:

184 (24 direct, 160 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2 at 0x483877F: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) by 0x109268: constructVect (269299.c:55) by 0x109440: main (269299.c:99) 

Answer 2

Good points

• Consistent and reasonable enough style.
• Includes are properly ordered: First the corresponding header, than sorted project-headers, than sorted other headers.

Comments

Obvious comments are useless:

• //Arr.h Yes, the editor shows it, even if that's scrolled off the screen. No need to belabor the point.
• //Arr.c Ditto.
• //Removes amount of vectors specified in count, the data is not fully deleted but it is no longer accessible Aside from being wrong (it should be: "Removes the number of elements specified"), this looks like the alibi-comment: "See! I did add a comment!"

If you add comments, they should either be doc-comments (meaning they are extracted by a tool to create (part of) the documentation), or they should describe your reasoning, why you do something non-obvious, not what exactly you do.

Interface

Your interface is inconsistent and some does not belong at all.

• Specifically, one constructor default-initializes a pointed-to Vect, the other copy-initializes a Vect it allocates.

• changeVect() is the only function not having the pointer to the vector first.

• The macro growCapacity() does not belong in the interface at all.

Your interface also needs much expansion:

• Anywhere non-Vect code (everything else) is called, you need direct access to the managed array. That is only possible by digging in the internals.
• You really should provide for inserting and removing elements by index too, instead only at the end. Yes, that involves moving the tail to dig / fill the hole.

Preprocessor Macros

Avoid them. const static globals or static functions are nearly always preferable.

If you actually have a good use for them (include-guards, conditional compilation, compile-time configuration, X-macros, ...), do your best to make them work as similar to a function as you can.

Thus, make sure they are exactly one fully parenthesized expression, failing that one compound-statement which just needs a terminating semicolon, and the arguments are parenthesized too.

Types

size_t is the dedicated type for size of objects, not int. The latter might be too small, or waste space, but it is certainly the wrong signedness.

Units

Are you dealing in elements (of type int) or bytes? Be consistent, especially internally.

Include-guard

Yes, your include-guard works, most of the time. There is a reason most IDEs put a long random string at the end when they generate them for you though:
Resilience against accidentally similarly named files.

Debug-aids

Consider assert()-ing easily tested preconditions which are obvious bugs.

Growth-factor

A Growth-factor of two or more virtually guarantees that the array never re-uses any memory it held any number of iterations of growth earlier.
Thus, try for a more modest growth-factor, maybe on the order of 1.6.

Your internal helper

There is just too much wrong with reallocate():

• Either it should work on a Vect directly, in which case it has to do all the bookkeeping, or it should work on raw memory, just massaging the behavior of realloc() into the form you need, leaving all the bookkeeping to the caller.
  I suggest the former.
• It should be static as nobody else should access it, even by accident.
• Passing it the old size is really useless.

Boolean logic

Non-zero is true in C. Thus, you can simplify testing against NULL and 0.

Errors

Error-output does not belong into stdout. stderr is dedicated to it.

Explicit types

Avoid sizeof(TYPE), sizeof *pointer avoids an additional and disconnected mention of some type which is hard to verify or refactor.

Casting should be minimized as it is error-prone. Specifically casting from void* to any other pointer-type is discouraged in C, as implicit conversion works.

"Do I cast the result of malloc?".

C99 features

• return 0; is implicit for main().
• Compound-literals would simplify initVect().
• Compound-literals and designated initializers would simplify constructVect().

Answer 3

Design weakness - capacity

.capacity is the byte size - arrgh! It took a while to see that.

capacity is more idiomatically the size in the same units as .count. In OP's code, capacity is in bytes, count is number of int.

• Use the same units - the number of int.

• Do not use a magic 4, use sizeof.

• Recommend to not use capacity in constructVect(), set .capacity same as .count.

Candidate constructVect() with const, re-ordered parameters for static code analysis, more error checking, handle 0 count:

Vect* constructVect(size_t count, const array[count]) { Vect* v = malloc(sizeof *v); if (v == NULL) { return NULL; } v->Array = malloc(sizeof vect->Array[0] * count); if (v->Array == NULL && count > 0) { free(v); return NULL; } v->capacity = capacity; v->count = capacity; return v; } 

Naming

ARR_H, growCapacity, Vect, initVect, constructVect, addVect, changeVect, removeVect are added when including Arr.h.

I recommend consistency based on the include file name.

Such style issues best determined by group's coding standard.

Arr or Vect

Choose one.

Leading or trailing

initVect or Vect_init or the like. (VectInit)

I recommend a common prefix.

Uniqueness

The names Arr and Vect are common - likely to collide in a large project. I'd consider something less so. Problem remains no matter what name, just trying to reduce its possibilities.

Documentation

The .h file deserves some text describing the overall usage of Vect.

Document (from a user point-of-view) the functions.

Assume users do not have access to the .c file, nor want to see it.

Example

Vect_H (or VECT_H), Vect, Vect_init, Vect_construct, Vect_add, Vect_change, Vect_remove in Vect.h.

growCapacity move to Vect.c as not needed by the public.

---

Reallocating to 0

Good use of if(newSize == 0) { free(vect->Array);. Proper return value of realloc(..., 0) is a head-ache.

Answer 4

• Consider hiding the implementation entirely by putting the struct in the implementation file.
• Be consistent and always pass the vector as the first argument.
• Consider using a namespace prefix at the front like vec_init instead of the other way around. That way the auto-complete is more helpful in IDEs:
• Instead of get/set functions, you might use a singe get function which returns a pointer to the element. That way the user can access the element as they wish.
• Provide a way to free the vector. Currently you are leaking the memory.
• Add more documentation to the header file.

Here's how I would organize the header:

// Vector.h /* * An implementation of a dynamic array that resizes as needed */ #ifndef VECTOR_H #define VECTOR_H #pragma once #include <stddef.h> // size_t typedef struct vec_impl* Vec; // Default init. No elements. Vec vec_init(); // Create a vector, copy values from the array. // Calls abort on allocation failure. Vec vec_init_with(int const* array, size_t size); // Free the memory associated with the vector and all its elements. // NOOP if the pointer is null. void vec_deinit(Vec); // Push an element to the back of the vector. // Calls abort on allocation failure. void vec_append(Vec, int value); // Get the element at the provided index. // UB if index is out of bounds int* vec_get(Vec, size_t index); // Remove the element at the back of the vector. // UB if the vector is empty void vec_pop_back(Vec); // Remove `n` elements from the back of the array. // UB if the size of the array is less than `n` void vec_pop_back_n(Vec, size_t n); // Get number of items currently in the vector size_t vec_get_size(Vec); // Get number of elements the vector can hold before // needing a reallocation. size_t vec_get_capacity(Vec); #endif // !VECTOR_H