Don't confuse a FIFO with a circular queue. Most UART drivers/ISR use a circular queue and just move pointers around the like a loop. There will be times when the tail may point to a lower memory location and also the other way around.
Jim
Yes I do realize it's a circular queue, I named the array fifo because circular_queue was too long, but I've implemented it as a circular queue in the code as you can see, by handling the wraparounds.
I maybe have missed something, but what exactly is the difference between a FIFO and a circular queue?
Meindert
A FIFO and a queue are the same thing. You can implement them without size limits by mallocing on insert, and freeing on removal, with a linked list, for example. A circular queue has limits on the total length, set by the size of the buffer.
-- Chuck F (cbfalconer at maineline dot net) Available for consulting/temporary embedded and systems.
When I think of FIFO I think of a linear system, possibly hardware based, that may or may not have "wrap around" in the memory pointer sense. Like a stack that pushes on one end and pops at the other that you may not be able manipulate the data pointer directly. I know I'm splitting hairs and may not even be exactly correct in my thinking, but when I mean a circular queue I say it. In the end I was really just trying to point out that there will be times when the pointers into the queue can wrap around at different times and make doing simple math like num_in_queue = queue_head - queue_tail might not work right unless you take into account that when the head pointer rolls back around before the tail pointer the answer is going to wrap also. Not that it is a show stopper it just needs to be accounted for.
Jim
I wasn't thinking of a queue of chars, but rather of records or lines. The lines variant is likely to have a two level allocation, for the header and for the variable length line itself. The point was that a queue need not be length limited, but a circular buffer must be.
-- Chuck F (cbfalconer at maineline dot net) Available for consulting/temporary embedded and systems.
In my world (embedded hardware and software design) a FIFO chip has a limit on total length and they have circular address registers. In software, my circular buffers/queues/fifos also have a size limit and pointers/indices that wrap around. So there's no difference. Also, considered as a black box, they operate the same: whatever you put in first, comes out first. So it's a FIFO. Both.
Meindert
How can you implement a FIFO without wrapping pointers around?
Which is a LIFO, not a fifo in my opinion.
Make the operations atomic.
Meindert
The only difference in a LIFO and FIFO is how the data is pulled. I guess maybe I'm not expressing myself well here. I am speaking of how you mentally model the queue, not necessarily how it is physically implemented.
OK, the operations are atomic. How does that stop the head pointer from wrapping around and pointing at a lower address that the tail pointer?
Ah, misread that. But, if you make the buffer size a power of two, you can simply subtract the tail from the head and AND the result with bufsize-1. I do that all the time. Another way is to add a byte/element counter.
I must admit that I very often miss hardware support for circular buffers in micros. All it needs is a hardware AND/OR and a smart linker that puts the buffer at a power of 2-boundary. Very common feature in DSPs.
Meindert
Right, I guess we were both thinking the same thought, I just couldn't see exactly what you were saying and just got caught up in the terminology. I could see how in a DSP it(hardware queue support) would be handy to store samples that need to be sent out to a codec or ones that have come in from conversion.
Jim
On 18/10/2006 the venerable galapogos etched in runes:
Sorry I've been away since yesterday so haven't been here until now.
The correct way top do this is to have a separate variable which is initialised to BUFFLEN. 'BufferSpace' would be a good name. Every time you add a character to the buffer 'BufferSpace' is incremented and when a character is removed 'BufferSpace' is decremented. It then always tracks the available space.
That has caught me out more than once.
-- John B
Oops..... :-)=)
Meindert
Another question. Is there any way an MCU can provide a clock to another UART device? I'm asking because I'm trying to emulate ISO7816 via a regular UART, and the smart card needs a 1-5MHz clock(ideally
3.5712MHz for 9600baud) and I'm trying to reduce cost and not having a separate osc for the card.
What has this got to do with anything? You failed to quote any preceding material.
-- Chuck F (cbfalconer at maineline dot net) Available for consulting/temporary embedded and systems.
Yeah coz it's another new question that doesn't have much to do with the earlier ones, but still UART related.
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.