1 /* $NetBSD: hash.c,v 1.5 2009/04/19 06:06:40 lukem Exp $ */ 2 3 /* 4 * Copyright (c) 1995 5 * Bill Paul <wpaul@ctr.columbia.edu>. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by Bill Paul. 18 * 4. Neither the name of the author nor the names of any co-contributors 19 * may be used to endorse or promote products derived from this software 20 * without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY Bill Paul AND CONTRIBUTORS ``AS IS'' AND 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL Bill Paul OR CONTRIBUTORS BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 * 34 */ 35 36 #include <sys/cdefs.h> 37 #ifndef lint 38 __RCSID("$NetBSD: hash.c,v 1.5 2009/04/19 06:06:40 lukem Exp $"); 39 #endif 40 41 #include <sys/types.h> 42 43 #include <stdio.h> 44 #include <stdlib.h> 45 #include <string.h> 46 47 #include "hash.h" 48 49 u_int32_t hash(const void *, size_t); 50 u_int32_t hashkey(const char *); 51 52 53 /* 54 * This hash function is stolen directly from the 55 * Berkeley DB package. It already exists inside libc, but 56 * it's declared static which prevents us from calling it 57 * from here. 58 */ 59 60 /* 61 * OZ's original sdbm hash 62 */ 63 u_int32_t 64 hash(const void *keyarg, size_t len) 65 { 66 const u_char *key; 67 size_t loop; 68 u_int32_t h; 69 70 #define HASHC h = *key++ + 65599 * h 71 72 h = 0; 73 key = keyarg; 74 if (len > 0) { 75 loop = (len + 8 - 1) >> 3; 76 77 switch (len & (8 - 1)) { 78 case 0: 79 do { 80 HASHC; 81 /* FALLTHROUGH */ 82 case 7: 83 HASHC; 84 /* FALLTHROUGH */ 85 case 6: 86 HASHC; 87 /* FALLTHROUGH */ 88 case 5: 89 HASHC; 90 /* FALLTHROUGH */ 91 case 4: 92 HASHC; 93 /* FALLTHROUGH */ 94 case 3: 95 HASHC; 96 /* FALLTHROUGH */ 97 case 2: 98 HASHC; 99 /* FALLTHROUGH */ 100 case 1: 101 HASHC; 102 } while (--loop); 103 } 104 } 105 return (h); 106 } 107 108 /* 109 * Generate a hash value for a given key (character string). 110 * We mask off all but the lower 8 bits since our table array 111 * can only hold 256 elements. 112 */ 113 u_int32_t 114 hashkey(const char *key) 115 { 116 117 if (key == NULL) 118 return (-1); 119 return(hash((const void *)key, strlen(key)) & HASH_MASK); 120 } 121 122 /* Find an entry in the hash table (may be hanging off a linked list). */ 123 char * 124 lookup(struct group_entry **table, const char *key) 125 { 126 struct group_entry *cur; 127 128 cur = table[hashkey(key)]; 129 130 while (cur) { 131 if (!strcmp(cur->key, key)) 132 return(cur->data); 133 cur = cur->next; 134 } 135 136 return(NULL); 137 } 138 139 /* 140 * Store an entry in the main netgroup hash table. Here's how this 141 * works: the table can only be so big when we initialize it (TABLESIZE) 142 * but the number of netgroups in the /etc/netgroup file could easily be 143 * much larger than the table. Since our hash values are adjusted to 144 * never be greater than TABLESIZE too, this means it won't be long before 145 * we find ourselves with two keys that hash to the same value. 146 * 147 * One way to deal with this is to malloc(2) a second table and start 148 * doing indirection, but this is a pain in the butt and it's not worth 149 * going to all that trouble for a dinky little program like this. Instead, 150 * we turn each table entry into a linked list and simply link keys 151 * with the same hash value together at the same index location within 152 * the table. 153 * 154 * That's a lot of comment for such a small piece of code, isn't it. 155 */ 156 void 157 store(struct group_entry *table[], const char *key, const char *data) 158 { 159 struct group_entry *new; 160 u_int32_t i; 161 162 i = hashkey(key); 163 164 new = (struct group_entry *)malloc(sizeof(struct group_entry)); 165 new->key = strdup(key); 166 new->data = strdup(data); 167 new->next = table[i]; 168 table[i] = new; 169 170 return; 171 } 172 173 /* 174 * Store a group member entry and/or update its grouplist. This is 175 * a bit more complicated than the previous function since we have to 176 * maintain not only the hash table of group members, each group member 177 * structure also has a linked list of groups hung off it. If handed 178 * a member name that we haven't encountered before, we have to do 179 * two things: add that member to the table (possibly hanging them 180 * off the end of a linked list, as above), and add a group name to 181 * the member's grouplist list. If we're handed a name that already has 182 * an entry in the table, then we just have to do one thing, which is 183 * to update its grouplist. 184 */ 185 void 186 mstore(struct member_entry *table[], const char *key, const char *data, 187 const char *domain) 188 { 189 struct member_entry *cur, *new; 190 struct grouplist *tmp,*p; 191 u_int32_t i; 192 193 i = hashkey(key); 194 cur = table[i]; 195 196 tmp = (struct grouplist *)malloc(sizeof(struct grouplist)); 197 tmp->groupname = strdup(data); 198 tmp->next = NULL; 199 200 /* Check if all we have to do is insert a new groupname. */ 201 while (cur) { 202 if (!strcmp(cur->key, key) && !strcmp(cur->domain,domain)) { 203 p = cur->groups; 204 while(p) { 205 if (!strcmp(p->groupname,data)) { 206 /* group already there */ 207 free(tmp); 208 return; 209 } 210 p = p->next; 211 } 212 tmp->next = cur->groups; 213 cur->groups = tmp; 214 return; 215 } 216 cur = cur->next; 217 } 218 219 /* Didn't find a match -- add the whole mess to the table. */ 220 new = (struct member_entry *)malloc(sizeof(struct member_entry)); 221 new->key = strdup(key); 222 new->domain = strdup(domain); 223 new->groups = tmp; 224 new->next = table[i]; 225 table[i] = new; 226 227 return; 228 } 229