## rw-queue.api
#
# Simple mutable queues. For immutable fully-persistent queues see
#
# src/lib/src/queue.api#
# This package use two lists to implement a queue via the usual trick
# of adding to the q.back list, removing from the q.front list,
# and when the q.front list is empty, reversing the q.back list
# and making it the new q.front list.
#
# This is a nice simple algorithm where both push and unpull
# are O(1) amortized cost. (Pull is O(N) worst-case cost.)
#
# We publish our datastructure because many clients duplicate
# critical fns locally for speed because the compiler does not
# yet do cross-package inlining.
# (Also, the datastructure isn't likely to change,
# so there is little need to encapsulate it anyhow.)
#
# This is the core queue used throughout threadkit
# for run queues and wait queues.
#
# There's nothing thread-specific about the implemention.
#
# NB: We actually implement both adding and removing from
# both front and back of queue, making this technically
# a deque rather than a queue, but we use it primarily
# as a queue and thus for clarity continue to call it that.
# Compiled by:
# src/lib/std/standard.lib### "If you cannot grok the overall pattern
### of a program while taking a shower,
### you are not ready to code it."
###
### -- Richard Pattis
# This api is implemented in:
#
# src/lib/src/rw-queue.pkg#
api Rw_Queue {
#
Rw_Queue(X) = RW_QUEUE { front: Ref( List(X) ),
back: Ref( List(X) )
};
make_rw_queue: Void -> Rw_Queue(X);
same_queue: (Rw_Queue(X), Rw_Queue(X)) -> Bool; # Returns TRUE iff the two queues are the same. This is an O(1) computation -- essentially pointer equality.
queue_is_empty: Rw_Queue(X) -> Bool; # Returns TRUE iff the queue is empty.
put_on_back_of_queue: (Rw_Queue(X), X) -> Void; # The normal way of inserting an item into the queue. O(1) worst-case cost.
push: (Rw_Queue(X), X) -> Void; # Synonym for previous.
take_from_front_of_queue: Rw_Queue(X) -> Null_Or(X); # De-queue and return the next item in the queue. Return NULL if the queue is empty. O(1) amortized cost, O(N) worst-case cost.
pull: Rw_Queue(X) -> Null_Or(X); # Synonym for previous.
clear_queue_to_empty: Rw_Queue(X) -> Void; # Reset a queue to all empty, discarding any and all current contents. O(1) cost.
put_on_front_of_queue: (Rw_Queue(X), X) -> Void; # We occasionally use this when a thread needs to run immediately. O(1) worst-case cost.
unpull: (Rw_Queue(X), X) -> Void; # Synonym for previous.
take_from_back_of_queue: Rw_Queue(X) -> Null_Or(X); # Abnormal case included for completeness -- currently unused: Dequeue and return the last item in the queue. O(1) amortized cost, O(N) worst-case cost.
unpush: Rw_Queue(X) -> Null_Or(X); # Synonym for previous.
to_list: Rw_Queue(X) -> List(X); # Return contents of queue as a list. O(N) cost.
take_from_front_of_queue_or_raise_exception # Dequeue an item; raise exception DIE "queue is empty" if the queue is empty.
: # This is a grody efficiency hack; use it only if it is a coding
Rw_Queue(X) -> X; # error for the queue to be empty at that point in the code.
# For debug and unit testing:
#
frontq: Rw_Queue(X) -> List(X);
backq: Rw_Queue(X) -> List(X);
};