home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / cpm / turbopas / tlist11.lbr / HASHTBLS.PQS / hashtbls.pas
Encoding:
Pascal/Delphi Source File  |  1985-11-08  |  3.8 KB  |  107 lines
  1. FUNCTION Hash(VAR Symbol : Symbol_Type;
  2.                   Hash_size : INTEGER) : INTEGER;
  3. {
  4. This function returns the hash code for a particular symbol given the hash size.
  5. }
  6.  
  7. VAR
  8.  String_length, Key : INTEGER;
  9.  
  10. BEGIN
  11.  String_length := LENGTH(Symbol);
  12.  IF String_length = 1 THEN
  13.   Key := ORD(Symbol[1])
  14.  ELSE
  15.   IF String_length < 4 THEN
  16.    Key := ORD(Symbol[1])*100 + ORD(Symbol[2])
  17.   ELSE
  18.    Key := ORD(Symbol[1])*100 + ORD(Symbol[String_length DIV 2 + 1]);
  19.  Hash := Key MOD Hash_size + 1;
  20. END;
  21.  
  22. PROCEDURE Find_Symbol(VAR Symbol : Symbol_Type;
  23.                       VAR Hash_table_pntr, Chain_table_pntr, Symbol_table_pntr;
  24.                           Hash_size : INTEGER;
  25.  
  26.                       VAR Found : BOOLEAN;
  27.                       VAR Index : INTEGER);
  28. {
  29. This routine searches for a given symbol in the given hashed symbol table and,
  30. if it is found, returns Found = TRUE and its index in the symbol table.
  31. Symbol is the symbol to store.  Hash_table_pntr is the table to hash to; its
  32. contents point to positions in the Symbol_table and in the Chain_table (denoted
  33. formally by Symbol_table_pntr and Chain_table_pntr, respectively).  If a symbol
  34. hashes to the same location in the Hash_table, then it will exist in the symbol
  35. table along the links established by the Chain_table.  Only the addresses of
  36. the hash, chain, and symbol tables are passed so that variable-length data
  37. structures are accommodated.
  38. }
  39.  
  40. TYPE
  41.  Hash_Table_Type = ARRAY[1..Max_Hash_size] OF INTEGER;
  42.  Chain_Table_Type = ARRAY[1..Max_Table_size] OF INTEGER;
  43.  Symbol_Table_Type = ARRAY[1..Max_Table_size] OF STRING[Max_word_length];
  44.  
  45. VAR
  46.  Hash_table : Hash_Table_Type ABSOLUTE Hash_table_pntr;
  47.  Chain_table : Chain_Table_Type ABSOLUTE Chain_table_pntr;
  48.  Symbol_table : Symbol_Table_Type ABSOLUTE Symbol_table_pntr;
  49.  
  50. BEGIN
  51.  Index := Hash_table[Hash(Symbol, Hash_size)];
  52.  IF Index = 0 THEN
  53.   Found := FALSE
  54.  ELSE
  55.   BEGIN
  56.    WHILE (Symbol <> Symbol_table[Index]) AND (Chain_table[Index] <> 0) DO
  57.     Index := Chain_table[Index];
  58.    Found := Symbol = Symbol_table[Index];
  59.   END;
  60. END;
  61.  
  62. PROCEDURE Store_Symbol(VAR Symbol : Symbol_Type;
  63.                        VAR Hash_table_pntr, Chain_table_pntr, Symbol_table_pntr;
  64.                            Hash_size : INTEGER;
  65.                            Check_first : BOOLEAN;
  66.                        VAR Count : INTEGER);
  67. {
  68. This routine stores a symbol in the given hashed symbol table.  See comments in
  69. the procedure: Find_Symbol.  Count is the current number of entries in the
  70. tables.  Only the addresses of the hash, chain, and symbol tables are passed
  71. so that variable-length data structures are accommodated.
  72. }
  73.  
  74. TYPE
  75.  Hash_Table_Type = ARRAY[1..Max_Hash_size] OF INTEGER;
  76.  Chain_Table_Type = ARRAY[1..Max_Table_size] OF INTEGER;
  77.  Symbol_Table_Type = ARRAY[1..Max_Table_size] OF STRING[Max_word_length];
  78.  
  79. VAR
  80.  Hash_table : Hash_Table_Type ABSOLUTE Hash_table_pntr;
  81.  Chain_table : Chain_Table_Type ABSOLUTE Chain_table_pntr;
  82.  Symbol_table : Symbol_Table_Type ABSOLUTE Symbol_table_pntr;
  83.  Index : INTEGER;
  84.  Found : BOOLEAN;
  85.  
  86. BEGIN
  87.  IF Check_first THEN
  88.   BEGIN
  89.    Find_Symbol(Symbol, Hash_table, Chain_table, Symbol_table, Hash_size,
  90.                Found, Index);
  91.    IF Found THEN EXIT;    {If it is already in the table, don't enter it again}
  92.   END;
  93.  Count := Count + 1;
  94.  IF Count > Max_Table_size THEN
  95.   BEGIN
  96.    Writeln('Error: Hash Table Overflow!');
  97.    HALT;
  98.   END;
  99.  Symbol_table[Count] := Symbol;                  {Store in symbol table}
  100.  Index := Hash(Symbol, Hash_size);
  101.  IF Hash_table[Index] = 0 THEN
  102.   Chain_table[Count] := 0                        {Start new chain}
  103.  ELSE
  104.   Chain_table[Count] := Hash_table[Index];       {Insert in chain}
  105.  Hash_table[Index] := Count;                     {Store in hash table}
  106. END;
  107.