hash_table.c File Reference

keyword hash tables More...

Go to the source code of this file.

Functions
ptr_hash_table	hash_create (int size)
	HASH_CREATE. More...
void	hash_expand (ptr_hash_table table, int new_size)
	HASH_EXPAND. More...
int	hash_code (ptr_hash_table table, char *symbol)
	HASH_CODE. More...
int	hash_find (ptr_hash_table table, char *symbol)
	hash_find More...
ptr_keyword	hash_lookup (ptr_hash_table table, char *symbol)
	HASH_LOOKUP. More...
void	hash_insert (ptr_hash_table table, char *symbol, ptr_keyword keyword)
	HASH_INSERT. More...
void	hash_display (ptr_hash_table table)
	HASH_DISPLAY. More...

Variables
ptr_definition	first_definition =NULL
long	rand_array [256]

Detailed Description

keyword hash tables

KEYWORDS RM: Feb 3 1993 New version of the keyword table and related routines. The keyword table will not NOT be sorted, however, access will be hashed. Each module has its own hash table of symbols. All definition are stores in a linked list starting at first_definition.

Definition in file hash_table.c.

Function Documentation

int hash_code	(	ptr_hash_table	table,
		char *	symbol
	)

HASH_CODE.

Parameters

table	- ptr_hash_table table
symbol	- char *symbol

Return the hash code for a symbol

Definition at line 79 of file hash_table.c.

References rand_array, and wl_hash_table::size.

{
  int n=0;
  
  /* printf("code of %s ",symbol); */
  
  while(*symbol) {
    n ^= rand_array[*symbol]+rand_array[n&255];
    n++;
    symbol++;
  }
  
  n &= (table->size-1);
  
  
  /* printf("=%d\n",n); */
  
  return n;
}

ptr_hash_table hash_create

(

int

size

)

HASH_CREATE.

Parameters

size	- int size

Create a hash-table for max size keywords.

Definition at line 25 of file hash_table.c.

References NULL, and wl_hash_table::size.

{
  ptr_hash_table new;
  int i;
  
  new=(ptr_hash_table)malloc(sizeof(struct wl_hash_table));
  new->size=size;
  new->used=0;
  new->data=(ptr_keyword *)malloc(size*sizeof(ptr_keyword));
  for(i=0;i<size;i++)
    new->data[i]=NULL;
  return new;
}

void hash_display

(

ptr_hash_table

table

)

HASH_DISPLAY.

Parameters

table

- ptr_hash_table table

Display a symbol table (for debugging).

Definition at line 174 of file hash_table.c.

References hash_code().

{
  int i;
  int n;
  char *s;
  int c=0;
  int t=0;
  
  printf("*** Hash table %lx:\n",(long)table);
  printf("Size: %d\n",table->size);
  printf("Used: %d\n",table->used);
  
  for(i=0;i<table->size;i++)
    if(table->data[i]) {
      t++;
      s=table->data[i]->symbol;
      n=hash_code(table,s);
      
      printf("%4d %4d %s %s\n",
         i,
         n,
         i==n?"ok   ":"*bad*",
         s);
      
      if(i!=n)
    c++;
    }
  
  printf("Really used: %d\n",t);
  printf("Collisions: %d = %1.3f%%\n",
     c,
     100.0*c/(double)t);
}

void hash_expand	(	ptr_hash_table	table,
		int	new_size
	)

HASH_EXPAND.

Parameters

table	- ptr_hash_table table
new_size	- int new_size

Allocate a bigger hash table.

Definition at line 47 of file hash_table.c.

References wl_hash_table::data, hash_insert(), NULL, wl_hash_table::size, and wl_hash_table::used.

{
  ptr_keyword *old_data;
  int old_size;
  int i;

  
  old_data=table->data;
  old_size=table->size;

  table->size=new_size; /* Must be power of 2 */
  table->used=0;
  table->data=(ptr_keyword *)malloc(new_size*sizeof(ptr_keyword));
  
  for(i=0;i<new_size;i++)
    table->data[i]=NULL;
  
  for(i=0;i<old_size;i++)
    if(old_data[i])
      hash_insert(table,old_data[i]->symbol,old_data[i]);

  free(old_data);
}

int hash_find	(	ptr_hash_table	table,
		char *	symbol
	)

hash_find

Parameters

table	- ptr_hash_table table
symbol	- char *symbol

Definition at line 106 of file hash_table.c.

References wl_hash_table::data, hash_code(), wl_hash_table::size, and wl_keyword::symbol.

{
  int n;
  int i=1;
  
  n=hash_code(table,symbol);
  
  while(table->data[n] && strcmp(table->data[n]->symbol,symbol)) {
    /* Not a direct hit... */
    n+= i*i;
    /* i++; */
    n &= table->size-1;
  }
  
  return n;
}

void hash_insert	(	ptr_hash_table	table,
		char *	symbol,
		ptr_keyword	keyword
	)

HASH_INSERT.

Parameters

table	- ptr_hash_table table
symbol	- char *symbol
keyword	- ptr_keyword keyword

Add a symbol and data to a table. Overwrite previous data.

Definition at line 151 of file hash_table.c.

References wl_hash_table::data, hash_expand(), hash_find(), wl_hash_table::size, and wl_hash_table::used.

{
  int n;

  n=hash_find(table,symbol);

  /* printf("inserting %s at %d keyword %x\n",symbol,n,keyword); */
  
  if(!table->data[n])
    table->used++;
  table->data[n]=keyword;
  
  if(table->used*2>table->size)
    hash_expand(table,table->size*2);
}

ptr_keyword hash_lookup	(	ptr_hash_table	table,
		char *	symbol
	)

HASH_LOOKUP.

Parameters

table	- ptr_hash_table table
symbol	- char *symbol

Look up a symbol in the symbol table.

Definition at line 131 of file hash_table.c.

References wl_hash_table::data, and hash_find().

{
  int n;
  
  n=hash_find(table,symbol);
  
  /* printf("found %s at %d keyword %x\n",symbol,n,table->data[n]); */
  
  return table->data[n];
}

Variable Documentation

ptr_definition first_definition =NULL

Definition at line 14 of file hash_table.c.

long rand_array[256]

Definition at line 16 of file hash_table.c.