I've been tasked with implementing a type safe dynamic vector structure in C; however, I seem to have a problem: Every time I use the qsort() and then try casting the variables to an int* (in both erase_value() and print_vector_int()) I get a segmentation fault.
Example input:
4
p 3
i 0 10
e 0 20
p 4
This works as intended but, as soon as I use qsort(), either the erase_value() or print_vector_int() break.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_STR_LEN 64
typedef struct Vector {
void **data;
size_t element_size;
size_t size;
size_t capacity;
} Vector;
// Allocate vector to initial capacity (block_size elements),
// Set element_size, size (to 0), capacity
void init_vector(Vector *vector, size_t block_size, size_t element_size) {
vector->data = (void **)malloc(sizeof(void *) * block_size);
vector->element_size = element_size;
vector->capacity = block_size;
vector->size = 0;
}
// If new_capacity is greater than the current capacity,
// new storage is allocated, otherwise the function does nothing.
void reserve(Vector *vector, size_t new_capacity) {
if (vector->capacity < new_capacity) {
vector->capacity = new_capacity;
vector->data = (void **)realloc(vector->data, sizeof(void *) * (vector->capacity));
}
}
// Resizes the vector to contain new_size elements.
// If the current size is greater than new_size, the container is
// reduced to its first new_size elements.
// If the current size is less than new_size,
// additional zero-initialized elements are appended
void resize(Vector *vector, size_t new_size) {
if (new_size <= vector->size) {
for (size_t i = vector->size; i > new_size; --i) {
free(vector->data[i]);
}
vector->size = new_size;
} else {
if (new_size > vector->capacity) {
vector->capacity = (vector->capacity) * 2;
vector->data = (void **)realloc(vector->data, sizeof(void *) * vector->capacity);
}
for (size_t i = vector->size; i < new_size; ++i) {
vector->data[i] = (void *)calloc(1, vector->element_size);
}
vector->size = new_size;
}
}
// Insert new element at index (0 <= index <= size) position
void insert(Vector *vector, int index, void *value) {
if (index >= vector->capacity) {
vector->capacity = vector->capacity * 2;
vector-> data = (void **)realloc(vector->data, sizeof(void *) * (vector->capacity));
}
if (index >= 0 && index <= vector->size) {
vector->data[vector->size] = (void *)malloc(vector->element_size);
for (size_t i = vector->size; i > index; --i) {
memcpy(vector->data[i], vector->data[i - 1], vector->element_size);
}
memcpy(vector->data[index], value, vector->element_size);
++(vector->size);
}
}
// Add element to the end of the vector
void push_back(Vector *vector, void *value) {
if (vector->size == 0)
insert(vector, 0, value);
else
insert(vector, vector->size, value);
}
// Remove all elements from the vector
void clear(Vector *vector) {
for (int i = (vector->size) - 1; i >= 0; --i) {
free(vector->data[i]);
}
vector->size = 0;
}
// Erase element at position index
void erase(Vector *vector, int index) {
for (size_t i = index; i < vector->size - 1; ++i) {
memcpy(vector->data[i], vector->data[i + 1], vector->element_size);
}
free(vector->data[vector->size - 1]);
--(vector->size);
}
// Erase all elements that compare equal to value from the container
void erase_value(Vector *vector, void *value, int(*cmp)(const void *, const void *)) {
for(size_t i = 0; i < vector->size; ++i) {
if (cmp(vector->data[i], value) == 0)
erase(vector, i);
}
}
// Erase all elements that satisfy the predicate from the vector
void erase_if(Vector *vector, int (*predicate)(void *)) {
for (size_t i = 0; i < vector->size; ++i) {
if (predicate(vector->data[i]))
erase(vector, i);
}
}
// Request the removal of unused capacity
void shrink_to_fit(Vector *vector) {
vector->capacity = vector->size;
vector->data = (void **)realloc(vector->data, sizeof(void *) * (vector->capacity));
}
// Print integer vector
void print_vector_int(Vector *vector) {
printf("%ld\n", vector->capacity);
for (int i = 0;i < vector->size; ++i) {
int item = *(int *)vector->data[i];
printf("%d ", item);
}
}
int int_cmp(const void *v1, const void *v2) {
const int aa = *(const int *)v1;
const int bb = *(const int *)v2;
return aa - bb;
}
int is_even(void *value) {
const int aa = *(int *)value;
return aa % 2 == 0;
}
void read_int(void *value) {
scanf("%d", (int *)value);
}
void vector_test(Vector *vector, int n, void (*read)(void *),
int (*cmp)(const void *, const void *), int (*predicate)(void *)) {
char op[2];
int index;
size_t size;
void *v = malloc(vector->element_size);
for (int i = 0; i < n; ++i) {
scanf("%s", op);
switch (op[0]) {
case 'p': // push_back
read(v);
push_back(vector, v);
break;
case 'i': // insert
scanf("%d", &index);
read(v);
insert(vector, index, v);
break;
case 'e': // erase
scanf("%d", &index);
read(v);
erase(vector, index);
erase_value(vector, v, cmp);
break;
case 'd': // erase (predicate)
erase_if(vector, predicate);
break;
case 'r': // resize
scanf("%zu", &size);
resize(vector, size);
break;
case 'c': // clear
clear(vector);
break;
case 'f': // shrink
shrink_to_fit(vector);
break;
case 's': // sort
qsort(vector->data, vector->size,
vector->element_size, cmp);
break;
default:
printf("No such operation: %s\n", op);
break;
}
}
free(v);
}
int main(void) {
int n;
Vector vector_int;
scanf("%d", &n);
init_vector(&vector_int, 4, sizeof(int));
vector_test(&vector_int, n, read_int, int_cmp, is_even);
print_vector_int(&vector_int);
free(vector_int.data);
return 0;
}
I suspect it might be a problem with the int_cmp(), since q-sorting a sorted list does not result in a seg-fault.
