The SDL language and the C++ binding to SDL support indices through a simple interface to the underlying Shore Storage Manager (SSM) index facility. Indices are declared as attributes of SDL interfaces, using the template style notation index<keytype,valtype> for the type of the attribute.
With the alpha release, the types of keys and values are limited, but we plan to generalize this. Keys can be strings, enumerations, any of the integer types, floating point (or double), BOOL, OCTET, CHAR, ANY. (See the Shore Data Language Reference Manual ). Values have any of the types that keys can have, with the addition of references ( REF<type> ).
Index operations are performed through member function calls on index attributes. The index facility allows users to insert key/value pairs into an index, to retrieve the set of key-value pairs stored in the index for some range of keys, and to delete specific key-value pairs. Keys and values within a particular index instance will each range over some fixed type; usually, the key will be a numeric type or string, and the value will be a reference to some SDL object type.
The underlying Shore Storage Manager support for indices orders keys based on bitwise binary lexical ordering. This ordering works well for the primitive integral and floating point types on the Sparc architecture machines supported by the alpha release, and for strings. Care must be taken if composed types such as struct s are used as keys; the ordering used may be problematic. There is currently no way to specify a user defined ordering. Similarly, uniqueness of key-value pairs is dependent on equality comparison of values inserted for equal keys; this comparison for equality is based on strict bitwise equality.
Indices in SDL are declared as attributes within objects with a declaration of the form
interface a {
public:
attribute index<keytype,valtype> varname;
// other attributes and methods
};
The index<keytype,valtype> type declarator may be used in other contexts, e.g. as an element of structs and arrays, but it is best to restrict its use to the top level attributes of interfaces. At the C++ language level, an interface attribute looks like a C++ template class instantiation, with visible fields and member functions as listed below.
template <class keytype, class valtype>
class Index
{
public:
// externally visibly names for the type parameters
typedef keytype KeyType;
typedef valtype ValType;
// initialize an index and set type of index.
init(IndexKind kind) const;
// insert a key-value pair
int insert(keytype key,valtype val) const;
// remove a key-value pair
int remove(keytype key,valtype val) const;
// remove all key-value pairs with a given key
int removeall(keytype key) const;
// find all key-value pairs with a given key
find(keytype key, valtype & elt) const;
};
If an object type (that is, the name of an SDL interface type) is used as the value type parameter in the declaration of an index in SDL, the object is always inserted by reference; that is, a ref to the object is stored as the value, not a copy of its contents. The member functions on index attributes are all declared "const" because they do not modify the object containing the attribute; the underlying index modified, of course, but the object containing the attribute is not.
After an object containing an index attribute is created, the index must be initialized using the init method of the index attribute. Allowable values for the single parameter to the init function, which determines the type of SSM index used, are the elements of the enumeration type IndexKind, shown below.
enum IndexKind { LHash, BTree, UniqueBTree, RTree, RDTree }
The following example illustrates the creation of an index and insertion of values into the index. Here, we assume the existence of an array of persistent pointers and we create an index which will associate each element of the array with its position in the array.
// SDL language declaration
module index_vars {
interface a {
// declaration of an object type we wish to provide an index for.
// ...
public:
attribute long int_val;
};
interface ind_obj {
public:
attribute index<long,a> ind;
}
}
// C++ binding source fragment.
#include "index_vars.sdl.h" // generated by "sdlcxx index_vars"
const int n_elts = 100;
extern REF(Pool) MyPool; // storage pool initialized elsewhere.
REF(index_obj) MyIndex;
// creation of index object and initialization of index
// init_stuff
create_index()
{
MyIndex = new(MyPool) ind_obj;
MyIndex->ind.init(BTree);
}
void
add_elts(int n) // create n objects of type a;
// insert refs to these objects into the index
{
int i;
REF(a) aref;
for (i=0; i<n; i ++)
{
aref = new(MyPool) a;
aref.update->int_val = i;
MyIndex->ind.insert(i,aref);
}
}
Elements could be deleted from the index through similar calls to the remove member function.
If there is only one key-value pair in an index for some key, the value associated with that key may be found using the find member function of the index attribute. If more than one key-value pair exists for the particular key, the result is undefined.
Index lookups which require more that one key-value pair to be returned are more complicated. An index_iter class template is provided to implement retrieval of the set of key-value pairs associated with some range of keys. This template implements a simple iteration primitive which allows the programmer to iterate over the sequence of key-value pairs that are the result of a particular index lookup operation. The iterator template class contains public "cursor" data fields which indicate the "current" key-value pair in the set of such pairs resulting from the lookup and a "next" member function which is used to move the cursor to the next element of the set. The class is initialized through parameters to its constructors; range bounds may also be separately specified by SetUB and SetLB member functions to set the upper and lower bounds of the retrieve range, respectively. Note that range queries using upper and lower bounds are meaningful only for b-tree indices; hash indices do not support retrieves where the upper and lower bounds differ.
The external interface to the index_iter class template is described by the annotated class template declaration given below: the actual declaration contained in the SDL include file is somewhat more complicated due to the use of inheritance, and due to object values being stored by reference while other value types are copied.
// the index_iter class is parameterize by the type of the index
// it is used to iterate over; the key and value types are determined
// from the class parameter of the template by use of nested type
// name scoping.
template <class ind_t>
class index_iter
{
public:
bool_t eof;
ind_t::KeyType cur_key;
ind_t::ValType cur_val;
index_iter(const ind_t &idx); // used if upper and lower bounds set
// separately.
index_iter(const ind_t &idx,ind_t::KeyType l, ind_t::KeyType u)
// sets upper and lower bounds
SetLB(ind_t::KeyType b);
SetUB(ind_t::KeyType b);
next();
~index_iter();
};
NP
The
index_iter
iterator class must be used in conjunction with an
index attribute of an SDL object, and the type parameter of the iterator
class must match the type of the index attribute. The type of the
attribute should be determined with the g++ typeof operator.
The following function illustrates the retrieval of a set of key-value
pairs from the index we used above.
The general idiom, as illustrated
below, is to use a for loop to iterate over the sequence of values
that result from a retrieve operation, accessing the public data
members of the index_iter iterator class to get the key and
pointer value for each particular index entry in the sequence.
// in an SDL definition file
interface ind_obj {
public:
attribute index<long,long> int_to_int;
// attribute maps integers to integers via an index
};
// in a .C file
REF(ind_obj) ind_ref;
printvals(int lower, int upper)
{
index_iter<typeof(ind_ref->int_to_int)>
range_retr(ind_ref->int_to_int,lower,upper);
for (range_retr.next(); !range_retr.eof; range_retr.next())
{
printf("key value %d element value %d\n",
range_retr.cur_key, range_retr.cur_val);
}
}