\section{Map Library}\label{sec:map}

The final $x$-kernel tool we describe is the id mapper.  This tool
provides a facility for maintaining a set of bindings between
identifiers.  The id mapper supports operations for adding new
bindings to the set, removing bindings from the set, and mapping one
identifier into another, relative to a set of bindings.  Protocol
implementations use these operations to translate identifiers
extracted from message headers (e.g., addresses, demultiplexing keys)
into capabilities for (pointers to) $x$-kernel objects such as
sessions. (See \cite{Idmap} for a description of how the map library
is implemented.)

The id mapper supports two main objects: {\it maps} and {\it
bindings}, represented by the types {\var Map} and {\var Binding},
respectively. A map is simply a table of bindings, where each binding
is given by the pair $\langle$ external key, internal id $\rangle$. An
external key is a variable length byte string, and an internal id is a
fixed-sized identifier (e.g., a 32 or 64-bit memory address).
Typically, an external key is constructed from various fields in a
message header, and an internal id is a pointer to a protocol or
session object. A map is created with the following operation:

\begin{quote}
{\var Map mapCreate(int number, int size)}
\end{quote}

\noindent This operation creates a map that is able to hold
{\var number} bindings in it, where the external keys bound in this
map are {\var size} bytes long.

Once a map is created, protocols can perform two basic operations on
it. The first puts bindings into the map and the latter resolves
external keys according to the map and returns the corresponding
internal id:

\begin{quote}
{\var Binding mapBind(Map map, void *key, void *id)}\\
\\
{\var XkReturn mapResolve(Map map, void *key, void **id)}
\end{quote}

The first operation inserts a binding of {\var key} to {\var id} into
the specified {\var map}, and returns a pointer to the resulting
binding. If {\var key} is already bound to some {\var id} in the {\var
map}, then a pointer to that existing binding is returned.  The second
operation returns the internal {\var id} bound to the specified {\var
key} in the given {\var map}. If the {\var key} is not found in the
map, then {\var mapResolve} reports failure by returning {\var
XK\_FAILURE}.

The id mapper also provides a pair of operations for removing bindings
from a map:

\begin{quote}
{\var XkReturn mapRemoveBinding(Map map, Binding binding)}\\
\\
{\var XkReturn mapRemoveKey(Map map, void *key)}
\end{quote}

The first removes the specified {\var binding}---the value returned by
an earlier {\var mapBind}---and the second removes the binding for the
specified {\var key}. Both operations return a failure code if the
binding does not exist in the map.

Protocols generally maintain two maps: an active map and a passive
map.  Active maps are used to map keys found in incoming messages into
the session that will process the message. Thus, the active map holds
information about the set of currently active connections.  Passive
maps are used to bind keys found in incoming messages into protocol
objects, thereby allowing a protocol to create a session when a
message that is part of a new connection arrives.

Typically, a protocol binds an active key to a session in its
implementation of {\var xOpen}, and a passive key to a protocol object
in its {\var xOpenEnable} routine. These bindings are then used in the
protocol's {\var xDemux} operation. This general pattern is illustrated
in the example given Section~\ref{sec:example}.