111814Swpaul/* 211814Swpaul * Copyright (c) 1995 311814Swpaul * Bill Paul <wpaul@ctr.columbia.edu>. All rights reserved. 411814Swpaul * 511814Swpaul * Redistribution and use in source and binary forms, with or without 611814Swpaul * modification, are permitted provided that the following conditions 711814Swpaul * are met: 811814Swpaul * 1. Redistributions of source code must retain the above copyright 911814Swpaul * notice, this list of conditions and the following disclaimer. 1011814Swpaul * 2. Redistributions in binary form must reproduce the above copyright 1111814Swpaul * notice, this list of conditions and the following disclaimer in the 1211814Swpaul * documentation and/or other materials provided with the distribution. 1311814Swpaul * 3. All advertising materials mentioning features or use of this software 1411814Swpaul * must display the following acknowledgement: 1511814Swpaul * This product includes software developed by Bill Paul. 1611814Swpaul * 4. Neither the name of the author nor the names of any co-contributors 1711814Swpaul * may be used to endorse or promote products derived from this software 1811814Swpaul * without specific prior written permission. 1911814Swpaul * 2011814Swpaul * THIS SOFTWARE IS PROVIDED BY Bill Paul AND CONTRIBUTORS ``AS IS'' AND 2111814Swpaul * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2211814Swpaul * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2311814Swpaul * ARE DISCLAIMED. IN NO EVENT SHALL Bill Paul OR CONTRIBUTORS BE LIABLE 2411814Swpaul * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2511814Swpaul * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2611814Swpaul * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2711814Swpaul * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2811814Swpaul * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2911814Swpaul * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3011814Swpaul * SUCH DAMAGE. 3111814Swpaul */ 3211814Swpaul 3331404Scharnier#ifndef lint 3431404Scharnierstatic const char rcsid[] = 3550476Speter "$FreeBSD$"; 3631404Scharnier#endif /* not lint */ 3731404Scharnier 3811814Swpaul#include <stdio.h> 3911814Swpaul#include <stdlib.h> 4011814Swpaul#include <string.h> 4111814Swpaul#include <sys/types.h> 4211814Swpaul#include "hash.h" 4311814Swpaul 4411814Swpaul/* 4511814Swpaul * This hash function is stolen directly from the 4611814Swpaul * Berkeley DB package. It already exists inside libc, but 4711814Swpaul * it's declared static which prevents us from calling it 4811814Swpaul * from here. 4911814Swpaul */ 5011814Swpaul/* 5111814Swpaul * OZ's original sdbm hash 5211814Swpaul */ 5311814Swpaulu_int32_t 5490377Simphash(const void *keyarg, size_t len) 5511814Swpaul{ 5690377Simp const u_char *key; 5790377Simp size_t loop; 5890377Simp u_int32_t h; 5911814Swpaul 6011814Swpaul#define HASHC h = *key++ + 65599 * h 6111814Swpaul 6211814Swpaul h = 0; 6311814Swpaul key = keyarg; 6411814Swpaul if (len > 0) { 6511814Swpaul loop = (len + 8 - 1) >> 3; 6611814Swpaul 6711814Swpaul switch (len & (8 - 1)) { 6811814Swpaul case 0: 6911814Swpaul do { 7011814Swpaul HASHC; 7111814Swpaul /* FALLTHROUGH */ 7211814Swpaul case 7: 7311814Swpaul HASHC; 7411814Swpaul /* FALLTHROUGH */ 7511814Swpaul case 6: 7611814Swpaul HASHC; 7711814Swpaul /* FALLTHROUGH */ 7811814Swpaul case 5: 7911814Swpaul HASHC; 8011814Swpaul /* FALLTHROUGH */ 8111814Swpaul case 4: 8211814Swpaul HASHC; 8311814Swpaul /* FALLTHROUGH */ 8411814Swpaul case 3: 8511814Swpaul HASHC; 8611814Swpaul /* FALLTHROUGH */ 8711814Swpaul case 2: 8811814Swpaul HASHC; 8911814Swpaul /* FALLTHROUGH */ 9011814Swpaul case 1: 9111814Swpaul HASHC; 9211814Swpaul } while (--loop); 9311814Swpaul } 9411814Swpaul } 9511814Swpaul return (h); 9611814Swpaul} 9711814Swpaul 9811814Swpaul/* 9911814Swpaul * Generate a hash value for a given key (character string). 10011814Swpaul * We mask off all but the lower 8 bits since our table array 10115754Swpaul * can only hold 256 elements. 10211814Swpaul */ 10390377Simpu_int32_t 10490377Simphashkey(char *key) 10511814Swpaul{ 10611814Swpaul 10711814Swpaul if (key == NULL) 10811814Swpaul return (-1); 10911814Swpaul return(hash((void *)key, strlen(key)) & HASH_MASK); 11011814Swpaul} 11111814Swpaul 11211814Swpaul/* Find an entry in the hash table (may be hanging off a linked list). */ 11390377Simpchar * 11490377Simplookup(struct group_entry *table[], char *key) 11511814Swpaul{ 11611814Swpaul struct group_entry *cur; 11711814Swpaul 11811814Swpaul cur = table[hashkey(key)]; 11911814Swpaul 12011814Swpaul while (cur) { 12111814Swpaul if (!strcmp(cur->key, key)) 12211814Swpaul return(cur->data); 12311814Swpaul cur = cur->next; 12411814Swpaul } 12511814Swpaul 12611814Swpaul return(NULL); 12711814Swpaul} 12811814Swpaul 12911814Swpaul/* 13011814Swpaul * Store an entry in the main netgroup hash table. Here's how this 13111814Swpaul * works: the table can only be so big when we initialize it (TABLESIZE) 13211814Swpaul * but the number of netgroups in the /etc/netgroup file could easily be 13311814Swpaul * much larger than the table. Since our hash values are adjusted to 13411814Swpaul * never be greater than TABLESIZE too, this means it won't be long before 13511814Swpaul * we find ourselves with two keys that hash to the same value. 13611814Swpaul * 13711814Swpaul * One way to deal with this is to malloc(2) a second table and start 13811814Swpaul * doing indirection, but this is a pain in the butt and it's not worth 13915754Swpaul * going to all that trouble for a dinky little program like this. Instead, 14011814Swpaul * we turn each table entry into a linked list and simply link keys 14111814Swpaul * with the same hash value together at the same index location within 14211814Swpaul * the table. 14311814Swpaul * 14411814Swpaul * That's a lot of comment for such a small piece of code, isn't it. 14511814Swpaul */ 14690377Simpvoid 14790377Simpstore(struct group_entry *table[], char *key, char *data) 14811814Swpaul{ 14911814Swpaul struct group_entry *new; 15011814Swpaul u_int32_t i; 15111814Swpaul 15211814Swpaul i = hashkey(key); 15311814Swpaul 15411814Swpaul new = (struct group_entry *)malloc(sizeof(struct group_entry)); 15511814Swpaul new->key = strdup(key); 15611814Swpaul new->data = strdup(data); 15711814Swpaul new->next = table[i]; 15811814Swpaul table[i] = new; 15911814Swpaul 16011814Swpaul return; 16111814Swpaul} 16211814Swpaul 16311814Swpaul/* 16415754Swpaul * Store a group member entry and/or update its grouplist. This is 16511814Swpaul * a bit more complicated than the previous function since we have to 16611814Swpaul * maintain not only the hash table of group members, each group member 16711814Swpaul * structure also has a linked list of groups hung off it. If handed 16811814Swpaul * a member name that we haven't encountered before, we have to do 16911814Swpaul * two things: add that member to the table (possibly hanging them 17011814Swpaul * off the end of a linked list, as above), and add a group name to 17111814Swpaul * the member's grouplist list. If we're handed a name that already has 17211814Swpaul * an entry in the table, then we just have to do one thing, which is 17311814Swpaul * to update its grouplist. 17411814Swpaul */ 17590377Simpvoid 17690377Simpmstore(struct member_entry *table[], char *key, char *data, char *domain) 17711814Swpaul{ 17811814Swpaul struct member_entry *cur, *new; 17911814Swpaul struct grouplist *tmp; 18011814Swpaul u_int32_t i; 18111814Swpaul 18211814Swpaul i = hashkey(key); 18311814Swpaul cur = table[i]; 18411814Swpaul 18511814Swpaul tmp = (struct grouplist *)malloc(sizeof(struct grouplist)); 18611814Swpaul tmp->groupname = strdup(data); 18711814Swpaul tmp->next = NULL; 18811814Swpaul 18911814Swpaul /* Check if all we have to do is insert a new groupname. */ 19011814Swpaul while (cur) { 19111814Swpaul if (!strcmp(cur->key, key)) { 19211814Swpaul tmp->next = cur->groups; 19311814Swpaul cur->groups = tmp; 19411814Swpaul return; 19511814Swpaul } 19611814Swpaul cur = cur->next; 19711814Swpaul } 19811814Swpaul 19911814Swpaul /* Didn't find a match -- add the whole mess to the table. */ 20011814Swpaul new = (struct member_entry *)malloc(sizeof(struct member_entry)); 20111814Swpaul new->key = strdup(key); 20211814Swpaul new->domain = domain ? strdup(domain) : "*"; 20311814Swpaul new->groups = tmp; 20411814Swpaul new->next = table[i]; 20511814Swpaul table[i] = new; 20611814Swpaul 20711814Swpaul return; 20811814Swpaul} 209