1 /*
2 * Author: William Chia-Wei Cheng (bill.cheng@acm.org)
3 *
4 * Copyright (C) 2001-2009, William Chia-Wei Cheng.
5 *
6 * This file may be distributed under the terms of the Q Public License
7 * as defined by Trolltech AS of Norway and appearing in the file
8 * LICENSE.QPL included in the packaging of this file.
9 *
10 * THIS FILE IS PROVIDED AS IS WITH NO WARRANTY OF ANY KIND, INCLUDING
11 * THE WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
12 * PURPOSE. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL,
13 * INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING
14 * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
15 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
16 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 *
18 * @(#)$Header: /mm2/home/cvs/bc-src/tgif/hash.c,v 1.7 2011/05/16 16:21:57 william Exp $
19 */
20
21 #define _INCLUDE_FROM_HASH_C_
22
23 #include "tgifdefs.h"
24
25 #include "hash.e"
26 #include "msg.e"
27 #include "util.e"
28
29 #define INT_HASH_DATA 0
30 #define STR_HASH_DATA 1
31
32 typedef struct tagHashData {
33 char *psz_key;
34 int key_sz;
35 int type;
36 union {
37 char *sval;
38 int ival;
39 } detail;
40 } HashData;
41
42 /* ------------------ Utility Functions ------------------ */
43
44 static
FreeHashData(phd)45 void FreeHashData(phd)
46 HashData *phd;
47 {
48 switch (phd->type) {
49 case INT_HASH_DATA: break;
50 case STR_HASH_DATA: UtilFree(phd->detail.sval); break;
51 }
52 UtilFree(phd->psz_key);
53 free(phd);
54 }
55
56 static
NewIntHashData(psz_key,key_sz,ival)57 HashData *NewIntHashData(psz_key, key_sz, ival)
58 char *psz_key;
59 int key_sz, ival;
60 {
61 HashData *phd=(HashData*)malloc(sizeof(HashData));
62
63 if (phd == NULL) FailAllocMessage();
64
65 memset(phd, 0, sizeof(HashData));
66 phd->psz_key = (char*)malloc(key_sz);
67 if (phd->psz_key == NULL) FailAllocMessage();
68 memcpy(phd->psz_key, psz_key, key_sz);
69 phd->key_sz = key_sz;
70 phd->type = INT_HASH_DATA;
71 phd->detail.ival = ival;
72
73 return phd;
74 }
75
76 static
NewStrHashData(psz_key,key_sz,psz_value)77 HashData *NewStrHashData(psz_key, key_sz, psz_value)
78 char *psz_key, *psz_value;
79 int key_sz;
80 {
81 HashData *phd=(HashData*)malloc(sizeof(HashData));
82
83 if (phd == NULL) FailAllocMessage();
84
85 memset(phd, 0, sizeof(HashData));
86 phd->psz_key = (char*)malloc(key_sz);
87 if (phd->psz_key == NULL) FailAllocMessage();
88 memcpy(phd->psz_key, psz_key, key_sz);
89 phd->type = STR_HASH_DATA;
90 phd->detail.sval = UtilStrDup(psz_value);
91 if (phd->detail.sval == NULL) FailAllocMessage();
92
93 return phd;
94 }
95
96 static
GetBucket(p_hash,psz_key,key_sz)97 unsigned int GetBucket(p_hash, psz_key, key_sz)
98 TgHash *p_hash;
99 char *psz_key;
100 int key_sz;
101 {
102 unsigned int ival=0, ival2=0, bucket=0;
103
104 switch (key_sz) {
105 case 0: return FALSE;
106 case 1:
107 ival = (unsigned int)(unsigned char)*psz_key;
108 break;
109 case 2:
110 ival = ((((unsigned int)(unsigned char)psz_key[0]) & 0x0ff) << 8) |
111 (((unsigned int)(unsigned char)psz_key[1]) & 0x0ff);
112 break;
113 case 3:
114 ival = ((((unsigned int)(unsigned char)psz_key[0]) & 0x0ff) << 16) |
115 ((((unsigned int)(unsigned char)psz_key[1]) & 0x0ff) << 8) |
116 (((unsigned int)(unsigned char)psz_key[2]) & 0x0ff);
117 break;
118 default:
119 for ( ; key_sz >= 4; key_sz-=4) {
120 ival2 =
121 ((((unsigned int)(unsigned char)psz_key[0]) & 0x0ff) << 24) |
122 ((((unsigned int)(unsigned char)psz_key[1]) & 0x0ff) << 16) |
123 ((((unsigned int)(unsigned char)psz_key[2]) & 0x0ff) << 8) |
124 (((unsigned int)(unsigned char)psz_key[3]) & 0x0ff);
125
126 ival = (ival>>1) ^ ival2;
127 psz_key = &psz_key[4];
128 }
129 switch (key_sz) {
130 case 0: break;
131 case 1:
132 ival2 = ((((unsigned int)(unsigned char)psz_key[0]) & 0x0ff) << 24);
133 ival = (ival>>1) ^ ival2;
134 break;
135 case 2:
136 ival2 =
137 ((((unsigned int)(unsigned char)psz_key[0]) & 0x0ff) << 24) |
138 ((((unsigned int)(unsigned char)psz_key[1]) & 0x0ff) << 16);
139 ival = (ival>>1) ^ ival2;
140 break;
141 case 3:
142 ival2 =
143 ((((unsigned int)(unsigned char)psz_key[0]) & 0x0ff) << 24) |
144 ((((unsigned int)(unsigned char)psz_key[1]) & 0x0ff) << 16) |
145 ((((unsigned int)(unsigned char)psz_key[2]) & 0x0ff) << 8);
146 ival = (ival>>1) ^ ival2;
147 break;
148 }
149 break;
150 }
151 bucket = ival % p_hash->num_buckets;
152
153 return bucket;
154 }
155
156 /* ------------------ CleanUpHash() ------------------ */
157
CleanUpHash(p_hash)158 void CleanUpHash(p_hash)
159 TgHash *p_hash;
160 {
161 int i=0;
162
163 for (i=0; i < p_hash->num_buckets; i++) {
164 CVList *p_list=(&p_hash->buckets[i]);
165
166 if (ListLength(p_list) > 0) {
167 CVListElem *e=NULL;
168
169 for (e=ListFirst(p_list); e != NULL; e=ListNext(p_list,e)) {
170 HashData *phd=(HashData*)(e->obj);
171
172 FreeHashData(phd);
173 }
174 ListUnlinkAll(p_list);
175 }
176 }
177 free(p_hash->buckets);
178 }
179
180 /* ------------------ InitHash() ------------------ */
181
InitHash(p_hash,which)182 int InitHash(p_hash, which)
183 TgHash *p_hash;
184 int which;
185 {
186 int i=0;
187
188 switch (which) {
189 case TG_HASH_SIZE_SMALL: break;
190 case TG_HASH_SIZE_MEDIUM: break;
191 case TG_HASH_SIZE_LARGE: break;
192 default: return FALSE;
193 }
194 p_hash->num_buckets = which;
195 p_hash->buckets = (CVList*)malloc(which*sizeof(CVList));
196 if (p_hash->buckets == NULL) FailAllocMessage();
197 memset(p_hash->buckets, 0, which*sizeof(CVList));
198
199 for (i=0; i < which; i++) {
200 CVListInit(&p_hash->buckets[i]);
201 }
202 return TRUE;
203 }
204
205 /* ------------------ HashStoreInt() ------------------ */
206
HashStoreInt(p_hash,psz_key,key_sz,ival)207 int HashStoreInt(p_hash, psz_key, key_sz, ival)
208 TgHash *p_hash;
209 char *psz_key;
210 int key_sz, ival;
211 {
212 unsigned int bucket=GetBucket(p_hash, psz_key, key_sz);
213 CVList *list=(&p_hash->buckets[bucket]);
214 HashData *phd=NewIntHashData(psz_key, key_sz, ival);
215
216 ListPrepend(list, phd);
217
218 return TRUE;
219 }
220
221 /* ------------------ HashStoreStr() ------------------ */
222
HashStoreStr(p_hash,psz_key,key_sz,psz_val)223 int HashStoreStr(p_hash, psz_key, key_sz, psz_val)
224 TgHash *p_hash;
225 char *psz_key, *psz_val;
226 int key_sz;
227 {
228 unsigned int bucket=GetBucket(p_hash, psz_key, key_sz);
229 CVList *list=(&p_hash->buckets[bucket]);
230 HashData *phd=NewStrHashData(psz_key, key_sz, psz_val);
231
232 ListPrepend(list, phd);
233
234 return TRUE;
235 }
236
237 /* ------------------ HashLookUpInt() ------------------ */
238
HashLookUpInt(p_hash,psz_key,key_sz,pn_value_return)239 int HashLookUpInt(p_hash, psz_key, key_sz, pn_value_return)
240 TgHash *p_hash;
241 char *psz_key;
242 int key_sz, *pn_value_return;
243 {
244 unsigned int bucket=GetBucket(p_hash, psz_key, key_sz);
245 CVList *list=(&p_hash->buckets[bucket]);
246 CVListElem *e=NULL;
247
248 for (e=ListFirst(list); e != NULL; e=ListNext(list,e)) {
249 HashData *phd=(HashData*)(e->obj);
250
251 if (phd->key_sz == key_sz && memcmp(phd->psz_key, psz_key, key_sz) == 0) {
252 if (phd->type == INT_HASH_DATA) {
253 *pn_value_return = phd->detail.ival;
254 return TRUE;
255 }
256 return FALSE;
257 }
258 }
259 return FALSE;
260 }
261
262 /* ------------------ HashLookUpStr() ------------------ */
263
HashLookUpStr(p_hash,psz_key,key_sz)264 char *HashLookUpStr(p_hash, psz_key, key_sz)
265 TgHash *p_hash;
266 char *psz_key;
267 int key_sz;
268 {
269 unsigned int bucket=GetBucket(p_hash, psz_key, key_sz);
270 CVList *list=(&p_hash->buckets[bucket]);
271 CVListElem *e=NULL;
272
273 for (e=ListFirst(list); e != NULL; e=ListNext(list,e)) {
274 HashData *phd=(HashData*)(e->obj);
275
276 if (phd->key_sz == key_sz && memcmp(phd->psz_key, psz_key, key_sz) == 0) {
277 if (phd->type == STR_HASH_DATA) {
278 return phd->detail.sval;
279 }
280 return NULL;
281 }
282 }
283 return NULL;
284 }
285
286