1df57947fSPedro F. Giffuni /*- 2df57947fSPedro F. Giffuni * SPDX-License-Identifier: BSD-4-Clause 3df57947fSPedro F. Giffuni * 4ca09eb42SBill Paul * Copyright (c) 1995 5ca09eb42SBill Paul * Bill Paul <wpaul@ctr.columbia.edu>. All rights reserved. 6ca09eb42SBill Paul * 7ca09eb42SBill Paul * Redistribution and use in source and binary forms, with or without 8ca09eb42SBill Paul * modification, are permitted provided that the following conditions 9ca09eb42SBill Paul * are met: 10ca09eb42SBill Paul * 1. Redistributions of source code must retain the above copyright 11ca09eb42SBill Paul * notice, this list of conditions and the following disclaimer. 12ca09eb42SBill Paul * 2. Redistributions in binary form must reproduce the above copyright 13ca09eb42SBill Paul * notice, this list of conditions and the following disclaimer in the 14ca09eb42SBill Paul * documentation and/or other materials provided with the distribution. 15ca09eb42SBill Paul * 3. All advertising materials mentioning features or use of this software 16ca09eb42SBill Paul * must display the following acknowledgement: 17ca09eb42SBill Paul * This product includes software developed by Bill Paul. 18ca09eb42SBill Paul * 4. Neither the name of the author nor the names of any co-contributors 19ca09eb42SBill Paul * may be used to endorse or promote products derived from this software 20ca09eb42SBill Paul * without specific prior written permission. 21ca09eb42SBill Paul * 22ca09eb42SBill Paul * THIS SOFTWARE IS PROVIDED BY Bill Paul AND CONTRIBUTORS ``AS IS'' AND 23ca09eb42SBill Paul * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24ca09eb42SBill Paul * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25ca09eb42SBill Paul * ARE DISCLAIMED. IN NO EVENT SHALL Bill Paul OR CONTRIBUTORS BE LIABLE 26ca09eb42SBill Paul * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27ca09eb42SBill Paul * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28ca09eb42SBill Paul * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29ca09eb42SBill Paul * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30ca09eb42SBill Paul * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31ca09eb42SBill Paul * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32ca09eb42SBill Paul * SUCH DAMAGE. 33ca09eb42SBill Paul */ 34ca09eb42SBill Paul 35ca09eb42SBill Paul #include <stdio.h> 36ca09eb42SBill Paul #include <stdlib.h> 37ca09eb42SBill Paul #include <string.h> 38ca09eb42SBill Paul #include <sys/types.h> 39ca09eb42SBill Paul #include "hash.h" 40ca09eb42SBill Paul 41ca09eb42SBill Paul #ifndef lint 42ad17ca10SPhilippe Charnier static const char rcsid[] = 437f3dea24SPeter Wemm "$FreeBSD$"; 44ad17ca10SPhilippe Charnier #endif /* not lint */ 45ca09eb42SBill Paul 46ca09eb42SBill Paul /* 47ca09eb42SBill Paul * This hash function is stolen directly from the 48ca09eb42SBill Paul * Berkeley DB package. It already exists inside libc, but 49ca09eb42SBill Paul * it's declared static which prevents us from calling it 50ca09eb42SBill Paul * from here. 51ca09eb42SBill Paul */ 52ca09eb42SBill Paul /* 53ca09eb42SBill Paul * OZ's original sdbm hash 54ca09eb42SBill Paul */ 55ca09eb42SBill Paul u_int32_t 5671233f4fSWarner Losh hash(const void *keyarg, size_t len) 57ca09eb42SBill Paul { 5871233f4fSWarner Losh const u_char *key; 5971233f4fSWarner Losh size_t loop; 6071233f4fSWarner Losh u_int32_t h; 61ca09eb42SBill Paul 62ca09eb42SBill Paul #define HASHC h = *key++ + 65599 * h 63ca09eb42SBill Paul 64ca09eb42SBill Paul h = 0; 65ca09eb42SBill Paul key = keyarg; 66ca09eb42SBill Paul if (len > 0) { 67ca09eb42SBill Paul loop = (len + 8 - 1) >> 3; 68ca09eb42SBill Paul 69ca09eb42SBill Paul switch (len & (8 - 1)) { 70ca09eb42SBill Paul case 0: 71ca09eb42SBill Paul do { 72ca09eb42SBill Paul HASHC; 73ca09eb42SBill Paul /* FALLTHROUGH */ 74ca09eb42SBill Paul case 7: 75ca09eb42SBill Paul HASHC; 76ca09eb42SBill Paul /* FALLTHROUGH */ 77ca09eb42SBill Paul case 6: 78ca09eb42SBill Paul HASHC; 79ca09eb42SBill Paul /* FALLTHROUGH */ 80ca09eb42SBill Paul case 5: 81ca09eb42SBill Paul HASHC; 82ca09eb42SBill Paul /* FALLTHROUGH */ 83ca09eb42SBill Paul case 4: 84ca09eb42SBill Paul HASHC; 85ca09eb42SBill Paul /* FALLTHROUGH */ 86ca09eb42SBill Paul case 3: 87ca09eb42SBill Paul HASHC; 88ca09eb42SBill Paul /* FALLTHROUGH */ 89ca09eb42SBill Paul case 2: 90ca09eb42SBill Paul HASHC; 91ca09eb42SBill Paul /* FALLTHROUGH */ 92ca09eb42SBill Paul case 1: 93ca09eb42SBill Paul HASHC; 94ca09eb42SBill Paul } while (--loop); 95ca09eb42SBill Paul } 96ca09eb42SBill Paul } 97ca09eb42SBill Paul return (h); 98ca09eb42SBill Paul } 99ca09eb42SBill Paul 100ca09eb42SBill Paul /* 101ca09eb42SBill Paul * Generate a hash value for a given key (character string). 102ca09eb42SBill Paul * We mask off all but the lower 8 bits since our table array 103ca09eb42SBill Paul * can only hole 256 elements. 104ca09eb42SBill Paul */ 10571233f4fSWarner Losh u_int32_t hashkey(char *key) 106ca09eb42SBill Paul { 107ca09eb42SBill Paul 108ca09eb42SBill Paul if (key == NULL) 109ca09eb42SBill Paul return (-1); 110ca09eb42SBill Paul return(hash((void *)key, strlen(key)) & HASH_MASK); 111ca09eb42SBill Paul } 112ca09eb42SBill Paul 113ca09eb42SBill Paul /* Find an entry in the hash table (may be hanging off a linked list). */ 11471233f4fSWarner Losh struct grouplist *lookup(struct member_entry *table[], char *key) 115ca09eb42SBill Paul { 116ca09eb42SBill Paul struct member_entry *cur; 117ca09eb42SBill Paul 118ca09eb42SBill Paul cur = table[hashkey(key)]; 119ca09eb42SBill Paul 120ca09eb42SBill Paul while (cur) { 121ca09eb42SBill Paul if (!strcmp(cur->key, key)) 122ca09eb42SBill Paul return(cur->groups); 123ca09eb42SBill Paul cur = cur->next; 124ca09eb42SBill Paul } 125ca09eb42SBill Paul 126ca09eb42SBill Paul return(NULL); 127ca09eb42SBill Paul } 128ca09eb42SBill Paul 129ca09eb42SBill Paul struct grouplist dummy = { 99999, NULL }; 130ca09eb42SBill Paul 131ca09eb42SBill Paul /* 132d64ada50SJens Schweikhardt * Store a group member entry and/or update its grouplist. 133ca09eb42SBill Paul */ 13471233f4fSWarner Losh void mstore (struct member_entry *table[], char *key, int gid, int dup) 135ca09eb42SBill Paul { 136ca09eb42SBill Paul struct member_entry *cur, *new; 137ca09eb42SBill Paul struct grouplist *tmp; 138ca09eb42SBill Paul u_int32_t i; 139ca09eb42SBill Paul 140ca09eb42SBill Paul i = hashkey(key); 141ca09eb42SBill Paul cur = table[i]; 142ca09eb42SBill Paul 143ca09eb42SBill Paul if (!dup) { 144ca09eb42SBill Paul tmp = (struct grouplist *)malloc(sizeof(struct grouplist)); 145ca09eb42SBill Paul tmp->groupid = gid; 146ca09eb42SBill Paul tmp->next = NULL; 147ca09eb42SBill Paul } 148ca09eb42SBill Paul 149ca09eb42SBill Paul /* Check if all we have to do is insert a new groupname. */ 150ca09eb42SBill Paul while (cur) { 151ca09eb42SBill Paul if (!dup && !strcmp(cur->key, key)) { 152ca09eb42SBill Paul tmp->next = cur->groups; 153ca09eb42SBill Paul cur->groups = tmp; 154ca09eb42SBill Paul return; 155ca09eb42SBill Paul } 156ca09eb42SBill Paul cur = cur->next; 157ca09eb42SBill Paul } 158ca09eb42SBill Paul 159ca09eb42SBill Paul /* Didn't find a match -- add the whole mess to the table. */ 160ca09eb42SBill Paul new = (struct member_entry *)malloc(sizeof(struct member_entry)); 161ca09eb42SBill Paul new->key = strdup(key); 162ca09eb42SBill Paul if (!dup) 163ca09eb42SBill Paul new->groups = tmp; 164ca09eb42SBill Paul else 165ca09eb42SBill Paul new->groups = (struct grouplist *)&dummy; 166ca09eb42SBill Paul new->next = table[i]; 167ca09eb42SBill Paul table[i] = new; 168ca09eb42SBill Paul 169ca09eb42SBill Paul return; 170ca09eb42SBill Paul } 171