nhash.c revision 5c51f1241dbbdf2656d0e10011981411ed0c9673
fa9e4066f08beec538e775443c5be79dd423fcabahrens/*
fa9e4066f08beec538e775443c5be79dd423fcabahrens * CDDL HEADER START
fa9e4066f08beec538e775443c5be79dd423fcabahrens *
fa9e4066f08beec538e775443c5be79dd423fcabahrens * The contents of this file are subject to the terms of the
441d80aa4f613b6298fc8bd3151f4be02dbf84fclling * Common Development and Distribution License (the "License").
441d80aa4f613b6298fc8bd3151f4be02dbf84fclling * You may not use this file except in compliance with the License.
fa9e4066f08beec538e775443c5be79dd423fcabahrens *
fa9e4066f08beec538e775443c5be79dd423fcabahrens * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
fa9e4066f08beec538e775443c5be79dd423fcabahrens * or http://www.opensolaris.org/os/licensing.
fa9e4066f08beec538e775443c5be79dd423fcabahrens * See the License for the specific language governing permissions
fa9e4066f08beec538e775443c5be79dd423fcabahrens * and limitations under the License.
fa9e4066f08beec538e775443c5be79dd423fcabahrens *
fa9e4066f08beec538e775443c5be79dd423fcabahrens * When distributing Covered Code, include this CDDL HEADER in each
fa9e4066f08beec538e775443c5be79dd423fcabahrens * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
fa9e4066f08beec538e775443c5be79dd423fcabahrens * If applicable, add the following below this CDDL HEADER, with the
fa9e4066f08beec538e775443c5be79dd423fcabahrens * fields enclosed by brackets "[]" replaced with your own identifying
fa9e4066f08beec538e775443c5be79dd423fcabahrens * information: Portions Copyright [yyyy] [name of copyright owner]
fa9e4066f08beec538e775443c5be79dd423fcabahrens *
fa9e4066f08beec538e775443c5be79dd423fcabahrens * CDDL HEADER END
fa9e4066f08beec538e775443c5be79dd423fcabahrens */
ad135b5d644628e791c3188a6ecbd9c257961ef8Christopher Siden
fa9e4066f08beec538e775443c5be79dd423fcabahrens/*
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
0d8fa8f8eba3ea46bc79d73445009505d1dd5d7dMartin Matuska * Use is subject to license terms.
1df56ada43861dec046a93e1643fec1c4e7b2ed5Martin Matuska */
5878fad70d76d8711f6608c1f80b0447601261c6Dan McDonald
752fd8dabccac68d6d09f82f3bf3561e055e400bJosef 'Jeff' Sipek
45b1747515a17db45e8971501ee84a26bdff37b2Alex Wilson#include <stdio.h>
6de9bb5603e65b16816b7ab29e39bac820e2da2bMatthew Ahrens#include <string.h>
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#include <stdlib.h>
a7a845e4bf22fd1b2a284729ccd95c7370a0438cSteven Hartland#include <strings.h>
c3d26abc9ee97b4f60233556aadeb57e0bd30bb9Matthew Ahrens#include "pkglib.h"
c8811bd3e2427dddbac6c05a59cfe117d8fea370Toomas Soome#include "nhash.h"
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens#include "pkglocale.h"
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens#ifndef _KERNEL
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens#define bcopy(a, b, c) (void) memmove(b, a, c)
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens#define bcmp memcmp
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens#define bzero(a, c) (void) memset(a, '\0', c)
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens#else /* _KERNEL */
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens#define malloc bkmem_alloc
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens#endif /* _KERNEL */
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens#define VERIFY_HASH_REALLOC
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrensstatic int
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew AhrensBCMP(void *str1, void *str2, int len)
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens{
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens return (bcmp((char *)str1, (char *)str2, len));
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens}
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrensstatic int
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew AhrensHASH(void *datap, int datalen, int hsz)
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens{
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens char *cp;
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens char *np;
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens int hv = 0;
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens /* determine starting and ending positions */
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens cp = (char *)datap;
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens np = ((char *)cp + datalen);
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens /* compute hash over all characters from start to end */
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens while (cp != np) {
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens hv += ((int)*cp++);
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens }
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens /* return computed hash */
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens return (hv % hsz);
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens}
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrensint
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrensinit_cache(Cache **cp, int hsz, int bsz,
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens int (*hfunc)(void *, int, int), int (*cfunc)(void *, void *, int))
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens{
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens if ((*cp = (Cache *) malloc(sizeof (**cp))) == NULL) {
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens (void) fprintf(stderr, pkg_gt("malloc(Cache **cp)"));
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens return (-1);
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens }
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens if (((*cp)->bp =
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens (Bucket *) malloc(sizeof (*(*cp)->bp) * hsz)) == NULL) {
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens (void) fprintf(stderr, pkg_gt("malloc(Bucket cp->bp)"));
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens return (-1);
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens }
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens (*cp)->hsz = hsz;
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens (*cp)->bsz = bsz;
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens bzero((*cp)->bp, sizeof (*(*cp)->bp) * hsz);
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens if (hfunc != (int (*)()) NULL) {
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens (*cp)->hfunc = hfunc;
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens } else {
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens (*cp)->hfunc = HASH;
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens }
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens if (cfunc != (int (*)()) NULL) {
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens (*cp)->cfunc = cfunc;
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens } else {
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens (*cp)->cfunc = BCMP;
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens }
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens return (0);
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens}
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrensint
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrensadd_cache(Cache *cp, Item *itemp)
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens{
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens Bucket *bp;
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens Item **titempp;
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens /*
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens * If cp is NULL, then init_cache() wasn't called. Quietly return the
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens * error code and let the caller deal with it.
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens */
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens if (cp == NULL)
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens return (-1);
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens bp = &cp->bp[(*cp->hfunc)(itemp->key, itemp->keyl, cp->hsz)];
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens if (bp->nent >= bp->nalloc) {
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens if (bp->nalloc == 0) {
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens bp->itempp =
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens (Item **) malloc(sizeof (*bp->itempp) * cp->bsz);
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens } else {
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens#ifdef VERIFY_HASH_REALLOC
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens (void) fprintf(stderr,
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens pkg_gt("realloc(%d) bucket=%d\n"),
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens bp->nalloc + cp->bsz,
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens (*cp->hfunc)(itemp->key, itemp->keyl, cp->hsz));
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens#endif /* VERIFY_HASH_REALLOC */
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens if ((titempp =
4445fffbbb1ea25fd0e9ea68b9380dd7a6709025Matthew Ahrens (Item **) malloc(sizeof (*bp->itempp) *
e9103aaee0c546d4644791198c54abb03c89969eGarrett D'Amore (bp->nalloc + cp->bsz))) != NULL) {
fa9e4066f08beec538e775443c5be79dd423fcabahrens bcopy((char *)bp->itempp, (char *)titempp,
fa9e4066f08beec538e775443c5be79dd423fcabahrens (sizeof (*bp->itempp) * bp->nalloc));
fa9e4066f08beec538e775443c5be79dd423fcabahrens#ifdef _KERNEL
fa9e4066f08beec538e775443c5be79dd423fcabahrens bkmem_free(bp->itempp,
fa9e4066f08beec538e775443c5be79dd423fcabahrens (sizeof (*bp->itempp) * bp->nalloc));
fa9e4066f08beec538e775443c5be79dd423fcabahrens#else /* !_KERNEL */
fa9e4066f08beec538e775443c5be79dd423fcabahrens free(bp->itempp);
fa9e4066f08beec538e775443c5be79dd423fcabahrens#endif /* _KERNEL */
fa9e4066f08beec538e775443c5be79dd423fcabahrens bp->itempp = titempp;
fa9e4066f08beec538e775443c5be79dd423fcabahrens } else
fa9e4066f08beec538e775443c5be79dd423fcabahrens bp->itempp = NULL;
fa9e4066f08beec538e775443c5be79dd423fcabahrens }
fa9e4066f08beec538e775443c5be79dd423fcabahrens if (bp->itempp == NULL) {
fa9e4066f08beec538e775443c5be79dd423fcabahrens (void) fprintf(stderr,
4201a95e0468170d576f82c3aa63afecf718497aRic Aleshire pkg_gt("add_cache(): out of memory\n"));
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw return (-1);
fa9e4066f08beec538e775443c5be79dd423fcabahrens }
fa9e4066f08beec538e775443c5be79dd423fcabahrens bp->nalloc += cp->bsz;
b1b8ab34de515a5e83206da22c3d7e563241b021lling }
fa9e4066f08beec538e775443c5be79dd423fcabahrens bp->itempp[bp->nent] = itemp;
4201a95e0468170d576f82c3aa63afecf718497aRic Aleshire bp->nent++;
fa9e4066f08beec538e775443c5be79dd423fcabahrens return (0);
fa9e4066f08beec538e775443c5be79dd423fcabahrens}
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrensItem *
ecd6cf800b63704be73fb264c3f5b6e0dafc068dmarkslookup_cache(Cache *cp, void *datap, int datalen)
ecd6cf800b63704be73fb264c3f5b6e0dafc068dmarks{
4e3c9f4489a18514e5e8caeb91d4e6db07c98415Bill Pijewski int i;
3b2aab18808792cbd248a12f1edf139b89833c13Matthew Ahrens Bucket *bp;
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrens /*
fa9e4066f08beec538e775443c5be79dd423fcabahrens * If cp is NULL, then init_cache() wasn't called. Quietly return the
fa9e4066f08beec538e775443c5be79dd423fcabahrens * error code and let the caller deal with it.
fa9e4066f08beec538e775443c5be79dd423fcabahrens */
fa9e4066f08beec538e775443c5be79dd423fcabahrens if (cp == NULL) {
fa9e4066f08beec538e775443c5be79dd423fcabahrens return (Null_Item);
fa9e4066f08beec538e775443c5be79dd423fcabahrens }
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrens bp = &cp->bp[(*cp->hfunc)(datap, datalen, cp->hsz)];
fa9e4066f08beec538e775443c5be79dd423fcabahrens
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw for (i = 0; i < bp->nent; i++) {
c99e4bdccfb4ac4da569c64a43baaf908d726329Chris Kirby if (!(*cp->cfunc)((void *)bp->itempp[i]->key, datap, datalen)) {
a2eea2e101e6a163a537dcc6d4e3c4da2a0ea5b2ahrens return (bp->itempp[i]);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling }
ecd6cf800b63704be73fb264c3f5b6e0dafc068dmarks }
f18faf3f3e5def85fdfff681617d227703ace2adek return (Null_Item);
3b2aab18808792cbd248a12f1edf139b89833c13Matthew Ahrens}
3b2aab18808792cbd248a12f1edf139b89833c13Matthew Ahrens