FUNCTION Hash(VAR Symbol : Symbol_Type;
                  Hash_size : INTEGER) : INTEGER;
{
This function returns the hash code for a particular symbol given the hash size.
}

VAR
 String_length, Key : INTEGER;

BEGIN
 String_length := LENGTH(Symbol);
 IF String_length = 1 THEN
  Key := ORD(Symbol[1])
 ELSE
  IF String_length < 4 THEN
   Key := ORD(Symbol[1])*100 + ORD(Symbol[2])
  ELSE
   Key := ORD(Symbol[1])*100 + ORD(Symbol[String_length DIV 2 + 1]);
 Hash := Key MOD Hash_size + 1;
END;

PROCEDURE Find_Symbol(VAR Symbol : Symbol_Type;
                      VAR Hash_table_pntr, Chain_table_pntr, Symbol_table_pntr;
                          Hash_size : INTEGER;

                      VAR Found : BOOLEAN;
                      VAR Index : INTEGER);
{
This routine searches for a given symbol in the given hashed symbol table and,
if it is found, returns Found = TRUE and its index in the symbol table.
Symbol is the symbol to store.  Hash_table_pntr is the table to hash to; its
contents point to positions in the Symbol_table and in the Chain_table (denoted
formally by Symbol_table_pntr and Chain_table_pntr, respectively).  If a symbol
hashes to the same location in the Hash_table, then it will exist in the symbol
table along the links established by the Chain_table.  Only the addresses of
the hash, chain, and symbol tables are passed so that variable-length data
structures are accommodated.
}

TYPE
 Hash_Table_Type = ARRAY[1..Max_Hash_size] OF INTEGER;
 Chain_Table_Type = ARRAY[1..Max_Table_size] OF INTEGER;
 Symbol_Table_Type = ARRAY[1..Max_Table_size] OF STRING[Max_word_length];

VAR
 Hash_table : Hash_Table_Type ABSOLUTE Hash_table_pntr;
 Chain_table : Chain_Table_Type ABSOLUTE Chain_table_pntr;
 Symbol_table : Symbol_Table_Type ABSOLUTE Symbol_table_pntr;

BEGIN
 Index := Hash_table[Hash(Symbol, Hash_size)];
 IF Index = 0 THEN
  Found := FALSE
 ELSE
  BEGIN
   WHILE (Symbol <> Symbol_table[Index]) AND (Chain_table[Index] <> 0) DO
    Index := Chain_table[Index];
   Found := Symbol = Symbol_table[Index];
  END;
END;

PROCEDURE Store_Symbol(VAR Symbol : Symbol_Type;
                       VAR Hash_table_pntr, Chain_table_pntr, Symbol_table_pntr;
                           Hash_size : INTEGER;
                           Check_first : BOOLEAN;
                       VAR Count : INTEGER);
{
This routine stores a symbol in the given hashed symbol table.  See comments in
the procedure: Find_Symbol.  Count is the current number of entries in the
tables.  Only the addresses of the hash, chain, and symbol tables are passed
so that variable-length data structures are accommodated.
}

TYPE
 Hash_Table_Type = ARRAY[1..Max_Hash_size] OF INTEGER;
 Chain_Table_Type = ARRAY[1..Max_Table_size] OF INTEGER;
 Symbol_Table_Type = ARRAY[1..Max_Table_size] OF STRING[Max_word_length];

VAR
 Hash_table : Hash_Table_Type ABSOLUTE Hash_table_pntr;
 Chain_table : Chain_Table_Type ABSOLUTE Chain_table_pntr;
 Symbol_table : Symbol_Table_Type ABSOLUTE Symbol_table_pntr;
 Index : INTEGER;
 Found : BOOLEAN;

BEGIN
 IF Check_first THEN
  BEGIN
   Find_Symbol(Symbol, Hash_table, Chain_table, Symbol_table, Hash_size,
               Found, Index);
   IF Found THEN EXIT;    {If it is already in the table, don't enter it again}
  END;
 Count := Count + 1;
 IF Count > Max_Table_size THEN
  BEGIN
   Writeln('Error: Hash Table Overflow!');
   HALT;
  END;
 Symbol_table[Count] := Symbol;                  {Store in symbol table}
 Index := Hash(Symbol, Hash_size);
 IF Hash_table[Index] = 0 THEN
  Chain_table[Count] := 0                        {Start new chain}
 ELSE
  Chain_table[Count] := Hash_table[Index];       {Insert in chain}
 Hash_table[Index] := Count;                     {Store in hash table}
END;