Edit: Partially solved. I switched the NULL check to be first in the while loop check as suggested by the first answer, however I am still unable to access any element of the queue except the first one. I can access data->head, but I cannot access data->head->next unless I specifically create a node struct that points to data->head->next. If I specifically create that node though (let's call it temp), then temp->next is also inaccessible. Basically the ->next functionality is completely lost when I pass my queue to this function and I have no idea why.
I'm working on a school project for Uni in which we build a modified mergesort (edit: one commenter noted this is a form of TimSort), where instead of the normal mergesort algorithm it divides the dataset into chunks of already sorted data, and then recombines them to theoretically reduce runtime.
As an example with the set
3 4 5 2 9 4 3 2
would be split into
[3 4 5] [2 9] [4 3 2]
and then merged back together in sorted order. Our particular implementation has to be done with linked lists, queues, and stacks.
Here is my linked list definition and my queue definition:
typedef struct node_t
{
int value;
struct node_t * next;
} node_t;
typedef struct queue_t
{
node_t *head, *tail;
} queue_t;
The code I am having trouble with is in the function that identifies "runs", or areas of the data where the data is already sorted. It takes a queue as input, iterates through and identifies if the first node is less than or greater than the next node. It then chooses which loop to run and dequeues each value into a new queue, which will then be returned as a "run", which is a subset of sorted data.
For some reason whenever I try to use data->head->next or data->head->next->value it throws a segmentation fault, even though I know that the node exists and the value exists. I've been running my program through gdb to find the error points, I'm on windows and I can't use valgrind.
Here is the code for the function I am having trouble with:
queue_t * extract_next_run(queue_t * data)
{
queue_t * queue = queue_create();
int ascend = 0;
//when there is only one value in the list
if(data->head->next = NULL)
{
queue_enqueue(queue, queue_dequeue(data));
return queue;
}
//ascending run *CRASHES ON THIS WHILE LOOP*
while(data->head->value <= data->head->next->value && data->head->next != NULL)
{
queue_enqueue(queue, queue_dequeue(data));
//not sure if this improves runtime over just "ascend = 1" every iteration
if(ascend != 1)
ascend = 1;
}
//descending run
while(data->head->value > data->head->next->value && data->head->next != NULL)
{
queue_enqueue(queue, queue_dequeue(data));
}
if(ascend == 0)
queue_reverse(queue);
queue->tail->next = NULL;
return queue;
}
Here's what makes it hard for me to understand:
//things I have tested in this function
printf("%d", data->head->value); // works fine
printf("%d", data->head->next->value); // segmentation fault
data->head = data->head->next; //segmentation fault
if(data->head->next == NULL) //works fine
node_t * temp = data->head->next; // works fine
printf("%d", temp->value); // works fine
temp = temp->next; //segmentation fault
The other thing that bugs me is I am able to use queue->head = queue->head->next in other functions and it works fine, and I can use node = node->next and it works fine, so I really have no idea what the problem is. I know the functions called in this function work, but I am happy to provide the code for them. Here are there declarations, I can provide all my code if needed (didn't want to make this question too terribly long):
// mallocs a queue and sets its head and tail to NULL
queue_t * queue_create();
// takes a value and adds it to the end of the queue
void queue_enqueue(queue_t * queue, int data);
// removes the first node of the queue and returns its value
int queue_dequeue(queue_t * queue);
// takes a queue, reads it into a stack,
// then uses stack_pop to return values in reverse order
void queue_reverse(queue_t * queue);
Any help would be greatly appreciated, I've been trying to figure out what the issue is but I have had no success thus far. Thanks in advance!
You've narrowed down the problem to this while loop:
while(data->head->value <= data->head->next->value && data->head->next != NULL) {
In fact, you seem to be fingering the loop control expression. Consider that expression then: why does it include a test for data->head->next != NULL?
Consider what happens when that part of the condition is false -- that is, when data->head->next == NULL is true. The program does not (ever) evaluate that condition before first evaluating the left-hand operand of the &&, which includes evaluating data->head->next->value, and that produces undefined behavior when data->head->next is null. You might as well not have the null check at all, and indeed, some compilers might optimize it away.
For the null check to be effective, it must be evaluated before any of the evaluations it serves to protect.