Linked list in C - first node data incorrect and can't figure it out

Question

I have a multithreaded C program, where one thread creates random times and numbers, and stores them in a sorted linked list, and the second thread compares the the time in the first node to the current system time and deletes the node whenever the times are equal. However, 0 0 gets added to the linked list first, and I can't find where. It's not being added in the insert function as far as I can tell. Any help would be greatly appreciated. Here is the relevant code:

#include <pthread.h> 
#include <stdio.h>
#include <stdlib.h> 
#include <unistd.h> 
#include <time.h>
#include <signal.h> 

pthread_mutex_t count_mutex;

/* Link list node */
struct node
{
    int roomNo;
    time_t time;
    struct node* next;
};

void printList(struct node *node)
{
  while(node!=NULL)
  {
    printf("%d ", node->roomNo);
    printf("%d\n ", node->time);
    node = node->next;
  }
}

/* Function to insert a node at the beginging of the linked list */
void insert(struct node** head_ref, int new_room, time_t new_time)
{
  /* allocate node */
  struct node* new_node =
  (struct node*) malloc(sizeof(struct node));

  /* put in the data  */
  new_node->roomNo  = new_room;
  new_node->time  = new_time;

  /* link the old list off the new node */
  new_node->next = (*head_ref);    

  /* move the head to point to the new node */
  (*head_ref)    = new_node;
    MergeSort(&(*head_ref));
} 


/* sorts the linked list by changing next pointers (not data) */
void MergeSort(struct node** headRef)
{
  struct node* head = *headRef;
  struct node* a;
  struct node* b;

  /* Base case -- length 0 or 1 */
  if ((head == NULL) || (head->next == NULL))
  {
     return;
  }

    /* Split head into 'a' and 'b' sublists */
  FrontBackSplit(head, &a, &b); 

  /* Recursively sort the sublists */
  MergeSort(&a);
  MergeSort(&b);

  /* answer = merge the two sorted lists together */
  *headRef = SortedMerge(a, b);
}


struct node* SortedMerge(struct node* a, struct node* b)
{
  struct node* result = NULL;

  /* Base cases */
  if (a == NULL)
    return(b);
  else if (b==NULL)
    return(a);

  /* Pick either a or b, and recur */
  if (a->time <= b->time)
  {
    result = a;
    result->next = SortedMerge(a->next, b);
  }
  else
  {
    result = b;
    result->next = SortedMerge(a, b->next);
  }
  return(result);
 }


void FrontBackSplit(struct node* source,
                     struct node** frontRef, struct node** backRef)
{
  struct node* fast;
  struct node* slow;
  if (source==NULL || source->next==NULL)
  {
    /* length < 2 cases */
    *frontRef = source;
    *backRef = NULL;
  }
  else
  {
    slow = source;
    fast = source->next;

    /* Advance 'fast' two nodes, and advance 'slow' one node */
    while (fast != NULL)
    {
       fast = fast->next;
      if (fast != NULL)
      {
        slow = slow->next;
        fast = fast->next;
      }
    }

    /* 'slow' is before the midpoint in the list, so split it in two
     at that point. */
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
  }
}

void * addThread(void *n) 
{  
  struct node *llnode = n;
  int i;
        for(i = 0; i <4; i++)
    { 
             pthread_mutex_lock(&count_mutex);
             printf("Adding node.\n");
             insert(&llnode, getRandRoom(), getRandTime());
     sleep(1);
             printf("the list is...\n");
             printList(llnode);
             pthread_mutex_unlock(&count_mutex);
    }
}

struct node* head;

int main()
{
    signal(SIGINT, ctrlc_catch);

    pthread_t addWakeup, makeWakeup;

    pthread_create(&addWakeup, NULL, addThread, (void*)&head);
    pthread_create(&makeWakeup, NULL, wakeThread, (void*)&head);

    pthread_join(addWakeup, NULL);
    pthread_join(makeWakeup, NULL);

      return 0;
}

Example output is:

Adding node.
the list is...
0 0
 4000 1323882918
 Adding node.
the list is...
 0 0
 809 1323882890
 4000 1323882918
 Adding node.
the list is...
0 0
 809 1323882890
 7617 1323882908
 4000 1323882918
 Adding node.
the list is...
0 0
 809 1323882890
 7617 1323882908
 4000 1323882918
 4426 1323882926

Answer 1

You problem is most likely due to passing address of head (i.e. ~struct node**) instead of head(i.e. struct node*) to the thread function where void * is typecast to struct node*. Change this call pthread_create(&addWakeup, NULL, addThread, (void*)&head); to pthread_create(&addWakeup, NULL, addThread, (void*)head); & next call also on similar lines. Unfortunately you were not seeing a crash in the current case. On my system I observed that initializing head to NULL was crashing the program. Similar suggestion has already been provided by @wildplasser. Try this change out and check the list printed.
Hope this helps!

Answer 2

While it may exist in code not shown, the code may need a call to pthread_mutex_init to initialize the mutex. It is possible that the contents of the variable count_mutex are initialized "by chance" to values that will actually work, but it would not be good to rely on that.

Answer 3

Your function addthread creates a local copy llnode of its argument n, and uses a pointer to llnode to call insert(). Insert can alter llnode, but that change will only affect the local copy.

You should change addThread to take an argument of type struct node**, instead of struct node*.