Tables Module (tables.hhf)

The HLA Tables module provides support for associative lookup tables. You can view a table as an array of objects that uses a string index rather than an integer index. The HLA table routines use a hash table to rapidly look up the specified string in the table and return a pointer to the specified element in the table.

Note: Because of their high-level nature, this document only provides high-level calling sequences for the table management procedures. Low-level calls are possible, but are generally so painful that they aren’t worth making. If you are dead set on making low-level calls to table class methods and procedures, please consult the HLA documentation for directions on how this is done.

A Note About Thread Safety: The HLA standard library table module does not attempt to synchronize thread access to the table data structures. If you are going to be manipulating tables from multiple threads, it is your responsibility to ensure that the threads use properly synchronized access to this resource. This issue may be addressed in a future version of the standard library, for now it is your responsibility to ensure correct operation in a multi-threaded environment.

### The Tables Module

To use the table class and methods in your application, you will need to include one of the following statements at the beginning of your HLA application:

#include( “tables.hhf” )

or

#include( “stdlib.hhf” )

### The Table Class

The HLA stdlib tables module consists of two classes: the table class and the node class. To create a table object, you first create a new node type by overloading the node class and then you can use the table class’ methods to manipulate a table of these nodes.

To begin with, each element (called a node) in an HLA table uses the following structure:

tableNode_t:

record

link: pointer to tableNode_t;

Value: dword;

id: string;

endrecord;

The link field is for internal use by the table management routines; you should never modify its value.

The id field points at the string that indexes the current node in the table. You may use the value of this string, but you must never modify the characters in the string. The hashing function utilitized by the table management code will not be able to locate this string if you change the characters in the string after entering the string into the table.

The Value field is reserved for your own purposes. Other than initializing this field to zero when they create a table entry, the table management routines ignore this field. If you wish to associate data with an entry in the table you can either store the data directly in this field (if the data is four bytes or less), or you can allocate storage for the data outside the table entry and store a pointer to the data in this field (remember, pointers are four-byte objects).

The table_t data type is a class that provides the following methods and procedures:

procedure table_t.create( HashSize:uns32 );

method table_t.destroy( FreeValue:procedure );

method table_t.getNode( id:string );

method table_t.lookup( id:string );

iterator table_t.item();

Like most HLA classes, the table_t class provides a constructor named table_t.create and a destructor named table_t.destroy. The class also provides two additional methods and an iterator, table_t.getNode, table_t.lookup, and table_t.item. Although there doesn’t appear to be much to this class, these few routines provide considerable power.

procedure table_t.create( HashSize:uns32 );

The create procedure, being a static procedure constructor, is typically called in one of two fashions:

When dynamically allocating a table_t object on the heap and storing the pointer away into a variable whose type is "pointer to table_t":

table_t.create( some_constant );

mov( esi, PtrToTableVar );

When you’ve got a var or static variable object (named table_var_name in this example), you can use code like the following to construct the table_t object:

table_var_name.create( some_constant );

The table_t constructor requires a single uns32 parameter. This value should be approximately the number of entries (elements) you expect to insert into the table. This value does not have to be exact. Anytime you want to add a new element to the table, you may do so; there are no limitations (other than available memory) on the number of elements in a table. However, this parameter value is a hint to the table management routines so it can allocate a hash table of an appropriate size so that (1) access to the table elements is fast, and (2) the hash table doesn’t waste an inordinate amount of space. If the hint value you supply is too small, the table lookup routines will still function properly, but they will run a little slower. If the hint value you supply is too large, the table management routines will waste some memory.

HLA high-level calling sequence example:

table_t.create( 128 );

mov( esi, someTableVarName );

SomeStaticTableVarName.create( 256 );

method table_t.destroy( FreeValue:procedure );

