Home > database >  Segmentation Fault in c Hashing implementation
Segmentation Fault in c Hashing implementation

Time:07-21

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.

  • Related