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