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 45 BCMP(void *str1, void *str2, int len) 46 { 47 return (memcmp((char *)str1, (char *)str2, len)); 48 } 49 50 static int 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 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 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 * 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 * 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 * 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 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 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 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 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