7
\$\begingroup\$

My previous implementation: My queue implementation (in C)

I rewrote the queue following @vnp's suggestions. Here is the second version of it: Any suggestions or tips are appreciated :) (even tips about spacing/naming code)

(The client must malloc() the data needed to be inserted into the queue, and must provide dtor() while destroying the queue)

#include <stdlib.h>
/* malloc(), EXIT_SUCCESS */
#include <stdio.h>
/* fprintf(), printf() */
#include <stddef.h>
/* size_t */
#include <assert.h>
/* assert() */

struct Queue_node {
    struct Queue_node *next;
    void *data;
};

struct Queue {
    struct Queue_node *front;
    struct Queue_node *back;

    size_t size;
};

struct Queue* create_queue(void) {

    struct Queue *created_queue = malloc(sizeof(*created_queue));

    if (created_queue == NULL) { // if malloc() failed
        return NULL;
    }

    created_queue->front = NULL;
    created_queue->back = NULL;
    created_queue->size = 0; // an empty queue

    return created_queue;
}

struct Queue* destroy_queue(struct Queue *input_queue, void (*data_dtor)(void*)) { // (pointer arg) to force l-value

    while (input_queue->front != NULL) {

        struct Queue_node *deleted_node = input_queue->front;
        input_queue->front = input_queue->front->next;

        if (data_dtor != NULL) {
            data_dtor(deleted_node->data);
        }
        free(deleted_node);
    }
    free(input_queue);
}

void queue_push(struct Queue *input_queue, void *input_data) {

    struct Queue_node *input_node = malloc(sizeof(*input_node));
    if (input_node == NULL) {
        fprintf(stderr, "malloc() failed in queue_push()\n");
    }
    input_node->next = NULL;
    input_node->data = input_data;

    if (input_queue->front == NULL) { // first insert
        assert(input_queue->back == NULL);
        assert(input_queue->size == 0);
        input_queue->front = input_node;
    }
    else {
        assert(input_queue->back != NULL);
        assert(input_queue->size > 0);
        input_queue->back->next = input_node;
    }
    input_queue->back = input_node;

    ++input_queue->size;
}

void* queue_pop(struct Queue *input_queue) {

    if (input_queue->front == NULL) {
        assert(input_queue->back == NULL);
        assert(input_queue->size == 0);
        return NULL;
    }

    assert(input_queue->front != NULL);
    assert(input_queue->back != NULL);
    assert(input_queue->size > 0);

    --input_queue->size;

    struct Queue_node *deleted_node = input_queue->front;
    input_queue->front = input_queue->front->next;

    void *return_data = deleted_node->data;
    free(deleted_node);

    return return_data;
}

/*---- dtor written by client -----*/

void dtor(void *data) {
    printf("DTOR: %i destroyed\n", *((int*)data));
    free(data);
}

/*---------------------------------*/

int main() {

    struct Queue *my_queue = create_queue();
    if (my_queue == NULL) {
        fprintf(stderr, "malloc() failed in create_queue()\n");
    }
    // ^ creates queue

    for (int i = 0; i < 10; ++i) {

        int *my_node = malloc(sizeof(int));
        *my_node = i;
        queue_push(my_queue, my_node);
    }
    // ^ appends 10 nodes

    for (int i = 0; i < 8; ++i) {

        int *my_data = queue_pop(my_queue);
        printf("POP: %i popped\n", *my_data);
        free(my_data);
    }
    // ^ pops and displays 8 nodes

    destroy_queue(my_queue, dtor);
    // ^ destroys the queue

    return EXIT_SUCCESS;
}

It gives the output:

POP: 0 popped
POP: 1 popped
POP: 2 popped
POP: 3 popped
POP: 4 popped
POP: 5 popped
POP: 6 popped
POP: 7 popped
DTOR: 8 destroyed
DTOR: 9 destroyed

Any suggestions or tips are appreciated :)

(even tips about spacing/naming code)

Edit: There is a mistake in the code. Return type of destroy_queue must be void and not struct Queue. Also in the queue_pop function, we need to set back to NULL when front is NULL. Otherwise trying to pop an empty queue causes assert.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Please do not update the code in your question after receiving answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Mast
    Oct 12, 2020 at 15:40
  • \$\begingroup\$ The edit was necessary. It added a comment and fixed the return type of a function. It did not otherwise change the code. \$\endgroup\$ Oct 12, 2020 at 17:35
  • 2
    \$\begingroup\$ I know that you might not agree with it but I rolled back your last edit. In addition to the meta that Mast referenced, please see the section What should I not do? on The Help Center page: What should I do when someone answers my question? for more information. Protip: you can post a new version of the code and likely earn more reputation that way... \$\endgroup\$ Oct 12, 2020 at 18:23
  • \$\begingroup\$ Ok. I added a sentence at the end instead of editing the code. My bad, thanks. \$\endgroup\$ Oct 12, 2020 at 18:40

1 Answer 1

2
\$\begingroup\$

One thing that I would do different is create a queue_alloc_item so you can decide to use malloc or another memory manager in the future.

You have:

int *my_node = malloc(sizeof(int));

for ints which always uses malloc. When there are clients using this already and you find a better way to replace the memory manager for small objects you can't change this anymore

\$\endgroup\$
4
  • \$\begingroup\$ Thanks a lot for replying! I did not understand what you said about queue_alloc_item, can you give a small example? Do you mean queue_alloc_item is a function which allocates *data (to be passed into the queue)? \$\endgroup\$ Oct 12, 2020 at 7:23
  • 1
    \$\begingroup\$ edited changes in \$\endgroup\$ Oct 12, 2020 at 9:01
  • \$\begingroup\$ Do you mean have something like this: int *my_node = queue_alloc_item(value_of_node); queue_push(my_queue, my_node); where queue_alloc_item() is written by the person who wants to use the queue? If so, thanks, noted. :) do you have any other tips? ^_^ \$\endgroup\$ Oct 12, 2020 at 11:19
  • 2
    \$\begingroup\$ -1 The queue implementation leaves the memory management of data associated with nodes up to users of the queue while hiding the internal memory management for the queue. In this model, there is no added value to queue_alloc_item unless users of the queue would want to participate in the queue's memory manager. \$\endgroup\$
    – Eric
    Oct 12, 2020 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.