HLA Standard Template Library

[Randall Hyde]

Hi All,
I'm currently working on a set of library modules that mimic the capabilities of the C++ Standard Template Library (STL). I've currently got vectors working and I'm implementing Deques at this point. I'll probably post something to webster when I get vectors, deques, and lists functioning.

For those who are unfamiliar with the C++ STL, what the STL does is provide a set of "templates" (macros) that expand to class types and their associated methods based on some parameters you supply. For example, the vector template lets you create dynamic arrays of data (which automatically adjust their size at run-time) of any type. For example, you can create a vector of bytes with a declaration like the following:

type
   byteVector: stl.vector( byte );

and you can also create a vector of int32 objects thusly

type
   int32Vector: std.vector( int32 );

or even a vector of some user-defined type:

type
  myTypesVector: std.vector( myType );

The vector template not only creates a type you can use to allocate vector objects of the specified type, it also creates all the methods you can use to manipulate objects of that type. For example, with vector objects you can insert, delete, and access elements of the vector. Here's the list of the methods that the vector template supports:

//////////////////////////////////////////////////////////////////////////////
//
// The vector type.
//
// This is a dynamic array (single dimension) whose size can change
// as needed at runtime.
//
// Arguments:
//
//  vectorType-
//   data type for each element in the vector
//
//  specificCapabilities-
//   Enabled/disabled capabilities for this vector (used to alter
//   the default settings for a vector).
//
//
// Produces:
//
//  Three different types:
//
//   vectorType-
//    a class for the specified vector type.
//
//   vectorType_cursor-
//    a type for cursors that point into the vectorType class.
//
//   p_vectorType-
//    a pointer to the vectorType class.
//
//  (Note: substitute the actual parameter name for "vectorType"
//   in each of the above)
//
// Publically accessible fields in the class created by this macro
// (these fields should be treated as read-only):
//
//  isSTL_c-
//   a constant, set to true, that you can use @define on to
//   determine that this type is an STL type.
//
//  capabilities_c (compile-time)
//  capabilities (run-time)
//   a bit-mapped array of booleans that specify the capabilities of
//   a vector object. Test for the presence of a capability by ANDing
//   with one of the *_c constants.
//
//      typeName-
//   a string holding the vectorType type name.
//
//      containerName-
//   the string "vector".
//
//
// procedures, methods, and iterators:
//
//      procedure create( numElements:uns32 );
//   Constructor for the vector class. If called with the class
//   name (e.g., symbol.create(n)) then it will create the object
//   on the heap and return a pointer to the new "symbol" object
//   in the ESI register. If called with an actual "symbol" variable,
//   this constructor initializes that variable.
//
//   Note: if the underlying vector type is a class type, this
//   constructor does *not* call the create procedure for each
//   of the underlying elements in the vector. That is the caller's
//   responsibility.
//
//      method destroy;
//   Destructor for the vector template class. Deallocates the storage
//   associated with the object. Note that if the underlying elements
//   are a class type, this destructor does not call the destructor
//   for each of those elements. You must explicitly destroy them
//   prior to calling this destructor.
//
//  method getSize;
//   returns the number of vector elements in EAX. Operates in O(1) time.
//
//      method getAllocSize; @returns( "eax" );
//   Returns the number of bytes allocated for the data in the
//   vector (in EAX). Operates in O(1) time.
//
//      method getDataSize; @returns( "eax" );
//   Returns the number of bytes allocated for the data in actual
//   use in the vector. Operates in O(1) time.
//
//      method clear;
//   Removes all elements from the vector. Operates in O(1) time.
//
//      iterator forEachElement;
//   Iterates through the vector from beginning to end and on each
//   iteration returns a pointer to the current vector element in
//   the EAX register.
//
//      iterator rForEachElement;
//   As above, except it iterates through the vector from the end
//   back to the beginning.
//
//      method appendRef( var toAppend:vectorType );
//   Appends the object "toAppend" (passed by reference) to the end
//   of the vector. Operates in O(1) time.
//
//      method appendVal( toAppend:vectorType );
//   Appends the object "toAppend" (passed by value) to the end
//   of the vector. Operates in O(1) time.
//
//  method prependRef( var toPrepend:vectorType );
//   Inserts the object "toPrepend" at the beginning of the list.
//   toPrepend is passed by reference (great for large vectorType
//   objects). Operates in O(n) time.
//
//  method prependVal( toPrepend:vectorType );
//   Inserts the object "toPrepend" at the beginning of the list.
//   toPrepend is passed by value (great for smaller vectorType
//   objects). Operates in O(n) time.
//
//      method insertRef( var toInsert:vectorType; posn:uns32 );
//   Inserts the object "toInsert" in front the the posnTH object.
//   toInsert is passed by reference (great for large vectorType
//   objects). Operates in O(n) time.  Note that items are indexed
//   starting with position zero. If posn is greater than the
//   number of vector elements, this method appends the object
//   to the end of the vector.
//
//      method insertVal( toInsert:vectorType; posn:uns32 );
//   Inserts the object "toInsert" in front the the posnTH object.
//   toInsert is passed by value (great for small vectorType
//   objects). Operates in O(n) time.  Note that items are indexed
//   starting with position zero. If posn is greater than the
//   number of vector elements, this method appends the object
//   to the end of the vector.
//
//      method remove( n:uns32 );
//   Removes the object at posn "n" from the vector. If n is greater
//   than the number of vector elements, this method has no effect.
//   Operates in O(n) time.
//
//      method remove_first;
//   Removes the first element from the vector.
//   Operates in O(n) time.
//
//      method remove_last;
//   Removes the last element from the vector.
//   Operates in O(1) time.
//
//  Cursor methods:
//   Note: you should not assume that there is a correspondance
//   between cursors and pointers to vector elements. Though this
//   may be the actual implementation, subclassed vector types
//   may not guarantee this same implementation. Treat cursors as
//   opaque (private) types that are used internally by vector methods.
//
//      method nextCursor( var cursor:cursorType );
//   Modifies the cursor object passed by reference so that it
//   points at the next element of the vector (relative to where
//   it currently points). If this would advance the cursor beyond
//   the end of the vector, this method sets "cursor" to point at
//   just beyond the end of the vector (i.e., endCursor). Operates
//   in O(1) time.
//
//      method prevCursor( var cursor:cursorType );
//   Modifies the cursor object passed by reference so that it
//   points at the previous element of the vector (relative to where
//   it currently points). If this would advance the cursor before
//   the beginning of the vector, this method sets "cursor" to point at
//   the start of the vector (i.e., beginCursor). Operates in O(1)
//   time.
//
//      method beginCursor( var cursor:cursorType );
//   Points the cursor object passed by reference at the start of
//   the vector. Operates in O(1) time.
//
//      method endCursor( var cursor:cursorType );
//   Points the cursor object passed by reference to the point
//   just beyond the end of the vector. Operates in O(1) time.
//
//      method front; @returns( "eax" );
//   Returns a cursor value in EAX that corresponds to the start
//   of the vector. Operates in O(1) time.
//
//      method back; @returns( "eax" );
//   Returns a cursor value in EAX that corresponds to the end
//   of the vector (points beyond the end of the vector). Operates
//   in O(1) time.
//
//      method atBack( cursor:cursorType ); @returns( "@z" );
//   Compares the cursor passed by reference against the end of
//   the vector and sets the Z flag if the cursor is at the end
//   of the vector. Operates in O(1) time.
//
//      method atFront( cursor:cursorType ); @returns( "@z" );
//   Compares the cursor passed by reference against the beginning
//   of the vector and sets the Z flag if the cursor as at the
//   start of the vector. Operates in O(1) time.
//
//      method at( cursor:cursorType in eax ); @returns( "eax" );
//   Returns a pointer (in EAX) to the vector element data referenced by
//   the cursor passed by reference. You should use this method to
//   convert a cursor to a data element pointer and not assume that
//   cursors and data element pointers are equivalent. Operates in
//   O(1) time.
//
//      method getAt( cursor:cursorType; var dest:vectorType );
//   Copies the data at the vector element referenced by the cursor
//   you pass as the first argument to the location specified by
//   the second argument. Operates in O(1) time relative to n (the
//   number of vector elements).
//
//      method insertAtVal( toInsert:vectorType; cursor:cursorType );
//   Inserts the value "toInsert" before the item referenced by
//   the cursor passed as the second argument. Value (toInsert) is
//   passed by value, making this routine good for small vectorType
//   objects. Operates in O(n) time.
//
//      method insertAtRef( var toInsert:vectorType; cursor:cursorType );
//   Inserts the value "toInsert" before the item referenced by
//   the cursor passed as the second argument. Value (toInsert) is
//   passed by reference, making this routine good for large vectorType
//   objects. Operates in O(n) time.
//
//      method removeAt( cursor:cursorType );
//   Removes the vector entry referenced by the cursor passed
//   as the argument. Operates in O(n) time.
//
//      method getRef( n:uns32 in eax ); @returns( "eax" );
//   Computes and returns the address (in EAX) of the nTH element
//   in the vector. Operates in O(1) time.
//
//      method getVal( n:uns32; var dest:vectorType );
//   Copies the value in the nTH vector element to the location
//   specified by the second parameter.
//
//  method swapObj( var obj:symbol );
//   Swaps the current vector object (THIS) with the one specified
//   by the parameter. This routine operates in O(1) time and is
//   very fast.
//
//  method swapElements( var first:vectorType; second:vectorType );
//   Swaps two vector elements (not necessarily in the same vector).
//   Operates in O(1) time.
//
//      method isEqual
//      (
//       var left:vectorType;
//       var right:vectorType
//      );  @returns( "al" );
//
//   Compares two vectorType objects that are passed by reference
//   and returns AL=1 (and clears the Z flag) if they are equal.
//     
//      method isLess
//      (
//       var left:vectorType;
//       var right:vectorType
//      );  @returns( "al" );
//
//   Compares two vectorType objects that are passed by reference
//   and returns AL=1 (and clears the Z flag) if left < right.
//     
//     
//      method isLessEqual
//      (
//       var left:vectorType;
//       var right:vectorType
//      );  @returns( "al" );
//
//   Compares two vectorType objects that are passed by reference
//   and returns AL=1 (and clears the Z flag) if left <= right.
//
//  Note: you can simulate <>, >, and >= by inverting the value in AL
//  upon return from the above three routines.     
//     
//      method toString; @external( outputFunc[0] );
//   (Optional implementation) Converts an object of type "symbol"
//   to a string for use by output routines like stdout.put.
//


Note that the vector template provides complete control over which methods you want to implement on a type by type basis. That is, you can create a vector type that does not support comparisons (isEqual, isLess, isLessEqual) if you don't need this functionality.

Oh well, back to work.
Cheers,
Randy Hyde