#ifndef HASH_H #define HASH_H /** ********************************************************************** * \file hash.h ** Hash_Table: Hash_Table ** Description: ** ** ** Largely based on code written by ejp@ausmelb.oz ** ** Constants: ** HASH_TABLE_NULL - the null Hash_Table ** ************************************************************************/ /* * This work was supported by the United States Government, and is * not subject to copyright. * * $Log: hash.h,v $ * Revision 1.6 1997/10/22 16:36:49 sauderd * Changed the use and definitions of the compiler macros MUL and DIV. They * seem to be defined and used only within hash.h and hash.c * * Revision 1.5 1997/01/21 19:17:11 dar * made C++ compatible * * Revision 1.4 1993/10/15 18:49:23 libes * CADDETC certified * * Revision 1.3 1992/08/18 17:15:40 libes * rm'd extraneous error messages * * Revision 1.2 1992/05/31 08:36:48 libes * multiple files * * Revision 1.1 1992/05/28 03:56:02 libes * Initial revision * * Revision 1.4 1992/05/14 10:14:33 libes * don't remember * * Revision 1.3 1992/02/12 07:06:15 libes * do sub/supertype * * Revision 1.2 1992/02/09 00:47:45 libes * does ref/use correctly * * Revision 1.1 1992/02/05 08:40:30 libes * Initial revision * * Revision 1.1 1992/01/22 02:17:49 libes * Initial revision * * Revision 1.7 1992/01/15 19:56:15 shepherd * Commented out text after #else and #endif. * * Revision 1.5 91/10/30 08:36:54 silver * Express N14 Changes * * Revision 1.6 1991/08/30 16:36:07 libes * fixed HASHlist to use state from parameter instead of static * * Revision 1.5 1991/08/06 18:55:21 libes * Declared HASHcopy for DICT_copy support * * Revision 1.4 1991/07/19 03:53:36 libes * added action HASH_DELETE * made action HASH_INSERT return failure upon duplicate entry * * Revision 1.3 1991/02/26 21:05:59 libes * Defined routines to visit every element in hash table. * * Revision 1.2 1990/09/06 10:51:11 clark * BPR 2.1 alpha * * Revision 1.1 90/06/11 17:05:54 clark * Initial revision * */ #include "basic.h" /* get basic definitions */ /*************/ /* constants */ /*************/ #define HASH_NULL (Hash_Table)NULL #define SEGMENT_SIZE 256 #define SEGMENT_SIZE_SHIFT 8 /**< log2(SEGMENT_SIZE) */ #define DIRECTORY_SIZE 256 #define DIRECTORY_SIZE_SHIFT 8 /**< log2(DIRECTORY_SIZE) */ #define PRIME1 37 #define PRIME2 1048583 #define MAX_LOAD_FACTOR 5 /*****************/ /* packages used */ /*****************/ #include #include "memory.h" /************/ /* typedefs */ /************/ typedef enum { HASH_FIND, HASH_INSERT, HASH_DELETE } Action; typedef unsigned long Address; /****************/ /* abstractions */ /****************/ typedef struct Element_ { char * key; char * data; struct Element_ * next; Symbol * symbol; /**< for debugging hash conflicts */ char type; /**< user-supplied type */ } * Element; typedef Element * Segment; typedef struct Hash_Table_ { #if 0 int in_use; /**< If someone is traversing the hash table */ #endif unsigned int p; /**< Next bucket to be split */ unsigned int maxp; /**< upper bound on p during expansion */ unsigned int KeyCount; /**< current # keys */ unsigned int SegmentCount; /**< current # segments */ unsigned int MinLoadFactor; unsigned int MaxLoadFactor; Segment Directory[DIRECTORY_SIZE]; } * Hash_Table; typedef struct { unsigned int i; /**< segment index (i think) */ unsigned int j; /**< key index in segment (ditto) */ Element p; /**< usually the next element to be returned */ Hash_Table table; char type; Element e; /**< originally thought of as a place for * the caller of HASHlist to temporarily stash the return value * to allow the caller (i.e., DICTdo) to be macroized, but now * conveniently used by HASHlist, which both stores the ultimate * value here as well as returns it via the return value of HASHlist */ } HashEntry; /********************/ /* global variables */ /********************/ extern SC_EXPRESS_EXPORT struct freelist_head HASH_Table_fl; extern SC_EXPRESS_EXPORT struct freelist_head HASH_Element_fl; /******************************/ /* macro function definitions */ /******************************/ /* ** Fast arithmetic, relying on powers of 2 */ /** The centerline compiler was having problems with MUL and DIV. Where DIV was called like this DIV(NewAddress, SEGMENT_SIZE) it is now being called like DIV(NewAddress, SEGMENT_SIZE_SHIFT). The compiler was mentioning some kind of problem with ##. I wonder if maybe the precompiler was expanding SEGMENT_SIZE (which is also defined as a macro) before turning it into SEGMENT_SIZE_SHIFT. SEGMENT_SIZE and DIRECTORY_SIZE were used to call these macros. They are both defined to be 8 though so it seems these are always being used the same way. This change only seems to have affected hash.h and hash.c */ /* #define MUL(x,y) ((x) << (y##_SHIFT)) */ #define MUL(x,y) ((x) << (y)) /* #define DIV(x,y) ((x) >> (y##_SHIFT)) */ #define DIV(x,y) ((x) >> (y)) #define MOD(x,y) ((x) & ((y)-1)) #define HASH_Table_new() (struct Hash_Table_ *)MEM_new(&HASH_Table_fl) #define HASH_Table_destroy(x) MEM_destroy(&HASH_Table_fl,(Freelist *)(Generic)x) #define HASH_Element_new() (struct Element_ *)MEM_new(&HASH_Element_fl) #define HASH_Element_destroy(x) MEM_destroy(&HASH_Element_fl,(Freelist *)(char *)x) /***********************/ /* function prototypes */ /***********************/ extern SC_EXPRESS_EXPORT void HASHinitialize PROTO( ( void ) ); extern SC_EXPRESS_EXPORT Hash_Table HASHcreate PROTO( ( unsigned ) ); extern SC_EXPRESS_EXPORT Hash_Table HASHcopy PROTO( ( Hash_Table ) ); extern SC_EXPRESS_EXPORT void HASHdestroy PROTO( ( Hash_Table ) ); extern SC_EXPRESS_EXPORT Element HASHsearch PROTO( ( Hash_Table, Element, Action ) ); extern SC_EXPRESS_EXPORT void HASHlistinit PROTO( ( Hash_Table, HashEntry * ) ); extern SC_EXPRESS_EXPORT void HASHlistinit_by_type PROTO( ( Hash_Table, HashEntry *, char ) ); extern SC_EXPRESS_EXPORT Element HASHlist PROTO( ( HashEntry * ) ); #endif /*HASH_H*/