Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Circular Queue data structure ..

Reply
Thread Tools

Circular Queue data structure ..

 
 
herrcho
Guest
Posts: n/a
 
      10-01-2003
#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[i]);

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 ?
 
Reply With Quote
 
 
 
 
Ivan Vecerina
Guest
Posts: n/a
 
      10-01-2003
Hi,
"herrcho" <(E-Mail Removed)> wrote in message
news:bleech$ovj$(E-Mail Removed)...
| 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


 
Reply With Quote
 
 
 
 
Richard Bos
Guest
Posts: n/a
 
      10-01-2003
"herrcho" <(E-Mail Removed)> 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
 
Reply With Quote
 
j
Guest
Posts: n/a
 
      10-01-2003

"herrcho" <(E-Mail Removed)> wrote in message
news:bleech$ovj$(E-Mail Removed)...
> #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[i]);
>
> 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.


 
Reply With Quote
 
BruceS
Guest
Posts: n/a
 
      10-02-2003

"Richard Bos" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
<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.


 
Reply With Quote
 
Richard Bos
Guest
Posts: n/a
 
      10-02-2003
"BruceS" <(E-Mail Removed)> wrote:

> "Richard Bos" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
> <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
 
Reply With Quote
 
BruceS
Guest
Posts: n/a
 
      10-02-2003

"Richard Bos" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> "BruceS" <(E-Mail Removed)> wrote:
>
> > "Richard Bos" <(E-Mail Removed)> wrote in message
> > news:(E-Mail Removed)...
> > <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.


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Difference between circular queue and double-ended queue (deque) bintom C++ 6 11-03-2012 01:22 PM
Program blocked in Queue.Queue.get and Queue.Queue.put Kris Python 0 01-04-2012 03:46 PM
Is Queue.Queue.queue.clear() thread-safe? Russell Warren Python 4 06-27-2006 03:03 PM
Semi-circular definitions (plus circular references) Kiuhnm C++ 16 01-03-2005 03:49 AM
name of data structure for circular array? Bob Jenkins C Programming 2 06-29-2004 02:41 PM



Advertisments