path: root/doc/UsersGuide/UtilityRoutines.tex

% /*@@
%   @file      UtilityRoutines.tex
%   @date      27 Jan 1999
%   @author    Jonathan Thornburg
%   @desc
%   Description of the Util_* utility routines for the Cactus User's Guide.
%   @enddesc
%   @version $Header$
% @@*/

\begin{cactuspart}{Utility Routines}{$RCSfile$}{$Revision$}
\label{part:UtilityRoutines}
\renewcommand{\thepage}{\Alph{part}\arabic{page}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Introduction}

As well as the high-level \verb|CCTK_|* routines, Cactus also
provides a set of lower-level \verb|Util_|* utility routines, which
are mostly independent of the rest of Cactus.  This chapter gives a
general overview of programming with these utility routines.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Key/Value Tables}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Motivation}

Cactus functions may need to pass information through a generic
interface.  In the past, we have used various ad hoc means to do this,
and we often had trouble passing "extra" information that wasn't
anticipated in the original design.  For example, for periodic output
of grid variables,
\verb|CCTK_OutputVarAsByMethod()| requires that
any parameters (such as hyperslabbing parameters) be appended as an option
string to the variable's character string name.  Similarly, elliptic
solvers often need to pass various parameters, but we haven't had a
good way to do this.

Key/value tables (\textit{tables} for short) provide a clean solution
to these problems.  They're implemented by the \verb|Util_Table|*
functions (described in detail in the Reference Manual).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The Basic Idea}

Basically, a table is an object which maps strings to almost arbitrary
user-defined data.  (If you know Perl, a table is very much like a
Perl hash table.  Alternatively, if you know Unix shells, a table is
like the set of all environment variables.  As yet another analogy,
if you know Awk, a table is like an Awk associative array.)%%%
\footnote{%%%
	 However, the present Cactus tables implementation
	 is optimized for a relatively small number of
	 distinct keys in any one table.  It will still
	 work OK for huge numbers of keys, but it will be
	 slow.
	 }%%%

More formally, a table is an object which stores a set of \textit{keys}
and a corresponding set of \textit{values}.  We refer to a (key,value)
pair as a table \textit{entry}.

