TOC PREV NEXT INDEX

Put your logo here!


28 HLA Table Support (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.

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


 
	tableNode:
 
		record
 

 
			link:			pointer to tableNode;
 
			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 data type is a class that provides the following methods and procedures1:


 
procedure table.create( HashSize:uns32 ); 
 
method table.destroy( FreeValue:procedure ); 
 
method table.getNode( id:string ); 
 
method table.lookup( id:string ); 
 
iterator table.item();
 

 

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

table.create( HashSize:uns32 ); 
 

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

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


 
table.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 object:


 
table_var_name.create( some_constant );
 

 

The table 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.

table.destroy( FreeValue:procedure ); 
 

The table.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 above) in the table. Unfortunately, the table.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.destroy calls a user-defined function that is responsible for cleaning up the data associated with Value. You will notice that table.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 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.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.

table.lookup( id:string ); 
 

The table.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 record in the table, if the specified node is present (that is, the node's id field matches the string passed to table.lookup). If the node is not present in the table, then the table.lookup method returns NULL (zero) in the EAX register.

table.getNode( id:string ); 
 

The table.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.tableNode) 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.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.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 node2.

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.lookup to see if the node previously exists (and fail if it does). You may then call table.getNode to insert a new node into the table. While it would be easy to add this functionality to the table class, it would be rarely used and probably isn't needed.

table.item;
 

The table.item iterator yields each node in the table during the execution of the corresponding foreach loop. Note that table.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.tableNode object.

1The table class also has three data fields, HashMask, HashCnt, and HashTable, but these fields are considered private and you should never modify them.

2Of course, if there is a memory allocation error, getNode will not return but will raise an exception instead.



TOC PREV NEXT INDEX