Queue example from TI-RTOS

Discussion in 'Programmer's Corner' started by bug13, Aug 9, 2019.

  1. bug13

    Thread Starter Senior Member

    Feb 13, 2012
    1,662
    62
    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 (Text):
    1.  
    2. typedef struct Rec {
    3.     Queue_Elem elem;
    4.     Int data;
    5. } Rec;
    6.  
    7. // some code removed for easier reading...
    8.  
    9. // Add r1 and r2 to the back of myQ.
    10. Queue_enqueue(myQ, &(r1.elem));  // <<=== how Queue_enqueue() find the size of Rec???
    11. Queue_enqueue(myQ, &(r2.elem));

    Here are the full codes:
    Code (Text):
    1. typedef struct Queue_Elem {
    2.     Queue_Elem *next;
    3.     Queue_Elem *prev;
    4. } Queue_Elem;
    Code (Text):
    1. /* This structure can be added to a Queue because the first field is a Queue_Elem. */
    2. typedef struct Rec {
    3.     Queue_Elem elem;
    4.     Int data;
    5. } Rec;
    6.  
    7. Queue_Handle myQ;
    8. Rec r1, r2;
    9. Rec* rp;
    10.  
    11. r1.data = 100;
    12. r2.data = 200;
    13.  
    14. // No parameters or Error block are needed to create a Queue.
    15. myQ = Queue_create(NULL, NULL);
    16.  
    17. // Add r1 and r2 to the back of myQ.
    18. Queue_enqueue(myQ, &(r1.elem));
    19. Queue_enqueue(myQ, &(r2.elem));
    20.  
    21. // Dequeue the records and print their data
    22. while (!Queue_empty(myQ)) {
    23.     // Implicit cast from (Queue_Elem *) to (Rec *)
    24.     rp = Queue_dequeue(myQ);
    25.     System_printf("rec: %d\n", rp->data);
    26. }
    Thanks team!
     
  2. mckenney

    Member

    Nov 10, 2018
    53
    14
    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
     
    bug13 likes this.
  3. BobaMosfet

    AAC Fanatic!

    Jul 1, 2009
    696
    168
    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 (Text):
    1.  
    2. typedef struct Queue_Elem     // <-- 'Queue_Elem' is a forward reference allowing the compiler to reference this type before it's fully defined
    3.    {
    4.    Queue_Elem *next;              // it's using a reference to this type before it's fully defined
    5.    Queue_Elem *prev;
    6.    }Queue_Elem;
    7.  
    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 (Text):
    1.  
    2. typedef struct Rec
    3.    {
    4.    Queue_Elem elem;
    5.    int data;
    6.    }Rec;
    7.  
    It knows exactly what size the structure is.

    A handle is just a pointer, for dereferencing purposes. So if you make this call:
    Code (Text):
    1.  
    2. Queue_enqueue(myQ, &(r1.elem));
    3.  
    ...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.
     
    bug13 likes this.
  4. bug13

    Thread Starter Senior Member

    Feb 13, 2012
    1,662
    62
    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?
     
  5. mckenney

    Member

    Nov 10, 2018
    53
    14
    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.
     
    bug13 likes this.
  6. bug13

    Thread Starter Senior Member

    Feb 13, 2012
    1,662
    62
    That's good to know, thanks @mckenney, FreeRTOS is next on my list to look at.
     
  7. BobaMosfet

    AAC Fanatic!

    Jul 1, 2009
    696
    168
    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.
     
    bug13 likes this.
Loading...