Circular Queue data structure ..

Discussion in 'C Programming' started by herrcho, Oct 1, 2003.

  1. herrcho

    herrcho Guest

    #include <stdio.h>
    #define MAX 10

    int queue[MAX];
    int front, rear;

    void init_queue()
    {
    front=rear=0;
    }

    void clear_queue(void)
    {
    front=rear;
    }

    int put(int k)
    {
    if ( (rear + 1) % MAX == front)
    {
    printf("\n Queue overflow.");
    return -1;
    }
    queue[rear] = k;
    rear = ++rear % MAX; <------------------------ 1
    return k;
    }

    int get()
    {
    int i;
    if (front == rear)
    {
    printf("\n Queue underflow.");
    return -1;
    }
    i = queue[front];
    front = ++front % MAX; <------------------------------- 2
    return i;
    }

    void print_queue(void)
    {
    int i;
    printf("\n Queue contents : Front -------> Rear \n");
    for (i=front;i != rear ;i = ++i % MAX )
    printf("%-6d", queue);

    the above is for implementing 'Circular Queue' data structure using
    array.

    when i complile it. 1 & 2 line shows the following warning message .

    operation on `rear' may be undefined.
    operation on `front' may be undefined.

    but executues alright.. Did i miss something ?
    herrcho, Oct 1, 2003
    #1
    1. Advertising

  2. Hi,
    "herrcho" <> wrote in message
    news:bleech$ovj$...
    | rear = ++rear % MAX;
    ....
    | front = ++front % MAX;
    .....
    | when i complile it. 1 & 2 line shows the following warning message .
    |
    | operation on `rear' may be undefined.
    | operation on `front' may be undefined.
    |
    | but executues alright.. Did i miss something ?

    The compiler is right, and warns you about undefined behavior.
    In the code lines above, the value of the same variable is
    changed twice within the same statement:
    var = ++var % MAX;
    If var is initially 6, and MAX is 6:
    - ++var will attempt to assign the value '6' to var
    - the = operator will attempt to assign the value 0 to var
    Which one occurs first is not defined, and the two
    assignments may interfere in unexpected ways.

    What you need to write is:
    ++var; var %= MAX; // two statements
    or:
    var = (var+1)%MAX; // var+1 does not try to modify 'var'

    hth,
    Ivan
    --
    http://ivan.vecerina.com
    Ivan Vecerina, Oct 1, 2003
    #2
    1. Advertising

  3. herrcho

    Richard Bos Guest

    "herrcho" <> wrote:

    > rear = ++rear % MAX; <------------------------ 1


    > front = ++front % MAX; <------------------------------- 2


    > when i complile it. 1 & 2 line shows the following warning message .
    >
    > operation on `rear' may be undefined.
    > operation on `front' may be undefined.


    That's right. You modify rear and front twice between two sequence
    points. That's undefined behaviour.
    In these cases, the ++ operator increases rear (resp. front), and the =
    operator assigns something to rear/front again. You don't actually mean
    that. You don't care for the increase-object side-effect of ++; all you
    need is the value-plus-one evaluation. So, instead, use an expression
    that only gives you the _value_ rear+1, mod MAX.

    > but executues alright.


    By accident. UB is allowed to do what you think it will do. It's also
    allowed to do this, _until_ you demonstrate the program to your
    supervisor.

    Richard
    Richard Bos, Oct 1, 2003
    #3
  4. herrcho

    j Guest

    "herrcho" <> wrote in message
    news:bleech$ovj$...
    > #include <stdio.h>
    > #define MAX 10
    >
    > int queue[MAX];
    > int front, rear;
    >
    > void init_queue()
    > {
    > front=rear=0;
    > }
    >
    > void clear_queue(void)
    > {
    > front=rear;
    > }
    >
    > int put(int k)
    > {
    > if ( (rear + 1) % MAX == front)
    > {
    > printf("\n Queue overflow.");
    > return -1;
    > }
    > queue[rear] = k;
    > rear = ++rear % MAX; <------------------------ 1
    > return k;
    > }
    >
    > int get()
    > {
    > int i;
    > if (front == rear)
    > {
    > printf("\n Queue underflow.");
    > return -1;
    > }
    > i = queue[front];
    > front = ++front % MAX; <------------------------------- 2
    > return i;
    > }
    >
    > void print_queue(void)
    > {
    > int i;
    > printf("\n Queue contents : Front -------> Rear \n");
    > for (i=front;i != rear ;i = ++i % MAX )
    > printf("%-6d", queue);
    >
    > the above is for implementing 'Circular Queue' data structure using
    > array.
    >
    > when i complile it. 1 & 2 line shows the following warning message .
    >
    > operation on `rear' may be undefined.
    > operation on `front' may be undefined.
    >
    > but executues alright.. Did i miss something ?


    Yes you did. The standard states that
    ``Between the previous and next sequence point an object shall have its
    stored value
    modified at most once by the evaluation of an expression.''

    rear = ++rear;

    ++, operates on an lvalue, increments the value in the object -- by one --
    which rear represents
    Now its stored value has been modified already, then you modify it again by
    assigning
    this value to the object which rear designates, which violates this sequence
    point law
    and thus the reason for the diagnostic which your compiler so kindly gave
    you.

    Likewise for front.
    j, Oct 1, 2003
    #4
  5. herrcho

    BruceS Guest

    "Richard Bos" <> wrote in message
    news:...
    <snip> (working)
    > By accident. UB is allowed to do what you think it will do. It's also
    > allowed to do this, _until_ you demonstrate the program to your
    > supervisor.


    LOL. I think this is the best description of UB I've yet seen. Thanks.
    BruceS, Oct 2, 2003
    #5
  6. herrcho

    Richard Bos Guest

    "BruceS" <> wrote:

    > "Richard Bos" <> wrote in message
    > news:...
    > <snip> (working)
    > > By accident. UB is allowed to do what you think it will do. It's also
    > > allowed to do this, _until_ you demonstrate the program to your
    > > supervisor.

    >
    > LOL. I think this is the best description of UB I've yet seen. Thanks.


    Not only that, but it's more or less realistic. Some forms of UB depend
    on the system running the program - move it to your supervisor's
    differently configured system to demonstrate it, and you might well find
    that on this system, the effect of the UB is not to silently continue
    but to crash or print garbage.
    One particularly common form of this is the difference you get when you
    always run your program in a debugging environment, but your supervisor
    runs it directly from the OS.

    Richard
    Richard Bos, Oct 2, 2003
    #6
  7. herrcho

    BruceS Guest

    "Richard Bos" <> wrote in message
    news:...
    > "BruceS" <> wrote:
    >
    > > "Richard Bos" <> wrote in message
    > > news:...
    > > <snip> (working)
    > > > By accident. UB is allowed to do what you think it will do. It's also
    > > > allowed to do this, _until_ you demonstrate the program to your
    > > > supervisor.

    > >
    > > LOL. I think this is the best description of UB I've yet seen. Thanks.

    >
    > Not only that, but it's more or less realistic. Some forms of UB depend
    > on the system running the program - move it to your supervisor's
    > differently configured system to demonstrate it, and you might well find
    > that on this system, the effect of the UB is not to silently continue
    > but to crash or print garbage.
    > One particularly common form of this is the difference you get when you
    > always run your program in a debugging environment, but your supervisor
    > runs it directly from the OS.


    Exactly, and why I like it. Also, while some may laugh at the idea of nasal
    demons, and keep using the code because "it works fine", they're more likely
    to pay attention to a warning such as above. A cohort at my first C job
    liked to use the phrase "working by accident", and demanded such things be
    fixed, as we never knew what change might prevent the accident.
    BruceS, Oct 2, 2003
    #7
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kiuhnm
    Replies:
    16
    Views:
    728
    Jonathan Mcdougall
    Jan 3, 2005
  2. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    662
    Russell Warren
    Jun 27, 2006
  3. Replies:
    10
    Views:
    3,469
  4. Kris
    Replies:
    0
    Views:
    461
  5. bintom
    Replies:
    6
    Views:
    603
    Öö Tiib
    Nov 3, 2012
Loading...

Share This Page