The table_t.destroy method frees up the data in the table. This routine deallocates the storage associated with the hash table, it deallocates the storage associated with each node in the table, and it deallocates the storage associated with each string (the id field in record tableNode_t above) in the table. Unfortunately, the table_t.destroy method doesn’t know anything at all about the Value field of each node. If this is just some simple data, then the destructor probably doesn’t need to do anything with the Value field. On the other hand, if Value is a pointer to some other data that was dynamically allocated, destroy should probably deallocate the storage associated with the Value field. Unfortunately, destroy has no apriori knowledge about the Value field, so it cannot determine if (or how) it should deallocate storage associated with Value.

To resolve the problem above, table_t.destroy calls a user-defined function that is responsible for cleaning up the data associated with Value. You will notice that table_t.destroy has a single parameter: FreeValue. This parameter must be the address of a procedure whose job is to handle the destruction of the Value field. If no clean up is necessary, you must still provide the address of some routine. That routine should simply return without further activity.

Upon entry into the FreeValue procedure, the EBX register contains a pointer to the current tableNode_t record being deallocated. At this point, none of the other fields have been modified; in particular, the id field is still pointing at the string associated with the node. The FreeValue procedure may access the id field, but it must not deallocate the storage associated with this string. The table_t.destroy method takes care of that after FreeValue returns.

The "tabledemo.hla" file accompanying the HLA release gives another example of how you could use the FreeValue procedure. This code doesn’t deallocate any storage in this procedure (named PrintIt in this file), instead, it uses this call to dump the data associated with the node to the display when the table is freed.

HLA high-level calling sequence example:

// Dummy free routine, nothing to do:

procedure myFree; @noframe;

begin myFree;

ret();

end myFree;

.

.

.

table_t.create( 128 );

mov( esi, myTable );

.

.

.

myTable.destroy( &myFree );

method table_t.lookup( id:string ); @returns( “eax” );

The table_t.lookup method locates a node in the table. The string parameter specifies which node to find in the table. On return, EAX contains the address of the corresponding tableNode_t record in the table, if the specified node is present (that is, the node’s id field matches the string passed to table_t.lookup). If the node is not present in the table, then the table_t.lookup method returns NULL (zero) in the EAX register.

HLA high-level calling sequence example:

table_t.create( 16 );

mov( eax, tableVar );

.

.

.

tableVar.lookup( “someString” );

if( eax <> NULL ) then

stdout.put( “Found ‘someString’ in the table” nl );

else

stdout.put( “Did not find ‘someString’ in the table” nl );

endif;

method table_t.getNode( id:string ); @returns( “eax” );

The table_t.getNode method serves two purposes. First of all, it looks up the specified string value in the table. If it finds a node in the table corresponding to the string parameter, it returns a pointer to that (table_t.tableNode_t) node in the EAX register. If it does not find the string in the table, then it creates a new node and inserts the string into that new node; it also initializes the Value field to zero in this case. Note that table_t.getNode makes a copy (using str.a_cpy) of the string, it does not store the string pointer you pass directly into the id field. Upon return, EAX will point at the new node. Note that whether or not an existing node is present in the table, table_t.getNode will always return a pointer to the node associated with the specified string. It either returns a pointer to a pre-existing node or it returns the pointer to the new node.

If you want to insert a new node into the table and fail if the node already exists, you will need to first call table_t.lookup to see if the node previously exists (and fail if it does). You may then call table_t.getNode to insert a new node into the table. While it would be easy to add this functionality to the table_t class, it would be rarely used and probably isn’t needed.

HLA high-level calling sequence example:

table_t.create( 16 );

mov( eax, tableVar );

tableVar.getNode( “someString” ); // Insert “someString”

.

.

.

tableVar.getNode( “someString” ); // Retrieve ptr to “someString”

method table_t.getNode( id:string ); @returns( “eax” );

The table_t.item iterator yields each node in the table during the execution of the corresponding foreach loop. Note that table_t.item does not yield the nodes in any particular (discernable) order. However, it will yield each item in the list exactly once. The iterator returns with EAX pointing at a table_t.tableNode_t object.

HLA high-level calling sequence example:

table_t.create( 16 );

mov( eax, tableVar );

.

.

.

foreach tableVar.item() do

// Process node pointed at by EAX.

endfor;