Partial application of linux/alpha patch. Courtesy of Falk Hueffner <falk.hueffner...
[btb/d2x.git] / 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 }