Commit | Line | Data |
---|---|---|
86530b38 AT |
1 | /* |
2 | * ========== Copyright Header Begin ========================================== | |
3 | * | |
4 | * OpenSPARC T2 Processor File: hasher.c | |
5 | * Copyright (C) 1995-2007 Sun Microsystems, Inc. All Rights Reserved | |
6 | * 4150 Network Circle, Santa Clara, California 95054, U.S.A. | |
7 | * | |
8 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
9 | * | |
10 | * This program is free software; you can redistribute it and/or modify | |
11 | * it under the terms of the GNU General Public License as published by | |
12 | * the Free Software Foundation; version 2 of the License. | |
13 | * | |
14 | * This program is distributed in the hope that it will be useful, | |
15 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
16 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
17 | * GNU General Public License for more details. | |
18 | * | |
19 | * You should have received a copy of the GNU General Public License | |
20 | * along with this program; if not, write to the Free Software | |
21 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
22 | * | |
23 | * For the avoidance of doubt, and except that if any non-GPL license | |
24 | * choice is available it will apply instead, Sun elects to use only | |
25 | * the General Public License version 2 (GPLv2) at this time for any | |
26 | * software where a choice of GPL license versions is made | |
27 | * available with the language indicating that GPLv2 or any later version | |
28 | * may be used, or where a choice of which version of the GPL is applied is | |
29 | * otherwise unspecified. | |
30 | * | |
31 | * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
32 | * CA 95054 USA or visit www.sun.com if you need additional information or | |
33 | * have any questions. | |
34 | * | |
35 | * | |
36 | * ========== Copyright Header End ============================================ | |
37 | */ | |
38 | #include <stdlib.h> | |
39 | #include <stdio.h> | |
40 | #include <string.h> | |
41 | #include <math.h> | |
42 | #include <assert.h> | |
43 | #include "hasher.h" | |
44 | ||
45 | struct hash_ent | |
46 | { | |
47 | struct hash_ent *next; | |
48 | unsigned long h_hash; | |
49 | char *key; | |
50 | void *data; | |
51 | }; | |
52 | ||
53 | struct hash_tbl | |
54 | { | |
55 | long size; | |
56 | long mask; | |
57 | long used; | |
58 | long limit; | |
59 | struct hash_ent **tbl; | |
60 | }; | |
61 | ||
62 | HASH_TBL *ht_new(unsigned int ht_size) | |
63 | /* ht_size should be power of 2 */ | |
64 | { | |
65 | HASH_TBL *retval; | |
66 | retval=(HASH_TBL *)malloc(sizeof(HASH_TBL)); | |
67 | int i; | |
68 | ||
69 | if (retval==NULL) | |
70 | { | |
71 | perror("Not enough memory to create hash table..."); | |
72 | } | |
73 | ||
74 | retval->size=(long)pow(2.0, log((double)ht_size)/log(2.0) + 0.5 ); | |
75 | retval->mask=retval->size-1; | |
76 | retval->limit=(retval->size*2)/3; | |
77 | retval->used=0; | |
78 | ||
79 | retval->tbl=(struct hash_ent **)malloc(retval->size*sizeof(struct hash_ent *)); | |
80 | if (retval->tbl==NULL) | |
81 | { | |
82 | perror("Not enough memory to create hash table entries..."); | |
83 | } | |
84 | ||
85 | for(i=0; i<retval->size; retval->tbl[i++]=0) | |
86 | ; | |
87 | ||
88 | return retval; | |
89 | } | |
90 | ||
91 | /* GCCism, get rid of inline if we migrate away from GCC */ | |
92 | static unsigned long hash_value(const char *string) | |
93 | { | |
94 | unsigned char *p; /* or signed char *, not really important */ | |
95 | unsigned long h; | |
96 | ||
97 | h = 0; | |
98 | for (p = (unsigned char *)string; *p != '\0'; p++) | |
99 | h = h * 33 + *p; | |
100 | ||
101 | return h; | |
102 | } | |
103 | ||
104 | static void expand_table(register HASH_TBL *table) | |
105 | { | |
106 | register int n = table->size * 2, i; | |
107 | register struct hash_ent *p, **h, **newh, **oldh, *q; | |
108 | ||
109 | newh = (struct hash_ent **)malloc(n * sizeof *newh); | |
110 | if (newh==NULL) | |
111 | { | |
112 | perror("Not enough memory to expand hash table..."); | |
113 | } | |
114 | ||
115 | for (h = newh, i = n; --i >= 0;) | |
116 | *h++=0; | |
117 | ||
118 | oldh = table->tbl; | |
119 | n--; /* change to mask */ | |
120 | for (i = table->size; --i >= 0;) | |
121 | { | |
122 | for (p = *oldh++; p != NULL; p = q) | |
123 | { | |
124 | q = p->next; | |
125 | p->next = newh[p->h_hash & n]; | |
126 | newh[p->h_hash & n] = p; | |
127 | } | |
128 | } | |
129 | ||
130 | free((char *)table->tbl); | |
131 | table->tbl = newh; | |
132 | table->mask = n; | |
133 | table->size = ++n; | |
134 | table->limit= (table->size*2)/3; | |
135 | } | |
136 | ||
137 | void *ht_get(HASH_TBL *table, const char *key) | |
138 | { | |
139 | struct hash_ent *ptr; | |
140 | unsigned long hash=hash_value(key); | |
141 | ||
142 | for (ptr=table->tbl[hash&table->mask]; ptr && strcmp(key, ptr->key); | |
143 | ptr=ptr->next) | |
144 | ; | |
145 | ||
146 | return ptr ? ptr->data : NULL; | |
147 | } | |
148 | ||
149 | /* assumes that entry is not already in table */ | |
150 | void ht_put(HASH_TBL *table, char *key, void *data) | |
151 | { | |
152 | struct hash_ent *newnode; | |
153 | newnode=(struct hash_ent *)malloc(sizeof(struct hash_ent)); | |
154 | unsigned long hash=hash_value(key); | |
155 | ||
156 | if (newnode==NULL) | |
157 | { | |
158 | perror("Not enough memory to add to hash table..."); | |
159 | } | |
160 | ||
161 | newnode->h_hash=hash; | |
162 | newnode->key=strdup(key); | |
163 | newnode->data=data; | |
164 | newnode->next=table->tbl[hash&table->mask]; | |
165 | table->tbl[hash&table->mask]=newnode; | |
166 | table->used++; | |
167 | if (table->used>table->limit) | |
168 | expand_table(table); | |
169 | } | |
170 | ||
171 | char *ht_rm_ent(HASH_TBL *table, char *key) | |
172 | { | |
173 | unsigned long hash=hash_value(key); | |
174 | struct hash_ent *nxt=0, *prv=0; | |
175 | char *retval=0; | |
176 | ||
177 | for (nxt=table->tbl[hash&table->mask]; nxt && strcmp(key, nxt->key); | |
178 | prv=nxt, nxt=nxt->next) | |
179 | ; | |
180 | ||
181 | if (nxt) | |
182 | { | |
183 | if (!prv) | |
184 | { | |
185 | table->tbl[hash&table->mask]=nxt->next; | |
186 | } else | |
187 | prv->next=nxt->next; | |
188 | retval=(char*)nxt->data; | |
189 | free((void *)nxt); | |
190 | } | |
191 | ||
192 | return retval; | |
193 | } | |
194 | ||
195 | /* returns a sorted list of (void *), | |
196 | each of which points to one of the objects in the hash table */ | |
197 | /* The list is sorted by data. The comparison routine doesn't get the key | |
198 | explicitly so if you want to sort by key you have to get what the keys are | |
199 | some other way (such as if the key happens to be in the objects pointed by | |
200 | the void pointers). Yes, the return type is "wrong", you can't get it | |
201 | "right" in C anyways.*/ | |
202 | /* it takes a comparison function, which gets passed into qsort() */ | |
203 | /* be careful since qsort() will give the comparison function a pointer | |
204 | to a pointer to the actual object */ | |
205 | /* a 0 terminates the list */ | |
206 | void *ht_sorted_list(HASH_TBL *table, int (*cmp)(const void *, const void *)) | |
207 | { | |
208 | void **list=(void**)malloc((table->used+1)*sizeof(void *)); | |
209 | long i=0; | |
210 | long bucket; | |
211 | struct hash_ent *p, **h; | |
212 | ||
213 | h = table->tbl; | |
214 | for(bucket=table->size; --bucket >=0; ) | |
215 | { | |
216 | for (p = *h++; p; p = p->next) | |
217 | { | |
218 | if(p->data) | |
219 | list[i++]=p->data; | |
220 | } | |
221 | } | |
222 | assert(i<=table->used); | |
223 | fflush(stdout); | |
224 | qsort(list, i, sizeof(void *), cmp); | |
225 | list[i]=0; | |
226 | ||
227 | fflush(stdout); | |
228 | return list; | |
229 | } | |
230 | ||
231 | /* this only frees all memory if the data have already been freed somehow */ | |
232 | void ht_delete(HASH_TBL *table) | |
233 | { | |
234 | long i; | |
235 | struct hash_ent *p, *q, **ht; | |
236 | ||
237 | for(i=table->size, ht=table->tbl; --i>=0;) | |
238 | { | |
239 | for (p=*ht++; p; p=q) | |
240 | { | |
241 | q=p->next; | |
242 | free(p->key); | |
243 | free((void *)p); | |
244 | } | |
245 | } | |
246 | ||
247 | free((void *)table->tbl); | |
248 | free((void *)table); | |
249 | } |