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

[Kevin Klues]

Yes, thats true.  In fact, the scheduler could even be implemented
using an FcfsResourceQueue if you wanted.  I think I may have even
taken parts of the code from the scheduler in order to implement it.

Kevin

On 9/20/07, Philip Levis <pal at cs.stanford.edu> wrote:
> 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
>


-- 
~Kevin