home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / lifeos2.zip / LIFE-1.02 / SOURCE / HASH_TAB.C < prev    next >
C/C++ Source or Header  |  1996-06-04  |  4KB  |  224 lines
  1. /******************************* KEYWORDS *************************************
  2.   RM: Feb 3 1993
  3.   
  4.   New version of the keyword table and related routines.
  5.  
  6.   The keyword table will not NOT be sorted, however, access will be hashed.
  7.  
  8.   Each module has its own hash table of symbols.
  9.  
  10.   All definition are stores in a linked list starting at first_definition.
  11.   */
  12. /*     $Id: hash_table.c,v 1.2 1994/12/08 23:24:09 duchier Exp $     */
  13.  
  14. #ifndef lint
  15. static char vcid[] = "$Id: hash_table.c,v 1.2 1994/12/08 23:24:09 duchier Exp $";
  16. #endif /* lint */
  17.  
  18.  
  19. #include "extern.h"
  20.  
  21.  
  22. ptr_definition first_definition=NULL;
  23.  
  24. int rand_array[256];
  25.  
  26.  
  27.  
  28. /******** HASH_CREATE(size)
  29.   Create a hash-table for max size keywords.
  30.   */
  31.   
  32. ptr_hash_table hash_create(size)
  33.  
  34.      int size;
  35. {
  36.   ptr_hash_table new;
  37.   int i;
  38.   
  39.   new=(ptr_hash_table)malloc(sizeof(struct wl_hash_table));
  40.   new->size=size;
  41.   new->used=0;
  42.   new->data=(ptr_keyword *)malloc(size*sizeof(ptr_keyword));
  43.   for(i=0;i<size;i++)
  44.     new->data[i]=NULL;
  45.   return new;
  46. }
  47.  
  48.  
  49.  
  50. /******** HASH_EXPAND(table,new_size)
  51.   Allocate a bigger hash table.
  52.   */
  53.  
  54. void hash_expand(table,new_size)
  55.  
  56.      ptr_hash_table table;
  57.      int new_size;
  58. {
  59.   ptr_keyword *old_data;
  60.   int old_size;
  61.   int i;
  62.  
  63.   
  64.   old_data=table->data;
  65.   old_size=table->size;
  66.  
  67.   table->size=new_size; /* Must be power of 2 */
  68.   table->used=0;
  69.   table->data=(ptr_keyword *)malloc(new_size*sizeof(ptr_keyword));
  70.   
  71.   for(i=0;i<new_size;i++)
  72.     table->data[i]=NULL;
  73.   
  74.   for(i=0;i<old_size;i++)
  75.     if(old_data[i])
  76.       hash_insert(table,old_data[i]->symbol,old_data[i]);
  77.  
  78.   free(old_data);
  79. }
  80.  
  81.  
  82.  
  83. /******** HASH_CODE(table,symbol)
  84.   Return the hash code for a symbol
  85.   */
  86.  
  87. int hash_code(table,symbol)
  88.      
  89.      ptr_hash_table table;
  90.      char *symbol;
  91. {
  92.   int n=0;
  93.   
  94.   /* printf("code of %s ",symbol); */
  95.   
  96.   while(*symbol) {
  97.     n ^= rand_array[*symbol]+rand_array[n&255];
  98.     n++;
  99.     symbol++;
  100.   }
  101.   
  102.   n &= (table->size-1);
  103.   
  104.   
  105.   /* printf("=%d\n",n); */
  106.   
  107.   return n;
  108. }
  109.  
  110.  
  111.  
  112. int hash_find(table,symbol)
  113.  
  114.      ptr_hash_table table;
  115.      char *symbol;
  116.  
  117. {
  118.   int n;
  119.   int i=1;
  120.   
  121.   n=hash_code(table,symbol);
  122.   
  123.   while(table->data[n] && strcmp(table->data[n]->symbol,symbol)) {
  124.     /* Not a direct hit... */
  125.     n+= i*i;
  126.     /* i++; */
  127.     n &= table->size-1;
  128.   }
  129.   
  130.   return n;
  131. }
  132.  
  133.  
  134.  
  135. /******** HASH_LOOKUP(table,symbol)
  136.   Look up a symbol in the symbol table.
  137.   */
  138.  
  139. ptr_keyword hash_lookup(table,symbol)
  140.      
  141.      ptr_hash_table table;
  142.      char *symbol;
  143.  
  144. {
  145.   int n;
  146.  
  147.   
  148.   n=hash_find(table,symbol);
  149.   
  150.   /* printf("found %s at %d keyword %x\n",symbol,n,table->data[n]); */
  151.   
  152.   return table->data[n];
  153. }
  154.  
  155.  
  156.  
  157. /******** HASH_INSERT(table,symbol,keyword)
  158.   Add a symbol and data to a table. Overwrite previous data.
  159.   */
  160.  
  161. void hash_insert(table,symbol,keyword)
  162.      
  163.      ptr_hash_table table;
  164.      char *symbol;
  165.      ptr_keyword keyword;
  166. {
  167.   int n;
  168.  
  169.  
  170.   n=hash_find(table,symbol);
  171.  
  172.   /* printf("inserting %s at %d keyword %x\n",symbol,n,keyword); */
  173.   
  174.   if(!table->data[n])
  175.     table->used++;
  176.   table->data[n]=keyword;
  177.   
  178.   if(table->used*2>table->size)
  179.     hash_expand(table,table->size*2);
  180. }
  181.  
  182.  
  183.  
  184. /******** HASH_DISPLAY(table)
  185.   Display a symbol table (for debugging).
  186.   */
  187.  
  188. void hash_display(table)
  189.      
  190.      ptr_hash_table table;
  191.      
  192. {
  193.   int i;
  194.   int n;
  195.   char *s;
  196.   int c=0;
  197.   int t=0;
  198.   
  199.   printf("*** Hash table %x:\n",table);
  200.   printf("Size: %d\n",table->size);
  201.   printf("Used: %d\n",table->used);
  202.   
  203.   for(i=0;i<table->size;i++)
  204.     if(table->data[i]) {
  205.       t++;
  206.       s=table->data[i]->symbol;
  207.       n=hash_code(table,s);
  208.       
  209.       printf("%4d %4d %s %s\n",
  210.          i,
  211.          n,
  212.          i==n?"ok   ":"*bad*",
  213.          s);
  214.       
  215.       if(i!=n)
  216.     c++;
  217.     }
  218.   
  219.   printf("Really used: %d\n",t);
  220.   printf("Collisions: %d = %1.3f%%\n",
  221.      c,
  222.      100.0*c/(double)t);
  223. }
  224.