## http://www.cactuscode.org/Development/Specs/KeyValueLookup.txt ## $Id: KeyValueLookup.txt,v 1.4 2001/10/26 12:54:54 rideout Exp $ Key Value Look-up Tables ------------------------ Author: Jonathan Thornburg, assistance from Tom Goodale, Thomas Radke Date: September-October 2001 Version: This is version 4 of the proposal Motivation ---------- Various Cactus functions need to pass information through a generic interface. Right now we use a collection of ad-hoc means to do this, and we often have trouble passing "extra" information that wasn't anticipated in the original design. For example, for interpolation we encode the order of the interpolant into its character string name, and I recently proposed adding an extra argument for an "operation code" for each output array. For elliptic solvers I don't think we have a really good way to pass various parameters the solver might want. This proposal is for generic key/value lookup-table objects, to provide a clean solution to these and other problems. It is planned for this to be implemented soon after this proposal is complete (October-November 2001). Proposal -------- Basically, a lookup-table object is modelled on a Perl hash table. Keys are C-style null-terminated character strings, with the character '/' reserved for future expansion (think of hierarchical tables for storing tree-like data structures). Values are 1-dimensional arrays any of the usual Cactus data types POINTER = void * = generic data pointer FN_POINTER = void (*)() = generic function pointer CHAR = char = single character HANDLE = typedef to int = generic Cactus handle INT = CCTK_INT INT2, INT4, INT8 REAL = CCTK_REAL REAL4, REAL8, REAL16 COMPLEX = CCTK_COMPLEX COMPLEX8, COMPLEX16, COMPLEX32 A string can be stored by treating it as a 1-dimensional array of CHAR (There's an example of this below). We have come up with the following user interface: (I only show the Get/Set functions for REAL, but there would actually be parallel functions for each of the data types.) (There would also be both C and Fortran versions of all the functions; for Fortran compatability we have placed all character string arguments at the end of the argument lists.) /* create an empty lookup table, return a handle to it, or -ve for error */ /* flags argument is inclusive-or (= sum) of various flag values */ /* (#define in some header file, maybe "cctk_Table.h") */ /* this would specify (eg) whether or not keys are case-sensitive */ int handle = Util_TableCreate(int flags); /* query flags for a table */ /* return flags if table exists, -ve for error */ int flags = Util_TableQueryFlags(int handle); /* set the value for the specified key to be (a copy of) * /* an array of nelem REALs */ /* return 1 for key already existed (old value was overwritten), */ /* 0 for key did not already exist, */ /* -ve for error */ /* n.b. this is really a set of functions, one for each Cactus datatype */ int status = Util_TableSetReal(int handle, int nelem, const CCTK_REAL buffer[], const char *key); /* convenience function for common special case of Util_TableSetReal(): */ /* set the value for the specified key to be the specified REAL value */ /* return 1 for key already existed (old value was overwritten), */ /* 0 for key did not already exist, */ /* -ve for error */ /* n.b. this is really a set of functions, one for each Cactus datatype */ int status = Util_TableSet1Real(int handle, CCTK_REAL value, const char *key); /* convenience function for common special case */ /* of Util_TableCreate() and Util_TableSet1{Int,Real,String}(): */ /* create a new table and put INT/REAL/STRING values into it from a string */ /* using parameter-file semantics (i.e. not case-sensitive) */ /* probably set "autodelete at next Cactus time step" flag bit */ /* return handle to table, or -ve for error */ int handle = Util_TableCreateFromString(const char buffer[]); /* query metadata (value's type and number of elements) for specified key */ /* return 1 for key exists, */ /* 0 for key does not exist, */ /* -ve for error */ int status = Util_TableQueryKey(int handle, int *type, int *nelem, const char *key); /* query total number of keys in the table */ /* return number of keys (>= 0), -ve for error */ int nelem = Util_TableQueryNKeys(int handle); /* query maximum key length in the table */ /* return maximum key length (>= 0), -ve for error */ int nelem = Util_TableQueryMaxKeyLength(int handle); /* get (a copy of) the value for the specified key */ /* (or at least as much of it as will fit) into the user's buffer */ /* return number of values copied, /* -ve for error (including the case that this key's value */ /* is actually an array of size > nelem) */ /* n.b. this is really a set of functions, one for each Cactus datatype */ int status = Util_TableGetReal(int handle, int nelem, CCTK_REAL buffer[], const char *key); /* convenience function for common special case of Util_TableGetReal(): */ /* get the (scalar) value for the specified key */ /* return 1 (= number of values copied) for ok, */ /* -ve for error (including the case that this key's value */ /* is actually an array of size not equal to 1) */ /* n.b. this is really a set of functions, one for each Cactus datatype */ int status = Util_TableGet1Real(int handle, CCTK_REAL *buffer, const char *key); /* delete this key from the table */ /* return 1 for key existed before this call, */ /* 0 for key did not exist before this call, */ /* -ve for error */ int status = Util_TableDeleteKey(int handle, const char *key); /* destroy the table */ /* return 0 for ok, -ve for error */ int status = Util_TableDestroy(int handle); We have also designed the following interface to allow generic code to walk through any table without knowing what the keys are. An iterator is an abstraction of a pointer to a particular table entry. Iterators are analogous to the Unix current working directory, to database cursors, and to the DIR * pointers used by the POSIX opendir()/readdir()/closedir()/etc functions. Inserting a new key, or deleting any existing key, invalidates all iterators for the table (i.e. using any such iterator is an error, which may result in anything from a core dump to garbage results). An iterator may be used to walk through some or all of the table entries; all iterators define the same ordering of the table entries. This ordering is arbitrary (i.e. if we use hash tables it may be the internal ordering), and may change if a new key is inserted or any existing key is deleted (i.e. it's ok for these operations to reorganize the table or rebalance a binary tree). /* create an iterator */ /* caller supplies handle to an existing table */ /* return handle to iterator, or -ve for error */ int ihandle = Util_TableIteratorCreate(int handle); /* query whether iterator is non-null */ /* return 1 for iterator points to some table entry, */ /* 0 for iterator is in "null-pointer" state, */ /* -ve for error */ int status = Util_TableIteratorQueryIsNonNull(int ihandle); /* query which table an iterator points into */ /* return table handle, /* -ve for error */ int handle = Util_TableIteratorQueryTable(int ihandle); /* query metadata (key length, key, value type and number of elements) */ /* pointed to by iterator */ /* return number of characters of key copied for ok, -ve for error */ int status = Util_TableIteratorQuery(int ihandle, int keybuflen, char keybuf[], int *keylen, int *type, int *nelem) /* ++iterator in internal order */ /* return 0 for ok, */ /* 1 for advance-past-last-entry */ /* (sets iterator to "null-pointer" state) */ /* -ve for error */ /* i.e. return value is Util_TableIteratorIsNull(ihandle) */ int status = Util_TableIteratorAdvance(int ihandle); /* reset iterator to starting entry in internal order */ /* return 0 for ok, -ve for error */ int status = Util_TableIteratorReset(int ihandle); /* set iterator to "null-pointer" state */ /* return 0 for ok, -ve for error */ int status = Util_TableIteratorSetToNull(int ihandle); /* destroy an iterator */ /* return 0 for ok, -ve for error */ int status = Util_TableIteratorDestroy(int ihandle); Discussion ---------- A typical use of this interface might be to pass information to the new generalized interpolator interface I (JT) am working on: /* simple case: just interpolate some gridfns with default options */ /* ==> create table from literal string, */ /* automagic cleanup at end of cactus time step */ int blah = CCTK_GInterpGV(..., Util_TableCreateFromString("order=3"), ...) /* more complicated case: also tell the interpolator about mask gridfn */ /* so it can avoid trying to use masked-off data */ /* ==> store multiple keys in table, explicitly delete table when done */ int order = 3; int mask_gridfn_index = CCTK_VarIndex("emask"); int handle = Util_TableCreate(CCTK_TABLE_DEFAULT); Util_TableSet1Int(handle, order, "order"); Util_TableSet1Int(handle, mask_gridfn_index, "mask_gridfn_index"); int blah = CCTK_GInterpGV(..., handle, ...) Util_TableDestroy(handle); /* really fancy case: also have interpolator take some derivatives */ /* ==> also pass an array of operation codes to the interpolator */ #include "cctk_GInterp.h" int order = 3; int smoothing = 2; int mask_gridfn_index = CCTK_VarIndex("emask"); int opcodes[] = {GINTERP, GINTERP_DX,GINTERP_DY,GINTERP_DZ}; #define N_OPCODES (sizeof(opcodes)/sizeof(opcodes[0])) int handle = Util_TableCreate(CCTK_TABLE_DEFAULT); Util_TableSet1Int(handle, order, "order"); Util_TableSet1Int(handle, smoothing, "smoothing"); Util_TableSet1Int(handle, mask_gridfn_index, "mask_gridfn_index"); Util_TableSetInt(handle, N_OPCODES, opcodes, "opcodes"); int blah = CCTK_GInterpGV(..., handle, ...) Util_TableDestroy(handle); The key point is that CCTK_GInterpGV() can define new parameters without requiring all calls on it to be changed -- it is always passed a table handle, and it can look in the table for whatever parameters it needs (supplying defaults if they're not present). Once the table functionality is in Cactus, we may want to revisit various existing Cactus interfaces to see if they should take tables for various parameters. For instance the httpd stuff might be able to use it (especially if we extend tables to heirarchical keys). Multithreading ============== In a multithreaded environment, all the table functions are thread-safe. That is, user code may call these functions concurrently from multiple threads, and the thread routines will take care of any necessary locking. Note that tables and iterators will still be 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 chdir() system call. For the implementation, this means that we need a reader/writer lock for each table and for each iterator: any number of threads can concurrently read the data structure, but any write must have exclusive access. Metadata about All Tables ========================= We have decided that tables do not *themselves* have names or other attributes. However, there will probably be some special tables used by Cactus itself to store this sort of information for those cases where it's needed. For example, if you want a table to be checkpointed, it will probably suffice to just set the "checkpoint me" bit in the table's flag word. 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 checkpoing table by looking in a special "system table" that records handles of other interesting tables.) For example: #include "cctk_Table.h" /* maybe this is already included in "cctk.h" */ int checkpoint_table_handle = Util_TableQuery1Int(CCTK_SYSTEM_TABLE_HANDLE); Util_TableSetChar(checkpoint_table_handle, strlen("my.table.name"), "my.table.name"); (This example also shows storing a string as an array of characters.)