General restructuring.

git-svn-id: http://svn.cactuscode.org/flesh/trunk@4548 17b73243-c579-4c4c-a9d2-2d5706c11dac

1 files changed, 415 insertions, 0 deletions

diff --git a/doc/UsersGuide/Appendices.tex b/doc/UsersGuide/Appendices.tex
index 2db45a31..a7904e1a 100644
--- a/doc/UsersGuide/Appendices.tex
+++ b/doc/UsersGuide/Appendices.tex
@@ -1174,6 +1174,421 @@ No other lines should be output by the script.
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
+\chapter{Utility Routines}
+
+\section{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.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{Key/Value Tables}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\subsection{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).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\subsection{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.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\subsection{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}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\subsection{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}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\subsection{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.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\subsection{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).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\subsection{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.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\subsection{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.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\subsection{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.)
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
 \chapter{Schedule Bins}
 \label{sec:Appendix.schedule_bins}