MAINSAIL Utilities User's Guide, Chapter 15

previous   next   top   contents   index   framed top   this page unframed

15. HSHMOD, Hash Lookup Utility

15.1. Overview

The MODULE HSHMOD (“HaSH MODule”) is a program utility, i.e., not a utility that is invoked from the MAINEX executive. Rather, it is a MODULE that can be called from a program.

HSHMOD maintains a symbol table implemented with a hash code retrieval algorithm for fast lookup. The symbol table consists of an ARRAY, the “collision ARRAY”, declared as POINTER(hashedRecord) ARRAY. Each element of the collision ARRAY is the head of a linked list of all records that hash to the element's index. The CLASS hashedRecord is declared as shown in Figure 15–1.

Figure 15–1. Declaration of hashedRecord
CLASS hashedRecord (
    STRING key;
    POINTER(hashedRecord) link;
);

The records in the symbol table are allocated by the user, and must have hashedRecord as a prefix CLASS; see Example 15–2. The CLASS person provides records with a key, link, homeAddress, and age to be entered into HSHMOD's symbol table. Records of the CLASS person may be passed to the HSHMOD PROCEDUREs described below since they inherit from the hashedRecord CLASS that is known to HSHMOD.

Example 15–2. Using hashedRecord as a Prefix CLASS
CLASS(hashedRecord) person (
    STRING homeAddress;
    INTEGER age;
);

HSHMOD's interface is shown in Figure 15–3. XIDAK reserves the right to change this interface by adding new fields and new OPTIONAL parameters to the PROCEDUREs.

Figure 15–3. HSHMOD Interface
CLASS hshCls (
    PROCEDURE hashInit
        (OPTIONAL INTEGER tableSize);
    PROCEDURE hashEnter
        (POINTER(hashedRecord) p);
    POINTER(hashedRecord) PROCEDURE hashLookup
        (STRING key);
    POINTER(hashedRecord) PROCEDURE hashRemove
        (STRING key);
    POINTER(hashedRecord) PROCEDURE hashNext
        (POINTER(hashedRecord) p);
    PROCEDURE hashLookupNextInit
        (STRING key);
    POINTER(hashedRecord) PROCEDURE hashLookupNext;
    BOOLEAN PROCEDURE hashRemoveRecord
        (POINTER(hashedRecord) p);
    LONG INTEGER PROCEDURE hashStore
        (POINTER(dataFile) f;
         OPTIONAL LONG INTEGER startPageOrPos;
         OPTIONAL BITS ctrlBits);
    LONG INTEGER PROCEDURE hashLoad
        (POINTER(dataFile) f;
         OPTIONAL LONG INTEGER startPageOrPos;
         OPTIONAL BITS ctrlBits);
);

MODULE(hshCls) hshMod;

15.2. HSHMOD Header

The file with logical name (system library) contains the CLASS declarations for hashedRecord and hshCls and the declaration of HSHMOD. To use HSHMOD, include the directives shown in Figure 15–4 at the beginning of each MODULE that uses HSHMOD. HSHMOD is included as a standard MODULE in the MAINSAIL system runtime library.

Figure 15–4. Including the HSHMOD Declarations
REDEFINE $scanName = "hshHdr";
SOURCEFILE "(system library)";

15.3. The PROCEDURE hashInit

hashInit is meant to be used at most once, before any of the other PROCEDUREs have been called, to specify the size of the hash table. The hash algorithm computes a number between 0 and tableSize - 1 from key, and uses this number as an index into the collision ARRAY. Any number greater than zero can be specified, though prime numbers are recommended. The larger tableSize, the more efficient the hash lookup. If hashInit is not called by the user, HSHMOD automatically invokes hashInit(131) the first time one of its PROCEDUREs is invoked, since 131 is a good table size for applications that store moderate numbers of identifiers. Very large applications may wish to use a larger table size.

15.4. The PROCEDURE hashEnter

hashEnter(p) enters the record pointed to by p in the symbol table. p.key is used as the hash key. Many records with the same hash value may be entered into the symbol table. Each record is added to the front of its collision list. More than one record with the same key may be entered in the symbol table.

When a POINTER p is passed to hashEnter, p itself is used as the entry in the hash table; no copy of p's record is made. Therefore, disposing p's record or making any change to the field p.key after calling hashEnter(p) has undefined effects.

15.5. The PROCEDURE hashLookup

hashLookup(s) searches for the record with key s, and if found, returns a POINTER to the record stored in the symbol table. If not found, NULLPOINTER is returned. If more than one record with key s is in the symbol table, it is not specified which one is returned by hashLookup. The code shown in Example 15–5 ensures that a symbol is entered just once.