Keys are C-style null-terminated character strings, with the slash
character `{\tt /}' reserved for future expansion.%%%
\footnote{%%%
	 Think of hierarchical tables for storing
	 tree-like data structures.%%%
	 }%%%

Values are 1-dimensional arrays of any of the usual Cactus data types
described in Section~\ref{sect-ThornWriting/DataTypes}.
A string can be stored by treating it as a 1-dimensional array of
\verb|CCTK_CHAR| (there's an example of this below).

The basic ``life cycle'' of a table looks like this:
\begin{enumerate}
\item	Some code creates it with \verb|Util_TableCreate()|
	or \verb|Util_TableClone()|.
\item	Some code (often the same piece of code, but maybe some
	other piece) sets entries in it using one or more of
	the \verb|Util_TableSet*()|, \verb|Util_TableSet*Array()|,
	\verb|Util_TableSetGeneric()|, \verb|Util_TableSetGenericArray()|,
	and/or \verb|Util_TableSetString()| functions.
\item	Some other piece or pieces of code can get (copies of)
	the values which were set, using one or more of the
	\verb|Util_TableGet*()|, \verb|Util_TableGet*Array()|,
	\verb|Util_TableGetGeneric()|, \verb|Util_TableGetGenericArray()|,
	and/or \verb|Util_TableGetString()| functions.
\item	When everyone is through with a table, some (single)
	piece of code should destroy it with \verb|Util_TableDestroy()|.
\end{enumerate}

There are also convenience functions \verb|Util_TableSetFromString()|
to set entries in a table based on a parameter-file-style string,
and \verb|Util_TableCreateFromString()| to create a table and then
set entries in it based on a parameter-file-style string.

As well, there are ``table iterator'' functions \verb|Util_TableIt*()|
to allow manipulation of a table even if you don't know its keys.

A table has an integer ``flags word'' which may be used to specify
various options, via bit flags defined in \verb|util_Table.h|.
For example, the flags word can be used to control whether keys
should be compared as case sensitive or case insensitive strings.
See the detailed function description of \verb|Util_TableCreate()|
in the Reference Manual for a list
of the possible bit flags and their semantics.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{A Simple Example}
\label{Tables_Simple_Example}

Here's a simple example (in C)%%%
\footnote{%%%
	 All (or almost all) of the table routines
	 are also usable from Fortran.  See the full
	 descriptions in the Reference Manual
	 for details.
	 }%%%
{} of how to use a table:
\begin{verbatim}
#include "util_Table.h"
#include "cctk.h"

/* create a table and set some entries in it */
int handle = Util_TableCreate(UTIL_TABLE_FLAGS_DEFAULT);
Util_TableSetInt(handle, 2, "two");
Util_TableSetReal(handle, 3.14, "pi");

...

/* get the values from the table */
CCTK_INT two_value;
CCTK_REAL pi_value;
Util_TableGetInt(handle, &two_value, "two");    /* sets two_value = 2 */
Util_TableGetReal(handle, &pi_value, "pi");     /* sets pi_value = 3.14 */
\end{verbatim}

Actually, you shouldn't write code like this---in the real world
errors sometimes happen, and it's much better to catch them close to
their point of occurrence, rather than silently produce garbage results
or crash your program.  So, the \emph{right} thing to do is to always
check for errors.  To allow this, all the table routines return a status,
which is zero or positive for a successful return, but negative if
and only if some sort of error has occurred.%%%
\footnote{%%%
	 Often (as in the examples here) you don't care
	 about the details of which error occurred.  But if
	 you do, there are various error codes defined in
	 {\t util\_Table.h} and {\t util\_ErrorCodes.h};
	 the detailed function descriptions in
	 the Reference Manual
	 say which error codes each function can return.
	 }%%%
{}  So, the above example should be rewritten like this:

\begin{verbatim}
#include "util_Table.h"

/* create a table and set some entries in it */
int handle = Util_TableCreate(UTIL_TABLE_FLAGS_DEFAULT);
if (handle < 0)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't create table!");

/* try to set some table entries */
if (Util_TableSetInt(handle, 2, "two") < 0)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't set integer value in table!");
if (Util_TableSetReal(handle, 3.14, "pi") < 0)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't set real value in table!");

...

/* try to get the values from the table */
CCTK_INT two_value;
CCTK_REAL pi_value;
if (Util_TableGetInt(handle, &two_value, "two") < 0)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't get integer value from table!");
if (Util_TableGetReal(handle, &pi_value, "pi") < 0)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't get integer value from table!");

/* if we get to here, then two_value = 2 and pi_value = 3.14 */
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Arrays as Table Values}

As well as a single numbers (or characters or pointers), tables can
also store 1-dimensional arrays of numbers (or characters or pointers).%%%
\footnote{%%%
	 Note that the table makes (stores) a \emph{copy} of the array
	 you pass in, so it's somewhat inefficient to store a large array
	 (e.g.~a grid function) this way.  If this is a problem, consider
	 storing a \texttt{CCTK\_POINTER} (pointing to the array) in the table
	 instead.  (Of course, this requires that you ensure that the array still exists whenever that \texttt{CCTK\_POINTER} is used.)
	 }%%%

For example (continuing the previous example):
\begin{verbatim}
static const CCTK_INT a[3] = { 42, 69, 105 };
if (Util_TableSetIntArray(handle, 3, a, "my array") < 0)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't set integer array value in table!");

...

CCTK_INT blah[10];
int count = Util_TableGetIntArray(handle, 10, blah, "my array");
if (count < 0)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't get integer array value from table!");
/* now count = 3, blah[0] = 42, blah[1] = 69, blah[2] = 105, */
/*     and all remaining elements of blah[] are unchanged */
\end{verbatim}
As you can see, a table entry remembers the length of any array
value that has been stored in it.%%%
\footnote{%%%
	 In fact, actually \emph{all} table values are
	 arrays---setting or getting a single value is
	 just the special case where the array length is 1.
	 }%%%
{}

If you only want the first few values of a larger array, just pass
in the appropriate length of your array,
that's OK:
\begin{verbatim}
CCTK_INT blah2[2];
int count = Util_TableGetIntArray(handle, 2, blah2, "my array");
if (count < 0)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't get integer array value from table!");
/* now count = 3, blah2[0] = 42, blah2[1] = 69 */
\end{verbatim}
You can even ask for just the first value:
\begin{verbatim}
CCTK_INT blah1;
int count = Util_TableGetInt(handle, &blah1, "my array");
if (count < 0)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't get integer array value from table!");
/* now count = 3, blah1 = 42 */
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Character Strings}

One very common thing you might want to store in a table is a
character string.  While you could do this by explicitly storing
an array of \verb|CCTK_CHAR|, there are also routines
specially for conveniently setting and getting strings:
\begin{verbatim}
if (Util_TableSetString(handle, "black holes are fun", "bh") < 0)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't set string value in table!");

...
char buffer[50];
if (Util_TableGetString(handle, 50, buffer, "bh") < 0)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't get string value from table!");

/* now buffer[] contains the string "black holes are fun" */
\end{verbatim}

\verb|Util_TableGetString()| guarantees that the string is
terminated by a null character (`\verb|\0|'), and also returns an
error if the string is too long for the buffer.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Convenience Routines}

There are also convenience routines for the common case of setting
values in a table based on a string.

For example, the following code sets up exactly the same table as the
example in Section \ref{Tables_Simple_Example}:

\begin{verbatim}
#include <util_Table.h>

/* create a table and set some values in it */
int handle = Util_TableCreate(UTIL_TABLE_FLAGS_DEFAULT);
if (handle < 0)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't create table!");

/* try to set some table entries */
if (Util_TableSetFromString(handle, "two=2 pi=3.14") != 2)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't set values in table!");
\end{verbatim}

