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