# include "jam.h"
# include "hash.h"
char *hashsccssid="@(#)hash.c 1.14 () 6/20/88";
struct hashhdr {
struct item *next;
int keyval;
} ;
struct hashdata {
char *key;
} ;
typedef struct item {
struct hashhdr hdr;
struct hashdata data;
} ITEM ;
# define MAX_LISTS 32
struct hash
{
struct {
int nel;
ITEM **base;
} tab;
int bloat;
int inel;
struct {
int more;
char *next;
int datalen;
int size;
int nel;
int list;
struct {
int nel;
char *base;
} lists[ MAX_LISTS ];
} items;
char *name;
} ;
static void hashrehash();
static void hashstat();
int
hashitem( hp, data, enter )
register struct hash *hp;
HASHDATA **data;
{
ITEM **base;
register ITEM *i;
char *b = (*data)->key;
int keyval;
if( enter && !hp->items.more )
hashrehash( hp );
if( !enter && !hp->items.nel )
return 0;
keyval = *b;
while( *b )
keyval = keyval * 2147059363 + *b++;
keyval &= 0x7FFFFFFF;
base = hp->tab.base + ( keyval % hp->tab.nel );
for( i = *base; i; i = i->hdr.next )
if( keyval == i->hdr.keyval &&
!strcmp( i->data.key, (*data)->key ) )
{
*data = &i->data;
return !0;
}
if( enter )
{
i = (ITEM *)hp->items.next;
hp->items.next += hp->items.size;
hp->items.more--;
memcpy( (char *)&i->data, (char *)*data, hp->items.datalen );
i->hdr.keyval = keyval;
i->hdr.next = *base;
*base = i;
*data = &i->data;
}
return 0;
}
static void hashrehash( hp )
register struct hash *hp;
{
int i = ++hp->items.list;
hp->items.more = i ? 2 * hp->items.nel : hp->inel;
hp->items.next = (char *)malloc( hp->items.more * hp->items.size );
hp->items.lists[i].nel = hp->items.more;
hp->items.lists[i].base = hp->items.next;
hp->items.nel += hp->items.more;
if( hp->tab.base )
free( (char *)hp->tab.base );
hp->tab.nel = hp->items.nel * hp->bloat;
hp->tab.base = (ITEM **)malloc( hp->tab.nel * sizeof(ITEM **) );
memset( (char *)hp->tab.base, '\0', hp->tab.nel * sizeof( ITEM * ) );
for( i = 0; i < hp->items.list; i++ )
{
int nel = hp->items.lists[i].nel;
char *next = hp->items.lists[i].base;
for( ; nel--; next += hp->items.size )
{
register ITEM *i = (ITEM *)next;
ITEM **ip = hp->tab.base + i->hdr.keyval % hp->tab.nel;
i->hdr.next = *ip;
*ip = i;
}
}
}
# define ALIGNED(x) ( ( x + sizeof( ITEM ) - 1 ) & ~( sizeof( ITEM ) - 1 ) )
struct hash *
hashinit( datalen, name )
char *name;
{
struct hash *hp = (struct hash *)malloc( sizeof( *hp ) );
hp->bloat = 3;
hp->tab.nel = 0;
hp->tab.base = (ITEM **)0;
hp->items.more = 0;
hp->items.datalen = datalen;
hp->items.size = sizeof( struct hashhdr ) + ALIGNED( datalen );
hp->items.list = -1;
hp->items.nel = 0;
hp->inel = 11;
hp->name = name;
return hp;
}
void
hashdone( hp )
struct hash *hp;
{
int i;
if( !hp )
return;
if( DEBUG_MEM )
hashstat( hp );
if( hp->tab.base )
free( (char *)hp->tab.base );
for( i = 0; i <= hp->items.list; i++ )
free( hp->items.lists[i].base );
free( (char *)hp );
}
static void
hashstat( hp )
struct hash *hp;
{
ITEM **tab = hp->tab.base;
int nel = hp->tab.nel;
int count = 0;
int sets = 0;
int run = ( tab[ nel - 1 ] != (ITEM *)0 );
int i, here;
for( i = nel; i > 0; i-- )
{
if( (here = ( *tab++ != (ITEM *)0 )) != 0 )
count++;
if( here && !run )
sets++;
run = here;
}
printf( "%s table: %d+%d+%d (%dK+%dK) items+table+hash, %f density\n",
hp->name,
count,
hp->items.nel,
hp->tab.nel,
hp->items.nel * hp->items.size / 1024,
hp->tab.nel * (int)sizeof( ITEM ** ) / 1024,
(float)count / (float)sets );
}
#ifdef APPLE_EXTENSIONS
void
hashiterate( hp, iterfunc, contextinfo )
struct hash *hp;
hashiterfunc *iterfunc;
void *contextinfo;
{
register int i;
for( i = 0; i < hp->tab.nel; i++ )
{
register ITEM *item = hp->tab.base[i];
while ( item != NULL )
{
(iterfunc)(hp, &item->data, contextinfo);
item = item->hdr.next;
}
}
}
#endif