home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 549b.lha / M2P_v1.0_sources / source.lzh / HashTab.mpp < prev    next >
Text File  |  1991-08-10  |  10KB  |  220 lines
  1. (*======================================================================*)
  2. (*           Programming Support Routines - Managing Hash Tables        *)
  3. (*======================================================================*)
  4. (*  Version:  1.20              Author:   Dennis Brueni                 *)
  5. (*  Date:     1-20-91           Changes:  original                      *)
  6. (*  Date:     1-25-91           Changes:  Duplicate handling            *)
  7. (*  Date:     1-25-91           Changes:  .Symbol field became POINTER  *)
  8. (*  Date:     1-26-91           Changes:  Fixed bug in CaseSensitive    *)
  9. (*  Date:     3-07-91           Changes:  Duplicate Handling removed    *)
  10. (*                                        Case Sensitivity removed      *)
  11. (*                                        Listify function added        *)
  12. (*  Date:     3-12-91           Changes:  Many Optimizations            *)
  13. (*======================================================================*)
  14. (*  HashTab contains all the routines necessary to create, use, and     *)
  15. (*  maintain a Hash table of size n.  It is assumed herein that the     *)
  16. (*  hash table will be used to store strings.                           *)
  17. (*======================================================================*)
  18. (*  Often one will want to aggregate additional information with a      *)
  19. (*  symbol, so to make this table as general as possible, the symbol    *)
  20. (*  must be sent as a pointer to record of the following form when      *)
  21. (*  performing insertions.  (note: m should be less than 512)           *)
  22. (*                                                                      *)
  23. (*       symbolrec = RECORD OF                                          *)
  24. (*                      Symbol:  POINTER TO ARRAY [0..m] OF CHAR;       *)
  25. (*                      |                                               *)
  26. (*                   END;                                               *)
  27. (*                                                                      *)
  28. (*======================================================================*)
  29.  
  30. IMPLEMENTATION MODULE HashTab;
  31.  
  32. IMPORT SYSTEM;
  33. IMPORT SymLists,FStorage;
  34.  
  35. @INCLUDE "MACROS"
  36.  
  37. @LongAddressing
  38.  
  39. (*----------------------------------------------------------------------*)
  40. (*  Definition of the hash table and symbol types.  The array bounds    *)
  41. (*  of the .tab field of the Hash table are just limits, not actual.    *)
  42. (*  I had to tell the compiler something, so I made it a very large     *)
  43. (*  something.                                                          *)
  44. (*----------------------------------------------------------------------*)
  45.  
  46. TYPE SymbolPtr = POINTER TO SymbolEntry;
  47.  
  48.      SymbolEntry = RECORD 
  49.                       Symbol: POINTER TO ARRAY [0..511] OF CHAR;  
  50.                       Key2:   CARDINAL;
  51.                    END;  
  52.  
  53.      HashTable = POINTER TO RECORD 
  54.                                siz: CARDINAL;
  55.                                tab: ARRAY [0..8000] OF SymLists.SymList;
  56.                             END;
  57.  
  58. (*----------------------------------------------------------------------*)
  59. (*  CREATE      Creates a hash table of length n, and initialize it     *)
  60. (*              to empty.                                               *)
  61. (*                                                                      *)
  62. (*  ADVICE      Chose n to be a prime.   Also, n must be <= 8000        *)
  63. (*                                                                      *)
  64. (*  PARAMETERS  HT -- the hash table pointer                            *)
  65. (*              n  -- the size of the hash table                        *)
  66. (*----------------------------------------------------------------------*)
  67.  
  68. PROCEDURE Create(VAR HT: HashTable; n: CARDINAL);
  69.  
  70. VAR i   : CARDINAL;
  71.     
  72. BEGIN
  73.    FStorage.ALLOCATE(HT,LONGCARD(SYSTEM.TSIZE(CARDINAL)+
  74.                                  (n+1)*SYSTEM.TSIZE(SymLists.SymList)));
  75.    IF HT # NIL THEN WITH HT^ DO 
  76.       siz:=n;
  77.       FOR i:=0 TO n DO
  78.          SymLists.Create(tab[i]);
  79.       END;
  80.    END; END;
  81. END Create;
  82.  
  83. (*----------------------------------------------------------------------*)
  84. (*  DESTROY     Destroy a hash table.  All information on the table at  *)
  85. (*              time of invocation will be unlinked from the table,     *)
  86. (*              possibly lost...  The hash table will be deallocated    *)
  87. (*              and HT set to NIL.                                      *)
  88. (*                                                                      *)
  89. (*  PARAMETERS  HT -- the hash table pointer                            *)
  90. (*----------------------------------------------------------------------*)
  91.  
  92. PROCEDURE Destroy(VAR HT: HashTable);
  93.  
  94. VAR i: CARDINAL;
  95. BEGIN
  96.    IF HT # NIL THEN 
  97.       WITH HT^ DO 
  98.          FOR i:= 0 TO siz DO
  99.             SymLists.Destroy(tab[i]);
  100.          END;
  101.       FStorage.DEALLOCATE(HT,LONGCARD(SYSTEM.TSIZE(CARDINAL)+
  102.                              (siz+1)*SYSTEM.TSIZE(SymLists.SymList)));
  103.       END;
  104.    END; 
  105. END Destroy;
  106.  
  107. (*----------------------------------------------------------------------*)
  108. (*  The biggy, the hash function.  This is similar to the standard      *)
  109. (*  AmigaDOS disk directory hashing function as it appears in "Amiga    *)
  110. (*  Disk Drives Inside and Out" published by Abacus Books, page 117.    *)
  111. (*  However, I have made some small changes to make it work a bit       *)
  112. (*  quicker and conform to variable size tables.  With ridiculuously    *)
  113. (*  large hash tables, it will begin to work rather lousy.              *)
  114. (*----------------------------------------------------------------------*)                                            
  115.  
  116. PROCEDURE Hash(VAR Symbol: ARRAY OF CHAR; n: CARDINAL):CARDINAL;
  117.  
  118. VAR hash: CARDINAL;
  119.        i: CARDINAL;
  120. BEGIN
  121.    hash:=3;
  122.    i:=0;
  123.    WHILE (Symbol[i]#0C) DO
  124.       hash:=(hash*13+(ORD(Symbol[i]) MOD 32)) MOD 4096;
  125.       INC(i);
  126.    END;
  127.    RETURN hash MOD n;
  128. END Hash;
  129.  
  130. (*----------------------------------------------------------------------*)
  131. (*  INSERT      Add a symbol to the hash table.  Chaining is used to    *)
  132. (*              handle all collisions in the present implementation.    *)
  133. (*                                                                      *)
  134. (*  PARAMETERS  HT          -- the hash table                           *)
  135. (*              SymbolEntry -- a pointer to a record of the form        *)
  136. (*                             described above.                         *)
  137. (*----------------------------------------------------------------------*)
  138.  
  139. PROCEDURE Insert(HT: HashTable; Symbol: SYSTEM.ADDRESS);
  140.  
  141. VAR symptr: SymbolPtr;
  142. BEGIN
  143.    IF HT # NIL THEN
  144.       symptr:=Symbol;
  145.       SymLists.Insert(HT^.tab[Hash(symptr^.Symbol^,HT^.siz)],Symbol);
  146.    END;
  147. END Insert;
  148.  
  149. (*----------------------------------------------------------------------*)
  150. (*  DELETE      Removes a symbol from the hash table.  If the symbol    *)
  151. (*              was not present this has no effect.                     *)
  152. (*                                                                      *)
  153. (*  PARAMETERS  HT      -- the hash table                               *)
  154. (*              Symbol  -- an array of char (must be null terminated)   *)
  155. (*----------------------------------------------------------------------*)
  156.  
  157. @NoCopyStrings
  158.  
  159. PROCEDURE Delete(HT: HashTable; Symbol: ARRAY OF CHAR);
  160.  
  161. BEGIN
  162.    IF HT # NIL THEN
  163.       SymLists.Delete(HT^.tab[Hash(Symbol,HT^.siz)],Symbol);
  164.    END;
  165. END Delete;
  166.  
  167. (*----------------------------------------------------------------------*)
  168. (*  SEARCH      Search for a symbol in the hash table and return a      *)
  169. (*              pointer to the record which it is found in.             *)
  170. (*                                                                      *)
  171. (*  PARAMETERS  HT      -- the hash table                               *)
  172. (*              Symbol  -- an array of char (must be null terminated)   *)
  173. (*                                                                      *)
  174. (*  RETURNS     NIL if the symbol was not found, or a pointer if found  *)
  175. (*----------------------------------------------------------------------*)
  176.  
  177. @NoCopyStrings
  178.  
  179. PROCEDURE Search(HT: HashTable; Symbol: ARRAY OF CHAR): SYSTEM.ADDRESS;
  180. BEGIN
  181.    IF HT # NIL THEN
  182.       RETURN SymLists.Search(HT^.tab[Hash(Symbol,HT^.siz)],Symbol);
  183.    END;
  184. END Search;
  185.  
  186. (*----------------------------------------------------------------------*)
  187. (*  LISTIFY     Since HashTab is built upon the SymList module, it is   *)
  188. (*              natural, and sometimes necessary to convert the         *)
  189. (*              contents of a hashtable into a SymList.  The original   *)
  190. (*              hashtable is left unchanged by this function.           *)
  191. (*                                                                      *)
  192. (*  PARAMETERS  HT -- the hashtable                                     *)
  193. (*                                                                      *)
  194. (*  RETURNS     A SymList holding all the entries from the HashTable    *)
  195. (*----------------------------------------------------------------------*)
  196.  
  197. PROCEDURE Listify(HT: HashTable):SymLists.SymList;
  198.  
  199. VAR SL:   SymLists.SymList;
  200.     temp: SymLists.SymList;
  201.     i:    CARDINAL;
  202. BEGIN
  203.    SymLists.Create(SL);
  204.    IF HT # NIL THEN
  205.       FOR i:=0 TO HT^.siz DO
  206.          temp:=HT^.tab[i];
  207.          WHILE NOT SymLists.Empty(temp) DO
  208.             SymLists.Insert(SL,SymLists.First(temp));
  209.             temp:=SymLists.Next(temp);
  210.          END;
  211.       END;
  212.    END;
  213.    RETURN SL;
  214. END Listify;
  215.  
  216. (************************************************************************)
  217. (*  MAIN inititalization code                                           *)
  218. (************************************************************************)
  219.  
  220. END HashTab.