205 lines
6.3 KiB
C
205 lines
6.3 KiB
C
#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 <sc_export.h>
|
|
#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*/
|