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