misc/hash.c

   1 /* $Id: hash.c,v 1.3 2003-02-18 20:35:35 btb Exp $ */
   2 /*
   3 THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
   4 SOFTWARE CORPORATION ("PARALLAX").  PARALLAX, IN DISTRIBUTING THE CODE TO
   5 END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
   6 ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
   7 IN USING, DISPLAYING,  AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
   8 SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
   9 FREE PURPOSES.  IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
  10 CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES.  THE END-USER UNDERSTANDS
  11 AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.
  12 COPYRIGHT 1993-1999 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
  13 */
  14
  15 #ifdef HAVE_CONFIG_H
  16 #include <conf.h>
  17 #endif
  18
  19 #ifdef RCS
  20 static char rcsid[] = "$Id: hash.c,v 1.3 2003-02-18 20:35:35 btb Exp $";
  21 #endif
  22
  23 #include <stdlib.h>
  24 #include <stdio.h>
  25 #include <string.h>
  26
  27 #include "u_mem.h"
  28 #include "strutil.h"
  29 #include "error.h"
  30 #include "hash.h"
  31
  32 int hashtable_init( hashtable *ht, int size )   {
  33         int i;
  34
  35         ht->size=0;
  36
  37         for (i=1; i<13; i++ )   {
  38                 if ( (1<<i) >= size )   {
  39                         ht->bitsize = i;
  40                         ht->size = 1<<i;
  41                         break;
  42                 }
  43         }
  44         size = ht->size;
  45         ht->and_mask = ht->size - 1;
  46         if (ht->size==0)
  47                 Error( "Hashtable has size of 0" );
  48
  49         ht->key = (char **)d_malloc( size * sizeof(char *) );
  50         if (ht->key==NULL)
  51                 Error( "Not enough memory to create a hash table of size %d", size );
  52
  53         for (i=0; i<size; i++ )
  54                 ht->key[i] = NULL;
  55
  56         // Use calloc cause we want zero'd array.
  57         ht->value = d_malloc( size*sizeof(int) );
  58         if (ht->value==NULL)    {
  59                 d_free(ht->key);
  60                 Error( "Not enough memory to create a hash table of size %d\n", size );
  61         }
  62
  63         ht->nitems = 0;
  64
  65         return 0;
  66 }
  67
  68 void hashtable_free( hashtable *ht )    {
  69         if (ht->key != NULL )
  70                 d_free( ht->key );
  71         if (ht->value != NULL )
  72                 d_free( ht->value );
  73         ht->size = 0;
  74 }
  75
  76 int hashtable_getkey( char *key )       {
  77         int k = 0, i=0;
  78
  79         while( *key )   {
  80                 k^=((int)(*key++))<<i;
  81                 i++;
  82         }
  83         return k;
  84 }
  85
  86 int hashtable_search( hashtable *ht, char *key )        {
  87         int i,j,k;
  88
  89         strlwr( key );
  90
  91         k = hashtable_getkey( key );
  92         i = 0;
  93
  94         while(i < ht->size )    {
  95                 j = (k+(i++)) & ht->and_mask;
  96                 if ( ht->key[j] == NULL )
  97                         return -1;
  98                 if (!stricmp(ht->key[j], key ))
  99                         return ht->value[j];
 100         }
 101         return -1;
 102 }
 103
 104 void hashtable_insert( hashtable *ht, char *key, int value )    {
 105         int i,j,k;
 106
 107         strlwr( key );
 108         k = hashtable_getkey( key );
 109         i = 0;
 110
 111         while(i < ht->size)     {
 112                 j = (k+(i++)) & ht->and_mask;
 113                 if ( ht->key[j] == NULL )       {
 114                         ht->nitems++;
 115                         ht->key[j] = key;
 116                         ht->value[j] = value;
 117                         return;
 118                 } else if (!stricmp( key, ht->key[j] )) {
 119                         return;
 120                 }
 121         }
 122         Error( "Out of hash slots\n" );
 123 }