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.def < prev    next >
Encoding:
Modula Definition  |  1991-08-10  |  6.5 KB  |  111 lines
  1. (*======================================================================*)
  2. (*           Programming Support Routines - Managing Hash Tables        *)
  3. (*======================================================================*)
  4. (*  Version:  2.00              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. (*                                        CaseSensitive proc. removed   *)
  11. (*                                        Listify function added        *)
  12. (*======================================================================*)
  13. (*  HashTab contains all the routines necessary to create, use, and     *)
  14. (*  maintain a Hash table of size n.  It is assumed herein that the     *)
  15. (*  hash table will be used to store strings.                           *)
  16. (*======================================================================*)
  17. (*  Often one will want to aggregate additional information with a      *)
  18. (*  symbol, so to make this table as general as possible, the symbol    *)
  19. (*  must be sent as a pointer to record of the following form when      *)
  20. (*  performing insertions.  (note: m should be less than 512)           *)
  21. (*                                                                      *)
  22. (*       symbolrec = RECORD OF                                          *)
  23. (*                      Symbol:  POINTER TO ARRAY [0..m] OF CHAR;       *)
  24. (*                      |                                               *)
  25. (*                   END;                                               *)
  26. (*                                                                      *)
  27. (*======================================================================*)
  28.  
  29. DEFINITION MODULE HashTab;
  30.  
  31. FROM SYSTEM   IMPORT ADDRESS;
  32. FROM SymLists IMPORT SymList;
  33.  
  34. (*----------------------------------------------------------------------*)
  35. (*  Opaque definition of the hash table.  Simply a pointer.             *)
  36. (*----------------------------------------------------------------------*)
  37.  
  38. TYPE HashTable;                         (* opaque defination of a table *)
  39.  
  40. (*----------------------------------------------------------------------*)
  41. (*  CREATE      Creates a hash table of length n, and initialize it     *)
  42. (*              to empty.                                               *)
  43. (*                                                                      *)
  44. (*  ADVICE      Chose n to be a prime.   Also, n must be <= 8000        *)
  45. (*                                                                      *)
  46. (*  PARAMETERS  HT -- the hash table pointer                            *)
  47. (*              n  -- the size of the hash table                        *)
  48. (*----------------------------------------------------------------------*)
  49.  
  50. PROCEDURE Create(VAR HT: HashTable; n: CARDINAL);
  51.  
  52. (*----------------------------------------------------------------------*)
  53. (*  DESTROY     Destroy a hash table.  All information on the table at  *)
  54. (*              time of invocation will be unlinked from the table,     *)
  55. (*              possibly lost...  The hash table will be deallocated    *)
  56. (*              and HT set to NIL.                                      *)
  57. (*                                                                      *)
  58. (*  PARAMETERS  HT -- the hash table pointer                            *)
  59. (*----------------------------------------------------------------------*)
  60.  
  61. PROCEDURE Destroy(VAR HT: HashTable);
  62.  
  63. (*----------------------------------------------------------------------*)
  64. (*  INSERT      Add a symbol to the hash table.  Chaining is used to    *)
  65. (*              handle all collisions in the present implementation.    *)
  66. (*                                                                      *)
  67. (*  PARAMETERS  HT          -- the hash table                           *)
  68. (*              SymbolEntry -- a pointer to a record of the form        *)
  69. (*                             described above.                         *)
  70. (*----------------------------------------------------------------------*)
  71.  
  72. PROCEDURE Insert(HT: HashTable; SymbolEntry: ADDRESS);
  73.  
  74. (*----------------------------------------------------------------------*)
  75. (*  DELETE      Removes a symbol from the hash table.  If the symbol    *)
  76. (*              was not present this has no effect.                     *)
  77. (*                                                                      *)
  78. (*  PARAMETERS  HT      -- the hash table                               *)
  79. (*              Symbol  -- an array of char (must be null terminated)   *)
  80. (*----------------------------------------------------------------------*)
  81.  
  82. PROCEDURE Delete(HT: HashTable; Symbol: ARRAY OF CHAR);
  83.  
  84. (*----------------------------------------------------------------------*)
  85. (*  SEARCH      Search for a symbol in the hash table and return a      *)
  86. (*              pointer to the record which it is found in.             *)
  87. (*                                                                      *)
  88. (*  PARAMETERS  HT      -- the hash table                               *)
  89. (*              Symbol  -- an array of char (must be null terminated)   *)
  90. (*                                                                      *)
  91. (*  RETURNS     NIL if the symbol was not found, or a pointer if found  *)
  92. (*----------------------------------------------------------------------*)
  93.  
  94. PROCEDURE Search(HT: HashTable; symbol: ARRAY OF CHAR): ADDRESS;
  95.  
  96. (*----------------------------------------------------------------------*)
  97. (*  LISTIFY     Since HashTab is built upon the SymList module, it is   *)
  98. (*              natural, and sometimes necessary to convert the         *)
  99. (*              contents of a hashtable into a SymList.  The original   *)
  100. (*              hashtable is left unchanged by this function.           *)
  101. (*                                                                      *)
  102. (*  PARAMETERS  HT -- the hashtable                                     *)
  103. (*                                                                      *)
  104. (*  RETURNS     A SymList holding all the entries from the HashTable    *)
  105. (*----------------------------------------------------------------------*)
  106.  
  107. PROCEDURE Listify(HT: HashTable):SymList;
  108.  
  109. (************************************************************************)
  110.  
  111. END HashTab.