Trying to implement a Hash table in C. But I'm running into a segmentation fault in mu insertion process.
Node Struct Definition
//define a Nodes
typedef struct node{
int data;
struct node* nextPtr;
} node;
typedef node* nodePtr;
HashTable "methods"
//Insert values into the hash table
void insertVal(nodePtr* aNode, int val){
nodePtr temp = (nodePtr) malloc(sizeof(node));
temp->data = val;
temp->nextPtr = NULL;
//Insert the value at the hashtable
if(!(*aNode)){
(*aNode) = temp;
}
else{
//Check if the first element is greater than temp's value
//Append to the front of the value
if(val < (*aNode)->data){
temp->nextPtr = (*aNode); //set temp's next to point to head node
*aNode = temp; //reset the position of the head node
}
else if(val >= (*aNode)->data) {
//Set up the walking nodes
nodePtr prev = NULL;
nodePtr curr = *aNode;
//Walk through list until either is false:
// - val <= curr
// - curr == NULL
while((val >= curr->data) && (curr)){
//Check if the values are equal
if(val == curr->data){
//Insert them
temp->nextPtr = curr->nextPtr;
curr->nextPtr = temp;
return;
}
prev = curr;
curr = curr->nextPtr;
}
//at either condition,
prev->nextPtr = temp; //Insert inbetween the prev and curr
temp->nextPtr = curr;
}
}
}
//Delete a value from the node Array
int delete(nodePtr* aNode) {
nodePtr temp = *aNode; //Get the leading node value
(*aNode) = (*aNode)->nextPtr;//Move head pointer to next node
int ret = temp->data; //Get the value of deleted node
free(temp); //Free Space allocated to deleted node
return ret; //Return the deleted value
}
//Function to search a Node for a value
int* search(nodePtr* aNode, int val){
int* valPos = calloc(2, sizeof(int)); //(0,1) = (arrayInd, nodeInd)
memset(valPos, -1, 2); //fill the memory with -1 and return
if(!(*aNode)){
return valPos;
}
int nodePos = 0;
nodePtr curr = *aNode;
//Walk node until:
// - value found
// - node's NULL
while((val == curr->data) && (curr)){
nodePos ; //Increment the node position
curr = curr->nextPtr; //Walking the node
}
valPos[0] = val; //get the val's array position
valPos[1] = nodePos; //Get the val's node level
return valPos;
}
main.c: Hash table is an array of nodes pointers. H(x) = x % 10, and H(x) is used for indexing values
int main(){
int A[5] = {21,23,11,23,41};
//Create a chaining hash table
nodePtr* aTable = calloc(10, sizeof(nodePtr)); //Array of nodePtrs
//Insert the values into the aTable
for(int i = 0; i<5; i ){
//Declare hash function
int hasFunc = A[i];
insertVal(&aTable[hasFunc], A[i]);
}
//Search for inserted values
for(int i = 0; i<5; i ){
int hasFunc = A[i];
int *res = search(&aTable[A[i]], A[i]);
if(res[0] != -1){
printf("Value: %d found at array index: %d, and node level: %d\n", A[i], res[0], res[1]);
}
else{
printf("value not found\n");
}
}
return 0;
}
Error in GDB based debugger. And, as you can see it happens during the insertion of the final element of the array.
Program received signal SIGSEGV, Segmentation fault.
0x00005555555554b4 in insertVal (aNode=0x5555555592a8, val=41) at Chaining.c:27
27 while((val >= curr->data) && (curr)){
(gdb) Quit
(gdb)
CodePudding user response:
The condition (val >= curr->data) && (curr)
is bad because it will dereference curr
before checking if curr
is NULL
.
The condition should be (curr) && (val >= curr->data)
or (without extra parenthesis) curr && val >= curr->data
.
Also note that casting results of malloc()
family is considered as a bad practice.