ADT queue

This is a discussion on ADT queue within the C Programming forums, part of the General Programming Boards category; I want a queue that can handle any data type I throw at it, so I decided to use pointers ...

  1. #1
    FOX
    Join Date
    May 2005
    Posts
    188

    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;
    }
    Last edited by ^xor; 06-15-2005 at 06:30 AM.

  2. #2
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    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

  3. #3
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    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;
    }
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  4. #4
    Registered User
    Join Date
    Mar 2005
    Posts
    36
    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.

  5. #5
    FOX
    Join Date
    May 2005
    Posts
    188
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 09:17 AM
  2. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  3. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 10:09 PM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 12:39 PM
  5. queue help
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 10-29-2001, 09:38 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21