home *** CD-ROM | disk | FTP | other *** search
/ ftptest.leeds.ac.uk / 2015.02.ftptest.leeds.ac.uk.tar / ftptest.leeds.ac.uk / bionet / CAE-GROUP / SCL-WIN3x / FED_PLUS.EXE / HASH.H < prev    next >
C/C++ Source or Header  |  1994-07-21  |  5KB  |  208 lines
  1. #ifndef HASH_H
  2. #define HASH_H
  3.  
  4. /* $Id: hash.h,v 1.4 1993/10/15 18:49:23 libes Exp $ */
  5.  
  6. /************************************************************************
  7. ** Hash_Table:    Hash_Table
  8. ** Description:    
  9. **    
  10. **    
  11. ** Largely based on code written by ejp@ausmelb.oz
  12. **
  13. ** Constants:
  14. **    HASH_TABLE_NULL    - the null Hash_Table
  15. **
  16. ************************************************************************/
  17.  
  18. /*
  19.  * This work was supported by the United States Government, and is
  20.  * not subject to copyright.
  21.  *
  22.  * $Log: hash.h,v $
  23.  * Revision 1.4  1993/10/15  18:49:23  libes
  24.  * CADDETC certified
  25.  *
  26.  * Revision 1.3  1992/08/18  17:15:40  libes
  27.  * rm'd extraneous error messages
  28.  *
  29.  * Revision 1.2  1992/05/31  08:36:48  libes
  30.  * multiple files
  31.  *
  32.  * Revision 1.1  1992/05/28  03:56:02  libes
  33.  * Initial revision
  34.  *
  35.  * Revision 1.4  1992/05/14  10:14:33  libes
  36.  * don't remember
  37.  *
  38.  * Revision 1.3  1992/02/12  07:06:15  libes
  39.  * do sub/supertype
  40.  *
  41.  * Revision 1.2  1992/02/09  00:47:45  libes
  42.  * does ref/use correctly
  43.  *
  44.  * Revision 1.1  1992/02/05  08:40:30  libes
  45.  * Initial revision
  46.  *
  47.  * Revision 1.1  1992/01/22  02:17:49  libes
  48.  * Initial revision
  49.  *
  50.  * Revision 1.7  1992/01/15  19:56:15  shepherd
  51.  * Commented out text after #else and #endif.
  52.  *
  53.  * Revision 1.5  91/10/30  08:36:54  silver
  54.  * Express N14 Changes
  55.  * 
  56.  * Revision 1.6  1991/08/30  16:36:07  libes
  57.  * fixed HASHlist to use state from parameter instead of static
  58.  *
  59.  * Revision 1.5  1991/08/06  18:55:21  libes
  60.  * Declared HASHcopy for DICT_copy support
  61.  *
  62.  * Revision 1.4  1991/07/19  03:53:36  libes
  63.  * added action HASH_DELETE
  64.  * made action HASH_INSERT return failure upon duplicate entry
  65.  *
  66.  * Revision 1.3  1991/02/26  21:05:59  libes
  67.  * Defined routines to visit every element in hash table.
  68.  *
  69.  * Revision 1.2  1990/09/06  10:51:11  clark
  70.  * BPR 2.1 alpha
  71.  *
  72.  * Revision 1.1  90/06/11  17:05:54  clark
  73.  * Initial revision
  74.  * 
  75.  */
  76.  
  77. #include "basic.h"    /* get basic definitions */
  78.  
  79. /*************/
  80. /* constants */
  81. /*************/
  82.  
  83. #define HASH_NULL    (Hash_Table)NULL
  84.  
  85. #define SEGMENT_SIZE        256
  86. #define SEGMENT_SIZE_SHIFT    8    /* log2(SEGMENT_SIZE)    */
  87. #define DIRECTORY_SIZE        256
  88. #define DIRECTORY_SIZE_SHIFT    8    /* log2(DIRECTORY_SIZE)    */
  89. #define PRIME1            37
  90. #define PRIME2            1048583
  91. #define MAX_LOAD_FACTOR    5
  92.  
  93. /*****************/
  94. /* packages used */
  95. /*****************/
  96.  
  97. #ifdef HASH_C
  98. #include <assert.h>
  99. #endif /*HASH_C*/
  100.  
  101. #include "memory.h"
  102.  
  103. /************/
  104. /* typedefs */
  105. /************/
  106.  
  107. typedef enum { HASH_FIND, HASH_INSERT, HASH_DELETE } Action;
  108.  
  109. typedef unsigned long Address;
  110.  
  111. /****************/
  112. /* abstractions */
  113. /****************/
  114.  
  115. typedef struct Element {
  116.     char        *key;
  117.     char        *data;
  118.     struct Element    *next;
  119.     Symbol        *symbol;/* for debugging hash conflicts */
  120.     char        type;    /* user-supplied type */
  121. } *Element;
  122.  
  123. typedef Element *Segment;
  124.  
  125. typedef struct Hash_Table {
  126. #if 0
  127.     int     in_use;        /* If someone is traversing the hash table */
  128. #endif
  129.     short    p;        /* Next bucket to be split    */
  130.     short    maxp;        /* upper bound on p during expansion    */
  131.     long    KeyCount;    /* current # keys    */
  132.     short    SegmentCount;    /* current # segments    */
  133.     short    MinLoadFactor;
  134.     short    MaxLoadFactor;
  135.     Segment    Directory[DIRECTORY_SIZE];
  136. } *Hash_Table;
  137.  
  138. typedef struct {
  139.     int i;    /* segment index (i think) */
  140.     int j;    /* key index in segment (ditto) */
  141.     Element p;    /* usually the next element to be returned */
  142.     Hash_Table table;
  143.     char type;
  144.     Element e;    /* originally thought of as a place for */
  145. /* the caller of HASHlist to temporarily stash the return value */
  146. /* to allow the caller (i.e., DICTdo) to be macroized, but now */
  147. /* conveniently used by HASHlist, which both stores the ultimate */
  148. /* value here as well as returns it via the return value of HASHlist */
  149. } HashEntry;
  150.  
  151. /****************/
  152. /* modules used */
  153. /****************/
  154.  
  155. /********************/
  156. /* global variables */
  157. /********************/
  158.  
  159. #ifdef HASH_C
  160. # define GLOBAL
  161. # define INITIALLY(value) = value
  162. #else
  163. # define GLOBAL extern
  164. # define INITIALLY(value)
  165. #endif /*HASH_C*/
  166.  
  167. GLOBAL struct freelist_head HASH_Table_fl;
  168. GLOBAL struct freelist_head HASH_Element_fl;
  169.  
  170. #undef GLOBAL
  171. #undef INITIALLY
  172.  
  173. /******************************/
  174. /* macro function definitions */
  175. /******************************/
  176.  
  177. /*
  178. ** Fast arithmetic, relying on powers of 2
  179. */
  180.  
  181. #define MUL(x,y)        ((x) << (y##_SHIFT))
  182. #define DIV(x,y)        ((x) >> (y##_SHIFT))
  183. #define MOD(x,y)        ((x) & ((y)-1))
  184.  
  185. #define HASH_Table_new()    (struct Hash_Table *)MEM_new(&HASH_Table_fl)
  186. #define HASH_Table_destroy(x)    MEM_destroy(&HASH_Table_fl,(Freelist *)(Generic)x)
  187. #define HASH_Element_new()    (struct Element *)MEM_new(&HASH_Element_fl)
  188. #define HASH_Element_destroy(x)    MEM_destroy(&HASH_Element_fl,(Freelist *)(char *)x)
  189.  
  190.  
  191. /***********************/
  192. /* function prototypes */
  193. /***********************/
  194.  
  195. extern void    HASHinitialize PROTO((void));
  196. extern Hash_Table    HASHcreate PROTO((unsigned));
  197. extern Hash_Table    HASHcopy PROTO((Hash_Table));
  198. extern void    HASHdestroy PROTO((Hash_Table));
  199. extern Element    HASHsearch PROTO((Hash_Table, Element, Action));
  200. extern void    HASHlistinit PROTO((Hash_Table,HashEntry *));
  201. extern void    HASHlistinit_by_type PROTO((Hash_Table,HashEntry *,char));
  202. extern Element    HASHlist PROTO((HashEntry *));
  203. #if 0
  204. extern void    HASHlistend PROTO((HashEntry *));
  205. #endif
  206.  
  207. #endif /*HASH_H*/
  208.