6
\$\begingroup\$

Thanks to the extremely helpful comments and answers from the original post, I've improved the interface and implementation of this general-purpose queue library.

Improvements include:

  • Fixed memory leak when dequeueing items
  • Enqueue is now a constant time operation
  • Improved accident prevention by enforcing a data size when enqueueing
  • Added clear()
  • const correctness

With a little bit of tweaking, it is also possible to implement a queue that may have items with different sizes.

/*
    Author: Jared Thomas
    Date:   Friday, August 5, 2022
    
    Type-generic queue using singly linked lists [Rev. 2]
*/

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

typedef struct Node {
    void *          data;
    size_t          data_size;
    struct Node *   next;
} Node;

typedef struct Queue {
    Node *  head;
    Node *  tail;
    size_t  length;
} Queue;

typedef struct Person {
    char const *        name;
    unsigned short int  age;
    char const *        occupation;
} Person;

Queue * create_queue(void);
void    enqueue(Queue *, void *data, size_t data_size);
void *  front(Queue *);
size_t  front_size(Queue const *);
size_t  length(Queue const *);
void    dequeue(Queue *);
void    clear(Queue *);
int     is_empty(Queue const *);
Queue * copy_queue(Queue *);
void    print(Queue *);
void    destroy_queue(Queue *);



/*
    Creates a heap-allocated node.
    The newly created node has a pointer to 
    a heap-allocated copy of data.

    Internal use only
*/
static Node *create_node(void *data, size_t size)
{
    Node *new_node = malloc(sizeof(Node));
    if(new_node == NULL) { return NULL; }
    new_node->data_size = size;
    new_node->data = malloc(new_node->data_size);
    if(new_node->data == NULL) { return NULL; }
    memcpy(new_node->data, data, new_node->data_size);
    new_node->next = NULL;
    return new_node;
}

/*  
    Frees memory occupied by the node's data
    and the node itself

    Internal use only
*/
static void destroy_node(Node *n)
{
    free(n->data);
    free(n);
}

Queue *create_queue(void)
{
    Queue *new_queue = malloc(sizeof(Queue));
    if(new_queue == NULL) { return NULL; }
    new_queue->head = NULL;
    new_queue->tail = NULL;
    new_queue->length = 0;
    return new_queue;
}

/*
    Input data is not null
*/
void enqueue(Queue *b, void *data, size_t data_size)
{
    Node *new_node = create_node(data, data_size);
    if(new_node == NULL) { assert(0); }

    (b->length)++;

    if(is_empty(b)) {
        b->head = new_node;
        b->tail = new_node;
        return;
    }
    b->tail->next = new_node;
    b->tail = new_node;
}

void *front(Queue *b)
{
    return b->head->data;
}

size_t front_size(Queue const *b)
{
    return b->head->data_size;
}

size_t length(Queue const *b)
{
    return b->length;
}

/*
    Input queue is not empty
*/
void dequeue(Queue *b)
{
    if(b->head == b->tail) {
        destroy_node(b->head);
        b->head = NULL;
        b->tail = NULL;
    }
    else {
        Node *upcoming = b->head->next;
        destroy_node(b->head);
        b->head = upcoming;
    }
    (b->length)--;
}

void clear(Queue *b)
{
    while(!is_empty(b)) {
        dequeue(b);
    }
}

int is_empty(Queue const *b)
{
    return b->head == NULL;
}

Queue *copy_queue(Queue *b)
{
    Queue *copy = create_queue();
    int count = length(b);
    while(count > 0) {
        enqueue(copy, front(b), front_size(b));
        dequeue(b);
        enqueue(b, front(copy), front_size(copy));
        count--;
    }
    return copy;
}

void print(Queue *b)
{
    if(is_empty(b)) {
        printf("[empty]\n");
        return;
    }
    Queue *copy = copy_queue(b);
    printf("[");
    while(!is_empty(copy)) {
        struct Person *d = (struct Person *)front(copy);
        printf("%s, ", d->name);
        dequeue(copy);
    }
    printf("]");
    printf("\n");
    destroy_queue(copy);
}

void destroy_queue(Queue *b)
{
    clear(b);
    free(b);
}



