Prev: Linux and C
Next: delete a pointer which has more then one reference in a vector
From: waltbrad on 8 Jan 2008 11:13
I'm in a chapter on advanced thread synchronization and the author
uses a queue structure as follows:

typedef struct queue_tag {
HANDLE q_guard; // for a mutex
HANDLE q_ne; // queue not empty
HANDLE q_nf; // queue not full
volatile DWORD q_size; // max queue size
volatile DWORD q_first; // index of oldest msg
volatile DWORD q_last; // index of youngest msg
volatile DWORD q_destroyed; // Q receiver has terminated
PVOID msg_array; // array of q_size messages

} queue_t;

Fine. Then comes this function.

DWORD q_full (queue_t *q)
{
return ((q -> q_first - q -> q_last) ==1 ||
(q -> q_last == q -> q_size - 1 && q -> q_first ==
0));

}

I don't understand the first condition of the return stmt. I
understand the first part of the second condition, but I don't
understand why they had to && it with q_first == 0.

There are two other functions I'm having trouble with the condition.
Both the same condition. It goes:

DWORD q_remove ( queue_t *q, PVOID msg, DWORD msize)
{
char *pm;

pm = (char *)q -> msg_array;
memcpy (msg, pm + (q -> q_first * msize), msize);
q -> q_first = (( q -> q_first +1) % q -> q_size);
return 0;

}

Now in this code I don't understand why they had to use the modulus
expression. What would be wrong with just saying q -> q_first = q -

> q_first + 1;

?

TIA
From: Jim Langston on 8 Jan 2008 11:40
waltbrad wrote:
> I'm in a chapter on advanced thread synchronization and the author
> uses a queue structure as follows:
>
> typedef struct queue_tag {
> HANDLE q_guard; // for a mutex
> HANDLE q_ne; // queue not empty
> HANDLE q_nf; // queue not full
> volatile DWORD q_size; // max queue size
> volatile DWORD q_first; // index of oldest msg
> volatile DWORD q_last; // index of youngest msg
> volatile DWORD q_destroyed; // Q receiver has terminated
> PVOID msg_array; // array of q_size messages
>
> } queue_t;
>
> Fine. Then comes this function.
>
> DWORD q_full (queue_t *q)
> {
> return ((q -> q_first - q -> q_last) ==1 ||
> (q -> q_last == q -> q_size - 1 && q -> q_first ==
> 0));
>
> }

I really don't see the code where queue_tag is being used so can only guess
at some of this.

It seems to me that q->q_first - q->q_last would return the number of
elements in your queue minus one. That is, you probably always have a head
and a tail. With an empty queue you would still have 2 elements in it, the
head and the tail. So if the head - tail = 1 then you have no elements in
your queue. Without seeing how it everything is used though I'm just
guessing.

Next we have q->q_last == q->q_size - 1 && q->q_first == 0. Okay, this
seems to be checking if the queue is full. If you have q_size possible
elements, and the first is 0, and the last is size-1 then you are full.

So this seems to be returning true if either there are no elements in the
queue, or there are q_size elements in the queue. Again just guessing on
some of it.

> I don't understand the first condition of the return stmt. I
> understand the first part of the second condition, but I don't
> understand why they had to && it with q_first == 0.
>
> There are two other functions I'm having trouble with the condition.
> Both the same condition. It goes:
>
> DWORD q_remove ( queue_t *q, PVOID msg, DWORD msize)
> {
> char *pm;
>
> pm = (char *)q -> msg_array;
> memcpy (msg, pm + (q -> q_first * msize), msize);
> q -> q_first = (( q -> q_first +1) % q -> q_size);
> return 0;
>
> }
>
> Now in this code I don't understand why they had to use the modulus
> expression. What would be wrong with just saying q -> q_first = q -
>
>> q_first + 1;
>
> ?

Well, usually that would be the case. Consider that q_first is, say, 1.
Say q_size is 10.. (q->first+1)%q->q_size. (1+1)%10 == 2. Which would be
the same as q_first +1. There are conditions where this won't be true
however. What if q->first is 9, 10 or 11?

The code isn't quite clear and we don't see the entire implementation of it,
but it seems to be checking on overflow here in a somewhat tricky manner.



--
Jim Langston
tazmaster(a)rocketmail.com


From: Daniel T. on 8 Jan 2008 12:14
In article
<b13a1399-ebfd-4fc7-9e89-e2a5275d19d8(a)e23g2000prf.googlegroups.com>,
waltbrad <waltbrad(a)hotmail.com> wrote:

> I'm in a chapter on advanced thread synchronization and the author
> uses a queue structure as follows:
>
> typedef struct queue_tag {
> HANDLE q_guard; // for a mutex
> HANDLE q_ne; // queue not empty
> HANDLE q_nf; // queue not full
> volatile DWORD q_size; // max queue size
> volatile DWORD q_first; // index of oldest msg
> volatile DWORD q_last; // index of youngest msg
> volatile DWORD q_destroyed; // Q receiver has terminated
> PVOID msg_array; // array of q_size messages
>
> } queue_t;
>
> Fine. Then comes this function.
>
> DWORD q_full (queue_t *q)
> {
> return ((q -> q_first - q -> q_last) ==1 ||
> (q -> q_last == q -> q_size - 1 && q -> q_first ==
> 0));
>
> }

My guess is that this is a circular buffer. if q_first - q_last == 1,
then adding an element would erase the oldest element, i.e., the queue
is full. However, if first - last doesn't equal 1, the queue may still
be full. For example if the last element is at the end (q_last == q_size
- 1) and the first element is at the beginning (q_first == 0) then the
queue is also full.

> I don't understand the first condition of the return stmt. I
> understand the first part of the second condition, but I don't
> understand why they had to && it with q_first == 0.

If q_last was at the end of the buffer, but q_first was at position 1
(for example) then the queue would not be full.

> There are two other functions I'm having trouble with the condition.
> Both the same condition. It goes:
>
> DWORD q_remove ( queue_t *q, PVOID msg, DWORD msize)
> {
> char *pm;
>
> pm = (char *)q -> msg_array;
> memcpy (msg, pm + (q -> q_first * msize), msize);
> q -> q_first = (( q -> q_first +1) % q -> q_size);
> return 0;
>
> }
>
> Now in this code I don't understand why they had to use the modulus
> expression. What would be wrong with just saying q -> q_first = q -
>
> > q_first + 1;

Because if q_first (and q_last) cannot be greater than or equal to
q_size. You can't just add 1 to q_first and be assured it is still
valid. The modulus forces a wrap.
 | 
Pages: 1
Prev: Linux and C
Next: delete a pointer which has more then one reference in a vector