There is also an even higher-level convenience function
\verb|Util_TableCreateFromString()|: this creates a table with the
case insensitive flag set (to match Cactus parameter file semantics),
then (assuming no errors occurred) calls \verb|Util_TableSetFromString()|
to set values in the table.

For example, the following code sets up a table (with the case insensitive flag
set) with four entries: an integer number ({\tt two}), a real number ({\tt
pi}), a string ({\tt buffer}), and an integer array with three elements ({\tt
array}):

\begin{verbatim}
#include <util_Table.h>

int handle = Util_TableCreateFromString(" two    = 2 "
                                        " pi     = 3.14 "
                                        " buffer = 'Hello World' "
                                        " array  = { 1 2 3 }");
if (handle < 0)
        CCTK_WARN(CCTK_WARN_ABORT, "couldn't create table from string!");
\end{verbatim}

Note that this code passes a single string to
\verb|Util_TableCreateFromString()|%%%
\footnote{C automatically concatenates
adjacent character string constants separated only by whitespace.}, 
which then gets parsed into key/value pairs, with the key separated from its
corresponding value by an equals sign.

Values for numbers are converted into integers ({\tt CCTK\_INT}) if possible
(no decimal point appears in the value), otherwise into reals ({\tt CCTK\_REAL}).
Strings must be enclosed in either single or double quotes. String values in
single quotes are interpreted literally, strings in double quotes may contain
character escape codes which then will be interpreted as in C.
Arrays must be enclosed in curly braces, array elements must be single numbers
of the same type (either all integer or all real).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Table Iterators}
\label{sect-UtilityRoutines/tables/table-iterators}

In the examples up to now, the code, which wanted to get values from
the table, knew what the keys were.  It's also useful to be able to
write generic code which can operate on a table without knowing the
keys.  ``Table iterators'' (``iterators'', for short) are used for this.

An iterator is an abstraction of a pointer to a particular table entry.
Iterators are analogous to the \verb|DIR *| pointers used by the POSIX
\verb|opendir()|, \verb|readdir()|, \verb|closedir()|, and similar
functions, to Perl hash tables' \verb|each()|, \verb|keys()|,
and \verb|values()|, and to the C++ Standard Template Library's
forward iterators.

At any time, the entries in a table may be considered to be in some
arbitrary (implementation-defined) order; an iterator may be used to
walk through some or all of the table entries in this order.  This
order is guaranteed to remain unchanged for any given table, so long
as no changes are made to that table, \ie{} so long as no
\verb|Util_TableSet*()|, \verb|Util_TableSet*Array()|,
\verb|Util_TableSetGeneric()|, \verb|Util_TableSetGenericArray()|,
\verb|Util_TableSetString()|, or \verb|Util_TableDeleteKey()| calls
are made on that table (making such calls on other tables doesn't
matter).  The order may change if there is any change in the table,
and it may differ even between different tables with identical key/value
contents (including those produced by \verb|Util_TableClone()|).%%%
\footnote{%%%
	 For example, if tables were implemented by hashing,
	 the internal order could be that of the hash buckets,
	 and the hash function could depend on the internal
	 table address.
	 }%%%
{}

Any change in the table also invalidates all iterators pointing
anywhere in the table; using any such iterator is an error.
Multiple iterators may point into the same table; they all use the
same order, and (unlike in Perl) they're all independent.

The detailed function description
in the Reference Manual
for \verb|Util_TableItQueryKeyValueInfo()| has an example of
using an iterator to print out all the entries in a table.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Multithreading and Multiprocessor Issues}

At the moment, the table functions are \emph{not} thread-safe
in a multithreaded environment. 
%% However, this should change in
%%the not-too-distant future: then all the table functions will default
%to being thread-safe.  That is, user code will be able call these
%%functions concurrently from multiple threads, with the table functions
%%automatically doing any necessary locking.%%%
%%\footnote{%%%
%	 For the implementation, this means that we will need a
%	 reader/writer lock for each table and for each iterator:
%	 any number of threads will be able to concurrently read
%	 the data structure, but any write will require exclusive
%	 access.
%	 }%%%
%{}  (We may add a flags-word bit to suppress this for maximum
%performance if you know you won't be making concurrent calls from
%multiple threads.)

Note that tables and iterators are process-wide, i.e. all
threads see the same tables and iterators (think of them as like the
Unix current working directory, with the various routines which modify
the table or change iterators acting like a Unix \verb|chdir()| system
call).

In a multiprocessor environment, tables are always processor-local.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Metadata about All Tables}

Tables do not \emph{themselves} have names or other
attributes.  However, we may add some special
``system tables'' to be used by Cactus itself to store this sort of
information for those cases where it's needed. For example, we may add support for a
``checkpoint me'' bit in a table's flags word, so that if you want a
table to be checkpointed, you just need to set this bit.
In this case, the table will probably get a system generated name in
the checkpoint dump file.  But if you want the table to have some
other name in the dump file, then you need to tell the checkpointing
code that, by setting an appropriate entry in a checkpoint table.
(You would find the checkpoint table by looking in a special
``master system table'' that records handles of other interesting tables.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{cactuspart}