language-Modula2-0.1: examples/Modula-2_Libraries/andrea-m2/lib/generic/wordhash.mod
IMPLEMENTATION MODULE WordHash;
(* Reserved Word Hash Table for Modula-2
* coded by J. Andrea, Jan 1986
* from
* Minimal Perfect Hash Functions for Reserved Word Lists
* R.W. Sebeasta and M.A. Taylor
* SigPlan Notices, V20, #12, December 1985
*
* The function HashValue returns a cardinal which can be compared with the
* values of the word values, not_a_reserved_word is returned if the input
* string is not a Modula-2 reserved word
*
*)
(* This code may be freely used and distributed, it may not be sold. *)
FROM StringOperations IMPORT Length;
CONST
min_char = 'A'; max_char = 'Z';
min_len = 2; max_len = 14;
TYPE
LetterInfo = RECORD
value :INTEGER;
position :INTEGER;
END;
WordInfo = RECORD
word_length :CARDINAL;
actual_word :ARRAY [0..max_len] OF CHAR;
END;
VAR
letters :ARRAY [min_char .. max_char] OF LetterInfo;
words :ARRAY [min_hash .. max_hash] OF WordInfo;
(* --------------------------------------------------------- *)
PROCEDURE HashValue( string :ARRAY OF CHAR ) :CARDINAL;
(* compute and return the hash value of a Modula-2 reserved word *)
VAR
length :CARDINAL;
first, last, second_last :CHAR;
value :INTEGER;
(* ------------------------------------------------------ *)
PROCEDURE SecondCheck() :BOOLEAN;
(* make sure its the actual word, with a char by char comparison *)
VAR
i, m, l :CARDINAL;
BEGIN (* SecondCheck *)
m := CARDINAL( value ); l := words[m].word_length;
i := 0;
WHILE ( i < l ) & ( string[i] = words[m].actual_word[i] ) DO
i := i + 1;
END; (* while *)
RETURN ( i >= l );
END SecondCheck;
BEGIN (* HashValue *)
length := Length(string);
IF ( length < min_len ) OR ( length > max_len ) THEN
RETURN not_a_reserved_word;
ELSE
first := string[0]; last := string[length-1];
second_last := string[length-2];
IF ( first < min_char ) OR ( first > max_char ) OR
( last < min_char ) OR ( last > max_char ) OR
( second_last < min_char ) OR ( second_last > max_char ) THEN
RETURN not_a_reserved_word;
ELSE
value := letters[first].value + letters[last].value +
INTEGER( length ) + letters[second_last].position;
IF ( value < min_hash ) OR ( value > max_hash ) THEN
RETURN not_a_reserved_word;
ELSE
IF SecondCheck() THEN
RETURN CARDINAL( value );
ELSE
RETURN not_a_reserved_word;
END; (* if *)
END; (* if *)
END; (* if *)
END; (* if *)
END HashValue;
BEGIN (* Wordhash *)
letters['A'].value := 18; letters['A'].position := 0;
letters['B'].value := 16; letters['B'].position := 1;
letters['C'].value := 3; letters['C'].position := 2;
letters['D'].value := - 3; letters['D'].position := 3;
letters['E'].value := -11; letters['E'].position := 4;
letters['F'].value := 4; letters['F'].position := 5;
letters['G'].value := 100; letters['G'].position := 6;
letters['H'].value := 14; letters['H'].position := 7;
letters['I'].value := 15; letters['I'].position := 8;
letters['J'].value := 100; letters['J'].position := 9;
letters['K'].value := 100; letters['K'].position := 10;
letters['L'].value := 15; letters['L'].position := 11;
letters['M'].value := 1; letters['M'].position := 12;
letters['N'].value := - 4; letters['N'].position := 13;
letters['O'].value := 7; letters['O'].position := 14;
letters['P'].value := 1; letters['P'].position := 15;
letters['Q'].value := 22; letters['Q'].position := 16;
letters['R'].value := - 1; letters['R'].position := 17;
letters['S'].value := 3; letters['S'].position := 18;
letters['T'].value := 0; letters['T'].position := 19;
letters['U'].value := 8; letters['U'].position := 20;
letters['V'].value := 22; letters['V'].position := 21;
letters['W'].value := - 2; letters['W'].position := 22;
letters['X'].value := 100; letters['X'].position := 23;
letters['Y'].value := 14; letters['Y'].position := 24;
letters['Z'].value := 100; letters['Z'].position := 25;
words[and].word_length := 3; words[and].actual_word := 'AND';
words[array].word_length := 5; words[array].actual_word := 'ARRAY';
words[begin].word_length := 5; words[begin].actual_word := 'BEGIN';
words[by].word_length := 2; words[by].actual_word := 'BY';
words[case].word_length := 4; words[case].actual_word := 'CASE';
words[const].word_length := 5; words[const].actual_word := 'CONST';
words[definition].word_length := 10;
words[definition].actual_word := 'DEFINITION';
words[div].word_length := 3; words[div].actual_word := 'DIV';
words[do].word_length := 2; words[do].actual_word := 'DO';
words[else].word_length := 4; words[else].actual_word := 'ELSE';
words[elsif].word_length := 5; words[elsif].actual_word := 'ELSIF';
words[end].word_length := 3; words[end].actual_word := 'END';
words[exit].word_length := 4; words[exit].actual_word := 'EXIT';
words[export].word_length := 6; words[export].actual_word := 'EXPORT';
words[for].word_length := 3; words[for].actual_word := 'FOR';
words[from].word_length := 4; words[from].actual_word := 'FROM';
words[if].word_length := 2; words[if].actual_word := 'IF';
words[implementation].word_length := 14;
words[implementation].actual_word := 'IMPLEMENTATION';
words[import].word_length := 6; words[import].actual_word := 'IMPORT';
words[in].word_length := 2; words[in].actual_word := 'IN';
words[loop].word_length := 4; words[loop].actual_word := 'LOOP';
words[mod].word_length := 3; words[mod].actual_word := 'MOD';
words[module].word_length := 6; words[module].actual_word := 'MODULE';
words[not].word_length := 3; words[not].actual_word := 'NOT';
words[of].word_length := 2; words[of].actual_word := 'OF';
words[or].word_length := 2; words[or].actual_word := 'OR';
words[pointer].word_length := 7; words[pointer].actual_word := 'POINTER';
words[procedure].word_length := 9;
words[procedure].actual_word := 'PROCEDURE';
words[qualified].word_length := 9;
words[qualified].actual_word := 'QUALIFIED';
words[record].word_length := 6; words[record].actual_word := 'RECORD';
words[repeat].word_length := 6; words[repeat].actual_word := 'REPEAT';
words[return].word_length := 6; words[return].actual_word := 'RETURN';
words[set].word_length := 3; words[set].actual_word := 'SET';
words[then].word_length := 4; words[then].actual_word := 'THEN';
words[to].word_length := 2; words[to].actual_word := 'TO';
words[type].word_length := 4; words[type].actual_word := 'TYPE';
words[until].word_length := 5; words[until].actual_word := 'UNTIL';
words[var].word_length := 3; words[var].actual_word := 'VAR';
words[while].word_length := 5; words[while].actual_word := 'WHILE';
words[with].word_length := 4; words[with].actual_word := 'WITH';
END WordHash.