\section{AGS Request Data Structure}

The request data structure contains enough information to process
the primitive being executed.
The most complex version is, 
of course, the request data structure
associated with an \gasplus{.}
In addition to general status information, the data structure
contains an entry for each branch in the \gasplus{.}
This branch entry contains an {\it op data structure} for the guard
and an array of such data structures for the body.
An op data structure contains copies of the \ts handle(s)
involved with the operation, space for a global timestamp,
the operator (e.g., {\bf in}), and its tuple index.
It also stores the length of the operation's data and information for each 
parameter, as well as a data area to store the value of actuals.
The information for each parameter includes 
its polarity (i.e., actual or formal),
the offset in the data area of its actual value (if any),
and opcode arguments.
The request data structure also contains space for the value 
of any formal parameters;
these are filled in by the code that manages the \ts
being referenced by the operation in question.

Once the invocation from the generated code to the FT-Linda library
has been made, the control logic in the library routes the
request appropriately.
For example, if it involves only a local \tsplus{,} it is dealt with
by the \ts management code within the library itself, while if
it involves a replicated \tsplus{,} 
it is multicast to the \ts state machine protocols using Consul.
In the latter case, this is the hand-off point between the user process
and the control thread that carries the message through the
{\it x}-kernel protocol graph to the network.
As such, the user process blocks on a {\it port} until the request has
been completed; 
this port is allocated by the library code, 
and is included within the request data structure.
When the request is completed, the request data structure is returned
to the user process, where the generated code 
copies the values for any formals to the corresponding
variables in the user address space.

Tuple spaces are implemented in two places, the FT-Linda library for
local \tss and the \ts state machine for replicated \tssplus{.}
The algorithms and data structures used in both places are essentially
identical.
In each, a table of \tss is maintained.
When a request to create a new \ts is processed,
a new table entry is allocated;
the index of this entry is known as the {\it \ts index}.
The \ts handle returned as the functional value of 
$ts\_create$ contains this index, as well as the attributes
of the tuple space.
A subsequent request to destroy a \ts frees the appropriate table
entry and increments an associated version number.
This number is used to detect future \ts operations on the destroyed \tsplus{.}

A \ts itself is represented as a hash table of tuples,
as shown in Figure~\ref{fig:impl-tuple}.
%
    \begin{figure}[tbh]
    \centering
    \leavevmode\hbox{\epsfig{file=tuple_eg.ps,height=1.50in}}
    \caption{\label{fig:impl-tuple} Tuple Hash Table}
    \end{figure}
%
The index into this table for a given tuple is simply the
tuple index assigned by the precompiler, while the 
entries are op data structures.
Both have been described above.

Also associated with each \ts is another hash table 
used to store blocked \gas requests. 
That is, at any given time, this table contains requests 
with guards of {\bf in} or {\bf rd} for which no 
matching tuple exists.
An example of such a table is shown in Figure~\ref{fig:impl-blocked}.
Here, the blocked \gas request has two {\bf in} guards: 
one waiting for a tuple named $A$ with a tuple index of 1
and the other waiting for a tuple named $B$ with a tuple index 
of 3.
Note that the request itself is stored indirectly in the table since,
in the general case, such an \gas may be waiting for any 
number of matching tuples.
%
    \begin{figure}[tbh]
    \centering
    \leavevmode\hbox{\epsfig{file=blocked_eg.ps,height=1.75in}}
    \caption{\label{fig:impl-blocked} Blocked Hash Table}
    \end{figure}