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 #include "hash.h" 32 #include "defs.h" 33 34 #define STRCMP(A, B) (cf(A, B) != 0) 35 #define FACTOR 035761254233 /* Magic multiplication factor */ 36 #define TABLENGTH 64 /* must be multiple of 2 */ 37 #define LOG2LEN 6 /* log2 of TABLENGTH */ 38 39 /* 40 NOTE: The following algorithm only works on machines where 41 the results of multiplying two integers is the least 42 significant part of the double word integer required to hold 43 the result. It is adapted from Knuth, Volume 3, section 6.4. 44 */ 45 46 #define hash(str) (int)(((unsigned)(crunch(str) * FACTOR)) >> shift) 47 struct node 48 { 49 ENTRY item; 50 struct node *next; 51 }; 52 53 static struct node **last; 54 static struct node *next; 55 static struct node **table; 56 57 static unsigned int bitsper; /* Bits per byte */ 58 static unsigned int shift; 59 60 static unsigned int crunch(); 61 62 void 63 hcreate(void) 64 { 65 unsigned char c = (unsigned char)~0; /* A byte full of 1's */ 66 int j; 67 68 table = (struct node **)alloc(TABLENGTH * sizeof(struct node *)); 69 70 for (j=0; j < TABLENGTH; ++j) 71 { 72 table[j] = 0; 73 } 74 75 bitsper = 0; 76 77 while (c) 78 { 79 c = (unsigned int)c >> 1; 80 bitsper++; 81 } 82 83 shift = (bitsper * sizeof(int)) - LOG2LEN; 84 } 85 86 87 void hscan(uscan) 88 void (*uscan)(); 89 { 90 struct node *p, *nxt; 91 int j; 92 93 for (j=0; j < TABLENGTH; ++j) 94 { 95 p = table[j]; 96 while (p) 97 { 98 nxt = p->next; 99 (*uscan)(&p->item); 100 p = nxt; 101 } 102 } 103 } 104 105 106 107 ENTRY * 108 hfind(str) 109 unsigned char *str; 110 { 111 struct node *p; 112 struct node **q; 113 unsigned int i; 114 int res; 115 116 i = hash(str); 117 118 if(table[i] == 0) 119 { 120 last = &table[i]; 121 next = 0; 122 return(0); 123 } 124 else 125 { 126 q = &table[i]; 127 p = table[i]; 128 while (p != 0 && (res = STRCMP(str, p->item.key))) 129 { 130 q = &(p->next); 131 p = p->next; 132 } 133 134 if (p != 0 && res == 0) 135 return(&(p->item)); 136 else 137 { 138 last = q; 139 next = p; 140 return(0); 141 } 142 } 143 } 144 145 ENTRY * 146 henter(item) 147 ENTRY item; 148 { 149 struct node *p = (struct node *)alloc(sizeof(struct node)); 150 151 p->item = item; 152 *last = p; 153 p->next = next; 154 return(&(p->item)); 155 } 156 157 158 static unsigned int 159 crunch(key) 160 unsigned char *key; 161 { 162 unsigned int sum = 0; 163 int s; 164 165 for (s = 0; *key; s++) /* Simply add up the bytes */ 166 sum += *key++; 167 168 return(sum + s); 169 } 170 171