hash.c revision 16729
1181053Srwatson/* 2188313Srwatson * Copyright (c) 1995 3155192Srwatson * Bill Paul <wpaul@ctr.columbia.edu>. All rights reserved. 4155192Srwatson * 5155192Srwatson * Redistribution and use in source and binary forms, with or without 6155192Srwatson * modification, are permitted provided that the following conditions 7155192Srwatson * are met: 8155192Srwatson * 1. Redistributions of source code must retain the above copyright 9155192Srwatson * notice, this list of conditions and the following disclaimer. 10155192Srwatson * 2. Redistributions in binary form must reproduce the above copyright 11155192Srwatson * notice, this list of conditions and the following disclaimer in the 12155192Srwatson * documentation and/or other materials provided with the distribution. 13180701Srwatson * 3. All advertising materials mentioning features or use of this software 14155192Srwatson * must display the following acknowledgement: 15155192Srwatson * This product includes software developed by Bill Paul. 16155192Srwatson * 4. Neither the name of the author nor the names of any co-contributors 17155192Srwatson * may be used to endorse or promote products derived from this software 18155192Srwatson * without specific prior written permission. 19155192Srwatson * 20155192Srwatson * THIS SOFTWARE IS PROVIDED BY Bill Paul AND CONTRIBUTORS ``AS IS'' AND 21155192Srwatson * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22155192Srwatson * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23155192Srwatson * ARE DISCLAIMED. IN NO EVENT SHALL Bill Paul OR CONTRIBUTORS BE LIABLE 24155192Srwatson * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25155192Srwatson * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26155192Srwatson * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27155192Srwatson * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28155192Srwatson * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29155192Srwatson * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30155192Srwatson * SUCH DAMAGE. 31155192Srwatson * 32155192Srwatson * $Id: hash.c,v 1.3 1996/06/24 22:48:50 wpaul Exp $ 33155192Srwatson */ 34155192Srwatson 35155192Srwatson#include <stdio.h> 36155192Srwatson#include <stdlib.h> 37156882Srwatson#include <string.h> 38156882Srwatson#include <sys/types.h> 39155192Srwatson#include "hash.h" 40155192Srwatson 41155192Srwatson#ifndef lint 42155192Srwatsonstatic const char rcsid[] = "$Id: hash.c,v 1.3 1996/06/24 22:48:50 wpaul Exp $"; 43155192Srwatson#endif 44255219Spjd 45155192Srwatson 46155192Srwatson/* 47155192Srwatson * This hash function is stolen directly from the 48155192Srwatson * Berkeley DB package. It already exists inside libc, but 49155192Srwatson * it's declared static which prevents us from calling it 50155192Srwatson * from here. 51155192Srwatson */ 52155192Srwatson/* 53155192Srwatson * OZ's original sdbm hash 54195177Ssson */ 55155192Srwatsonu_int32_t 56155192Srwatsonhash(keyarg, len) 57155192Srwatson const void *keyarg; 58156889Srwatson register size_t len; 59156889Srwatson{ 60155192Srwatson register const u_char *key; 61155192Srwatson register size_t loop; 62155192Srwatson register u_int32_t h; 63155192Srwatson 64155192Srwatson#define HASHC h = *key++ + 65599 * h 65155192Srwatson 66161813Swsalamon h = 0; 67161813Swsalamon key = keyarg; 68155192Srwatson if (len > 0) { 69155192Srwatson loop = (len + 8 - 1) >> 3; 70155192Srwatson 71155192Srwatson switch (len & (8 - 1)) { 72155192Srwatson case 0: 73156889Srwatson do { 74156889Srwatson HASHC; 75156889Srwatson /* FALLTHROUGH */ 76155192Srwatson case 7: 77155192Srwatson HASHC; 78159269Srwatson /* FALLTHROUGH */ 79159269Srwatson case 6: 80159269Srwatson HASHC; 81155192Srwatson /* FALLTHROUGH */ 82155192Srwatson case 5: 83155192Srwatson HASHC; 84155192Srwatson /* FALLTHROUGH */ 85159269Srwatson case 4: 86159269Srwatson HASHC; 87159269Srwatson /* FALLTHROUGH */ 88162380Scsjp case 3: 89162380Scsjp HASHC; 90162380Scsjp /* FALLTHROUGH */ 91155192Srwatson case 2: 92155192Srwatson HASHC; 93155192Srwatson /* FALLTHROUGH */ 94155192Srwatson case 1: 95155192Srwatson HASHC; 96155192Srwatson } while (--loop); 97155192Srwatson } 98155192Srwatson } 99156889Srwatson return (h); 100156889Srwatson} 101156889Srwatson 102156889Srwatson/* 103156889Srwatson * Generate a hash value for a given key (character string). 104156889Srwatson * We mask off all but the lower 8 bits since our table array 105156889Srwatson * can only hole 256 elements. 106155192Srwatson */ 107155192Srwatsonu_int32_t hashkey(key) 108155192Srwatson char *key; 109195177Ssson{ 110195177Ssson 111155192Srwatson if (key == NULL) 112155192Srwatson return (-1); 113155192Srwatson return(hash((void *)key, strlen(key)) & HASH_MASK); 114180709Srwatson} 115155192Srwatson 116155192Srwatson/* Find an entry in the hash table (may be hanging off a linked list). */ 117156889Srwatsonstruct grouplist *lookup(table, key) 118156889Srwatson struct member_entry *table[]; 119156889Srwatson char *key; 120156889Srwatson{ 121155192Srwatson struct member_entry *cur; 122155192Srwatson 123191270Srwatson cur = table[hashkey(key)]; 124191270Srwatson 125191270Srwatson while (cur) { 126191270Srwatson if (!strcmp(cur->key, key)) 127191270Srwatson return(cur->groups); 128191270Srwatson cur = cur->next; 129191270Srwatson } 130191270Srwatson 131191270Srwatson return(NULL); 132191270Srwatson} 133191270Srwatson 134191270Srwatsonstruct grouplist dummy = { 99999, NULL }; 135191270Srwatson 136155192Srwatson/* 137155192Srwatson * Store an group member entry and/or update its grouplist. 138191270Srwatson */ 139191270Srwatsonvoid mstore (table, key, gid, dup) 140191270Srwatson struct member_entry *table[]; 141155192Srwatson char *key; 142191270Srwatson int gid; 143191270Srwatson int dup; 144155192Srwatson{ 145155192Srwatson struct member_entry *cur, *new; 146155192Srwatson struct grouplist *tmp; 147155192Srwatson u_int32_t i; 148155192Srwatson 149155192Srwatson i = hashkey(key); 150191270Srwatson cur = table[i]; 151155192Srwatson 152155192Srwatson if (!dup) { 153184856Scsjp tmp = (struct grouplist *)malloc(sizeof(struct grouplist)); 154155192Srwatson tmp->groupid = gid; 155155192Srwatson tmp->next = NULL; 156155192Srwatson } 157156889Srwatson 158156889Srwatson /* Check if all we have to do is insert a new groupname. */ 159156889Srwatson while (cur) { 160155192Srwatson if (!dup && !strcmp(cur->key, key)) { 161155192Srwatson tmp->next = cur->groups; 162155192Srwatson cur->groups = tmp; 163155192Srwatson return; 164155192Srwatson } 165155192Srwatson cur = cur->next; 166155192Srwatson } 167155192Srwatson 168155192Srwatson /* Didn't find a match -- add the whole mess to the table. */ 169155192Srwatson new = (struct member_entry *)malloc(sizeof(struct member_entry)); 170155192Srwatson new->key = strdup(key); 171155192Srwatson if (!dup) 172155192Srwatson new->groups = tmp; 173156889Srwatson else 174156889Srwatson new->groups = (struct grouplist *)&dummy; 175156889Srwatson new->next = table[i]; 176156889Srwatson table[i] = new; 177156889Srwatson 178156889Srwatson return; 179156889Srwatson} 180156889Srwatson