Example 15–5. Using the PROCEDURE hashLookup
POINTER(hshCls) hshPtr;

...

IF NOT hshPtr.hashLookup(name) THENB # not already entered
    p := new(person); p.key := name;
    p.homeAddress := homeAddress; p.age := age;
    hshPtr.hashEnter(p) END;

15.6. The PROCEDURE hashRemove

hashRemove(s) searches for the record with key s, and if found, removes it from the symbol table and returns a POINTER to the removed record. If more than one record with key s is in the symbol table, it is not specified which one is removed by hashRemove. If not found, NULLPOINTER is returned.

15.7. The PROCEDURE hashNext

hashNext(p) provides a means of sequencing through the records in the hash table. hashNext returns a POINTER to the record in the symbol table that is “after” record p, where “after” means the record at p.link, if there is one, else the record at the next non-empty collision ARRAY element after the one containing p. If there are no more records in the symbol table, hashNext returns NULLPOINTER. If p is NULLPOINTER, the first record in the collision ARRAY is returned. hashNext is typically used as shown in Example 15–6.

Example 15–6. Using the PROCEDURE hashNext
 p := NULLPOINTER;
 WHILE p := hshPtr.hashNext(p) DOB
     ... process p's record... END

Example 15–7 shows how to use hashNext to dispose of all records in a symbol table.

Example 15–7. Disposing of All Records in a Symbol Table
WHILE p := hshPtr.hashNext(NULLPOINTER) DOB
    p := hshPtr.hashRemove(p.key); dispose(p) END

15.8. The PROCEDUREs hashLookupNextInit and hashLookupNext

hashLookupNextInit prepares HSHMOD to find all records with the key key. Subsequent calls to hashLookupNext return each record with the specified key until all such records have been returned; hashLookupNext then returns NULLPOINTER.

15.9. The PROCEDURE hashRemoveRecord

hashRemoveRecord removes the record to which p points from the hash table. It returns TRUE if it found p's record in the table, FALSE otherwise. If there are several records with the same key in the table, hashRemoveRecord may be used to remove a specified record. hashRemove removes an unspecified record with the given key; all records with a key s can be removed by:

DO UNTIL NOT hshPtr.hashRemove(s);

15.10. The PROCEDUREs hashLoad and hashStore

hashStore and hashLoad store and load a hash table into or from f at the position startPageOrPos. At present, hashStore and hashLoad use the Structure Blaster; ctrlBits may specify the valid ctrlBits to $structureWrite or $structureRead, respectively (this is subject to change). hashStore and hashLoad return the size of the structure stored or loaded, in pages or storage units, depending on whether or not $nonPaged is set in ctrlBits.

Since hashStore and hashLoad use the Structure Blaster, they do not work if the Structure Blaster is not present, and hash tables may not be stored between versions of MAINSAIL; all other Structure Blaster caveats also apply.

15.11. Creating Instances of HSHMOD

You should create an instance of HSHMOD for each symbol table rather than use the bound instance, since other MODULEs in the program may use HSHMOD for other symbol tables. Different HSHMOD instances must be created to keep the symbol tables separate. To do this, declare a POINTER for the instance, and use that POINTER to qualify all calls to the interface PROCEDUREs, as shown in Example 15–8.

Example 15–8. HSHMOD Pointers
POINTER(hshCls) mySymbolTable;
...
mySymbolTable := new(hshMod); # create the instance
...
# Use mySymbolTable for each call to a HSHMOD interface
# PROCEDURE
IF p := mySymbolTable.hashLookup(s) THEN ...
...
# When finished with the symbol table, dispose of each
# record as illustrated earlier, and then:
dispose(mySymbolTable); # dispose of the instance

15.12. Disposing HSHMOD Data

HSHMOD allocates its internal data structures in the same area as the current HSHMOD data section. The internal data structures do not include the individual hashedRecord records, which are allocated by the program using HSHMOD.

If you allocate all the hashedRecord records entered into a given HSHMOD data section in the same area as the HSHMOD data section itself, you can get rid of the entire hash table quickly by calling $clearArea or $disposeArea.

15.13. Efficiency Issues

The algorithms in HSHMOD are only moderately efficient. Applications in which hash table lookup is done in a tight loop and takes a substantial amount of the program's execution time should probably include custom written hash routines that are invoked as INLINE PROCEDUREs instead of using HSHMOD.
previous   next   top   contents   index   framed top   this page unframed

MAINSAIL Utilities User's Guide, Chapter 15