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
44static int
45BCMP(void *str1, void *str2, int len)
46{
47	return (memcmp((char *)str1, (char *)str2, len));
48}
49
50static int
51HASH(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
61int
62init_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
117int
118add_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
169Item *
170lookup_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
188Item *
189first_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
213Item *
214next_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
248void
249des_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
281int
282del_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
335void
336cache_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
368void
369pr_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