home *** CD-ROM | disk | FTP | other *** search
/ Amiga ACS 1998 #6 / amigaacscoverdisc1998-061998.iso / games / descent / source / main / hash.c < prev    next >
C/C++ Source or Header  |  1998-06-08  |  4KB  |  155 lines
  1. /*
  2. THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
  3. SOFTWARE CORPORATION ("PARALLAX").  PARALLAX, IN DISTRIBUTING THE CODE TO
  4. END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
  5. ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
  6. IN USING, DISPLAYING,  AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
  7. SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
  8. FREE PURPOSES.  IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
  9. CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES.  THE END-USER UNDERSTANDS
  10. AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.  
  11. COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
  12. */
  13. /*
  14.  * $Source: f:/miner/source/main/rcs/hash.c $
  15.  * $Revision: 2.0 $
  16.  * $Author: john $
  17.  * $Date: 1995/02/27 11:28:01 $
  18.  * 
  19.  * Functions to do hash table lookup.
  20.  * 
  21.  * $Log: hash.c $
  22.  * Revision 2.0  1995/02/27  11:28:01  john
  23.  * New version 2.0, which has no anonymous unions, builds with
  24.  * Watcom 10.0, and doesn't require parsing BITMAPS.TBL.
  25.  * 
  26.  * Revision 1.5  1994/12/05  23:37:06  matt
  27.  * Took out calls to warning() function
  28.  * 
  29.  * Revision 1.4  1994/05/09  20:02:33  john
  30.  * Fixed bug w/ upper/lower case.
  31.  * 
  32.  * Revision 1.3  1994/05/06  15:31:51  john
  33.  * Don't add duplicate names to the hash table.
  34.  * 
  35.  * Revision 1.2  1994/05/03  16:45:35  john
  36.  * Added hash table lookup to speed up loading.
  37.  * 
  38.  * Revision 1.1  1994/05/03  10:36:41  john
  39.  * Initial revision
  40.  * 
  41.  * 
  42.  */
  43.  
  44. #pragma off (unreferenced)
  45. static char rcsid[] = "$Id: hash.c 2.0 1995/02/27 11:28:01 john Exp $";
  46. #pragma on (unreferenced)
  47.  
  48. #include <stdlib.h>
  49. #include <stdio.h>
  50. #include <string.h>
  51.  
  52. #include "error.h"
  53. #include "mono.h"
  54. #include "hash.h"
  55. #include "key.h"
  56.     
  57. int hashtable_init( hashtable *ht, int size )    {
  58.     int i;
  59.  
  60.     ht->size=0;
  61.  
  62.     for (i=1; i<12; i++ )    {
  63.         if ( (1<<i) >= size )    {
  64.             ht->bitsize = i;
  65.             ht->size = 1<<i;
  66.             break;
  67.         }
  68.     }
  69.     size = ht->size;
  70.     ht->and_mask = ht->size - 1;
  71.     if (ht->size==0)
  72.         Error( "Hashtable has size of 0" );
  73.  
  74.     ht->key = (char **)malloc( size * sizeof(char *) );
  75.     if (ht->key==NULL)
  76.         Error( "Not enough memory to create a hash table of size %d", size );
  77.  
  78.     for (i=0; i<size; i++ )
  79.         ht->key[i] = NULL;
  80.  
  81.     // Use calloc cause we want zero'd array.
  82.     ht->value = malloc( size*sizeof(int) );
  83.     if (ht->value==NULL)    {
  84.         free(ht->key);
  85.         Error( "Not enough memory to create a hash table of size %d\n", size );
  86.     }
  87.  
  88.     ht->nitems = 0;
  89.  
  90.     return 0;
  91. }
  92.  
  93. void hashtable_free( hashtable *ht )    {
  94.     if (ht->key != NULL )
  95.         free( ht->key );
  96.     if (ht->value != NULL )
  97.         free( ht->value );
  98.     ht->size = 0;
  99. }
  100.  
  101. int hashtable_getkey( char *key )    {
  102.     int k = 0, i=0;
  103.  
  104.     while( *key )    {
  105.         k^=((int)(*key++))<<i;
  106.         i++;
  107.     }
  108.     return k;
  109. }
  110.  
  111. int hashtable_search( hashtable *ht, char *key )    {
  112.     int i,j,k;
  113.  
  114.     strlwr( key );
  115.  
  116.     k = hashtable_getkey( key );
  117.     i = 0;
  118.     
  119.     while(i < ht->size )    {
  120.         j = (k+(i++)) & ht->and_mask;
  121.         if ( ht->key[j] == NULL )
  122.             return -1;
  123.         if (!stricmp(ht->key[j], key ))
  124.             return ht->value[j];
  125.     }
  126.     return -1;
  127. }
  128.  
  129. void hashtable_insert( hashtable *ht, char *key, int value )    {
  130.     int i,j,k;
  131.  
  132. //    mprintf( 0, "Inserting '%s' into hash table\n", key );
  133. //    key_getch();
  134.  
  135.     strlwr( key );
  136.     k = hashtable_getkey( key );
  137.     i = 0;
  138.  
  139.     while(i < ht->size)    {
  140.         j = (k+(i++)) & ht->and_mask;
  141. //        Assert( j < ht->size );
  142. //        mprintf( 0, "Word '%s' (%d) at level %d has value of %d\n", key, k, i-1, j );
  143. //        mprintf( 0, "ht->key[%d]=%.8x\n", j, ht->key[j] );
  144.         if ( ht->key[j] == NULL )    {
  145.             ht->nitems++;
  146.             ht->key[j] = key;
  147.             ht->value[j] = value;
  148.             return;
  149.         } else if (!stricmp( key, ht->key[j] ))    {
  150.             return;
  151.         }
  152.     }
  153.     Error( "Out of hash slots\n" );
  154. }
  155.