home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 549a.lha / M2P_v1.0 / mods.lzh / HashTab.mod < prev    next >
Encoding:
Modula Implementation  |  1991-08-11  |  9.1 KB  |  229 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
  33.     SYSTEM;
  34. IMPORT
  35.     SymLists,FStorage;
  36.  
  37.  
  38.  
  39.  
  40.  
  41. (*----------------------------------------------------------------------*)
  42. (*  Definition of the hash table and symbol types.  The array bounds    *)
  43. (*  of the .tab field of the Hash table are just limits, not actual.    *)
  44. (*  I had to tell the compiler something, so I made it a very large     *)
  45. (*  something.                                                          *)
  46. (*----------------------------------------------------------------------*)
  47.  
  48. TYPE
  49.     SymbolPtr = POINTER TO SymbolEntry;
  50.  
  51.     SymbolEntry = RECORD
  52.         Symbol: POINTER TO ARRAY [0..511] OF CHAR;
  53.         Key2: CARDINAL;
  54.     END;
  55.  
  56.     HashTable = POINTER TO RECORD
  57.         siz: CARDINAL;
  58.         tab: ARRAY [0..8000] OF SymLists.SymList;
  59.     END;
  60.  
  61. (*----------------------------------------------------------------------*)
  62. (*  CREATE      Creates a hash table of length n, and initialize it     *)
  63. (*              to empty.                                               *)
  64. (*                                                                      *)
  65. (*  ADVICE      Chose n to be a prime.   Also, n must be <= 8000        *)
  66. (*                                                                      *)
  67. (*  PARAMETERS  HT -- the hash table pointer                            *)
  68. (*              n  -- the size of the hash table                        *)
  69. (*----------------------------------------------------------------------*)
  70.  
  71. PROCEDURE Create(VAR HT: HashTable; n: CARDINAL);
  72.  
  73. VAR
  74.     i : CARDINAL;
  75.  
  76. BEGIN
  77.     FStorage.ALLOCATE(HT,LONGCARD(SYSTEM.TSIZE(CARDINAL)+ (n+1)*SYSTEM.TSIZE(SymLists.SymList)));
  78.     IF HT # NIL THEN
  79.         WITH HT^ DO
  80.             siz:=n;
  81.             FOR i:=0 TO n DO
  82.                 SymLists.Create(tab[i]);
  83.             END;
  84.         END;
  85.     END;
  86. END Create;
  87.  
  88. (*----------------------------------------------------------------------*)
  89. (*  DESTROY     Destroy a hash table.  All information on the table at  *)
  90. (*              time of invocation will be unlinked from the table,     *)
  91. (*              possibly lost...  The hash table will be deallocated    *)
  92. (*              and HT set to NIL.                                      *)
  93. (*                                                                      *)
  94. (*  PARAMETERS  HT -- the hash table pointer                            *)
  95. (*----------------------------------------------------------------------*)
  96.  
  97. PROCEDURE Destroy(VAR HT: HashTable);
  98.  
  99. VAR
  100.     i: CARDINAL;
  101. BEGIN
  102.     IF HT # NIL THEN
  103.         WITH HT^ DO
  104.             FOR i:= 0 TO siz DO
  105.                 SymLists.Destroy(tab[i]);
  106.             END;
  107.             FStorage.DEALLOCATE(HT,LONGCARD(SYSTEM.TSIZE(CARDINAL)+ (siz+1)*SYSTEM.TSIZE(SymLists.SymList)));
  108.         END;
  109.     END;
  110. END Destroy;
  111.  
  112. (*----------------------------------------------------------------------*)
  113. (*  The biggy, the hash function.  This is similar to the standard      *)
  114. (*  AmigaDOS disk directory hashing function as it appears in "Amiga    *)
  115. (*  Disk Drives Inside and Out" published by Abacus Books, page 117.    *)
  116. (*  However, I have made some small changes to make it work a bit       *)
  117. (*  quicker and conform to variable size tables.  With ridiculuously    *)
  118. (*  large hash tables, it will begin to work rather lousy.              *)
  119. (*----------------------------------------------------------------------*)
  120.  
  121. PROCEDURE Hash(VAR Symbol: ARRAY OF CHAR; n: CARDINAL):CARDINAL;
  122.  
  123. VAR
  124.     hash: CARDINAL;
  125.     i: CARDINAL;
  126. BEGIN
  127.     hash:=3;
  128.     i:=0;
  129.     WHILE (Symbol[i]#0C) DO
  130.         hash:=(hash*13+(ORD(Symbol[i]) MOD 32)) MOD 4096;
  131.         INC(i);
  132.     END;
  133.     RETURN hash MOD n;
  134. END Hash;
  135.  
  136. (*----------------------------------------------------------------------*)
  137. (*  INSERT      Add a symbol to the hash table.  Chaining is used to    *)
  138. (*              handle all collisions in the present implementation.    *)
  139. (*                                                                      *)
  140. (*  PARAMETERS  HT          -- the hash table                           *)
  141. (*              SymbolEntry -- a pointer to a record of the form        *)
  142. (*                             described above.                         *)
  143. (*----------------------------------------------------------------------*)
  144.  
  145. PROCEDURE Insert(HT: HashTable; Symbol: SYSTEM.ADDRESS);
  146.  
  147. VAR
  148.     symptr: SymbolPtr;
  149. BEGIN
  150.     IF HT # NIL THEN
  151.         symptr:=Symbol;
  152.         SymLists.Insert(HT^.tab[Hash(symptr^.Symbol^,HT^.siz)],Symbol);
  153.     END;
  154. END Insert;
  155.  
  156. (*----------------------------------------------------------------------*)
  157. (*  DELETE      Removes a symbol from the hash table.  If the symbol    *)
  158. (*              was not present this has no effect.                     *)
  159. (*                                                                      *)
  160. (*  PARAMETERS  HT      -- the hash table                               *)
  161. (*              Symbol  -- an array of char (must be null terminated)   *)
  162. (*----------------------------------------------------------------------*)
  163.  
  164.  
  165.  
  166. PROCEDURE Delete(HT: HashTable; Symbol: ARRAY OF CHAR);
  167.  
  168. BEGIN
  169.     IF HT # NIL THEN
  170.         SymLists.Delete(HT^.tab[Hash(Symbol,HT^.siz)],Symbol);
  171.     END;
  172. END Delete;
  173.  
  174. (*----------------------------------------------------------------------*)
  175. (*  SEARCH      Search for a symbol in the hash table and return a      *)
  176. (*              pointer to the record which it is found in.             *)
  177. (*                                                                      *)
  178. (*  PARAMETERS  HT      -- the hash table                               *)
  179. (*              Symbol  -- an array of char (must be null terminated)   *)
  180. (*                                                                      *)
  181. (*  RETURNS     NIL if the symbol was not found, or a pointer if found  *)
  182. (*----------------------------------------------------------------------*)
  183.  
  184.  
  185.  
  186. PROCEDURE Search(HT: HashTable; Symbol: ARRAY OF CHAR): SYSTEM.ADDRESS;
  187. BEGIN
  188.     IF HT # NIL THEN
  189.         RETURN SymLists.Search(HT^.tab[Hash(Symbol,HT^.siz)],Symbol);
  190.     END;
  191. END Search;
  192.  
  193. (*----------------------------------------------------------------------*)
  194. (*  LISTIFY     Since HashTab is built upon the SymList module, it is   *)
  195. (*              natural, and sometimes necessary to convert the         *)
  196. (*              contents of a hashtable into a SymList.  The original   *)
  197. (*              hashtable is left unchanged by this function.           *)
  198. (*                                                                      *)
  199. (*  PARAMETERS  HT -- the hashtable                                     *)
  200. (*                                                                      *)
  201. (*  RETURNS     A SymList holding all the entries from the HashTable    *)
  202. (*----------------------------------------------------------------------*)
  203.  
  204. PROCEDURE Listify(HT: HashTable):SymLists.SymList;
  205.  
  206. VAR
  207.     SL: SymLists.SymList;
  208.     temp: SymLists.SymList;
  209.     i: CARDINAL;
  210. BEGIN
  211.     SymLists.Create(SL);
  212.     IF HT # NIL THEN
  213.         FOR i:=0 TO HT^.siz DO
  214.             temp:=HT^.tab[i];
  215.             WHILE NOT SymLists.Empty(temp) DO
  216.                 SymLists.Insert(SL,SymLists.First(temp));
  217.                 temp:=SymLists.Next(temp);
  218.             END;
  219.         END;
  220.     END;
  221.     RETURN SL;
  222. END Listify;
  223.  
  224. (************************************************************************)
  225. (*  MAIN inititalization code                                           *)
  226. (************************************************************************)
  227.  
  228. BEGIN END HashTab.
  229.