1*0Sstevel@tonic-gate /* 2*0Sstevel@tonic-gate * CDDL HEADER START 3*0Sstevel@tonic-gate * 4*0Sstevel@tonic-gate * The contents of this file are subject to the terms of the 5*0Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 6*0Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 7*0Sstevel@tonic-gate * with the License. 8*0Sstevel@tonic-gate * 9*0Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10*0Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 11*0Sstevel@tonic-gate * See the License for the specific language governing permissions 12*0Sstevel@tonic-gate * and limitations under the License. 13*0Sstevel@tonic-gate * 14*0Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 15*0Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16*0Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 17*0Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 18*0Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 19*0Sstevel@tonic-gate * 20*0Sstevel@tonic-gate * CDDL HEADER END 21*0Sstevel@tonic-gate */ 22*0Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 23*0Sstevel@tonic-gate /* All Rights Reserved */ 24*0Sstevel@tonic-gate 25*0Sstevel@tonic-gate 26*0Sstevel@tonic-gate #ident "%Z%%M% %I% %E% SMI" /* SVr4.0 1.3.2.1 */ 27*0Sstevel@tonic-gate 28*0Sstevel@tonic-gate #include "hash.h" 29*0Sstevel@tonic-gate #include "defs.h" 30*0Sstevel@tonic-gate 31*0Sstevel@tonic-gate #define STRCMP(A, B) (cf(A, B) != 0) 32*0Sstevel@tonic-gate #define FACTOR 035761254233 /* Magic multiplication factor */ 33*0Sstevel@tonic-gate #define TABLENGTH 64 /* must be multiple of 2 */ 34*0Sstevel@tonic-gate #define LOG2LEN 6 /* log2 of TABLENGTH */ 35*0Sstevel@tonic-gate 36*0Sstevel@tonic-gate /* 37*0Sstevel@tonic-gate NOTE: The following algorithm only works on machines where 38*0Sstevel@tonic-gate the results of multiplying two integers is the least 39*0Sstevel@tonic-gate significant part of the double word integer required to hold 40*0Sstevel@tonic-gate the result. It is adapted from Knuth, Volume 3, section 6.4. 41*0Sstevel@tonic-gate */ 42*0Sstevel@tonic-gate 43*0Sstevel@tonic-gate #define hash(str) (int)(((unsigned)(crunch(str) * FACTOR)) >> shift) 44*0Sstevel@tonic-gate struct node 45*0Sstevel@tonic-gate { 46*0Sstevel@tonic-gate ENTRY item; 47*0Sstevel@tonic-gate struct node *next; 48*0Sstevel@tonic-gate }; 49*0Sstevel@tonic-gate 50*0Sstevel@tonic-gate static struct node **last; 51*0Sstevel@tonic-gate static struct node *next; 52*0Sstevel@tonic-gate static struct node **table; 53*0Sstevel@tonic-gate 54*0Sstevel@tonic-gate static unsigned int bitsper; /* Bits per byte */ 55*0Sstevel@tonic-gate static unsigned int shift; 56*0Sstevel@tonic-gate 57*0Sstevel@tonic-gate static unsigned int crunch(); 58*0Sstevel@tonic-gate 59*0Sstevel@tonic-gate hcreate() 60*0Sstevel@tonic-gate { 61*0Sstevel@tonic-gate unsigned char c = (unsigned char)~0; /* A byte full of 1's */ 62*0Sstevel@tonic-gate int j; 63*0Sstevel@tonic-gate 64*0Sstevel@tonic-gate table = (struct node **)alloc(TABLENGTH * sizeof(struct node *)); 65*0Sstevel@tonic-gate 66*0Sstevel@tonic-gate for (j=0; j < TABLENGTH; ++j) 67*0Sstevel@tonic-gate { 68*0Sstevel@tonic-gate table[j] = 0; 69*0Sstevel@tonic-gate } 70*0Sstevel@tonic-gate 71*0Sstevel@tonic-gate bitsper = 0; 72*0Sstevel@tonic-gate 73*0Sstevel@tonic-gate while (c) 74*0Sstevel@tonic-gate { 75*0Sstevel@tonic-gate c = (unsigned int)c >> 1; 76*0Sstevel@tonic-gate bitsper++; 77*0Sstevel@tonic-gate } 78*0Sstevel@tonic-gate 79*0Sstevel@tonic-gate shift = (bitsper * sizeof(int)) - LOG2LEN; 80*0Sstevel@tonic-gate } 81*0Sstevel@tonic-gate 82*0Sstevel@tonic-gate 83*0Sstevel@tonic-gate void hscan(uscan) 84*0Sstevel@tonic-gate void (*uscan)(); 85*0Sstevel@tonic-gate { 86*0Sstevel@tonic-gate struct node *p, *nxt; 87*0Sstevel@tonic-gate int j; 88*0Sstevel@tonic-gate 89*0Sstevel@tonic-gate for (j=0; j < TABLENGTH; ++j) 90*0Sstevel@tonic-gate { 91*0Sstevel@tonic-gate p = table[j]; 92*0Sstevel@tonic-gate while (p) 93*0Sstevel@tonic-gate { 94*0Sstevel@tonic-gate nxt = p->next; 95*0Sstevel@tonic-gate (*uscan)(&p->item); 96*0Sstevel@tonic-gate p = nxt; 97*0Sstevel@tonic-gate } 98*0Sstevel@tonic-gate } 99*0Sstevel@tonic-gate } 100*0Sstevel@tonic-gate 101*0Sstevel@tonic-gate 102*0Sstevel@tonic-gate 103*0Sstevel@tonic-gate ENTRY * 104*0Sstevel@tonic-gate hfind(str) 105*0Sstevel@tonic-gate unsigned char *str; 106*0Sstevel@tonic-gate { 107*0Sstevel@tonic-gate struct node *p; 108*0Sstevel@tonic-gate struct node **q; 109*0Sstevel@tonic-gate unsigned int i; 110*0Sstevel@tonic-gate int res; 111*0Sstevel@tonic-gate 112*0Sstevel@tonic-gate i = hash(str); 113*0Sstevel@tonic-gate 114*0Sstevel@tonic-gate if(table[i] == 0) 115*0Sstevel@tonic-gate { 116*0Sstevel@tonic-gate last = &table[i]; 117*0Sstevel@tonic-gate next = 0; 118*0Sstevel@tonic-gate return(0); 119*0Sstevel@tonic-gate } 120*0Sstevel@tonic-gate else 121*0Sstevel@tonic-gate { 122*0Sstevel@tonic-gate q = &table[i]; 123*0Sstevel@tonic-gate p = table[i]; 124*0Sstevel@tonic-gate while (p != 0 && (res = STRCMP(str, p->item.key))) 125*0Sstevel@tonic-gate { 126*0Sstevel@tonic-gate q = &(p->next); 127*0Sstevel@tonic-gate p = p->next; 128*0Sstevel@tonic-gate } 129*0Sstevel@tonic-gate 130*0Sstevel@tonic-gate if (p != 0 && res == 0) 131*0Sstevel@tonic-gate return(&(p->item)); 132*0Sstevel@tonic-gate else 133*0Sstevel@tonic-gate { 134*0Sstevel@tonic-gate last = q; 135*0Sstevel@tonic-gate next = p; 136*0Sstevel@tonic-gate return(0); 137*0Sstevel@tonic-gate } 138*0Sstevel@tonic-gate } 139*0Sstevel@tonic-gate } 140*0Sstevel@tonic-gate 141*0Sstevel@tonic-gate ENTRY * 142*0Sstevel@tonic-gate henter(item) 143*0Sstevel@tonic-gate ENTRY item; 144*0Sstevel@tonic-gate { 145*0Sstevel@tonic-gate struct node *p = (struct node *)alloc(sizeof(struct node)); 146*0Sstevel@tonic-gate 147*0Sstevel@tonic-gate p->item = item; 148*0Sstevel@tonic-gate *last = p; 149*0Sstevel@tonic-gate p->next = next; 150*0Sstevel@tonic-gate return(&(p->item)); 151*0Sstevel@tonic-gate } 152*0Sstevel@tonic-gate 153*0Sstevel@tonic-gate 154*0Sstevel@tonic-gate static unsigned int 155*0Sstevel@tonic-gate crunch(key) 156*0Sstevel@tonic-gate unsigned char *key; 157*0Sstevel@tonic-gate { 158*0Sstevel@tonic-gate unsigned int sum = 0; 159*0Sstevel@tonic-gate int s; 160*0Sstevel@tonic-gate 161*0Sstevel@tonic-gate for (s = 0; *key; s++) /* Simply add up the bytes */ 162*0Sstevel@tonic-gate sum += *key++; 163*0Sstevel@tonic-gate 164*0Sstevel@tonic-gate return(sum + s); 165*0Sstevel@tonic-gate } 166*0Sstevel@tonic-gate 167