Circular Queue data structure ..

[herrcho]

#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 ?

 

[Ivan Vecerina]

Hi,
| 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

 

[Richard Bos]

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

 

[j]

#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.

 

[BruceS]

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.

 

[Richard Bos]

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

 

[BruceS]

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.