da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * CDDL HEADER START
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin *
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner * The contents of this file are subject to the terms of the
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * Common Development and Distribution License, Version 1.0 only
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * (the "License"). You may not use this file except in compliance
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin * with the License.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * or http://www.opensolaris.org/os/licensing.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * See the License for the specific language governing permissions
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * and limitations under the License.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * When distributing Covered Code, include this CDDL HEADER in each
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * If applicable, add the following below this CDDL HEADER, with the
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * fields enclosed by brackets "[]" replaced with your own identifying
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * information: Portions Copyright [yyyy] [name of copyright owner]
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * CDDL HEADER END
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * Use is subject to license terms.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* All Rights Reserved */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#pragma ident "%Z%%M% %I% %E% SMI"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include <stdlib.h>
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include "hash.h"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define LOCHWIDTH 3
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HICHWIDTH 3
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define CHARWIDTH (LOCHWIDTH+HICHWIDTH)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define LOCHMASK ((1<<LOCHWIDTH)-1)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * if HASHWIDTH + CHARWIDTH < bitsizeof(long)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * one could make LOCHWIDTH=6 and HICHWIDTH=0
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * and simplify accordingly; the hanky-panky
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * is to avoid overflow in long multiplication
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define NC 30
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic long hashsize = HASHSIZE;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic long pow2[NC*2];
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic signed char hashtab[] = {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin-1, -1, -1, -1, -1, -1, 0, 31, /* &' */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin-1, -1, -1, -1, 68, -1, 65, -1,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin2, 25, 20, 35, 54, 61, 40, 39, /* 0-7 */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin42, 33, 64, 67, -1, -1, -1, 66,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin-1, 60, 43, 30, 5, 16, 47, 18, /* A-G */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin41, 36, 51, 6, 13, 56, 55, 58,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin49, 12, 59, 46, 21, 32, 63, 34,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin57, 52, 3, -1, -1, -1, -1, -1,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin-1, 22, 29, 8, 7, 10, 1, 28, /* a-g */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin11, 62, 37, 48, 15, 50, 9, 4,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin19, 38, 45, 24, 23, 26, 17, 44,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin27, 14, 53, -1, -1, -1, -1, -1
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin};
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinunsigned long
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinhash(char *s)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int c;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin long *lp;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin unsigned long h = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for (lp = pow2; (c = *s++) != 0; ) {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin c = hashtab[c-' '];
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin h += (c&LOCHMASK) * *lp++;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin h += (c>>LOCHWIDTH) * *lp++;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin h %= hashsize;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return (h);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinvoid
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinhashinit(void)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if ((1L << (HASHWIDTH+LOCHWIDTH) == 0) || (1L << (HASHWIDTH+HICHWIDTH) == 0))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin abort(); /* overflow is imminent */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int i;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin pow2[0] = 1L<<(HASHWIDTH-CHARWIDTH-2);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for (i = 0; i < 2*NC-3; i += 2) {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin pow2[i+1] = (pow2[i]<<LOCHWIDTH) % hashsize;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin pow2[i+2] = (pow2[i+1]<<HICHWIDTH) % hashsize;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin