Last active
May 14, 2020 18:41
-
-
Save Mluckydwyer/5c8d93d42df8be3089570616c1182e72 to your computer and use it in GitHub Desktop.
Auto-Scaling Vector in C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Header File | |
#ifndef VECTOR_H_ | |
#define VECTOR_H_ | |
// Vector Struct with size and allocated values | |
typedef struct vector_t{ | |
int size; | |
int allocated; | |
int increment; | |
void** data; | |
void (*printItem)(void*); | |
} vector_t; | |
vector_t* newVector(); | |
void addVectorValue(vector_t *v, void *value); | |
void removeVectorValue(vector_t *v, int index); | |
void* getVectorValue(vector_t *v, int index); | |
void setVectorValue(vector_t *v, int index, void *value); | |
void expandVector(vector_t *v); | |
void contractVector(vector_t *v); | |
vector_t* cloneVector(vector_t *v); | |
void freeVector(vector_t* v); | |
void printVector(vector_t* v); | |
#endif /* VECTOR_H_ */ | |
// C file | |
#define SIZE_INCREMENT 2 | |
#define INITIAL_SIZE 100 | |
// Allocate a new vector and return a pointer to it | |
vector_t* newVector() { | |
vector_t *vect = malloc(sizeof(vector_t)); | |
vect->size = 0; | |
vect->allocated = INITIAL_SIZE; | |
vect->increment = SIZE_INCREMENT; | |
vect->data = malloc(vect->allocated * sizeof(void*)); | |
return vect; | |
} | |
// Manually scale a vector up by the size increment | |
void expandVector(vector_t *v) { | |
v->data = realloc(v->data, (v->allocated * v->increment) * sizeof(void*)); | |
v->allocated *= v->increment; | |
} | |
// Manually contratct vector by size increment (no checks on stored values) | |
void contractVector(vector_t *v) { | |
v->data = realloc(v->data, (v->allocated - v->increment) * sizeof(void*)); | |
v->allocated -= v->increment; | |
} | |
// Add a new value to the vector appended at the end | |
void addVectorValue(vector_t *v, void *value) { | |
if (v->size == (v->allocated - 1)) expandVector(v); | |
v->data[v->size] = value; | |
v->size++; | |
} | |
// Remove a vector value at a specific index | |
void removeVectorValue(vector_t *v, int index) { | |
size_t btc = (v->size - index - 1) * sizeof(void*); | |
if (btc > 0) memcpy(&v->data[index], &v->data[index + 1], btc); | |
v->size--; | |
if (v->allocated - v->size > 0 && !((v->allocated - v->size) % v->increment)) contractVector(v); | |
} | |
// Retrive a specified vector value at a perticular index | |
void* getVectorValue(vector_t *v, int index) { | |
if (index > v->size - 1 || index < 0) printf("Vector index out of bounds: index %d of size %d\n", index, v->size); | |
return v->data[index]; | |
} | |
// Set/Overwrite a vector value at a specific index | |
void setVectorValue(vector_t *v, int index, void *value) { | |
while (v->allocated - 1 < index) expandVector(v); | |
v->data[index] = value; | |
} | |
// Shallow clone a vector (Only pointers, not data values) | |
vector_t* cloneVector(vector_t *v) { | |
vector_t* newV = newVector(); | |
newV->data = malloc(sizeof(void*) * v->allocated); | |
memcpy(newV->data, v->data, sizeof(void*) * v->allocated); | |
newV->size = v->size; | |
newV->allocated = v->allocated; | |
return newV; | |
} | |
// Free memory of data stored in vactor and the vector itself | |
void freeVector(vector_t* v) { | |
int i = 0; | |
for (i = 0; i < v->size; i++) { | |
free(getVectorValue(v, i)); | |
} | |
free(v->data); | |
free(v); | |
} | |
// Only for int stored values, can be replaced with custom print function | |
void printVector(vector_t* v) { | |
printf("["); | |
if (v->size > 100) { | |
printf("%d,...,%d] Size:% d Allocated:% d\n", *(int*) getVectorValue(v, 0), *(int*) getVectorValue(v, v->size - 1), v->size, v->allocated); | |
return; | |
} | |
for(int i = 0; i < v->size; i++) { | |
if (i == v->size - 1) printf("%d] Size:% d Allocated:% d\n", *(int*) getVectorValue(v, i), v->size, v->allocated); | |
else printf("%d, ", *(int*) getVectorValue(v, i)); | |
} | |
fflush(stdout); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment