1*043fbe51Sderaadt /* $OpenBSD: hash.c,v 1.7 2009/10/27 23:59:58 deraadt Exp $ */
2345c9dd4Smaja /*
3345c9dd4Smaja * Copyright (c) 1995
4345c9dd4Smaja * Bill Paul <wpaul@ctr.columbia.edu>. All rights reserved.
5345c9dd4Smaja *
6345c9dd4Smaja * Redistribution and use in source and binary forms, with or without
7345c9dd4Smaja * modification, are permitted provided that the following conditions
8345c9dd4Smaja * are met:
9345c9dd4Smaja * 1. Redistributions of source code must retain the above copyright
10345c9dd4Smaja * notice, this list of conditions and the following disclaimer.
11345c9dd4Smaja * 2. Redistributions in binary form must reproduce the above copyright
12345c9dd4Smaja * notice, this list of conditions and the following disclaimer in the
13345c9dd4Smaja * documentation and/or other materials provided with the distribution.
14345c9dd4Smaja * 3. All advertising materials mentioning features or use of this software
15345c9dd4Smaja * must display the following acknowledgement:
16345c9dd4Smaja * This product includes software developed by Bill Paul.
17345c9dd4Smaja * 4. Neither the name of the author nor the names of any co-contributors
18345c9dd4Smaja * may be used to endorse or promote products derived from this software
19345c9dd4Smaja * without specific prior written permission.
20345c9dd4Smaja *
21345c9dd4Smaja * THIS SOFTWARE IS PROVIDED BY Bill Paul AND CONTRIBUTORS ``AS IS'' AND
22345c9dd4Smaja * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23345c9dd4Smaja * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24345c9dd4Smaja * ARE DISCLAIMED. IN NO EVENT SHALL Bill Paul OR CONTRIBUTORS BE LIABLE
25345c9dd4Smaja * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26345c9dd4Smaja * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27345c9dd4Smaja * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28345c9dd4Smaja * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29345c9dd4Smaja * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30345c9dd4Smaja * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31345c9dd4Smaja * SUCH DAMAGE.
32345c9dd4Smaja *
33345c9dd4Smaja * $FreeBSD: hash.c,v 1.4 1997/02/22 14:22:01 peter Exp $
34345c9dd4Smaja */
35345c9dd4Smaja
36345c9dd4Smaja #include <stdio.h>
37345c9dd4Smaja #include <stdlib.h>
38345c9dd4Smaja #include <string.h>
39345c9dd4Smaja #include <sys/types.h>
40345c9dd4Smaja #include "hash.h"
41345c9dd4Smaja
42345c9dd4Smaja /*
43345c9dd4Smaja * This hash function is stolen directly from the
44345c9dd4Smaja * Berkeley DB package. It already exists inside libc, but
45345c9dd4Smaja * it's declared static which prevents us from calling it
46345c9dd4Smaja * from here.
47345c9dd4Smaja */
48345c9dd4Smaja /*
49345c9dd4Smaja * OZ's original sdbm hash
50345c9dd4Smaja */
515325fcc5Sderaadt static u_int32_t
hash(const void * keyarg,size_t len)5233dd5606Sderaadt hash(const void *keyarg, size_t len)
53345c9dd4Smaja {
540ac0d02eSmpech const u_char *key;
550ac0d02eSmpech size_t loop;
560ac0d02eSmpech u_int32_t h;
57345c9dd4Smaja
58345c9dd4Smaja #define HASHC h = *key++ + 65599 * h
59345c9dd4Smaja
60345c9dd4Smaja h = 0;
61345c9dd4Smaja key = keyarg;
62345c9dd4Smaja if (len > 0) {
63345c9dd4Smaja loop = (len + 8 - 1) >> 3;
64345c9dd4Smaja
65345c9dd4Smaja switch (len & (8 - 1)) {
66345c9dd4Smaja case 0:
67345c9dd4Smaja do {
68345c9dd4Smaja HASHC;
69345c9dd4Smaja /* FALLTHROUGH */
70345c9dd4Smaja case 7:
71345c9dd4Smaja HASHC;
72345c9dd4Smaja /* FALLTHROUGH */
73345c9dd4Smaja case 6:
74345c9dd4Smaja HASHC;
75345c9dd4Smaja /* FALLTHROUGH */
76345c9dd4Smaja case 5:
77345c9dd4Smaja HASHC;
78345c9dd4Smaja /* FALLTHROUGH */
79345c9dd4Smaja case 4:
80345c9dd4Smaja HASHC;
81345c9dd4Smaja /* FALLTHROUGH */
82345c9dd4Smaja case 3:
83345c9dd4Smaja HASHC;
84345c9dd4Smaja /* FALLTHROUGH */
85345c9dd4Smaja case 2:
86345c9dd4Smaja HASHC;
87345c9dd4Smaja /* FALLTHROUGH */
88345c9dd4Smaja case 1:
89345c9dd4Smaja HASHC;
90345c9dd4Smaja } while (--loop);
91345c9dd4Smaja }
92345c9dd4Smaja }
93345c9dd4Smaja return (h);
94345c9dd4Smaja }
95345c9dd4Smaja
96345c9dd4Smaja /*
97345c9dd4Smaja * Generate a hash value for a given key (character string).
98345c9dd4Smaja * We mask off all but the lower 8 bits since our table array
99345c9dd4Smaja * can only hold 256 elements.
100345c9dd4Smaja */
1015325fcc5Sderaadt static u_int32_t
hashkey(char * key)10233dd5606Sderaadt hashkey(char *key)
103345c9dd4Smaja {
104345c9dd4Smaja
105345c9dd4Smaja if (key == NULL)
106345c9dd4Smaja return (-1);
107fb92953eSderaadt return(hash(key, strlen(key)) & HASH_MASK);
108345c9dd4Smaja }
109345c9dd4Smaja
110345c9dd4Smaja /* Find an entry in the hash table (may be hanging off a linked list). */
11133dd5606Sderaadt char *
lookup(struct group_entry * table[],char * key)11233dd5606Sderaadt lookup(struct group_entry *table[], char *key)
113345c9dd4Smaja {
114345c9dd4Smaja struct group_entry *cur;
115345c9dd4Smaja
116345c9dd4Smaja cur = table[hashkey(key)];
117345c9dd4Smaja
118345c9dd4Smaja while (cur) {
119345c9dd4Smaja if (!strcmp(cur->key, key))
120345c9dd4Smaja return(cur->data);
121345c9dd4Smaja cur = cur->next;
122345c9dd4Smaja }
123345c9dd4Smaja
124345c9dd4Smaja return(NULL);
125345c9dd4Smaja }
126345c9dd4Smaja
127345c9dd4Smaja /*
128345c9dd4Smaja * Store an entry in the main netgroup hash table. Here's how this
129345c9dd4Smaja * works: the table can only be so big when we initialize it (TABLESIZE)
130345c9dd4Smaja * but the number of netgroups in the /etc/netgroup file could easily be
131345c9dd4Smaja * much larger than the table. Since our hash values are adjusted to
132345c9dd4Smaja * never be greater than TABLESIZE too, this means it won't be long before
133345c9dd4Smaja * we find ourselves with two keys that hash to the same value.
134345c9dd4Smaja *
135345c9dd4Smaja * One way to deal with this is to malloc(2) a second table and start
136345c9dd4Smaja * doing indirection, but this is a pain in the butt and it's not worth
137345c9dd4Smaja * going to all that trouble for a dinky little program like this. Instead,
138345c9dd4Smaja * we turn each table entry into a linked list and simply link keys
139345c9dd4Smaja * with the same hash value together at the same index location within
140345c9dd4Smaja * the table.
141345c9dd4Smaja *
142345c9dd4Smaja * That's a lot of comment for such a small piece of code, isn't it.
143345c9dd4Smaja */
14433dd5606Sderaadt void
ngstore(struct group_entry * table[],char * key,char * data)145fb92953eSderaadt ngstore(struct group_entry *table[], char *key, char *data)
146345c9dd4Smaja {
147345c9dd4Smaja struct group_entry *new;
148345c9dd4Smaja u_int32_t i;
149345c9dd4Smaja
150345c9dd4Smaja i = hashkey(key);
151345c9dd4Smaja
152fb92953eSderaadt new = malloc(sizeof(struct group_entry));
153345c9dd4Smaja new->key = strdup(key);
154345c9dd4Smaja new->data = strdup(data);
155345c9dd4Smaja new->next = table[i];
156345c9dd4Smaja table[i] = new;
157345c9dd4Smaja }
158345c9dd4Smaja
159345c9dd4Smaja /*
160345c9dd4Smaja * Store a group member entry and/or update its grouplist. This is
161345c9dd4Smaja * a bit more complicated than the previous function since we have to
162345c9dd4Smaja * maintain not only the hash table of group members, each group member
163345c9dd4Smaja * structure also has a linked list of groups hung off it. If handed
164345c9dd4Smaja * a member name that we haven't encountered before, we have to do
165345c9dd4Smaja * two things: add that member to the table (possibly hanging them
166345c9dd4Smaja * off the end of a linked list, as above), and add a group name to
167345c9dd4Smaja * the member's grouplist list. If we're handed a name that already has
168345c9dd4Smaja * an entry in the table, then we just have to do one thing, which is
169345c9dd4Smaja * to update its grouplist.
170345c9dd4Smaja */
17133dd5606Sderaadt void
mstore(struct member_entry * table[],char * key,char * data,char * domain)17233dd5606Sderaadt mstore(struct member_entry *table[], char *key, char *data, char *domain)
173345c9dd4Smaja {
174345c9dd4Smaja struct member_entry *cur, *new;
175345c9dd4Smaja struct grouplist *tmp,*p;
176345c9dd4Smaja u_int32_t i;
177345c9dd4Smaja
178345c9dd4Smaja i = hashkey(key);
179345c9dd4Smaja cur = table[i];
180345c9dd4Smaja
181fb92953eSderaadt tmp = malloc(sizeof(struct grouplist));
182345c9dd4Smaja tmp->groupname = strdup(data);
183345c9dd4Smaja tmp->next = NULL;
184345c9dd4Smaja
185345c9dd4Smaja /* Check if all we have to do is insert a new groupname. */
186345c9dd4Smaja while (cur) {
187345c9dd4Smaja if (!strcmp(cur->key, key) && !strcmp(cur->domain, domain)) {
188345c9dd4Smaja p = cur->groups;
189345c9dd4Smaja while (p) {
19049ac4008Sderaadt if (!strcmp(p->groupname, data)) {
19149ac4008Sderaadt free(tmp->groupname);
19249ac4008Sderaadt free(tmp);
193345c9dd4Smaja return;
19449ac4008Sderaadt }
195345c9dd4Smaja p = p->next;
196345c9dd4Smaja }
197345c9dd4Smaja tmp->next = cur->groups;
198345c9dd4Smaja cur->groups = tmp;
199345c9dd4Smaja return;
200345c9dd4Smaja }
201345c9dd4Smaja cur = cur->next;
202345c9dd4Smaja }
203345c9dd4Smaja
204345c9dd4Smaja /* Didn't find a match -- add the whole mess to the table. */
205fb92953eSderaadt new = malloc(sizeof(struct member_entry));
206345c9dd4Smaja new->key = strdup(key);
207345c9dd4Smaja new->domain = strdup(domain);
208345c9dd4Smaja new->groups = tmp;
209345c9dd4Smaja new->next = table[i];
210345c9dd4Smaja table[i] = new;
211345c9dd4Smaja }
212