%
% x-kernel v3.3
%
% Copyright (c) 1996,1993,1991,1990  Arizona Board of Regents
%

\section{Map Library}\label{map_lib}

The map library provides a facility for maintaining a set of bindings
between identifiers.  The map library 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 (lookup).
Protocol implementations use these operations to translate identifiers
extracted from message headers (e.g., addresses, port numbers) into
capabilities for (pointers to) {\xk} objects (e.g., {\var Protl},
{\var Sessn}, {\var Enable}).

\subsection{Type Definitions}\label{map_type_defs}

The map library defines two data structures: {\var MapElement} and
{\var Map}.  A {\var Binding} is a pointer to a {\var MapElement}.  A
map element is a table of bindings, where each binding is given by the
pair <external key, internal id>.  An external key is a variable
length byte string, which typically is constructed from various fields
in a message header.  An internal id is a fixed-sized identifier
(e.g., a 32 or 64-bit memory address) which is a pointer to a protocol
or session object.
\medskip

\var
\index{Map}
\begin{tabbing}
xxxx \= xxxxxx \= xxxxxxxxxxxxxxxx \= \kill
\>typedef struct mapelement \{\\
\>\>struct mapelement \>*next;\\
\>\>void              \>*externalkey;\\
\>\>void              \>*internalid;\\
\>\} MapElement, *Binding;\\
\\
\>typedef struct \{\\
\>\>int               \>nEntries;\\
\>\>int               \>keySize;\\
\>\>MapElement        \>*cache;\\
\>\>MapElement        \>*freelist;\\
\>\>MapElement        \>**table;\\
\>\>XkReturn          \>(*resolve)();\\
\>\>Binding           \>(*bind)();\\
\>\>XkReturn          \>(*unbind)();\\
\>\>XkReturn          \>(*remove)();\\
\>\} *Map;
\end{tabbing}
\rm

\subsection{Map Operations}\label{map_ops}

\subsubsection{mapCreate}\label{mapCreate}
\index{mapCreate}

Creates a map with {\var table\_len} elements in it.  External keys
bound in this map are {\var keySize} bytes long.  The maximum value
for the key size is MAX\_MAP\_KEY\_SIZE, currently 100 bytes.
Programmers should normally use {\sf sizeof(structuretype)} as the key
size to facilitate platform independence.  Note that maps never
overflow, but they perform best if {\var table\_len} is chosen so that
the map is at most 50-80\% full. Returns 0 if the map could not be
created.
\medskip

{\var Map mapCreate(int table\_len, int keySize)}

\subsubsection{mapBind}\label{mapBind}
\index{mapBind}

Adds a binding of external {\var key} to internal {\var id} to 
{\var map}.  The binding will be done with {\var keySize} bytes of what
{\var key} points to, where {\var keySize} is the parameter that was
used in the {\var mapCreate} call.  The return value uniquely
identifies this binding; it can later be given as an argument to 
{\var mapRemoveBinding}.  A return value of {\var ERR\_BIND} indicates that
the {\var key} is already bound in the map to a different {\var id}.
If the {\var key} is already bound to the same {\var id}, that binding
is returned.
\medskip

{\var Binding mapBind(Map map, void *key, void *id)}

\subsubsection{mapResolve}\label{mapResolve}
\index{mapResolve}

Looks for the internal {\var id} bound to the external {\var key} in
{\var map}.  The resolution will be done with {\var keySize} bytes
of what {\var key} points to, where {\var keySize} is the parameter
that was used in the {\var mapCreate} call.  If a binding is found,
{\var *id} is assigned the value of the internal identifier and 
{\var XK\_SUCCESS} is returned.  If no appropriate binding is found, 
{\var mapResolve} returns {\var XK\_FAILURE}.  If {\var id} is NULL, only
the error code is returned.
\medskip

{\var XkReturn mapResolve(Map map, void *key, void **id)}

\subsubsection{mapRemoveBinding}\label{mapRemoveBinding}
\index{mapRemoveBinding}

Removes binding {\var bind} from {\var map}.  Returns 
{\var XK\_FAILURE} if the item is not in the map.
\medskip

