So now I am trying to implement deltaclock, and the first step I am trying to do is to make a priority queue that uses a double-linked list (I will do another deltaclock stuff later). The first element to be knocked out of the priority queue is the one at the root of the linked list (or deltaClock structure).
I push several items into the queue in my test, and after several pop operations there is one case in which it segfaults when it appears from an almost empty list.
When I comment on a line in the pop method, where I say "clock-> root-> previous = 0;", the program in the main method does not execute segfault when I exit the elements. However, the pointer to the previous node must be freed, since the previous node will no longer exist.
How can I make the new root previous pointer be empty when I perform a pop operation?
struct deltaNode{
int tics; // source
struct deltaNode* next;
struct deltaNode* previous;
};
struct deltaClock{
struct deltaNode* root;
struct deltaNode* tail;
int size;
};
void initDeltaClock(struct deltaClock **clock){
(*clock) = malloc(sizeof(struct deltaClock));
(*clock)->size = 0;
}
void push(struct deltaClock* clock, int numberOfTics){
if(clock->root == 0){
// root is empty, initialize it.
clock->root = malloc(sizeof(struct deltaNode));
clock->root->tics = numberOfTics;
clock->tail = clock->root;
}
else {
struct deltaNode* newNode = malloc(sizeof(struct deltaNode));
newNode->tics = numberOfTics;
struct deltaNode* temp = clock->root;
if(newNode->tics < temp->tics){
clock->root->previous = newNode;
newNode->next = clock->root;
clock->root = newNode;
} else {
while(newNode->tics > temp->tics){
if(temp->next == 0){
break;
}
temp = temp->next;
}
if(temp->next == 0 && newNode->tics > temp->tics){
clock->tail->next = newNode;
newNode->previous = clock->tail;
clock->tail = newNode;
}
else{
temp->previous->next = newNode;
newNode->previous = temp->previous;
newNode->next = temp;
temp->previous = newNode;
}
}
}
clock->size++;
}
int pop(struct deltaClock* clock){
struct deltaNode* temp = clock->root;
if(temp == 0){
return -1;
}
int result = temp->tics;
clock->root = clock->root->next;
clock->root->previous = 0;
free(temp);
clock->size--;
return result;
}
void printClock(struct deltaClock* clock){
struct deltaNode* iterator;
iterator = clock->root;
while(iterator != 0){
printf("\n%d",iterator->tics);
iterator = iterator->next;
}
}
int main(int argc, char* argv[]){
printf("\nHello world.");
struct deltaClock* clock;
initDeltaClock(&clock);
push(clock, 3);
push(clock, 2);
push(clock, 7);
push(clock, 33);
push(clock, 221);
push(clock, 5);
printClock(clock);
printf("\npopping %d",pop(clock));
printf("\npopping %d",pop(clock));
printf("\npopping %d",pop(clock));
printf("\npopping %d",pop(clock));
printf("\npopping %d",pop(clock));
printf("\npopping %d",pop(clock));
printf("\npopping %d",pop(clock));
printf("\npopping %d",pop(clock));
printf("\npopping %d",pop(clock));
printf("\npopping %d",pop(clock));
printf("\npopping %d",pop(clock));
printf("\npopping %d",pop(clock));
push(clock, 25);
printf("\npopping %d",pop(clock));
printf("\n");
}