Queue example from TI-RTOS

Thread Starter

bug13

Joined Feb 13, 2012
2,002
Hi team

I am looking at an example about Queue from TI-RTOS, I am simply not quite understand how it can be implemented.

Example is taken from here (page 126): http://www.ti.com/lit/ug/spruex3t/spruex3t.pdf

I simply don't understand how Queue_enqueue() may allocate the correct size from only the address of an element. How can Queue_enqueue() find the size of Rec??
Code:
typedef struct Rec { 
    Queue_Elem elem; 
    Int data; 
} Rec;

// some code removed for easier reading...

// Add r1 and r2 to the back of myQ.
Queue_enqueue(myQ, &(r1.elem));  // <<=== how Queue_enqueue() find the size of Rec???
Queue_enqueue(myQ, &(r2.elem));

Here are the full codes:
Code:
typedef struct Queue_Elem {
    Queue_Elem *next;
    Queue_Elem *prev;
} Queue_Elem;
Code:
/* This structure can be added to a Queue because the first field is a Queue_Elem. */
typedef struct Rec {
    Queue_Elem elem;
    Int data;
} Rec;

Queue_Handle myQ;
Rec r1, r2;
Rec* rp;

r1.data = 100;
r2.data = 200;

// No parameters or Error block are needed to create a Queue.
myQ = Queue_create(NULL, NULL);

// Add r1 and r2 to the back of myQ.
Queue_enqueue(myQ, &(r1.elem));
Queue_enqueue(myQ, &(r2.elem));

// Dequeue the records and print their data
while (!Queue_empty(myQ)) {
    // Implicit cast from (Queue_Elem *) to (Rec *)
    rp = Queue_dequeue(myQ);
    System_printf("rec: %d\n", rp->data);
}
Thanks team!
 

mckenney

Joined Nov 10, 2018
125
I think it can't, therefore it doesn't. I expect that it builds the queue (linked list) right there in the first two words of your variables. (Don't let them go out of scope!)

The source is presumably somewhere in c:\TI, but I lost patience trying to find it. My guess is that the first two lines of Queue_enqueue() look like:
void Queue_enqueue(Queue_Handle *hp, void *rp) {
Queue_Elem *ep = (Queue_elem *)rp; // The caller is expected to put these words here for me
 

BobaMosfet

Joined Jul 1, 2009
2,110
I'm not sure why you're confused. In fact, TI is showing you the actual correct way to define a structure with a forward reference to itself. Sizing is determined by the linker, at compile time.

When you enter:
Code:
typedef struct Queue_Elem     // <-- 'Queue_Elem' is a forward reference allowing the compiler to reference this type before it's fully defined
   {
   Queue_Elem *next;              // it's using a reference to this type before it's fully defined
   Queue_Elem *prev;
   }Queue_Elem;
This type is as valid as 'int', 'char', or any other compiler defined 'type'. So the compiler knows the size of Queue_Elem, and when you create another type referencing the above type:
Code:
typedef struct Rec
   {
   Queue_Elem elem;
   int data;
   }Rec;
It knows exactly what size the structure is.

A handle is just a pointer, for dereferencing purposes. So if you make this call:
Code:
Queue_enqueue(myQ, &(r1.elem));
...what you're actually saying is-- Pass the handle to the Q to Queue_enqueue(), so we know what queue we're working with. Pass the address of one of a queue elements from one of the Rec's you created (r1 in this case), and it will add that address to the queue. It's not allocating a structure, it's just passing the address.

What is probably confusing you is that the address of the first element in any structure is the same as the address of the structure itself.

&(r1.elem) is equal to &r1

But what is different is that although each is the same value as an address, the compiler sees each one as a different type. Queue_enqueue() is expecting an address of a Queue_Elem, not an address of a Rec. They're just being sneaky/clever in how they avoid casting/coercion to pass that address.
 

Thread Starter

bug13

Joined Feb 13, 2012
2,002
I'm not sure why you're confused. In fact, TI is showing you the actual correct way to define a structure with a forward reference to itself...
Hi @BobaMosfet, thanks for pointing these out, that makes sense.

If I understand it correctly, the Queue_enqueue() function is just queuing the address of the Rec struct, and the size of the address is known. So as long as we know the address of the whaterever structure, we can get it back.

While, me being not understanding it when I asked this question, I thought the Queue_enqueue() actually copy and allocate the actual structure in the memory. Because of this mis-understanding, I thought the Queue_enqueue() need to know the size of the Rec structure.

Is my understanding correct now?
 

mckenney

Joined Nov 10, 2018
125
FreeRTOS, by contrast, does it the way you originally thought: You tell queue initialization how big each entry is (and how many there can be), and it copies each item into/out of a private (to the RTOS) structure.
 

Thread Starter

bug13

Joined Feb 13, 2012
2,002
FreeRTOS, by contrast, does it the way you originally thought: You tell queue initialization how big each entry is (and how many there can be), and it copies each item into/out of a private (to the RTOS) structure.
That's good to know, thanks @mckenney, FreeRTOS is next on my list to look at.
 

BobaMosfet

Joined Jul 1, 2009
2,110
Hi @BobaMosfet, thanks for pointing these out, that makes sense.

If I understand it correctly, the Queue_enqueue() function is just queuing the address of the Rec struct, and the size of the address is known. So as long as we know the address of the whaterever structure, we can get it back.

While, me being not understanding it when I asked this question, I thought the Queue_enqueue() actually copy and allocate the actual structure in the memory. Because of this mis-understanding, I thought the Queue_enqueue() need to know the size of the Rec structure.

Is my understanding correct now?
No, it's _passing_ the address of the struct. They can then copy the data from that address. Look, whatever level you're at with C- stop. Take some time, and learn about addressing, pointers, memory. How RAM is organized. stack-pointers, stack-frames, program counters, registers.

If you will take the time to learn what it means to directly and indirectly address something, it will forever change the programming game for you and make it so much simpler. You will be able to do things your peers simply can't figure out. And it isn't hard. in fact, it's the easiest thing to understand- but it has tremendous benefits.
 
Top