17c478bd9Sstevel@tonic-gate /* 27c478bd9Sstevel@tonic-gate * CDDL HEADER START 37c478bd9Sstevel@tonic-gate * 47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the 57c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 67c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 77c478bd9Sstevel@tonic-gate * with the License. 87c478bd9Sstevel@tonic-gate * 97c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 107c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 117c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions 127c478bd9Sstevel@tonic-gate * and limitations under the License. 137c478bd9Sstevel@tonic-gate * 147c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 157c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 167c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 177c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 187c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 197c478bd9Sstevel@tonic-gate * 207c478bd9Sstevel@tonic-gate * CDDL HEADER END 217c478bd9Sstevel@tonic-gate */ 227c478bd9Sstevel@tonic-gate /* 23*0d8b5334Sceastha * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 247c478bd9Sstevel@tonic-gate * Use is subject to license terms. 257c478bd9Sstevel@tonic-gate */ 267c478bd9Sstevel@tonic-gate 277c478bd9Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 287c478bd9Sstevel@tonic-gate /* All Rights Reserved */ 297c478bd9Sstevel@tonic-gate 307c478bd9Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 317c478bd9Sstevel@tonic-gate 327c478bd9Sstevel@tonic-gate 337c478bd9Sstevel@tonic-gate #include <stdlib.h> 347c478bd9Sstevel@tonic-gate #include "hash.h" 357c478bd9Sstevel@tonic-gate 367c478bd9Sstevel@tonic-gate #define LOCHWIDTH 3 377c478bd9Sstevel@tonic-gate #define HICHWIDTH 3 387c478bd9Sstevel@tonic-gate #define CHARWIDTH (LOCHWIDTH+HICHWIDTH) 397c478bd9Sstevel@tonic-gate #define LOCHMASK ((1<<LOCHWIDTH)-1) 407c478bd9Sstevel@tonic-gate 417c478bd9Sstevel@tonic-gate /* 427c478bd9Sstevel@tonic-gate * if HASHWIDTH + CHARWIDTH < bitsizeof(long) 437c478bd9Sstevel@tonic-gate * one could make LOCHWIDTH=6 and HICHWIDTH=0 447c478bd9Sstevel@tonic-gate * and simplify accordingly; the hanky-panky 457c478bd9Sstevel@tonic-gate * is to avoid overflow in long multiplication 467c478bd9Sstevel@tonic-gate */ 477c478bd9Sstevel@tonic-gate #define NC 30 487c478bd9Sstevel@tonic-gate 497c478bd9Sstevel@tonic-gate static long hashsize = HASHSIZE; 507c478bd9Sstevel@tonic-gate static long pow2[NC*2]; 517c478bd9Sstevel@tonic-gate 527c478bd9Sstevel@tonic-gate static signed char hashtab[] = { 537c478bd9Sstevel@tonic-gate -1, -1, -1, -1, -1, -1, 0, 31, /* &' */ 547c478bd9Sstevel@tonic-gate -1, -1, -1, -1, 68, -1, 65, -1, 557c478bd9Sstevel@tonic-gate 2, 25, 20, 35, 54, 61, 40, 39, /* 0-7 */ 567c478bd9Sstevel@tonic-gate 42, 33, 64, 67, -1, -1, -1, 66, 577c478bd9Sstevel@tonic-gate -1, 60, 43, 30, 5, 16, 47, 18, /* A-G */ 587c478bd9Sstevel@tonic-gate 41, 36, 51, 6, 13, 56, 55, 58, 597c478bd9Sstevel@tonic-gate 49, 12, 59, 46, 21, 32, 63, 34, 607c478bd9Sstevel@tonic-gate 57, 52, 3, -1, -1, -1, -1, -1, 617c478bd9Sstevel@tonic-gate -1, 22, 29, 8, 7, 10, 1, 28, /* a-g */ 627c478bd9Sstevel@tonic-gate 11, 62, 37, 48, 15, 50, 9, 4, 637c478bd9Sstevel@tonic-gate 19, 38, 45, 24, 23, 26, 17, 44, 647c478bd9Sstevel@tonic-gate 27, 14, 53, -1, -1, -1, -1, -1 657c478bd9Sstevel@tonic-gate }; 667c478bd9Sstevel@tonic-gate 677c478bd9Sstevel@tonic-gate 687c478bd9Sstevel@tonic-gate unsigned long 697c478bd9Sstevel@tonic-gate hash(char *s) 707c478bd9Sstevel@tonic-gate { 71*0d8b5334Sceastha int c; 72*0d8b5334Sceastha long *lp; 737c478bd9Sstevel@tonic-gate unsigned long h = 0; 747c478bd9Sstevel@tonic-gate for (lp = pow2; (c = *s++) != 0; ) { 757c478bd9Sstevel@tonic-gate c = hashtab[c-' ']; 767c478bd9Sstevel@tonic-gate h += (c&LOCHMASK) * *lp++; 777c478bd9Sstevel@tonic-gate h += (c>>LOCHWIDTH) * *lp++; 787c478bd9Sstevel@tonic-gate h %= hashsize; 797c478bd9Sstevel@tonic-gate } 807c478bd9Sstevel@tonic-gate return (h); 817c478bd9Sstevel@tonic-gate } 827c478bd9Sstevel@tonic-gate 837c478bd9Sstevel@tonic-gate void 847c478bd9Sstevel@tonic-gate hashinit(void) 857c478bd9Sstevel@tonic-gate { 867c478bd9Sstevel@tonic-gate #if ((1L << (HASHWIDTH+LOCHWIDTH) == 0) || (1L << (HASHWIDTH+HICHWIDTH) == 0)) 877c478bd9Sstevel@tonic-gate abort(); /* overflow is imminent */ 887c478bd9Sstevel@tonic-gate #else 89*0d8b5334Sceastha int i; 907c478bd9Sstevel@tonic-gate 917c478bd9Sstevel@tonic-gate pow2[0] = 1L<<(HASHWIDTH-CHARWIDTH-2); 927c478bd9Sstevel@tonic-gate for (i = 0; i < 2*NC-3; i += 2) { 937c478bd9Sstevel@tonic-gate pow2[i+1] = (pow2[i]<<LOCHWIDTH) % hashsize; 947c478bd9Sstevel@tonic-gate pow2[i+2] = (pow2[i+1]<<HICHWIDTH) % hashsize; 957c478bd9Sstevel@tonic-gate } 967c478bd9Sstevel@tonic-gate #endif 977c478bd9Sstevel@tonic-gate } 98