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 (c) 1994, 2000 by Sun Microsystems, Inc.
24 * All rights reserved.
25 */
26
27 #pragma ident "%Z%%M% %I% %E% SMI"
28
29 #include <string.h>
30 #include <stdlib.h>
31 #include <stdio.h>
32 #include "med_hash.h"
33 #include "med_local.h"
34
35 #ifdef _KERNEL
36 #define memmove(a, b, c) bcopy(b, a, c)
37 #define memcmp bcmp
38 #define memset(a, '\0', c) bzero(a, c)
39 #define Malloc bkmem_alloc
40 #endif /* _KERNEL */
41
42 #define VERIFY_HASH_REALLOC
43
44 static int
BCMP(void * str1,void * str2,int len)45 BCMP(void *str1, void *str2, int len)
46 {
47 return (memcmp((char *)str1, (char *)str2, len));
48 }
49
50 static int
HASH(void * datap,int datalen,int hsz)51 HASH(void *datap, int datalen, int hsz)
52 {
53 char *cp;
54 int hv = 0;
55
56 for (cp = (char *)datap; cp != ((char *)datap + datalen); hv += *cp++)
57 ;
58 return (hv % hsz);
59 }
60
61 int
init_cache(Cache ** cp,int hsz,int bsz,int (* hfunc)(void *,int,int),int (* cfunc)(void *,void *,int),void (* kffunc)(void *),void (* dffunc)(void *))62 init_cache(
63 Cache **cp,
64 int hsz,
65 int bsz,
66 int (*hfunc)(void *, int, int),
67 int (*cfunc)(void *, void *, int),
68 void (*kffunc)(void *),
69 void (*dffunc)(void *)
70 )
71 {
72 int i;
73
74 if ((*cp = (Cache *) Malloc(sizeof (**cp))) == NULL) {
75 (void) fprintf(stderr, "Malloc(Cache **cp)");
76 return (-1);
77 }
78 (*cp)->bp = (Bucket *) Malloc(sizeof (*(*cp)->bp) * hsz);
79 if ((*cp)->bp == NULL) {
80 (void) fprintf(stderr, "Malloc(Bucket cp->bp)");
81 return (-1);
82 }
83 (*cp)->hsz = hsz;
84 (*cp)->bsz = bsz;
85 for (i = 0; i < (*cp)->hsz; i++) {
86 (*cp)->bp[i].nent = 0;
87 (*cp)->bp[i].nalloc = 0;
88 (*cp)->bp[i].itempp = NULL;
89 }
90 /* Hash function */
91 if (hfunc != (int (*)()) NULL)
92 (*cp)->hfunc = hfunc;
93 else
94 (*cp)->hfunc = HASH;
95
96 /* Compare function */
97 if (cfunc != (int (*)()) NULL)
98 (*cp)->cfunc = cfunc;
99 else
100 (*cp)->cfunc = BCMP;
101
102 /* Key free function */
103 if (kffunc != (void (*)()) NULL)
104 (*cp)->kffunc = kffunc;
105 else
106 (*cp)->kffunc = Free;
107
108 /* Data free function */
109 if (dffunc != (void (*)()) NULL)
110 (*cp)->dffunc = dffunc;
111 else
112 (*cp)->dffunc = Free;
113
114 return (0);
115 }
116
117 int
add_cache(Cache * cp,Item * itemp)118 add_cache(Cache *cp, Item *itemp)
119 {
120 Bucket *bp;
121 Item **titempp;
122
123 if (cp == NULL) {
124 (void) fprintf(stderr,
125 "add_cache(): init_cache() not called.\n");
126 return (-1);
127 }
128
129 bp = &cp->bp[(*cp->hfunc)(itemp->key, itemp->keyl, cp->hsz)];
130 if (bp->nent >= bp->nalloc) {
131 if (bp->nalloc == 0) {
132 bp->itempp =
133 (Item **) Malloc(sizeof (*bp->itempp) * cp->bsz);
134 } else {
135 #ifdef VERIFY_HASH_REALLOC
136 (void) fprintf(stderr,
137 "realloc(%d) bucket=%d\n", bp->nalloc + cp->bsz,
138 (*cp->hfunc)(itemp->key, itemp->keyl, cp->hsz));
139 #endif /* VERIFY_HASH_REALLOC */
140 titempp =
141 (Item **) Malloc(sizeof (*bp->itempp) *
142 (bp->nalloc + cp->bsz));
143 if (titempp != NULL) {
144 (void) memmove((char *)titempp,
145 (char *)bp->itempp,
146 (sizeof (*bp->itempp) * bp->nalloc));
147 #ifdef _KERNEL
148 bkmem_free(bp->itempp,
149 (sizeof (*bp->itempp) * bp->nalloc));
150 #else /* !_KERNEL */
151 Free(bp->itempp);
152 #endif /* _KERNEL */
153 bp->itempp = titempp;
154 } else
155 bp->itempp = NULL;
156 }
157 if (bp->itempp == NULL) {
158 (void) fprintf(stderr,
159 "add_cache(): out of memory\n");
160 return (-1);
161 }
162 bp->nalloc += cp->bsz;
163 }
164 bp->itempp[bp->nent] = itemp;
165 bp->nent++;
166 return (0);
167 }
168
169 Item *
lookup_cache(Cache * cp,void * datap,int datalen)170 lookup_cache(Cache *cp, void *datap, int datalen)
171 {
172 int i;
173 Bucket *bp;
174
175 if (cp == NULL) {
176 (void) fprintf(stderr,
177 "lookup_cache(): init_cache() not called.\n");
178 return (Null_Item);
179 }
180
181 bp = &cp->bp[(*cp->hfunc)(datap, datalen, cp->hsz)];
182 for (i = 0; i < bp->nent; i++)
183 if (!(*cp->cfunc)((void *)bp->itempp[i]->key, datap, datalen))
184 return (bp->itempp[i]);
185 return (Null_Item);
186 }
187
188 Item *
first_item(Cache * cp,int * bidx,int * iidx)189 first_item(Cache *cp, int *bidx, int *iidx)
190 {
191 Item *itemp = Null_Item;
192
193 if (cp == NULL) {
194 (void) fprintf(stderr,
195 "first_item(): init_cache() not called.\n");
196 return (Null_Item);
197 }
198
199 for (*bidx = 0; *bidx < cp->hsz && (cp->bp[*bidx].nalloc == 0 ||
200 cp->bp[*bidx].nent == 0); (*bidx)++)
201 /* void */;
202
203 if (*bidx < cp->hsz && cp->bp[*bidx].nent > 0) {
204 itemp = cp->bp[*bidx].itempp[0];
205 *iidx = 0;
206 } else {
207 *bidx = -1;
208 *iidx = -1;
209 }
210 return (itemp);
211 }
212
213 Item *
next_item(Cache * cp,int * bidx,int * iidx)214 next_item(Cache *cp, int *bidx, int *iidx)
215 {
216 Item *itemp = Null_Item;
217
218 if (cp == NULL) {
219 (void) fprintf(stderr,
220 "next_item(): init_cache() not called.\n");
221 return (Null_Item);
222 }
223
224 if (*bidx < cp->hsz && *bidx >= 0) {
225 if ((*iidx + 1) < cp->bp[*bidx].nent) {
226 itemp = cp->bp[*bidx].itempp[++(*iidx)];
227 } else {
228 for (++(*bidx);
229 *bidx < cp->hsz && (cp->bp[*bidx].nalloc == 0 ||
230 cp->bp[*bidx].nent == 0);
231 (*bidx)++)
232 /* void */;
233 if (*bidx < cp->hsz && cp->bp[*bidx].nent > 0) {
234 *iidx = 0;
235 itemp = cp->bp[*bidx].itempp[(*iidx)++];
236 } else {
237 *bidx = -1;
238 *iidx = -1;
239 }
240 }
241 } else {
242 *bidx = -1;
243 *iidx = -1;
244 }
245 return (itemp);
246 }
247
248 void
des_cache(Cache ** cpp)249 des_cache(Cache **cpp)
250 {
251 Cache *cp = *cpp;
252 Bucket *bp;
253 Item *itemp;
254 int i;
255 int j;
256
257 if (cp == NULL) {
258 (void) fprintf(stderr,
259 "des_cache(): init_cache() not called.\n");
260 return;
261 }
262
263 for (i = 0; i < cp->hsz; i++) {
264 bp = &cp->bp[i];
265 if (bp->nalloc > 0) {
266 for (j = 0; j < bp->nent; j++) {
267 itemp = bp->itempp[j];
268 if (itemp->key)
269 (void) (*cp->kffunc)(itemp->key);
270 if (itemp->data)
271 (void) (*cp->dffunc)(itemp->data);
272 }
273 }
274 (void) Free(bp->itempp);
275 }
276 (void) Free(cp->bp);
277 (void) Free(cp);
278 *cpp = NULL;
279 }
280
281 int
del_cache(Cache * cp,Item * itemp)282 del_cache(Cache *cp, Item *itemp)
283 {
284 Bucket *bp;
285 int bidx;
286 int iidx;
287 int tidx;
288 int retval = 0;
289 void *datap = itemp->key;
290 int datalen = itemp->keyl;
291 Item *titemp;
292
293 if (cp == NULL) {
294 (void) fprintf(stderr,
295 "del_cache(): init_cache() not called.\n");
296 return (-1);
297 }
298
299 bidx = (*cp->hfunc)(datap, datalen, cp->hsz);
300 bp = &cp->bp[bidx];
301
302 for (iidx = 0; iidx < bp->nent; iidx++)
303 if (!(*cp->cfunc)((void *)bp->itempp[iidx]->key, datap,
304 datalen)) {
305 titemp = bp->itempp[iidx];
306 break;
307 }
308 if (iidx < bp->nent) {
309 if (titemp->key)
310 (void) (*cp->kffunc)(titemp->key);
311 if (titemp->data)
312 (void) (*cp->dffunc)(titemp->data);
313 titemp->keyl = 0;
314 titemp->datal = 0;
315 bp->nent--;
316 if (bp->nent == 0) {
317 (void) Free(bp->itempp);
318 bp->itempp = NULL;
319 bp->nalloc = 0;
320 } else {
321 for (tidx = iidx + 1; tidx < (bp->nent + 1); tidx++) {
322 bp->itempp[iidx] = bp->itempp[tidx];
323 iidx = tidx;
324 }
325 }
326 } else {
327 (void) fprintf(stderr,
328 "del_cache(): item not found.\n");
329 retval = -1;
330 }
331 return (retval);
332 }
333
334 #ifdef DEBUG
335 void
cache_stat(Cache * cp,char * tag)336 cache_stat(Cache *cp, char *tag)
337 {
338 Bucket *bp;
339 int bidx;
340
341 if (cp == NULL) {
342 (void) fprintf(stderr,
343 "cache_stat(): init_cache() not called.\n");
344 return;
345 }
346
347 if (tag && *tag)
348 (void) printf("%s", tag);
349
350 for (bidx = 0; bidx < cp->hsz; bidx++) {
351 bp = &cp->bp[bidx];
352 if (bp->nalloc > 0) {
353 (void) printf("Bucket #%d Alloc %d", bidx, bp->nalloc);
354 if (bp->nent > 0) {
355 (void) printf(
356 " Entries %d Reallocs %d", bp->nent,
357 (bp->nalloc / cp->hsz));
358 (void) printf(
359 " Utilization %d%%",
360 ((bp->nent * 100)/bp->nalloc));
361 }
362 (void) printf("\n");
363 (void) fflush(stdout);
364 }
365 }
366 }
367
368 void
pr_cache(Cache * cp,char * tag,void (* pfunc)(void *,int,void *,int))369 pr_cache(Cache *cp, char *tag, void (*pfunc)(void *, int, void *, int))
370 {
371 int bidx;
372 int iidx;
373 Bucket *bp;
374 Item *itemp;
375
376 if (cp == NULL) {
377 (void) fprintf(stderr,
378 "pr_cache(): init_cache() not called.\n");
379 return;
380 }
381
382 if (tag && *tag)
383 (void) printf("%s", tag);
384
385 for (bidx = 0; bidx < cp->hsz; bidx++) {
386 bp = &cp->bp[bidx];
387 if (bp->nent > 0)
388 for (iidx = 0; iidx < bp->nent; iidx++) {
389 itemp = bp->itempp[iidx];
390 (*pfunc)(itemp->key, itemp->keyl,
391 itemp->data, itemp->datal);
392 }
393 }
394 }
395 #endif /* DEBUG */
396