Why do I override my struct? Implementing queues but it doesn'work

Question

I need to program queue structs in C for an assignment. The nodes have a pointer to the next node and the value (so far, so normal). But, as I need to use it with threads, I shall malloc all of the capacity on the heap. However, the nodes and queues are defined like this:

//Element of a queue
struct queue_node {
    // Pointer to next element in the queue
    struct queue_node* next;
    // Value/Data of the queue element
    int value;
};

// Queue data structure
    struct queue {
    // Head of the linked list
    struct queue_node* head;
    // Max capacity of the queue
    int capacity;
    // Current size of the queue. size <= capacity, always
    int size;
};

The problem I got with this, was to push elements, as I don't have any information on which is the start or the end of the allocated memory. So I decided to make the head node always the first one in the space, so I could work with the capacity And I programmed the basic functions like this:

struct queue* queue_new(int capacity){

    struct queue_node* head1 = malloc(sizeof(struct queue_node)*capacity);

    struct queue* ret = malloc(sizeof(struct queue));

    /*
    struct queue_node head2;
    head2.next = NULL;

    (*head1) = head2;
    */
    (*head1).next = NULL;

    (*ret).head = head1;
    (*ret).size = 0;
    (*ret).capacity = capacity;

    return ret;

    }



void queue_delete(struct queue* queue){
    free((*queue).head);
    free(queue);
    }

So. But, I get trouble, when I want to push something into the queue. Obviously, the first thing to do, is to fill the head. And that seems to work. But appending an element to the head node doesn't:

int queue_push_back(struct queue* queue, int value){

    if((*queue).size >= (*queue).capacity){
        return -1;
    }else if((*queue).size == 0){
        (*(*queue).head).value = value;
        (*queue).size++;
        return (*queue).size;
    } else{



        if((*(*queue).head).next == NULL){          ////((*queue).head + sizeof(struct queue_node))

            printf("Intern queue size 1: %d\n", (*queue).size);

            (*(*queue).head).next = ((*queue).head + sizeof(struct queue_node));
            printf("Error here?\n");
            (*(*(*queue).head).next).value = value;
            printf("Error here 2?\n");
            (*(*(*queue).head).next).next = NULL;
            printf("Error here 3?\n");


            printf("Intern queue size 2: %d\n", (*queue).size);
            printf("Intern queue capacity: %d\n", (*queue).capacity);

            (*queue).size++;
            return (*queue).size;

        }
}

I skipped the code for the common case, because this doesn't even works. For some reason, if I want to push a second element, it overrides my queue struct. And I have no idea why. Can someone help me and tell me, where I did something wrong?

Answer 1

You seem to be trying to mix two different approaches to the problem:

1. Maintaining the queue as an array, and

2. Maintaining the queue as a linked list.

Allocating space for the full complement of nodes in one block, keeping the queue head at the beginning of the block, and indeed having a fixed queue capacity in the first place, are all characteristic of array-like use. On the other hand, having element node structures with 'next' pointers is the form of a linked list.

If you manage the queue as an array, then the next pointers are redundant, and indeed they are constricting if you actually use them. Instead, you can always identify and navigate to a node by means of the pointer to the start of the block of nodes and a node index: my_queue_ptr->head[node_num]. You can also identify the next available node based on the queue's current size: my_queue_ptr->head[my_queue_ptr->size].

But then whenever you dequeue a node, you have to move all the other nodes -- or at least their data -- one position forward. If you move the whole nodes, then you screw up their next pointers, because the thing at each pointed-to location is different, and has different significance, from what was there before.

On the other hand, if you manage the queue as a linked list then it does not make sense to allocate all the nodes in one block. It would instead be conventional to allocate a new node for each value you enqueue, and to deallocate the node of each value that you dequeue. In that case you will modify the queue's head pointer upon enqueueing the first element and upon dequeuing any element. If you do not maintain a pointer to the current tail as well (as presently you don't), then every time you enqueue an element you'll need to walk the list to find the tail node, and append the new node there.

---

Update:

In the event that you nevertheless proceed with what you describe, the only way forward that makes sense to me is to adopt the array-based approach, and ignore altogether the linked-list aspects of the data structures. The queue_new() and queue_delete() functions you presented are reasonable for this. Your queue_push_back(), on the other hand, isn't even internally consistent, much less appropriate for the array-like approach.

Before, I go into details, however, I want to point out that your code is unnecessarily hard to read. Surely you have been introduced to the -> operator by this point; it is specifically designed to ease use of pointers to structures, and especially to easy use of chains of pointers to structures. Here is the first part of your queue_push_back() function, rewritten to use ->; the part presented is exactly equivalent to the corresponding part of your original:

int queue_push_back(struct queue* queue, int value){

    if (queue->size >= queue->capacity) {
        return -1;
    } else if (queue->size == 0) {
        queue->head->value = value;
        queue->size++;
        return queue->size;
    } else {

    // ...

}

That's much easier to read, at least for me. Now, with fewer distractions, it's easier to see that the only attribute of the head node that you set is its value. You do not set its next pointer. If you've understood my recommendation then you'll recognize that that's in fact just fine -- you'll be using indices into the array to access elements, not links, which would be at best redundant.

But now consider what you try to do when you push the next element. The very first thing is to test the value of the head node's next pointer, which you never set. Undefined behavior results. Now you could manage the links and use them (though you'd need something more sophisticated than what you now have if you want to support queues with capacity greater than 2), but as I said, my recommendation is to ignore the links altogether.

Having already verified that the queue has room for another element, you can access that element directly as queue->head[queue->size]:

    queue->head[queue->size].value = value;
    queue->size++;

And Lo, that's all there is to it. But wait, it gets better! If you look carefully, you'll see that there's very little difference between the case of the first node and the case of the others. In fact, the difference is purely syntactic; the first node (when queue->size == 0) would be equally well served by the code I've just presented; it doesn't need to be a special case at all:

int queue_push_back(struct queue* queue, int value){
    if (queue->size >= queue->capacity) {
        return -1;
    } else {
        queue->head[queue->size].value = value;
        return ++queue->size;
    }
    // That's all, folks!
}