1189251Ssam/*- 2189251Ssam * SPDX-License-Identifier: BSD-4-Clause 3252726Srpaulo * 4189251Ssam * Copyright (c) 1995 5252726Srpaulo * Bill Paul <wpaul@ctr.columbia.edu>. All rights reserved. 6252726Srpaulo * 7189251Ssam * Redistribution and use in source and binary forms, with or without 8189251Ssam * modification, are permitted provided that the following conditions 9189251Ssam * are met: 10189251Ssam * 1. Redistributions of source code must retain the above copyright 11189251Ssam * notice, this list of conditions and the following disclaimer. 12252726Srpaulo * 2. Redistributions in binary form must reproduce the above copyright 13252726Srpaulo * notice, this list of conditions and the following disclaimer in the 14189251Ssam * documentation and/or other materials provided with the distribution. 15189251Ssam * 3. All advertising materials mentioning features or use of this software 16189251Ssam * must display the following acknowledgement: 17189251Ssam * This product includes software developed by Bill Paul. 18189251Ssam * 4. Neither the name of the author nor the names of any co-contributors 19189251Ssam * may be used to endorse or promote products derived from this software 20189251Ssam * without specific prior written permission. 21189251Ssam * 22189251Ssam * THIS SOFTWARE IS PROVIDED BY Bill Paul AND CONTRIBUTORS ``AS IS'' AND 23189251Ssam * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24189251Ssam * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25189251Ssam * ARE DISCLAIMED. IN NO EVENT SHALL Bill Paul OR CONTRIBUTORS BE LIABLE 26189251Ssam * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27189251Ssam * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28189251Ssam * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29189251Ssam * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30189251Ssam * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31189251Ssam * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32189251Ssam * SUCH DAMAGE. 33189251Ssam */ 34189251Ssam 35189251Ssam#include <stdio.h> 36189251Ssam#include <stdlib.h> 37189251Ssam#include <string.h> 38189251Ssam#include <sys/types.h> 39189251Ssam#include "hash.h" 40189251Ssam 41189251Ssam/* 42189251Ssam * This hash function is stolen directly from the 43189251Ssam * Berkeley DB package. It already exists inside libc, but 44189251Ssam * it's declared static which prevents us from calling it 45189251Ssam * from here. 46189251Ssam */ 47189251Ssam/* 48189251Ssam * OZ's original sdbm hash 49252726Srpaulo */ 50252726Srpaulou_int32_t 51252726Srpaulohash(const void *keyarg, size_t len) 52252726Srpaulo{ 53252726Srpaulo const u_char *key; 54252726Srpaulo size_t loop; 55252726Srpaulo u_int32_t h; 56252726Srpaulo 57252726Srpaulo#define HASHC h = *key++ + 65599 * h 58189251Ssam 59189251Ssam h = 0; 60189251Ssam key = keyarg; 61189251Ssam if (len > 0) { 62189251Ssam loop = (len + 8 - 1) >> 3; 63189251Ssam 64189251Ssam switch (len & (8 - 1)) { 65189251Ssam case 0: 66189251Ssam do { 67189251Ssam HASHC; 68189251Ssam /* FALLTHROUGH */ 69189251Ssam case 7: 70189251Ssam HASHC; 71189251Ssam /* FALLTHROUGH */ 72189251Ssam case 6: 73189251Ssam HASHC; 74189251Ssam /* FALLTHROUGH */ 75189251Ssam case 5: 76189251Ssam HASHC; 77189251Ssam /* FALLTHROUGH */ 78189251Ssam case 4: 79189251Ssam HASHC; 80189251Ssam /* FALLTHROUGH */ 81189251Ssam case 3: 82189251Ssam HASHC; 83189251Ssam /* FALLTHROUGH */ 84189251Ssam case 2: 85189251Ssam HASHC; 86189251Ssam /* FALLTHROUGH */ 87189251Ssam case 1: 88189251Ssam HASHC; 89189251Ssam } while (--loop); 90189251Ssam } 91189251Ssam } 92189251Ssam return (h); 93189251Ssam} 94189251Ssam 95189251Ssam/* 96189251Ssam * Generate a hash value for a given key (character string). 97189251Ssam * We mask off all but the lower 8 bits since our table array 98189251Ssam * can only hole 256 elements. 99189251Ssam */ 100189251Ssamu_int32_t hashkey(char *key) 101189251Ssam{ 102189251Ssam 103189251Ssam if (key == NULL) 104189251Ssam return (-1); 105189251Ssam return(hash((void *)key, strlen(key)) & HASH_MASK); 106189251Ssam} 107189251Ssam 108189251Ssam/* Find an entry in the hash table (may be hanging off a linked list). */ 109189251Ssamstruct grouplist *lookup(struct member_entry *table[], char *key) 110189251Ssam{ 111189251Ssam struct member_entry *cur; 112189251Ssam 113189251Ssam cur = table[hashkey(key)]; 114189251Ssam 115189251Ssam while (cur) { 116189251Ssam if (!strcmp(cur->key, key)) 117189251Ssam return(cur->groups); 118189251Ssam cur = cur->next; 119189251Ssam } 120189251Ssam 121189251Ssam return(NULL); 122189251Ssam} 123189251Ssam 124189251Ssamstruct grouplist dummy = { 99999, NULL }; 125189251Ssam 126189251Ssam/* 127189251Ssam * Store a group member entry and/or update its grouplist. 128189251Ssam */ 129189251Ssamvoid mstore (struct member_entry *table[], char *key, int gid, int dup) 130189251Ssam{ 131189251Ssam struct member_entry *cur, *new; 132189251Ssam struct grouplist *tmp; 133189251Ssam u_int32_t i; 134189251Ssam 135189251Ssam i = hashkey(key); 136189251Ssam cur = table[i]; 137189251Ssam 138189251Ssam if (!dup) { 139189251Ssam tmp = (struct grouplist *)malloc(sizeof(struct grouplist)); 140189251Ssam tmp->groupid = gid; 141189251Ssam tmp->next = NULL; 142189251Ssam } 143189251Ssam 144189251Ssam /* Check if all we have to do is insert a new groupname. */ 145189251Ssam while (cur) { 146189251Ssam if (!dup && !strcmp(cur->key, key)) { 147189251Ssam tmp->next = cur->groups; 148189251Ssam cur->groups = tmp; 149189251Ssam return; 150189251Ssam } 151189251Ssam cur = cur->next; 152189251Ssam } 153189251Ssam 154189251Ssam /* Didn't find a match -- add the whole mess to the table. */ 155189251Ssam new = (struct member_entry *)malloc(sizeof(struct member_entry)); 156189251Ssam new->key = strdup(key); 157189251Ssam if (!dup) 158189251Ssam new->groups = tmp; 159189251Ssam else 160189251Ssam new->groups = (struct grouplist *)&dummy; 161189251Ssam new->next = table[i]; 162189251Ssam table[i] = new; 163189251Ssam 164189251Ssam return; 165189251Ssam} 166189251Ssam