116728Swpaul/* 216728Swpaul * Copyright (c) 1995 316728Swpaul * Bill Paul <wpaul@ctr.columbia.edu>. All rights reserved. 416728Swpaul * 516728Swpaul * Redistribution and use in source and binary forms, with or without 616728Swpaul * modification, are permitted provided that the following conditions 716728Swpaul * are met: 816728Swpaul * 1. Redistributions of source code must retain the above copyright 916728Swpaul * notice, this list of conditions and the following disclaimer. 1016728Swpaul * 2. Redistributions in binary form must reproduce the above copyright 1116728Swpaul * notice, this list of conditions and the following disclaimer in the 1216728Swpaul * documentation and/or other materials provided with the distribution. 1316728Swpaul * 3. All advertising materials mentioning features or use of this software 1416728Swpaul * must display the following acknowledgement: 1516728Swpaul * This product includes software developed by Bill Paul. 1616728Swpaul * 4. Neither the name of the author nor the names of any co-contributors 1716728Swpaul * may be used to endorse or promote products derived from this software 1816728Swpaul * without specific prior written permission. 1916728Swpaul * 2016728Swpaul * THIS SOFTWARE IS PROVIDED BY Bill Paul AND CONTRIBUTORS ``AS IS'' AND 2116728Swpaul * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2216728Swpaul * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2316728Swpaul * ARE DISCLAIMED. IN NO EVENT SHALL Bill Paul OR CONTRIBUTORS BE LIABLE 2416728Swpaul * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2516728Swpaul * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2616728Swpaul * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2716728Swpaul * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2816728Swpaul * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2916728Swpaul * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3016728Swpaul * SUCH DAMAGE. 3116728Swpaul */ 3216728Swpaul 3316728Swpaul#include <stdio.h> 3416728Swpaul#include <stdlib.h> 3516728Swpaul#include <string.h> 3616728Swpaul#include <sys/types.h> 3716728Swpaul#include "hash.h" 3816728Swpaul 3916728Swpaul#ifndef lint 4031385Scharnierstatic const char rcsid[] = 4150476Speter "$FreeBSD$"; 4231385Scharnier#endif /* not lint */ 4316728Swpaul 4416728Swpaul/* 4516728Swpaul * This hash function is stolen directly from the 4616728Swpaul * Berkeley DB package. It already exists inside libc, but 4716728Swpaul * it's declared static which prevents us from calling it 4816728Swpaul * from here. 4916728Swpaul */ 5016728Swpaul/* 5116728Swpaul * OZ's original sdbm hash 5216728Swpaul */ 5316728Swpaulu_int32_t 5490779Simphash(const void *keyarg, size_t len) 5516728Swpaul{ 5690779Simp const u_char *key; 5790779Simp size_t loop; 5890779Simp u_int32_t h; 5916728Swpaul 6016728Swpaul#define HASHC h = *key++ + 65599 * h 6116728Swpaul 6216728Swpaul h = 0; 6316728Swpaul key = keyarg; 6416728Swpaul if (len > 0) { 6516728Swpaul loop = (len + 8 - 1) >> 3; 6616728Swpaul 6716728Swpaul switch (len & (8 - 1)) { 6816728Swpaul case 0: 6916728Swpaul do { 7016728Swpaul HASHC; 7116728Swpaul /* FALLTHROUGH */ 7216728Swpaul case 7: 7316728Swpaul HASHC; 7416728Swpaul /* FALLTHROUGH */ 7516728Swpaul case 6: 7616728Swpaul HASHC; 7716728Swpaul /* FALLTHROUGH */ 7816728Swpaul case 5: 7916728Swpaul HASHC; 8016728Swpaul /* FALLTHROUGH */ 8116728Swpaul case 4: 8216728Swpaul HASHC; 8316728Swpaul /* FALLTHROUGH */ 8416728Swpaul case 3: 8516728Swpaul HASHC; 8616728Swpaul /* FALLTHROUGH */ 8716728Swpaul case 2: 8816728Swpaul HASHC; 8916728Swpaul /* FALLTHROUGH */ 9016728Swpaul case 1: 9116728Swpaul HASHC; 9216728Swpaul } while (--loop); 9316728Swpaul } 9416728Swpaul } 9516728Swpaul return (h); 9616728Swpaul} 9716728Swpaul 9816728Swpaul/* 9916728Swpaul * Generate a hash value for a given key (character string). 10016728Swpaul * We mask off all but the lower 8 bits since our table array 10116728Swpaul * can only hole 256 elements. 10216728Swpaul */ 10390779Simpu_int32_t hashkey(char *key) 10416728Swpaul{ 10516728Swpaul 10616728Swpaul if (key == NULL) 10716728Swpaul return (-1); 10816728Swpaul return(hash((void *)key, strlen(key)) & HASH_MASK); 10916728Swpaul} 11016728Swpaul 11116728Swpaul/* Find an entry in the hash table (may be hanging off a linked list). */ 11290779Simpstruct grouplist *lookup(struct member_entry *table[], char *key) 11316728Swpaul{ 11416728Swpaul struct member_entry *cur; 11516728Swpaul 11616728Swpaul cur = table[hashkey(key)]; 11716728Swpaul 11816728Swpaul while (cur) { 11916728Swpaul if (!strcmp(cur->key, key)) 12016728Swpaul return(cur->groups); 12116728Swpaul cur = cur->next; 12216728Swpaul } 12316728Swpaul 12416728Swpaul return(NULL); 12516728Swpaul} 12616728Swpaul 12716728Swpaulstruct grouplist dummy = { 99999, NULL }; 12816728Swpaul 12916728Swpaul/* 130108470Sschweikh * Store a group member entry and/or update its grouplist. 13116728Swpaul */ 13290779Simpvoid mstore (struct member_entry *table[], char *key, int gid, int dup) 13316728Swpaul{ 13416728Swpaul struct member_entry *cur, *new; 13516728Swpaul struct grouplist *tmp; 13616728Swpaul u_int32_t i; 13716728Swpaul 13816728Swpaul i = hashkey(key); 13916728Swpaul cur = table[i]; 14016728Swpaul 14116728Swpaul if (!dup) { 14216728Swpaul tmp = (struct grouplist *)malloc(sizeof(struct grouplist)); 14316728Swpaul tmp->groupid = gid; 14416728Swpaul tmp->next = NULL; 14516728Swpaul } 14616728Swpaul 14716728Swpaul /* Check if all we have to do is insert a new groupname. */ 14816728Swpaul while (cur) { 14916728Swpaul if (!dup && !strcmp(cur->key, key)) { 15016728Swpaul tmp->next = cur->groups; 15116728Swpaul cur->groups = tmp; 15216728Swpaul return; 15316728Swpaul } 15416728Swpaul cur = cur->next; 15516728Swpaul } 15616728Swpaul 15716728Swpaul /* Didn't find a match -- add the whole mess to the table. */ 15816728Swpaul new = (struct member_entry *)malloc(sizeof(struct member_entry)); 15916728Swpaul new->key = strdup(key); 16016728Swpaul if (!dup) 16116728Swpaul new->groups = tmp; 16216728Swpaul else 16316728Swpaul new->groups = (struct grouplist *)&dummy; 16416728Swpaul new->next = table[i]; 16516728Swpaul table[i] = new; 16616728Swpaul 16716728Swpaul return; 16816728Swpaul} 169