misc/hash.c

   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-1999 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
  12 */
  13
  14 #ifdef HAVE_CONFIG_H
  15 #include <conf.h>
  16 #endif
  17
  18 #ifdef RCS
  19 static char rcsid[] = "$Id: hash.c,v 1.2 2001-01-31 15:18:04 bradleyb Exp $";
  20 #endif
  21
  22 #include <stdlib.h>
  23 #include <stdio.h>
  24 #include <string.h>
  25
  26 #include "u_mem.h"
  27 #include "strutil.h"
  28 #include "error.h"
  29 #include "hash.h"
  30
  31 int hashtable_init( hashtable *ht, int size )   {
  32         int i;
  33
  34         ht->size=0;
  35
  36         for (i=1; i<13; i++ )   {
  37                 if ( (1<<i) >= size )   {
  38                         ht->bitsize = i;
  39                         ht->size = 1<<i;
  40                         break;
  41                 }
  42         }
  43         size = ht->size;
  44         ht->and_mask = ht->size - 1;
  45         if (ht->size==0)
  46                 Error( "Hashtable has size of 0" );
  47
  48         ht->key = (char **)d_malloc( size * sizeof(char *) );
  49         if (ht->key==NULL)
  50                 Error( "Not enough memory to create a hash table of size %d", size );
  51
  52         for (i=0; i<size; i++ )
  53                 ht->key[i] = NULL;
  54
  55         // Use calloc cause we want zero'd array.
  56         ht->value = d_malloc( size*sizeof(int) );
  57         if (ht->value==NULL)    {
  58                 d_free(ht->key);
  59                 Error( "Not enough memory to create a hash table of size %d\n", size );
  60         }
  61
  62         ht->nitems = 0;
  63
  64         return 0;
  65 }
  66
  67 void hashtable_free( hashtable *ht )    {
  68         if (ht->key != NULL )
  69                 d_free( ht->key );
  70         if (ht->value != NULL )
  71                 d_free( ht->value );
  72         ht->size = 0;
  73 }
  74
  75 int hashtable_getkey( char *key )       {
  76         int k = 0, i=0;
  77
  78         while( *key )   {
  79                 k^=((int)(*key++))<<i;
  80                 i++;
  81         }
  82         return k;
  83 }
  84
  85 int hashtable_search( hashtable *ht, char *key )        {
  86         int i,j,k;
  87
  88         strlwr( key );
  89
  90         k = hashtable_getkey( key );
  91         i = 0;
  92
  93         while(i < ht->size )    {
  94                 j = (k+(i++)) & ht->and_mask;
  95                 if ( ht->key[j] == NULL )
  96                         return -1;
  97                 if (!stricmp(ht->key[j], key ))
  98                         return ht->value[j];
  99         }
 100         return -1;
 101 }
 102
 103 void hashtable_insert( hashtable *ht, char *key, int value )    {
 104         int i,j,k;
 105
 106         strlwr( key );
 107         k = hashtable_getkey( key );
 108         i = 0;
 109
 110         while(i < ht->size)     {
 111                 j = (k+(i++)) & ht->and_mask;
 112                 if ( ht->key[j] == NULL )       {
 113                         ht->nitems++;
 114                         ht->key[j] = key;
 115                         ht->value[j] = value;
 116                         return;
 117                 } else if (!stricmp( key, ht->key[j] )) {
 118                         return;
 119                 }
 120         }
 121         Error( "Out of hash slots\n" );
 122 }