Go Down

Topic: How to implement an efficient list/reverse stack? (Read 775 times) previous topic - next topic


I am working on a mesh of transceivers connected to arduinos.
To make sure that a given transmission packet is not re-transmitted more than once by a node(when relaying), I am going to use a short list of eight bytes (each packet has a unique identifier of one byte). Each node will keep the last eight IDs of packets it has transmitted to look up to ensure no repetitive transmissions. It would not be a linked list but more like a stack but instead of pushing and popping from the top of a stack, I would be pushing the values on one end and losing them out the other.

i.e. The list is based on a first-in-first-out principle. Simplistically, as each packet received was re-transmitted, I would shuffle each of the entries in the list down one (popping the last one off the list thereby losing it) and put the ID of the new packet on the top of the list.

The problem is that when I receive a packet, I have to sequentially traverse the list (to check that the packet has not been sent before) and then go back again and shuffle all the values down and put the new one on top.

This involves a bit of housekeeping overhead for the list when I would like to be getting back the receiving function to check whether more packets have been received in a busy network.

I pretty sure I can't get away from the sequential checking of the list but I was wondering if anyone has a more efficient way of shuffling the values down the list (or other method of maintaining the list).


Nick Gammon

8 bytes isn't that much, but you could make a ring buffer (insertion point, removal point).


Yes, a ring buffer (circular queue) seems like the right answer here, although actually a full implementation might be overkill since there would (presumably) be nothing reading from the buffer.

For a bigger buffer, I'd search the buffer from the write pointer backwards (i.e. most recent first). But if you only have eight elements buffered, it hardly matters how you search them.
I only provide help via the forum - please do not contact me for private consultancy.


Thanks Guys.
Just what I was looking for.

Go Up