ADT queue

I want a queue that can handle any data type I throw at it, so I decided to use pointers for the data element inside the linked list. Anyone have a better way of doing it, or any comments on the code?

queue.h

Code:

---

#ifndef QUEUE_H
#define QUEUE_H

typedef void *qelem_t;

typedef struct qnode
{
        qelem_t elem;
        struct qnode *next;
        struct qnode *prev;
}qnode;

typedef struct
{
        qnode *back;
        qnode *front;
}queue;

/*
 * Create an queue.
 */
queue *q_create(void);

/*
 * Destroy an queue.
 * Returns 1 on success, and otherwise 0.
 */
int q_destroy(queue *q);

/*
 * Check if queue is empty.
 * Returns 1 if the queue is empty, and otherwise 0.
 */
int q_isempty(queue *q);

/*
 * Add element to queue.
 * Returns 1 on success, and otherwise 0.
 */
int q_enqueue(queue *q, qelem_t elem);

/*
 * Remove element from queue, and return it.
 */
qelem_t q_dequeue(queue *q);

#endif

---

queue.c

Code:

---

#include <stdlib.h>
#include "queue.h"

queue *q_create(void)
{
        queue *q = malloc(sizeof(*q));
        if (!q)
                return NULL;
        q->back = NULL;
        q->front = NULL;
        return q;
}

int q_destroy(queue *q)
{
        if (!q)
                return 0;
        while (!q_isempty(q))
                q_dequeue(q);
        free(q);
        return 1;
}

int q_isempty(queue *q)
{
        if (!q)
                return 1;
        if (!q->front)
                return 1;
        else
                return 0;
}

int q_enqueue(queue *q, qelem_t elem)
{
        qnode *new = malloc(sizeof(*new));
        if (!new)
                return 0;
        if (!q || !elem)
        {
                free(new);
                return 0;
        }
        new->elem = elem;
        new->next = q->back;
        new->prev = NULL;
        if (q->back)
                q->back->prev = new;
        q->back = new;
        if (!q->front)
                q->front = new;
        return 1;
}

qelem_t q_dequeue(queue *q)
{
        qnode *prev;
        qelem_t *elem;
        if (q_isempty(q))
                return NULL;
        prev = q->front->prev;
        elem = q->front->elem;
        free(q->front);
        q->front = prev;
        return elem;
}

---

main.c

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

int main(void)
{
        unsigned int i;
        qelem_t elem; /* Pointer to an ADT */
        queue *q = q_create();
        const int numbers[] = {0,1,2,3,4,5,6,7,8,9};
        const char *msg[] = {
                "abc",
                "123",
                NULL
        };

        for (i=0; i<2; i++)
        {
                if (!q_enqueue(q, (qelem_t) msg[i]))
                        puts("Enqueue error");
        }

        for (; i>0; i--)
        {
                elem = q_dequeue(q);
                if (!elem)
                        puts("Dequeue error");
                printf("%s\n", (char *) elem);
        }

        if (!q_destroy(q))
        {
                puts("Invalid queue pointer");
                return EXIT_FAILURE;
        }
        q = q_create();

        for (i=0; i<10; i++)
        {
                if (!q_enqueue(q, (qelem_t) &numbers[i]))
                        puts("Enqueue error");
        }

        for (; i>0; i--)
        {
                elem = q_dequeue(q);
                printf("%d\n", *(int *) elem);
        }
        if (!q_destroy(q))
        {
                puts("Invalid queue pointer");
                return EXIT_FAILURE;
        }
        return 0;
}

---

since qelem is a pointer, probably using pointer to qelem in functions could lead to use annoing double pointers, or more dificult error probing. Try using only qelem and not *qelem

This is just some lint.

Code:

---

int q_destroy(queue *q)
{
        if (!q)
                return 0;
        while (!q_isempty(q))
                q_dequeue(q);
/* [Warning 534] Ignoring return value of function 'q_dequeue(struct {...} *)' */
        free(q);
        return 1;
}

---

Code:

---

int q_isempty(queue *q)
{
        if (!q)
                return 1;
        if (!q->front)
                return 1;
        else
                return 0;
}/* [Info 818] Pointer parameter 'q' could be declared as pointing to const */

---

Code:

---

int q_enqueue(queue *q, qelem_t *elem)
{
        qnode *new = malloc(sizeof(*new));
        if (!new)
                return 0;
        if (!q || !elem)
                return 0; /* [Warning 429] Custodial pointer 'new' has not been freed or returned */
        new->elem = elem;
        new->next = q->back;
        new->prev = NULL;
        if (q->back)
                q->back->prev = new;
        q->back = new;
        if (!q->front)
                q->front = new;
        return 1;
}

---

Code:

---

int main(void)
{
        unsigned int i;
        qelem_t elem; /* Pointer to an ADT */
        queue *q = q_create();
        const int numbers[] = {0,1,2,3,4,5,6,7,8,9};
        const char *msg[] = {
                "abc",
                "123",
                NULL
        };

        for (i=0; i<2; i++)
        {
                if (!q_enqueue(q, (qelem_t *) msg[i]))
/* [Info 826] Suspicious pointer-to-pointer conversion (area too small) */
                {
                                puts("Enqueue error");
                                return EXIT_FAILURE;
                }
        }

        for (; i>0; i--)
        {
                elem = q_dequeue(q);
                if (!elem)
                {
                        puts("Dequeue error");
                        return EXIT_FAILURE;
                }
                printf("%s\n", (char *) elem);
        }

        q_destroy(q); /* Could probably use a q_clear(q) func here instead */
/* [Warning 534] Ignoring return value of function 'q_destroy(struct {...} *)' */
        q = q_create();

        for (i=0; i<10; i++)
                q_enqueue(q, (qelem_t *) &numbers[i]);
/* [Warning 534] Ignoring return value of function 'q_enqueue(struct {...} *, void **)' */
        for (; i>0; i--)
        {
                elem = q_dequeue(q);
                printf("%d\n", *(int *) elem);
/* [Warning 613] Possible use of null pointer 'unknown-name' in argument to operator 'unary *' */
        }

        return 0;
}

---

And in general, you should be aware that you are queueing pointers, not things, so be sure the things continue to exist as long as they are pointed to by the address in the queue.

Generally, if these thing are primitives (ints, doubles, floats, longs, chars, etc), a union would be more appropriate than using a void* pointer this way.

If they are pointers to various malloc'ed structs, you probably need a typecode in the first position of them, or a typecode in each qnode to keep them straight.

If you just want to be able to use the code for any type of element, but all elements of a queue will be the same, then this method (the code still needs fixing) will work - just be sure you aren't queueing a pointer to something on the stack that will disappear before you use the pointer.

The double pointer (qelem_t *) mistake was never intended. It was just pure luck the code worked with it. I've also fixed the potential memory leak in enqueue().

My lint checker (splint) is still giving me warnings about the queue pointer (q) memory not being released, even though I'm doing it with q_destroy(). Should I just ignore it? And how many of you cast the return value of puts/printf etc to void? :eek: