linked-list queue, endless loop

Question

I use nested structure to define the linked-list queue:

queue.h:

#define QUEUE_MAX_SIZE 4096

struct QUEUE_NODE {
  char *string;
  struct QUEUE_NODE *next;
}queue_node;

struct COMMON_QUEUE {
  struct QUEUE_NODE *q_node;
}common_queue;

=================================

queue.c:

/* here I define the operations */
struct COMMON_QUEUE *C_init_queue() {
  struct QUEUE_NODE *head;
  head = malloc(sizeof(struct QUEUE_NODE));
  if (head==NULL) {
    fprintf(stderr, "Insufficient memory!!!");
    return NULL;
  }
  struct COMMON_QUEUE *new_queue;
  new_queue = malloc(sizeof(struct COMMON_QUEUE));
  if (new_queue==NULL) {
    fprintf(stderr, "Insufficient memory!!!");
    return NULL;
  }
  head->next = NULL;
  head->string = NULL;

  new_queue->q_node = head;

  return new_queue;
}

int C_get_queue_length(struct COMMON_QUEUE *q) {
  int count;
  count = 0;

  while (q->q_node->next!=NULL) {
    count += 1;
    q->q_node = q->q_node->next;
  }

  return count;
}

int C_enqueue(struct COMMON_QUEUE *q, char *in) {
  if (C_get_queue_length(q)>=QUEUE_MAX_SIZE) {
    fprintf(stderr, "Linked queue is full!!!");
    return ERROR;
  }
  struct QUEUE_NODE *new_node;
  new_node = malloc(sizeof(struct QUEUE_NODE));
  if (new_node==NULL) {
    return ERROR;
  }
  new_node->next = NULL;
  new_node->string = NULL;

  while (q->q_node->next!=NULL) {
    q->q_node = q->q_node->next;
  }
  new_node->next = q->q_node->next;
  q->q_node->next = q->q_node;
  new_node->string = in;

  return OK;
  }

but when I use it in the main program, then it jumps into a endless loop, after backtracing, and I knew the problem is at:

while (q->q_node->next!=NULL) {
    count += 1;
    q->q_node = q->q_node->next;
}

but it seems correct, but I may make some mistake on my initialization of the two nested struct!

P.S. the I did not list the "free()".

Answer 1

This loop modifies the list while it traverses it. Specifically, it replaces q->q_node with q->q_node->next, which if nothing else will discard your entire loop.

while (q->q_node->next!=NULL) {
    count += 1;
    q->q_node = q->q_node->next;
}

If you want to correctly traverse the list, you need to declare a separate pointer that you use for traversal. Something like this:

int C_get_queue_length(struct COMMON_QUEUE *q) {
    int count;
    struct COMMON_QUEUE *p = q->q_node;
    count = 0;

    while (p->next != NULL) {
        count += 1;
        p = p->next;
    }

    return count;
}

The pointer p will step along the list without modifying the q_node pointers along the way.

You have a similar error in C_enqueue. You really want to use a separate pointer to walk the list, and not assign q->q_node during traversal. You can fix your C_enqueue similarly:

p = q->q_node;
while (p->next != NULL) {
    p = p->next;
}
p->next = new_node;     /* append the new node after where the list traversal stopped */
new_node->next = NULL;  /* always NULL, because you always insert at the end */

Answer 2

One problem with your code is that your iterations through the queue are destructive: rather than using a temporary variable to iterate your linked list, you perform the iteration using the q_node itself. This leads to C_get_queue_length calls effectively destroying the queue, without freeing its nodes (a memory leak).

Here is an example of how to iterate a list non-destructively, using your "get length" method:

int C_get_queue_length(struct COMMON_QUEUE *q) {
    int count;
    count = 0;
    struct QUEUE_NODE node = q->q_node;
    while (node->next != NULL) {
        count++;
        node = node->next;
    }

    return count;
}

Your decision to pre-allocate one node when creating a queue is also questionable: it appears that the head node is unused, and also excluded from the count. This makes it easier to write the code to insert and delete nodes, but the same could be done with an extra level of indirection (i.e. a pointer to a pointer).