Removing random element from linked list in C produces occasional segfault

Viewed 36

I am trying to remove a random element from a linked list. The element is selected with probability of the data of that element divided by the sum of the data in that list. Intended pseudocode is as follows

Take in a head pointer for a linked list (**lead)
Take in a pointer to the sum of the data in that linked list (*total)
Take in a value for selecting the element (threshold = total * gsl_rng_uniform())

track the sum of data observed in the linked list so far starting with the head element ( exp(logh) )
while the sum is less than the entered threshold value and while the linked list has at least one more element:
     store the current element
     set the current element equal to the next element
     add the new current element's data to the running sum

if the while loop was entered (at least two elements in the list and the element selected is not the head)
    store the next element as the previous element's next pointer
    remove the current element
otherwise
    remove the head of the list

cleanup and store the new sum of the linked list in *total

Actual code:

void search_pop (struct indiv **lead, double threshold, double *total)//, int *indivs)
{
    struct indiv *tmp = *lead, *prev = NULL;
    double logh = log(tmp->data);
    while (exp(logh) < threshold && tmp && tmp->nxt)
    {
        prev = tmp;
        tmp = tmp->nxt;
        logh = sum_logs(logh, log(tmp->data));
    }

    if (prev)
        prev->nxt = tmp->nxt;
    else
        *lead = tmp->nxt;
    free(tmp);

    if (*lead) 
        *total = sum_indivs(lead);
    else
        *total = 0.0;
}

The code above works the vast majority of the time, but about every 4 in a million executions ends up producing a segfault (Address not mapped), which makes me concerned that the function is misbehaving outside of segfault cases. The segfault is not addressed to the subfunctions sum_logs() or sum_indivs(), so I believe that the issue is separate from taking the log of some small number or total and ending up with -Inf. I thought that I sufficiently repaired the linked list traverse loop, but these segfaults keep occurring. My current suspicion is that *lead = tmp->nxt could be a subpar formatting option that behaves differently than I expect, but I can't see how.

1 Answers

You don't check if tmp is NULL before the following line:

double logh = log(tmp->data);

This is the only thing I have found.

I recommend to use address sanitizer.

Related