I am trying to write codes in C for dynamic array (vector), and it runs okay until I add another function pointer into the struct (line29: int (findEle)(vector, int) ), and initialize it (line 153: v->findEle = findEle) to point to the function implementation (line 125: int findEle(vector* v, int value)). The debugger starts returning segmentation fault every time I tried to run it. Please find the code below:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int BOOL;
#define TRUE 1
#define FALSE 0
typedef struct Vector vector;
struct Vector
{
int currCapacity;
int currSize;
int *items;
// TODO: Try to add another int field, will cause seg fault
int (*size)(vector*);
int (*capacity)(vector*);
BOOL (*is_empty)(vector*);
void *(*at)(vector*, int);
void (*push)(vector*, int);
void (*insert)(vector*, int, int);
void (*resize)(vector*, size_t);
int (*pop)(vector*);
void (*removeValue)(vector*, int);
void (*delete_ele)(vector*, int);
int (*findEle)(vector*, int);
};
// Vector Functions
int size(vector *v)
{
return v->currSize;
}
int capacity(vector *v)
{
return v->currCapacity;
}
BOOL is_empty(vector *v)
{
if(v->currSize==0){ return TRUE; }
return FALSE;
}
void *at(vector *v, int index)
{
if(index >= v->currSize){return NULL;}
return (int*)(v->items+index);
}
void push(vector *v, int item)
{
if(v->currSize == v->currCapacity)
{
v->items = (int*)realloc(v->items, sizeof(int)* (v->currCapacity * 2));
v->currCapacity = v->currCapacity * 2;
}
*(v->items+v->currSize) = item;
v->currSize++;
}
void insert(vector* v, int index, int item)
{
printf("Inserting %d at index %d\n", item, index);
if(v->currSize == v->currCapacity)
{
v->items = (int*)realloc(v->items, sizeof(int)* (v->currCapacity * 2));
printf("v->items address: %p\n", v->items);
v->currCapacity = v->currCapacity * 2;
}
int* shift_ptr = v->items+index;
memmove(v->items+index+1, v->items+index, sizeof(int)*(v->currSize-index));
*(v->items+index) = item;
v->currSize++;
}
void resize(vector* v, size_t size)
{
printf("Resizing from %d to %d\n", v->currSize, size);
v->items = (int*)realloc(v->items, sizeof(int)* size);
}
int pop(vector* v)
{
int last = *(v->items + (v->currSize-1));
v->currSize--;
if(v->currSize*4 == v->currCapacity)
{
v->resize(v, v->currCapacity/2);
}
return last;
}
void delete_ele(vector* v, int index)
{
int *curr_ptr = v->items+index;
if(v->currSize*4 == v->currCapacity)
{
v->resize(v, v->currCapacity/2);
}
memmove(curr_ptr, curr_ptr+1, sizeof(int)*(v->currSize-(index+1)));
v->currSize--;
}
void removeValue(vector *v, int value)
{
for(int i=0; i<v->currSize; i++)
{
int ptr_value = *(v->items+i);
printf("%d->%d ", i, ptr_value);
if(ptr_value==value)
{
delete_ele(v, i);
--i;
}
}
printf("\n");
}
int findEle(vector* v, int value)
{
for(int i=0; i<v->currSize; i++)
{
if(*(v->items+i)==value)
{
return i;
}
}
return -1;
}
vector *initializeVector()
{
vector *v;
v->currSize = 0;
v->currCapacity = 2;
v->items = (int*)malloc(sizeof(int) * v->currCapacity);
v->size = size;
v->capacity = capacity;
v->is_empty = is_empty;
v->at = at;
v->push = push;
v->insert = insert;
v->pop = pop;
v->removeValue = removeValue;
v->delete_ele = delete_ele;
v->findEle = findEle;
return v;
}
int main()
{
vector *v = initializeVector();
v->push(v, 8);
v->push(v, 25);
v->push(v, 25);
v->push(v, 12);
printf("element 0 :%d\n", *(int*)v->at(v, 0));
printf("element 1 :%d\n", *(int*)v->at(v, 1));
printf("element 2 :%d\n", *(int*)v->at(v, 2));
printf("element 3 :%d\n", *(int*)v->at(v, 3));
v->insert(v, 1, 50);
printf("element 0 :%d\n", *(int*)v->at(v, 0));
printf("element 1 :%d\n", *(int*)v->at(v, 1));
printf("element 2 :%d\n", *(int*)v->at(v, 2));
printf("element 3 :%d\n", *(int*)v->at(v, 3));
printf("element 4 :%d\n", *(int*)v->at(v, 4));
//printf("%d\n", v->pop(v));
printf("%d\n", v->findEle(v, 25));
v->removeValue(v, 25);
for(int i=0; i<v->currSize; i++)
{
int ptr_value = *(v->items+i);
printf("%d->%d ", i, ptr_value);
}
free(v->items);
return 0;
}
I tried to debug using gdb, it returns the below message:
Program received signal SIGSEGV, Segmentation fault.
0x0040189a in initializeVector () at Vector.c:153
153 v->findEle = findEle;
When I tried to get the address of the stated function, it showed the message below:
(gdb) x v->findEle
Cannot access memory at address 0x620000
Can someone kindly advice if I have some issues on memory allocation? Or the issue might be due to some other causes? Thanks!
>Solution :
At least in these functions
void resize(vector* v, size_t size)
{
printf("Resizing from %d to %d\n", v->currSize, size);
v->items = (int*)realloc(v->items, sizeof(int)* size);
}
int pop(vector* v)
{
int last = *(v->items + (v->currSize-1));
v->currSize--;
if(v->currSize*4 == v->currCapacity)
{
v->resize(v, v->currCapacity/2);
}
return last;
}
void delete_ele(vector* v, int index)
{
int *curr_ptr = v->items+index;
if(v->currSize*4 == v->currCapacity)
{
v->resize(v, v->currCapacity/2);
}
memmove(curr_ptr, curr_ptr+1, sizeof(int)*(v->currSize-(index+1)));
v->currSize--;
}
you do not update data members currCapacity and currSize
And in this function
vector *initializeVector()
{
vector *v;
v->currSize = 0;
v->currCapacity = 2;
v->items = (int*)malloc(sizeof(int) * v->currCapacity);
v->size = size;
v->capacity = capacity;
v->is_empty = is_empty;
v->at = at;
v->push = push;
v->insert = insert;
v->pop = pop;
v->removeValue = removeValue;
v->delete_ele = delete_ele;
v->findEle = findEle;
return v;
}
there is used the uninitialized pointer v that has an indeterminate value that results in undefined behavior.
Also you need to check the value of the parameter index in each function where it is used.