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 >
Wrap
Text File
|
1991-08-10
|
9KB
|
229 lines
(*======================================================================*)
(* Programming Support Routines - Managing Hash Tables *)
(*======================================================================*)
(* Version: 1.20 Author: Dennis Brueni *)
(* Date: 1-20-91 Changes: original *)
(* Date: 1-25-91 Changes: Duplicate handling *)
(* Date: 1-25-91 Changes: .Symbol field became POINTER *)
(* Date: 1-26-91 Changes: Fixed bug in CaseSensitive *)
(* Date: 3-07-91 Changes: Duplicate Handling removed *)
(* Case Sensitivity removed *)
(* Listify function added *)
(* Date: 3-12-91 Changes: Many Optimizations *)
(*======================================================================*)
(* HashTab contains all the routines necessary to create, use, and *)
(* maintain a Hash table of size n. It is assumed herein that the *)
(* hash table will be used to store strings. *)
(*======================================================================*)
(* Often one will want to aggregate additional information with a *)
(* symbol, so to make this table as general as possible, the symbol *)
(* must be sent as a pointer to record of the following form when *)
(* performing insertions. (note: m should be less than 512) *)
(* *)
(* symbolrec = RECORD OF *)
(* Symbol: POINTER TO ARRAY [0..m] OF CHAR; *)
(* | *)
(* END; *)
(* *)
(*======================================================================*)
IMPLEMENTATION MODULE HashTab;
IMPORT
SYSTEM;
IMPORT
SymLists,FStorage;
(*----------------------------------------------------------------------*)
(* Definition of the hash table and symbol types. The array bounds *)
(* of the .tab field of the Hash table are just limits, not actual. *)
(* I had to tell the compiler something, so I made it a very large *)
(* something. *)
(*----------------------------------------------------------------------*)
TYPE
SymbolPtr = POINTER TO SymbolEntry;
SymbolEntry = RECORD
Symbol: POINTER TO ARRAY [0..511] OF CHAR;
Key2: CARDINAL;
END;
HashTable = POINTER TO RECORD
siz: CARDINAL;
tab: ARRAY [0..8000] OF SymLists.SymList;
END;
(*----------------------------------------------------------------------*)
(* CREATE Creates a hash table of length n, and initialize it *)
(* to empty. *)
(* *)
(* ADVICE Chose n to be a prime. Also, n must be <= 8000 *)
(* *)
(* PARAMETERS HT -- the hash table pointer *)
(* n -- the size of the hash table *)
(*----------------------------------------------------------------------*)
PROCEDURE Create(VAR HT: HashTable; n: CARDINAL);
VAR
i : CARDINAL;
BEGIN
FStorage.ALLOCATE(HT,LONGCARD(SYSTEM.TSIZE(CARDINAL)+ (n+1)*SYSTEM.TSIZE(SymLists.SymList)));
IF HT # NIL THEN
WITH HT^ DO
siz:=n;
FOR i:=0 TO n DO
SymLists.Create(tab[i]);
END;
END;
END;
END Create;
(*----------------------------------------------------------------------*)
(* DESTROY Destroy a hash table. All information on the table at *)
(* time of invocation will be unlinked from the table, *)
(* possibly lost... The hash table will be deallocated *)
(* and HT set to NIL. *)
(* *)
(* PARAMETERS HT -- the hash table pointer *)
(*----------------------------------------------------------------------*)
PROCEDURE Destroy(VAR HT: HashTable);
VAR
i: CARDINAL;
BEGIN
IF HT # NIL THEN
WITH HT^ DO
FOR i:= 0 TO siz DO
SymLists.Destroy(tab[i]);
END;
FStorage.DEALLOCATE(HT,LONGCARD(SYSTEM.TSIZE(CARDINAL)+ (siz+1)*SYSTEM.TSIZE(SymLists.SymList)));
END;
END;
END Destroy;
(*----------------------------------------------------------------------*)
(* The biggy, the hash function. This is similar to the standard *)
(* AmigaDOS disk directory hashing function as it appears in "Amiga *)
(* Disk Drives Inside and Out" published by Abacus Books, page 117. *)
(* However, I have made some small changes to make it work a bit *)
(* quicker and conform to variable size tables. With ridiculuously *)
(* large hash tables, it will begin to work rather lousy. *)
(*----------------------------------------------------------------------*)
PROCEDURE Hash(VAR Symbol: ARRAY OF CHAR; n: CARDINAL):CARDINAL;
VAR
hash: CARDINAL;
i: CARDINAL;
BEGIN
hash:=3;
i:=0;
WHILE (Symbol[i]#0C) DO
hash:=(hash*13+(ORD(Symbol[i]) MOD 32)) MOD 4096;
INC(i);
END;
RETURN hash MOD n;
END Hash;
(*----------------------------------------------------------------------*)
(* INSERT Add a symbol to the hash table. Chaining is used to *)
(* handle all collisions in the present implementation. *)
(* *)
(* PARAMETERS HT -- the hash table *)
(* SymbolEntry -- a pointer to a record of the form *)
(* described above. *)
(*----------------------------------------------------------------------*)
PROCEDURE Insert(HT: HashTable; Symbol: SYSTEM.ADDRESS);
VAR
symptr: SymbolPtr;
BEGIN
IF HT # NIL THEN
symptr:=Symbol;
SymLists.Insert(HT^.tab[Hash(symptr^.Symbol^,HT^.siz)],Symbol);
END;
END Insert;
(*----------------------------------------------------------------------*)
(* DELETE Removes a symbol from the hash table. If the symbol *)
(* was not present this has no effect. *)
(* *)
(* PARAMETERS HT -- the hash table *)
(* Symbol -- an array of char (must be null terminated) *)
(*----------------------------------------------------------------------*)
PROCEDURE Delete(HT: HashTable; Symbol: ARRAY OF CHAR);
BEGIN
IF HT # NIL THEN
SymLists.Delete(HT^.tab[Hash(Symbol,HT^.siz)],Symbol);
END;
END Delete;
(*----------------------------------------------------------------------*)
(* SEARCH Search for a symbol in the hash table and return a *)
(* pointer to the record which it is found in. *)
(* *)
(* PARAMETERS HT -- the hash table *)
(* Symbol -- an array of char (must be null terminated) *)
(* *)
(* RETURNS NIL if the symbol was not found, or a pointer if found *)
(*----------------------------------------------------------------------*)
PROCEDURE Search(HT: HashTable; Symbol: ARRAY OF CHAR): SYSTEM.ADDRESS;
BEGIN
IF HT # NIL THEN
RETURN SymLists.Search(HT^.tab[Hash(Symbol,HT^.siz)],Symbol);
END;
END Search;
(*----------------------------------------------------------------------*)
(* LISTIFY Since HashTab is built upon the SymList module, it is *)
(* natural, and sometimes necessary to convert the *)
(* contents of a hashtable into a SymList. The original *)
(* hashtable is left unchanged by this function. *)
(* *)
(* PARAMETERS HT -- the hashtable *)
(* *)
(* RETURNS A SymList holding all the entries from the HashTable *)
(*----------------------------------------------------------------------*)
PROCEDURE Listify(HT: HashTable):SymLists.SymList;
VAR
SL: SymLists.SymList;
temp: SymLists.SymList;
i: CARDINAL;
BEGIN
SymLists.Create(SL);
IF HT # NIL THEN
FOR i:=0 TO HT^.siz DO
temp:=HT^.tab[i];
WHILE NOT SymLists.Empty(temp) DO
SymLists.Insert(SL,SymLists.First(temp));
temp:=SymLists.Next(temp);
END;
END;
END;
RETURN SL;
END Listify;
(************************************************************************)
(* MAIN inititalization code *)
(************************************************************************)
BEGIN END HashTab.