libpkg/common/nhash.c

5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland/*
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * CDDL HEADER START
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland *
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * The contents of this file are subject to the terms of the
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * Common Development and Distribution License (the "License").
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * You may not use this file except in compliance with the License.
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland *
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * or http://www.opensolaris.org/os/licensing.
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * See the License for the specific language governing permissions
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * and limitations under the License.
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland *
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * When distributing Covered Code, include this CDDL HEADER in each
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * If applicable, add the following below this CDDL HEADER, with the
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * fields enclosed by brackets "[]" replaced with your own identifying
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * information: Portions Copyright [yyyy] [name of copyright owner]
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland *
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * CDDL HEADER END
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland */
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland/*
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland * Use is subject to license terms.
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland */
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#include <stdio.h>
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#include <string.h>
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#include <stdlib.h>
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#include <strings.h>
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#include "pkglib.h"
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#include "nhash.h"
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#include "pkglocale.h"
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#ifndef _KERNEL
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#define bcopy(a, b, c)  (void) memmove(b, a, c)
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#define bcmp        memcmp
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#define bzero(a, c) (void) memset(a, '\0', c)
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#else   /* _KERNEL */
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#define malloc      bkmem_alloc
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#endif  /* _KERNEL */
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#define VERIFY_HASH_REALLOC
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterlandstatic int
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah WaterlandBCMP(void *str1, void *str2, int len)
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland{
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    return (bcmp((char *)str1, (char *)str2, len));
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland}
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterlandstatic int
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah WaterlandHASH(void *datap, int datalen, int hsz)
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland{
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    char    *cp;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    char    *np;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    int hv = 0;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    /* determine starting and ending positions */
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    cp = (char *)datap;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    np =  ((char *)cp + datalen);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    /* compute hash over all characters from start to end */
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    while (cp != np) {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        hv += ((int)*cp++);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    }
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    /* return computed hash */
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    return (hv % hsz);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland}
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterlandint
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterlandinit_cache(Cache **cp, int hsz, int bsz,
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        int (*hfunc)(void *, int, int), int (*cfunc)(void *, void *, int))
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland{
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    if ((*cp = (Cache *) malloc(sizeof (**cp))) == NULL) {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        (void) fprintf(stderr, pkg_gt("malloc(Cache **cp)"));
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        return (-1);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    }
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    if (((*cp)->bp =
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        (Bucket *) malloc(sizeof (*(*cp)->bp) * hsz)) == NULL) {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        (void) fprintf(stderr, pkg_gt("malloc(Bucket cp->bp)"));
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        return (-1);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    }
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    (*cp)->hsz = hsz;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    (*cp)->bsz = bsz;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    bzero((*cp)->bp, sizeof (*(*cp)->bp) * hsz);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    if (hfunc != (int (*)()) NULL) {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        (*cp)->hfunc = hfunc;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    } else {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        (*cp)->hfunc = HASH;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    }
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    if (cfunc != (int (*)()) NULL) {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        (*cp)->cfunc = cfunc;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    } else {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        (*cp)->cfunc = BCMP;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    }
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    return (0);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland}
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterlandint
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterlandadd_cache(Cache *cp, Item *itemp)
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland{
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    Bucket *bp;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    Item **titempp;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    /*
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland     * If cp is NULL, then init_cache() wasn't called. Quietly return the
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland     * error code and let the caller deal with it.
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland     */
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    if (cp == NULL)
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        return (-1);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    bp = &cp->bp[(*cp->hfunc)(itemp->key, itemp->keyl, cp->hsz)];
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    if (bp->nent >= bp->nalloc) {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        if (bp->nalloc == 0) {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland            bp->itempp =
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                (Item **) malloc(sizeof (*bp->itempp) * cp->bsz);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        } else {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#ifdef  VERIFY_HASH_REALLOC
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland            (void) fprintf(stderr,
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                pkg_gt("realloc(%d) bucket=%d\n"),
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                bp->nalloc + cp->bsz,
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                (*cp->hfunc)(itemp->key, itemp->keyl, cp->hsz));
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#endif  /* VERIFY_HASH_REALLOC */
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland            if ((titempp =
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                (Item **) malloc(sizeof (*bp->itempp) *
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                (bp->nalloc + cp->bsz))) != NULL) {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                bcopy((char *)bp->itempp, (char *)titempp,
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                    (sizeof (*bp->itempp) * bp->nalloc));
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#ifdef _KERNEL
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                bkmem_free(bp->itempp,
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                    (sizeof (*bp->itempp) * bp->nalloc));
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#else   /* !_KERNEL */
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                free(bp->itempp);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland#endif  /* _KERNEL */
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                bp->itempp = titempp;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland            } else
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                bp->itempp = NULL;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        }
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        if (bp->itempp == NULL) {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland            (void) fprintf(stderr,
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland                pkg_gt("add_cache(): out of memory\n"));
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland            return (-1);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        }
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        bp->nalloc += cp->bsz;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    }
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    bp->itempp[bp->nent] = itemp;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    bp->nent++;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    return (0);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland}
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah WaterlandItem *
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterlandlookup_cache(Cache *cp, void *datap, int datalen)
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland{
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    int i;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    Bucket *bp;
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    /*
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland     * If cp is NULL, then init_cache() wasn't called. Quietly return the
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland     * error code and let the caller deal with it.
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland     */
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    if (cp == NULL) {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        return (Null_Item);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    }
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    bp = &cp->bp[(*cp->hfunc)(datap, datalen, cp->hsz)];
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    for (i = 0; i < bp->nent; i++) {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        if (!(*cp->cfunc)((void *)bp->itempp[i]->key, datap, datalen)) {
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland            return (bp->itempp[i]);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland        }
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    }
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland    return (Null_Item);
5c51f1241dbbdf2656d0e10011981411ed0c9673Moriah Waterland}