Pages: [1]   Go Down
Author Topic: How to implement an efficient list/reverse stack?  (Read 670 times)
0 Members and 1 Guest are viewing this topic.
Australia
Offline Offline
Sr. Member
****
Karma: 10
Posts: 397
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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).

     
Logged

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 452
Posts: 18694
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

UK
Offline Offline
Shannon Member
****
Karma: 184
Posts: 11173
-
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
Logged

I only provide help via the forum - please do not contact me for private consultancy.

Australia
Offline Offline
Sr. Member
****
Karma: 10
Posts: 397
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Thanks Guys.
Just what I was looking for.
Cheers
Logged

Pages: [1]   Go Up
Jump to: