1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22 /*
23 * Copyright 2002 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 #include <synch.h>
31 #include <thread.h>
32 #include <memory.h>
33 #include <assert.h>
34 #include <libproc.h>
35 #include "ramdata.h"
36 #include "proto.h"
37 #include "htbl.h"
38
39
40 htbl_t *
init_hash(unsigned int size)41 init_hash(unsigned int size)
42 {
43 htbl_t *htp;
44 hashb_t *temp;
45 int i;
46
47 if ((size & (size - 1)) != 0)
48 abend("Size must be power of two", NULL);
49
50 htp = (htbl_t *)my_malloc(sizeof (htbl_t), NULL);
51 htp->size = size;
52 htp->tbl = (hashb_t *)
53 my_calloc((size_t)size, sizeof (hashb_t), NULL);
54
55 /* Init mutexes */
56 for (i = 0; i < size; i++) {
57 temp = &htp->tbl[i];
58 (void) mutex_init(&temp->block, USYNC_THREAD, NULL);
59 }
60
61 return (htp);
62 }
63
64 void
destroy_hash(htbl_t * htp)65 destroy_hash(htbl_t *htp)
66 {
67 int i;
68 hentry_t *tmp;
69 hentry_t *prev;
70 hashb_t *cur;
71
72 for (i = 0; i < htp->size; i++) {
73 cur = &htp->tbl[i];
74 (void) mutex_destroy(&cur->block);
75 tmp = cur->first;
76
77 while (tmp != NULL) {
78 prev = tmp;
79 tmp = tmp->next;
80
81 free(prev->key);
82 prev->key = NULL;
83 free(prev->lib);
84 prev->lib = NULL;
85
86 free((char *)prev);
87 if (tmp != NULL)
88 tmp->prev = NULL;
89 }
90 }
91 free((char *)htp->tbl);
92 htp->tbl = NULL;
93 free(htp);
94 }
95
96 static unsigned int
hash_str(char * str,unsigned int sz)97 hash_str(char *str, unsigned int sz)
98 {
99 uint_t hash = 0;
100 uint_t g;
101 char *p;
102
103 assert(str != NULL);
104 for (p = str; *p != '\0'; p++) {
105 hash = (hash << 4) + *p;
106 if ((g = (hash & 0xf0000000)) != 0) {
107 hash ^= (g >> 24);
108 hash ^= g;
109 }
110 }
111
112 return (hash & (sz - 1));
113 }
114
115
116 void
add_fcall(htbl_t * htp,char * lib,char * key,unsigned long cnt)117 add_fcall(htbl_t *htp, char *lib, char *key, unsigned long cnt)
118 {
119 unsigned int bucket;
120 hentry_t *tmp;
121 hentry_t *new;
122 hashb_t *cur;
123
124 bucket = hash_str(key, htp->size);
125 cur = &htp->tbl[bucket];
126
127 (void) mutex_lock(&cur->block);
128
129 tmp = cur->first;
130 while (tmp != NULL) {
131 if (strcmp(tmp->key, key) == 0) {
132 if (strcmp(tmp->lib, lib) == 0) {
133 tmp->count += cnt;
134 (void) mutex_unlock(&cur->block);
135 return;
136 }
137 }
138 tmp = tmp->next;
139 }
140
141 /*
142 * If we're still here, there was no such fcall recorded
143 * so we make a new entry and add it to the table
144 */
145
146 new = (hentry_t *)my_malloc(sizeof (hentry_t), NULL);
147 new->key = strdup(key);
148 if (new->key == NULL)
149 abend("Out of memory in htbl.c", NULL);
150 new->lib = strdup(lib);
151 if (new->lib == NULL)
152 abend("Out of memory in htbl.c", NULL);
153 new->count = cnt;
154 new->prev = NULL;
155 new->next = cur->first;
156 tmp = new->next;
157 if (tmp != NULL) {
158 tmp->prev = new;
159 }
160 cur->first = new;
161
162 (void) mutex_unlock(&cur->block);
163 }
164
165 /*
166 * iterate_hash locks the table and returns an enumeration struct
167 * using this it is possible to iterate through the entries of a hash table
168 * once finished, use iter_free to unlock the table and free the struct
169 */
170
171 hiter_t *
iterate_hash(htbl_t * tbl)172 iterate_hash(htbl_t *tbl)
173 {
174 int b;
175 int i;
176 hiter_t *new;
177 hashb_t *cur;
178 hentry_t *tmp = NULL;
179
180 new = (hiter_t *)my_malloc(sizeof (hiter_t), NULL);
181 new->table = tbl;
182
183 for (i = 0; i < tbl->size; i++) {
184 cur = &tbl->tbl[i];
185 (void) mutex_lock(&cur->block);
186 if (tmp == NULL) {
187 tmp = cur->first;
188 b = i;
189 }
190 }
191
192 new->next = tmp;
193 new->bucket = b;
194
195 return (new);
196 }
197
198 void
iter_free(hiter_t * itr)199 iter_free(hiter_t *itr)
200 {
201 int i;
202 hashb_t *cur;
203 htbl_t *tbl;
204
205 tbl = itr->table;
206 for (i = 0; i < tbl->size; i++) {
207 cur = &tbl->tbl[i];
208 (void) mutex_unlock(&cur->block);
209 }
210
211 free(itr);
212 }
213
214 hentry_t *
iter_next(hiter_t * itr)215 iter_next(hiter_t *itr)
216 {
217 int i;
218 hentry_t *tmp;
219 hentry_t *ret;
220 hashb_t *cur = NULL;
221 htbl_t *hash;
222
223 ret = itr->next;
224
225
226 if (ret == NULL)
227 return (ret);
228
229 hash = itr->table;
230 tmp = ret->next;
231 i = itr->bucket;
232
233 if (tmp == NULL) {
234 for (i = i + 1; i < hash->size; i++) {
235 cur = &hash->tbl[i];
236 tmp = cur->first;
237 if (tmp != NULL)
238 break;
239 }
240 }
241
242 itr->next = tmp;
243 itr->bucket = i;
244
245 return (ret);
246 }
247
248 size_t
elements_in_table(htbl_t * tbl)249 elements_in_table(htbl_t *tbl)
250 {
251 size_t elem = 0;
252 hiter_t *itr = iterate_hash(tbl);
253 hentry_t *tmp = iter_next(itr);
254 while (tmp != NULL) {
255 elem++;
256 tmp = iter_next(itr);
257 }
258 iter_free(itr);
259 return (elem);
260 }
261