1. Michele Bini
  2. Hard real-time queues


Hard real-time queues /

Filename Size Date modified Message
1.6 KB
1.2 KB
197 B
4.0 KB
193 B
1.7 KB
173 B
2.5 KB
Functional queues for Mythryl with hard real-time operations, based on
lazy lists and memoization. This implementation is based on techniques
described in "Purely Functional Data Structures" by Chris Okasaki,


This code was written in Mythryl: http://www.mythryl.org


Please consult the individual files for the copyright notices.   I
(Michele) will release them with a BSD-style or the MIT license given
a small compensation for the ~5 hours work (at least 90 EUR or 15


According to measurements, the maximum number of recursive calls
(including mutual recursion) performed during the execution of each
individual operation (enqueue/dequeue) is just 2, confirming the
the hard real-time constraint.

When comparing by average execution time, operations were measured to
be about 6 to 10 times slower than the same operations performed on
finger queues (https://bitbucket.org/rev22/finger-deques), on queues
with sizes in the order of one million of elements.


real-time-queue.pkg    		 Main library code.
real-time-queue--verbatim.pkg    Near-verbatim implementation
real-time-queue--complexity.pkg  Complexity measuring implementation