{\var XkReturn mapRemoveBinding(Map map, Binding bind)}

\subsubsection{mapRemoveKey}\label{mapRemoveKey}
\index{mapRemoveKey}

Removes binding of the association {\var key} from the {\var map}.
This is the inverse of {\var mapBind}.  Returns {\var XK\_FAILURE} if
the item is not in the map.
\medskip

{\var XkReturn mapRemoveKey(Map map, void *key)}

\subsubsection{mapClose}\label{mapClose}
\index{mapClose}

Destroys {\var map} and frees its space.  Any elements left in the map
will be unbound before the map is destroyed.
\medskip

{\var void mapClose(Map map)}

\subsubsection{mapForEach}\label{mapForEach}
\index{mapForEach}

Allows iterative access to the entries of a map by the provided
callback function {\var func}.  Each call to {\var mapForEach} puts
the external key and its internal id into arguments passed the
function {\var func}.  The third argument passed to {\var func} is the
supplied value {\var arg}.  As long as the flag {\var MFE\_CONTINUE}
is set in the callback function's return value and there are
unprocessed keys, {\var mapForEach} will continue to call {\var func}.

If the flag {\var MFE\_REMOVE} is set in the return value of the
callback function, {\var mapForEach} will remove the entry from the
map after the user function returns and before it is called with the
next map entry.  This is the only correct way to remove the
``current'' map entry during a {\var mapForEach} operation.  If the
user callback function attempts to remove the ``current'' entry
directly (via {\var mapRemoveBinding} or {\var mapRemoveKey}), the
result is unpredictable and may result in system crashes.

It is currently possible to remove entries other than the ``current''
entry from within the callback function.  However, we strongly
discourage such use as its correctness depends on implementation
details that may change in future versions of the {\xk}.

New map entries added in the middle of a {\var mapForEach} iteration
may or may not show up during that iteration.  Map manipulations
within a {\var mapForEach} user function are generally not
recommended.

{\var MFE\_REMOVE} and {\var MFE\_CONTINUE} are binary flags which may
be combined using bitwise OR.  The order in which keys are returned
depends on the internal structure of the map.
\medskip

{\var void mapForEach(Map map, MapForEachFun func, void *arg)}
\medskip

{\var typedef int MapForEachFun(void *key, void *id, void *arg)}

\subsection{Usage Rules}\label{map_usage}

\subsubsection{Map Modifications During mapForEach}\label{map_mods}

It is no longer permissible to directly remove the ``current'' entry
in a {\var mapForEach} callback function, as it was in {\xk} version
3.2.  When adapting a version 3.2 protocol, care should be take to
remove such illegal map modifications.

Illegal map modifications often appear in timeout handlers closing
active sessions.  Such code can be fixed easily because it is
customary to save the binding of an active session in the 
{\var binding} field of the {\var Sessn} and for functions that close
sessions to check this field and perform a {\var mapRemoveKey} only if
it is non-zero.  The fix is to modify the timeout handler to (a) reset
{\var binding} to zero, (b) call the session-closing function, and (c)
return the flag {\var MFE\_REMOVE} in addition to any other flags that
may have been returned by the {\var mapForEach} callback function.
This ensures that the map entry for the active session that is being
closed remains in the map until the {\var mapForEach} callback
function returns.

\subsubsection{External Keys}\label{ext_keys}

Maps are used to bind a variable length external key to an internal id
of type {\var int}.  The size of the external key is given as an
argument when a particular map is created.  All external keys bound
using this map are expected to be of this size.  It's important that
you use a zero-izing routine like {\var bzero} before assigning values
to a structure that will be used with the map routines.  The C
language can have uninitialized data in the interstices of structures
(i.e., padding areas), and these can cause structures that are
``equal'' (i.e., all fields have the same values) to fail to map to
the same value in the {\xk}.

\subsubsection{Active and Passive Maps}\label{active_passive_maps}

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 to {\var Enable} objects
(Section~\ref{enable_objs}), 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 
{\var xOpen} routine, and a passive key to an enable object in its 
{\var xOpenEnable} routine.  These bindings are then used in the 
protocol's {\var xDemux} routine.