[Tinyos-devel] Re: [Tinyos Core WG] Proposal for VariableSizedQueueC component

[Philip Levis]

On Sep 20, 2007, at 10:17 AM, Kevin Klues wrote:

> I remember bringing this same issue up a long time ago (more than a
> year ago), but it never got resolved.
>
> I came across it when implementing the resource queues for the
> arbiters.  To deal with it I implemented a ResourceQueue interface
> that is essentially the same as the Queue interface, but with async
> commands.  The parameter for what data structure is to be enqueued is
> also removed (since I know it is always a resource ID), as well as
> some of the commands unnecessary for queuing up resource ids.
>
> From this interface, the FcfsResourceQueueC and RoundRobinQueueC
> components have been created.  If anyone takes the time to actually
> implement an AsyncQueueC component I suggest looking here as a
> starting point.

Right -- but the big difference between these queue implementations  
and more general ones is that they only operate on resource IDs  
(values in the range of [0, size-1]) and a given value can only be  
inserted once. This enables them, for example, to support an O(1)  
isEnqueued, while for general queues it would be O(n).

Phil