usr/src/lib/libpkg/common/nhash.c

   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 (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21
  22 /*
  23  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26
  27
  28 #include <stdio.h>
  29 #include <string.h>
  30 #include <stdlib.h>
  31 #include <strings.h>
  32 #include "pkglib.h"
  33 #include "nhash.h"
  34 #include "pkglocale.h"
  35
  36 #ifndef _KERNEL
  37 #define bcopy(a, b, c)  (void) memmove(b, a, c)
  38 #define bcmp            memcmp
  39 #define bzero(a, c)     (void) memset(a, '\0', c)
  40 #else   /* _KERNEL */
  41 #define malloc          bkmem_alloc
  42 #endif  /* _KERNEL */
  43
  44 #define VERIFY_HASH_REALLOC
  45
  46 static int
  47 BCMP(void *str1, void *str2, int len)
  48 {
  49         return (bcmp((char *)str1, (char *)str2, len));
  50 }
  51
  52 static int
  53 HASH(void *datap, int datalen, int hsz)
  54 {
  55         char    *cp;
  56         char    *np;
  57         int     hv = 0;
  58
  59         /* determine starting and ending positions */
  60
  61         cp = (char *)datap;
  62         np =  ((char *)cp + datalen);
  63
  64         /* compute hash over all characters from start to end */
  65
  66         while (cp != np) {
  67                 hv += ((int)*cp++);
  68         }
  69
  70         /* return computed hash */
  71
  72         return (hv % hsz);
  73 }
  74
  75 int
  76 init_cache(Cache **cp, int hsz, int bsz,
  77             int (*hfunc)(void *, int, int), int (*cfunc)(void *, void *, int))
  78 {
  79         if ((*cp = (Cache *) malloc(sizeof (**cp))) == NULL) {
  80                 (void) fprintf(stderr, pkg_gt("malloc(Cache **cp)"));
  81                 return (-1);
  82         }
  83         if (((*cp)->bp =
  84             (Bucket *) malloc(sizeof (*(*cp)->bp) * hsz)) == NULL) {
  85                 (void) fprintf(stderr, pkg_gt("malloc(Bucket cp->bp)"));
  86                 return (-1);
  87         }
  88
  89         (*cp)->hsz = hsz;
  90         (*cp)->bsz = bsz;
  91
  92         bzero((*cp)->bp, sizeof (*(*cp)->bp) * hsz);
  93
  94         if (hfunc != (int (*)()) NULL) {
  95                 (*cp)->hfunc = hfunc;
  96         } else {
  97                 (*cp)->hfunc = HASH;
  98         }
  99
 100         if (cfunc != (int (*)()) NULL) {
 101                 (*cp)->cfunc = cfunc;
 102         } else {
 103                 (*cp)->cfunc = BCMP;
 104         }
 105         return (0);
 106 }
 107
 108 int
 109 add_cache(Cache *cp, Item *itemp)
 110 {
 111         Bucket *bp;
 112         Item **titempp;
 113
 114         /*
 115          * If cp is NULL, then init_cache() wasn't called. Quietly return the
 116          * error code and let the caller deal with it.
 117          */
 118         if (cp == NULL)
 119                 return (-1);
 120
 121         bp = &cp->bp[(*cp->hfunc)(itemp->key, itemp->keyl, cp->hsz)];
 122         if (bp->nent >= bp->nalloc) {
 123                 if (bp->nalloc == 0) {
 124                         bp->itempp =
 125                             (Item **) malloc(sizeof (*bp->itempp) * cp->bsz);
 126                 } else {
 127 #ifdef  VERIFY_HASH_REALLOC
 128                         (void) fprintf(stderr,
 129                             pkg_gt("realloc(%d) bucket=%d\n"),
 130                             bp->nalloc + cp->bsz,
 131                             (*cp->hfunc)(itemp->key, itemp->keyl, cp->hsz));
 132 #endif  /* VERIFY_HASH_REALLOC */
 133                         if ((titempp =
 134                             (Item **) malloc(sizeof (*bp->itempp) *
 135                             (bp->nalloc + cp->bsz))) != NULL) {
 136                                 bcopy((char *)bp->itempp, (char *)titempp,
 137                                     (sizeof (*bp->itempp) * bp->nalloc));
 138 #ifdef _KERNEL
 139                                 bkmem_free(bp->itempp,
 140                                         (sizeof (*bp->itempp) * bp->nalloc));
 141 #else   /* !_KERNEL */
 142                                 free(bp->itempp);
 143 #endif  /* _KERNEL */
 144                                 bp->itempp = titempp;
 145                         } else
 146                                 bp->itempp = NULL;
 147                 }
 148                 if (bp->itempp == NULL) {
 149                         (void) fprintf(stderr,
 150                             pkg_gt("add_cache(): out of memory\n"));
 151                         return (-1);
 152                 }
 153                 bp->nalloc += cp->bsz;
 154         }
 155         bp->itempp[bp->nent] = itemp;
 156         bp->nent++;
 157         return (0);
 158 }
 159
 160 Item *
 161 lookup_cache(Cache *cp, void *datap, int datalen)
 162 {
 163         int     i;
 164         Bucket *bp;
 165
 166         /*
 167          * If cp is NULL, then init_cache() wasn't called. Quietly return the
 168          * error code and let the caller deal with it.
 169          */
 170         if (cp == NULL) {
 171             return (Null_Item);
 172         }
 173
 174         bp = &cp->bp[(*cp->hfunc)(datap, datalen, cp->hsz)];
 175
 176         for (i = 0; i < bp->nent; i++) {
 177                 if (!(*cp->cfunc)((void *)bp->itempp[i]->key, datap, datalen)) {
 178                         return (bp->itempp[i]);
 179                 }
 180         }
 181         return (Null_Item);
 182 }