Queue in C

Discussion in 'C Programming' started by pandit, May 19, 2014.

  1. pandit

    pandit Guest

    AIM: Just wanted to write a queue in C, to know C better.
    PROBLEM: no problems in code
    WHAT I WANT: want comments from CLC for better C coding,
    program design etc.

    its working on solorias 10 with gcc 3.4.6.

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


    struct node
    {
    char c;
    struct node* next;
    };


    struct queue
    {
    struct node* head;
    struct node* tail;
    };


    /* for every function 0 is returned for success and negative integer for
    * failure. -11 is reserved for args check and -12 for malloc() failure */
    int enqueue(struct queue* q, char cr);
    void dequeue(struct queue* q, struct node* np);
    void create_queue(struct queue** q);
    void print_queue(struct queue* q);
    void print_node(struct node p);


    /* These operatiors was created just for the sake of understanding
    * pointers.
    */
    int search_queue(struct queue* q, const char cr);
    int delete_from_queue(struct queue* q, const char cr);
    int insert_after(struct queue* q, const char cr, const char elem);
    int insert_before(struct queue* q, const char cr, const char elem);



    int main(void)
    {
    int i, r;
    struct queue* q;
    struct node p;

    create_queue(&q);
    for(i = 97; i <= 101; ++i)
    {
    if((r = enqueue(q, i))) /* implicit conversion to charcter intended */
    {
    printf("Could not enqueue, r = %d\n", r);
    }
    }

    print_queue(q);
    dequeue(q, &p);
    print_queue(q);
    print_node(p);
    printf("Element 'n' exist == %d\n\n", search_queue(q, 'n'));
    delete_from_queue(q, 'e');
    print_queue(q);
    delete_from_queue(q, 'b');
    print_queue(q);

    printf("Element 'd' exist == %d\n\n", search_queue(q, 'd'));

    insert_after(q, 'e', 'd');
    insert_after(q, 's', 'r');
    print_queue(q);
    insert_before(q, 'b', 'c');
    insert_before(q, 'a', 'b');
    insert_before(q, 'a', 'B');
    print_queue(q);

    return EXIT_SUCCESS;
    }



    /* insert "cr" before "elem" */
    int insert_before(struct queue* q, const char cr, const char elem)
    {
    struct node *prev, *temp;
    if((NULL == q) || (NULL == q->head)) return -11;

    for(prev = NULL, temp = q->head; temp; temp = temp->next)
    {
    if(elem == temp->c)
    {
    struct node* t = malloc(1 * (sizeof *t));
    if(NULL == t) return -12;
    t->c = cr;
    if(NULL == prev) /* we are dealing with head */
    {
    t->next = q->head;
    q->head = t;
    }
    else
    {
    prev->next = t;
    t->next = temp;
    }
    return 0;
    }
    else
    {
    prev = temp;
    }
    }

    return -13;
    }


    /* insert "cr" next to "elem" */
    int insert_after(struct queue* q, const char cr, const char elem)
    {
    struct node* temp;
    if((NULL == q) || (NULL == q->head)) return -11;

    for(temp = q->head; temp; temp = temp->next)
    {
    if(elem == temp->c)
    {
    struct node* t = malloc(1 * (sizeof *t));
    if(NULL == t) return -12;
    t->c = cr;
    t->next = temp->next;
    temp->next = t;
    return 0;
    }
    }

    return -13;
    }


    int search_queue(struct queue* q, const char cr)
    {
    struct node* temp;
    if((NULL == q) || (NULL == q->head)) return -11;

    for(temp = q->head; temp; temp = temp->next)
    {
    if((cr == temp->c)) return 0;
    }

    return -13;
    }


    int delete_from_queue(struct queue* q, const char cr)
    {
    struct node *prev, *temp;;
    if((NULL == q) || (NULL == q->head)) return -11;

    for(prev = NULL, temp = q->head; temp; temp = temp->next)
    {
    if(cr == temp->c)
    {
    if(NULL == prev) /* we are dealing with head */
    {
    q->head = temp->next;
    free(temp);
    if(NULL == q->head) q->tail = q->head;
    return 0;
    }
    else
    {
    prev->next = temp->next ;
    free(temp);
    if(NULL == prev->next) q->tail = prev->next;
    return 0;
    }
    }
    else
    {
    prev = temp;
    }
    }

    return -13;
    }


    int enqueue(struct queue* q, char cr)
    {
    struct node* p;
    if((NULL == q)) return -11;

    p = malloc(1 * (sizeof *p));
    if(NULL == p) return -12;
    else p->c = cr;

    if((NULL == q->head) && (NULL == q->tail))
    {
    q->head = q->tail = p;
    }
    else if((NULL == q->head) || (NULL == q->tail))
    {
    free(p);
    return -13;
    }
    else
    {
    struct node* temp = q->tail;
    temp->next = p;
    q->tail = p;
    }

    return 0;
    }


    void dequeue(struct queue* q, struct node* np)
    {
    struct node* temp;

    if((NULL == q) || (NULL == np)) return;
    if((NULL == q->tail)) return;

    temp = q->head;
    q->head = q->head->next;
    np->c = temp->c;
    free(temp);
    if(NULL == q->head) q->tail = q->head;
    }


    void print_queue(struct queue* q)
    {
    if(q)
    {
    struct node* temp = q->head;
    while(temp)
    {
    printf("Element = %c\n", temp->c);
    temp = temp->next;
    }
    printf("--------------- EoQ -----------\n\n");
    }
    }

    void print_node(struct node p)
    {
    printf("Node = %c\n", p.c);
    }

    void create_queue(struct queue** q)
    {
    if(q && *q)
    {
    *q = malloc(1 * (sizeof **q));
    if(NULL == *q) exit(EXIT_FAILURE);

    (*q)->head = (*q)->tail = NULL;
    }
    }



    ================ OUTPUT ====================
    $ gcc -ansi -pedantic -Wall -Wextra LL.c
    $ ./a.out
    Element = a
    Element = b
    Element = c
    Element = d
    Element = e
    --------------- EoQ -----------

    Element = b
    Element = c
    Element = d
    Element = e
    --------------- EoQ -----------

    Node = a
    Element 'n' exist == -13

    Element = b
    Element = c
    Element = d
    --------------- EoQ -----------

    Element = c
    Element = d
    --------------- EoQ -----------

    Element 'd' exist == 0

    Element = c
    Element = d
    Element = e
    --------------- EoQ -----------

    Element = a
    Element = b
    Element = c
    Element = d
    Element = e
    --------------- EoQ -----------
     
    pandit, May 19, 2014
    #1
    1. Advertisements

  2. pandit

    Ike Naar Guest

    q is not initialized so its value is indeterminate.
    create_queue is called with &q as its argument.

    Looking at the definition of create_queue:
    In the call from main(), *q is indeterminate.
    If it happens to be a null pointer, then the body of
    the if statement is not executed and no queue will be
    created.
    What is the reason for testing the value of *q in the
    if condition anyway?
     
    Ike Naar, May 19, 2014
    #2
    1. Advertisements

  3. pandit

    Ike Naar Guest

    Here you set q->tail to NULL which is not correct.
    For a nonempty queue, q->tail should point to the last
    node in the queue, which is 'prev' at this point.
     
    Ike Naar, May 19, 2014
    #3
  4. pandit

    Ike Naar Guest

    If t is the last node in the list, q->tail should be updated:

    if (t->next == 0) q->tail = t;
     
    Ike Naar, May 19, 2014
    #4
  5. You can either implement a queue as a linked list, or as circular
    buffer. The linked list is a bit easier to write, and is naturally
    unbounded. The circular buffer will normally execute faster,
    but it's slightly tricky to ensure the head and tail positions
    don't overlap and wrap correctly. Also if the queue becomes too long
    for the buffer, you have problems.
     
    Malcolm McLean, May 19, 2014
    #5
  6. pandit

    BartC Guest

    It's not clear what all these -13s mean.

    Presumably they are an error return (but code -13 not documented). You
    should use a #define or enum name for these:

    #define unknownerror -13

    .....

    return unknownerror;

    But using a more descriptive name for whatever this error actually is.
     
    BartC, May 19, 2014
    #6
  7. True for only five functions and partially true for main. None of the
    others return an int.
    I wonder why cr is not const like it is in the last four prototypes
    below.
    Why use magic numbers that are meaningless on some machines. You
    could just as easily (and more understandably) code
    for (i = 'a'; i <= 'e'; ++i)
    which will work for both ASCII and EBCDIC.
    Wouldn't it would be useful to tell the user which value of i failed?
    101 is not 'e' on my machine.
    Wouldn't it be nice to tell the user why you are aborting the program?
     
    Barry Schwarz, May 19, 2014
    #7
  8. If q->head is NULL, can q->tail be anything else? Why check both?
    When can this ever evaluate to true?
    temp serves no purpose. This is equivalent to
    q->tail->next = p;
     
    Barry Schwarz, May 19, 2014
    #8
  9. It is not a big deal since struct node is small but it is much more
    common to pass a pointer to struct rather than an actual struct.
     
    Barry Schwarz, May 19, 2014
    #9
  10. pandit

    Stefan Ram Guest

    My personal coding style does not permit a library function
    to terminate an application. So, I'd write something like:

    void init_queue( struct queue * const q ){ q->head = q->tail = 0; }

    struct queue * new_queue()
    { struct queue * const q = malloc( sizeof *q );
    if( q )init_queue( q );
    return q; }

    struct queue * create_queue( struct queue * * const q )
    { return *q = new_queue(); }

    (untested)
     
    Stefan Ram, May 19, 2014
    #10
  11. In Baby X, I do all memory allocation via bbx_malloc(), which never returns null.
    That's so that the user doesn't have to check almost every single Baby X call for
    allocation failure. In xlib, you're not guaranteed clean behaviour if the X server
    runs out of memory, so we're not losing anything theoretically.

    Of course it's impossible to guarantee that box_malloc() will always give you the
    memory you ask for. So currently it calls exit() if it can't allocate memory.
    At some point I'll replace that with a user message. but the problem is that the user
    message itself requires memory.
     
    Malcolm McLean, May 19, 2014
    #11
  12. What is the significance of the numbers 97 and 101? If they're supposed
    to be 'a' and 'e', then write 'a' and 'e'. (Strictly speaking, there's
    no guarantee in the language that the values of 'a' through 'e' are
    contiguous, but it turns out to be a reasonably safe assumption, even
    for EBCDIC systems.)

    Various functions return -11, -12, and -13 in various circumstances.
    You never said what -13 means -- and you shouldn't expect users the
    values to be obvious just becuase you mentioned them in a comment.
    Reserving specific values for error codes is great, but define them as
    named constants.

    http://en.wikipedia.org/wiki/Magic_number_(programming)#Unnamed_numerical_constants
     
    Keith Thompson, May 19, 2014
    #12
  13. Consider this.

    Our program makes use of a small but still reasonably large number of file formats, for
    various this around the program. For example it uses JPEG, GIF, BMP and PNG formats to store
    images, xml for configuration, a vector format for vector graphics, and internal format
    for save states.
    Now there are essentially three things that can happen when we try to load or save a file.
    The function can work correctly, the user can pass a path which doesn't exist or is
    illegal, there can be an IO error, there can be a parse error (file or data in a format the
    function cannot read), or the computer can run out of memory. That's about it.

    So let's say we define

    #define ERR_OUT_OF_MEMORY -1

    Then we put that definition in jpeg.h. Great, but then xml.h has to include jpeg.h. Not
    acceptable. So maybe put the definition in file_errors.h Better, but now jpeg.c and jpeg.h
    are not idempotent. Not good.
    OK, so make in JPEG_ERR_OUT_OF_MEMORY.
    Well OK. Better. But we've obscured the fact that all the errors are essentially the same.
    JPEG_OUT_OF_MEMORY = PNG_OUT_OF_MEMORY = XML_OUT_OF_MEMORY. It's all the
    same underlying problem.

    Or use the convention that -1 always indicates an out-of-memory error.

    Much better, except that the convention isn't established. So establish it locally.
     
    Malcolm McLean, May 19, 2014
    #13
  14. pandit

    Martin Shobe Guest

    Why couldn't you put the define in file_errors.h and make jpeg.h and
    jpeg.c idempotent? (Though I don't see why we would should care if
    jpeg.c is idempotent.) It's what I do in situations like that.

    Martin Shobe
     
    Martin Shobe, May 19, 2014
    #14
  15. [...]

    That should be

    #define unknownerror (-13)

    to avoid operator precedence problems. It's likely that there are no
    actual uses of unknownerror that would cause problems, but it's better
    to be safe.

    And it's conventional to use all-caps for macro names; I suggest
    following that convention unless you have a good reason not to.
     
    Keith Thompson, May 19, 2014
    #15
  16. I wonder why cr *is* const in those last four prototypes. The "const"
    has no meaning for callers; it only prevents any modifications to cr
    inside the function.

    It would be reasonable to have "const char cr" in the function
    definition and just "char cr" in the separate prototype. (Or you could
    just use "char cr" everywhere, which is perhaps mildly sloppy but common
    practice.)

    [...]
    To expand on that: the C standard makes no guarantees about the numeric
    values of 'a' through 'z' or 'A' through 'Z'. In particular, it doesn't
    guarantee that their values are contiguous.

    In the ASCII and ASCII-derived character sets used by most modern
    systems (including Unicode), the 26 lowercase letters *are* contiguous,
    as are the 26 uppercase letters.

    In EBCDIC, most commonly used on IBM mainframes, the letters are not
    contiguous, but certain subranges are: 'a'..'i', 'j'..'r', and 's'..'z'
    (and likewise for uppercase).

    The letters 'a'..'e' are contiguous on every system I've ever heard of,
    but the C standard doesn't guarantee that.

    (It does guarantee that '0'..'9' are contiguous.)
    You use EBCDIC?

    [...]
     
    Keith Thompson, May 19, 2014
    #16
  17. Perhaps when there's a bug in the code? An assert() might be a
    good way to check that.
     
    Keith Thompson, May 19, 2014
    #17
  18. You want to be able to take jpeg.c and drop in into anything that needs to read or
    write jpegs. You don't want to be bothered messing about with an external file
    for a few trivial errors.
     
    Malcolm McLean, May 19, 2014
    #18
  19. pandit

    Ian Collins Guest

    A good reason to use an enum for return values rather than an ugly macro.
    Yet another...
     
    Ian Collins, May 19, 2014
    #19
  20. pandit

    Ian Collins Guest

    Wouldn't an assertion be better than calling exit?
     
    Ian Collins, May 19, 2014
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.