int main(void)
{
    Queue *queue = create_queue();
    if(queue == NULL) { assert(0); }
    Person chase = { "Chase", 49, "Banker" };
    Person evan  = { "Evan", 34, "Doctor" };
    Person susie = { "Susie", 43, "Teacher" };
    enqueue(queue, &chase, sizeof(Person));
    enqueue(queue, &evan, sizeof(Person));
    enqueue(queue, &susie, sizeof(Person));
    print(queue);
    dequeue(queue);
    print(queue);
    dequeue(queue);
    print(queue);
    dequeue(queue);
    print(queue);
    destroy_queue(queue);
    return 0;
}
\$\endgroup\$
2
  • \$\begingroup\$ @Deduplicator, Can you tell me how you fixed the "triple backtick issue"? I've been looking for a fix, but couldn't find one... did you just remove them manually? \$\endgroup\$
    – Mode77
    Aug 5 at 19:21
  • 1
    \$\begingroup\$ Yes, though adding more trailing whitespace would hide it too, I think. codereview.se just must demonstrate their uniqueness... \$\endgroup\$ Aug 5 at 19:22

2 Answers 2

6
\$\begingroup\$
  1. Cleanly separate test-code from the library.

    Users really don't need the test-code outside of verifying the library seems to work, if ever.

  2. create_node() leaks the node if allocating for the data fails.

  3. Dynamic memory allocation is quite costly. Thus, minimize the number of allocations by merging allocations if they have the same lifetime. It even reduces size, a second thing to minimize, even aside from bookkeeping overhead.

    #include <stddef.h>
    typedef struct Node {
        struct Node* next;
        size_t size;
         _Alignas(max_align_t) char data[];
    } Node;
    

    Doing it manually if you insist on pre-C11 conformance shouldn't be too hard either.

  4. copy_queue() throws away the first item after copying it on the copy, and duplicates the new first item. That messes up things for sure, and is UB if the the queue only contained one item.

  5. While horribly failing as detailed above, it does triple work:

    1. Duplicate item onto new queue
    2. Duplicate item onto old queue (moved to fix bug)
    3. Destroy item at the front

    The last two can be eliminated by using knowledge of the internal details (it's part of the implementation!), adding a function to iterate all items, or adding a function moving the front node to the back.

  6. Never use assert() to handle expected runtime failures. Either handle it yourself (retry?, different strategy, ...), notify the caller (return-code, hook, longjmp(), ...), or abort() (preferably with diagnostic message).

  7. if (condition) assert(0); is equivalent to assert(!(condition)), aside from side-effects of evaluating condition.

  8. return 0; is implicit for main() since C99, for what it's worth.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ What do you mean by Point 7? Surely, condition must be (or at least appear to be) fully evaluated exactly once in either case, right? So I am not sure how the side effects could differ. (Though I agree the second kind of assertion looks cleaner to me.) \$\endgroup\$ Aug 6 at 14:30
  • \$\begingroup\$ @AlexanderWolters No, in a release build (which means NDEBUG is defined), assert(x) doesn't evaluate anything, being replaced with ((void)0). en.cppreference.com/w/c/error/assert \$\endgroup\$ Aug 6 at 15:12
1
\$\begingroup\$

Corral namespace footprint

Rather than names like create_queue(), enqueue(), length(), print(), .., how about q77_create(), q77_enqueue(), q77_length(), q77_print().

Current names are spread out all over and can likely collide with user code, especially with names like length(), print().

I suggest a common prefix for all external names.

Divide into private/public

Form a .h file, perhaps q77.h and move the _necessary type and function declarations there. IN q77.c, move the implementation and into main.c, your sample usage code.

Allocation to the referenced type, not type

Easier to code right, review and maintain.

// new_queue = malloc(sizeof(Queue));
new_queue = malloc(sizeof new_queue[0]);

Tolerate freeing 0

Like free(NULL) is OK, let destroy_node(NULL) simply do nothing. This simplifies code clean-up.


GTG

destroy_node(Node *n)
\$\endgroup\$
1
  • \$\begingroup\$ As you demonstrate, there are (nearly) always more things to improve. \$\endgroup\$ Aug 7 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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