Power-Programmierung

home *** CD-ROM | disk | FTP | other *** search

/ Power-Programmierung / CD1.mdf / pascal / library / dos / nicol / sti_hash / sti_hash.txt next >

Wrap

Text File | 1990-08-22 | 20.6 KB | 739 lines

GENERIC HASHING SYSTEM 1.0 For Turbo Pascal Version 5.0 Copyright 1990, 1991 By Software Technology International All Rights Reserved -1- NOTICE ------ All parts of this manual and the accompanying soft- ware are copyrighted material. You, as a registered user, are granted permission to make as many copies of the software, or manual, as you wish, as long as they are for your personal use. You may not copy this soft- ware, or manual, in any form whatsoever for usage outside of your personal use. This includes, but is not limited to, duplication of the disk, the files on the disk or the manual, by manual or electronic means. -2- TABLE OF CONTENTS ----------------- Subject Page ----------------------------------------------------- GENERAL DESCRIPTION ...................... 4 Introduction ........................... 4 The software ........................... 4 THE SOFTWARE IN DETAIL ................... 5 Structures and Procedures .............. 5 Usage Pointers ......................... 9 INDEX .................................... 10 -3- GENERAL DESCRIPTION ------------------- Introduction ------------ Welcome to Version 1.0 of Software Technology Inter- nationals' Generic Hashing System. This group of func- tions will enable your Turbo Pascal Version 5.0 to create hash tables containing any kind of data and using any kind of key. The system does not limit you to one hash table per unit, but rather uses a pointer to specify the current table. The functions were written to be flexible, as fast as possible, and as easy to use as possible. We hope they live up to your expectations. Please feel free to write to us anytime with bug re- ports or suggestions for future versions. If you are a registered user, this will entitle you to a free up- grade. Remember that this software is copyrighted, so please don't copy and distribute it, this is a federal offense. The Software ------------ The software is a group of procedures that implement a generic hash table system for Turbo Pascal Version 4.0 or 5.0. Using this system, you can create any number of hash tables, and use each by only reassigning a single pointer. The only limits imposed are that you are limited by the size of available memory for the hash tables, and that each table can has only 23 direct entries, after that the entries are stored in a colli- sion table. Also, the keys are only significant up to 65535 bytes, everything else is ignored. However, despite these limitations, the search time is still very fast, and the unit is very flexible. If you buy the source, you can easily modify the maximum number of entries. The system uses one of the simplest, but most effective algorithms for hashing, namely, the one specified by Wirth in "Algorithms + Data Structures = Programs." With this algorithm, the best tables size is a prime number, for rather obvious, if esoteric rea- sons. -4- THE SOFTWARE IN DETAIL ---------------------- The Structures And Procedures ----------------------------- The unit is interfaced through the following struc- tures and procedures. Constants --------- MAXENTRY = 23; This is the size of the hash table. This was chosen because A) it is a prime and B) because increasing the size of the table doesn't decrease search time so much. This is a good tradeoff between memory usage and speed. Types ----- EntryPtr = ^EntryRec; This is a pointer to the generic entry record. EntryRec = record Data : pointer; Key : pointer; Next : EntryPtr; end; This is the generic entry record. The Data and Key fields general pointers, and can point to any valid data type, thereby freeing you from limits imposed by defining a specific type. The Next field points to another entry record, which is used to create a linked list when there are collisions. Entries = array[0..MAXENTRY] of EntryPtr; This is the array of entries used in the hash table. The size is set to the same value as MAXENTRY (above). UsedFlags = array[0..MAXENTRY] of boolean; This is a set of flags used to show whether a par- ticular entry is used or not. -5- HashTable = record Entry : Entries; Used : UsedFlags; end; This is the actual declaration of the hash table. It uses the arrays defined above as the core to the sys- tem. HashTPtr = ^HashTable; This is a pointer to a hashtable, the system actual- ly uses this to do all the work, thereby enabling you to use as many tables as you like. Variables --------- HTable : HashTPtr; This is a pointer to the current hash table the system is using. By reassigning this pointer you can use as many tables as you like. This pointer must be valid otherwise the system will crash. The STIHASH unit currently does little error checking. Procedures ---------- Procedure STI_EntryInit(Var Entry : EntryRec; DataSize, KeySize : word); This procedure initialises an entry record. It allocates and zeros the memory for the KEY and DATA records. The variable ENTRY will reflect the changes made to the pointers. Procedure STI_EntryCreate(Var Entry : EntryRec); This procedure creates a new entry. It is a little different from STI_EntryInit in that it doesn't allo- cate memory, it just sets the pointers to NIL. Procedure STI_EntryLink(Var Entry : EntryRec; NewRec : EntryRec); This procedure links NEWREC to ENTRY.NEXT. This should NOT be used externally except in very special cases. It has been interfaced only to allow maximum flexibility. -6- Procedure STI_EntryDestroy(Var Entry : EntryRec; KeySize, DataSize : word); This procedure is the opposite of STI_EntryCreate. It frees the memory allocated for the KEY and DATA records (using KEYSIZE and DATASIZE), and assign the pointers to NIL. Be careful to match the sizes to the actual allocated size, otherwise you will eat up your memory. Changes will be reflected in EntryRec. Procedure STI_EntrySet_Key(Var Entry : EntryRec; Var Key; Size : word); This procedure copies the KEY structure to the ENTRY.KEY pointer, using size as the number of bytes to copy. Make sure that SIZE is correct, otherwise the key will be corrupted. Changes will be reflected in the ENTRY.KEY pointer. Procedure STI_EntrySet_Data(Var Entry : EntryRec; Var Data; Size : word); This procedure is very similar to STI_EntrySetKey, except that it copies the DATA variable to the ENTRY.DATA pointer. Again, make sure that SIZE is correct otherwise the data will be corrupted. Changes will be reflected in the ENTRY.DATA pointer. Procedure STI_EntryGet_Data(Var Entry : EntryRec; Var Data; Size : word); This procedure is the opposite of STI_EntrySet_Data in that it copies the data from ENTRY.DATA to DATA. Again, be very careful with size, otherwise the data will be corrupted. Changes will be reflected in the DATA variable. Procedure STI_HashTableCreate; This procedure creates a hash tables. This is the current hash table pointed to by HTABLE. It does NO checking to make sure that everything is valid. -7- Procedure STI_HashTableEnter(E : EntryRec; KeySize : word; Var Duplicate : Boolean); This procedure enters an entry into the hash table. The entry is E. KEYSIZE determines the size of the key to be HASHED and COMPARED. This procedure does not do any data allocation at all, so try to keep the size to a minimum, otherwise things will get a lot slower VERY quickly. If there is already a matching key in the table the entry will NOT be stored, and DUPLICATE will be set to true. If this is a problem, think of a better key structure than the one you are using. Procedure STI_HashTableRetrieve(TheKey : EntryRec; KeySize : word; Var Found : Boolean; Var E : EntryRec); This procedure retrieves an entry from the hash table. KEYSIZE has the same effect here, as in STI_HashTableEnter, so again, try to keep it small. THEKEY is an entry record, but only the key is used. This is a bit of a kludge, but it is the easiest way to do things. FOUND will bet set to TRUE if the key was retrieved, and E will contain the entry from the table. If the entry was not in the table FOUND will be set to FALSE, and E will be junk. Procedure STI_HashTableDestroy(KeySize, DataSize : word); This procedure destroys the current hashtable point- ed to by HTABLE. It frees all memory, except the actual table itself. The table is returned to the state it was in just after STI_HashTableCreate was called. Be very careful the KEYSIZE and DATASIZE are correct, otherwise you will waste memory. NOTE ---- Some of these procedures and types are interfaced only to allow the maximum flexibility possible. If you use them, you face the risk of crashing the system. Take a good look at the demonstration program and unit for a good idea of implementation. Also, BE VERY CAREFUL TO USE THE RIGHT SIZES FOR PROCEDURES THAT NEED THEM. YOU WILL LOOSE MEMORY OTHER- WISE. -8- USAGE POINTERS -------------- You should have a very good look at the unit and demonstration program provided to get a feel for how to use this unit. As stated before, this unit currently does very little in the way of error checking, so it is easy to make it do strange things. This is partly due to us wanting to make it as flexible as possible, and thereby ignoring data types. The unit provided is a generic symbol table, which is basically the main type of application for hash tables. You can easily tailor this to your specific needs by changing the DATAREC and KEYREC types. The unit should handle these changes with few problems. Try that before attempting to write your own. As stated earlier, the KEY and DATA fields in the ENTRY record can be any valid type.. up to 65535 bytes, and the KEY is significant to 65535 bytes. Therefore, if your are writing a compiler for a language like PASCAL, you should limit the name size to 254 charac- ters or so, and use 1 byte to hold the LEVEL of the symbol (depth of nesting). Another point is that, because the hashtable is a pointer you SHOULD be able to push and pop them off the stack, thereby making recursive functions using hashta- bles possible. A problem here would be memory.... THE MOST IMPORTANT THING TO REMEMBER IS TO USE THE CORRECT SIZES WITH PROCEDURES THAT NEED THEM. Generous use of sizeof() is recommended. -9- INDEX ----- Topic Page Number ------------------------------------------------------- Constants.................................. 5 Contents................................... 3 Copying.................................... 2 Copyright.................................. 2 Data Size.................................. 9 Demonstration.............................. 9 Descriptions............................... 5 Entering Data.............................. 8 Entries.................................... 5 EntryPtr................................... 5 EntryRec................................... 5 General Description........................ 4 Hashing.................................... 4 HashTable(Type)............................ 6 HashTPtr................................... 6 HTable..................................... 6 Introduction............................... 4 Key Size................................... 9 Notes...................................... 8 Procedures................................. 5,6,7,8 Recursion.................................. 9 Retrieving Data............................ 8 STI_EnrtySet_Data.......................... 7 STI_EntryCreate............................ 6 STI_EntryDestroy........................... 7 STI_EntryGet_Data.......................... 7 STI_EntryInit.............................. 6 STI_EntryLink.............................. 6 STI_EntrySet_Key........................... 7 STI_HashTableCreate........................ 7 STI_HashTableDestroy....................... 8 STI_HashTableEnter......................... 8 STI_HashTableRetrieve...................... 8 Structures................................. 5 Types...................................... 5 Usage...................................... 9 UsedFlags.................................. 5 -10- Users...................................... 2 Variables.................................. 6 Warnings................................... 8, 9 -11-