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