#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 "alloc.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_ *)ALLOC_new(&HASH_Table_fl)

#define HASH_Table_destroy(x) ALLOC_destroy(&HASH_Table_fl,(Freelist *)x)

#define HASH_Element_new() (struct Element_ *)ALLOC_new(&HASH_Element_fl)

#define HASH_Element_destroy(x) ALLOC_destroy(&HASH_Element_fl,(Freelist *)(char *)x)

/***********************/

/* function prototypes */

/***********************/

extern SC_EXPRESS_EXPORT void HASHinitialize( void );

extern SC_EXPRESS_EXPORT Hash_Table HASHcreate( unsigned );

extern SC_EXPRESS_EXPORT Hash_Table HASHcopy( Hash_Table );

extern SC_EXPRESS_EXPORT void HASHdestroy( Hash_Table );

extern SC_EXPRESS_EXPORT Element HASHsearch( Hash_Table, Element, Action );

extern SC_EXPRESS_EXPORT void HASHlistinit( Hash_Table, HashEntry * );

extern SC_EXPRESS_EXPORT void HASHlistinit_by_type( Hash_Table, HashEntry *, char );

extern SC_EXPRESS_EXPORT Element HASHlist( HashEntry * );

#endif /*HASH_H*/