GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/ypserv/revnetgroup/hash.c Lines: 0 53 0.0 %
Date: 2017-11-13 Branches: 0 29 0.0 %

Line Branch Exec Source
1
/* $OpenBSD: hash.c,v 1.7 2009/10/27 23:59:58 deraadt Exp $ */
2
/*
3
 * Copyright (c) 1995
4
 *	Bill Paul <wpaul@ctr.columbia.edu>.  All rights reserved.
5
 *
6
 * Redistribution and use in source and binary forms, with or without
7
 * modification, are permitted provided that the following conditions
8
 * are met:
9
 * 1. Redistributions of source code must retain the above copyright
10
 *    notice, this list of conditions and the following disclaimer.
11
 * 2. Redistributions in binary form must reproduce the above copyright
12
 *    notice, this list of conditions and the following disclaimer in the
13
 *    documentation and/or other materials provided with the distribution.
14
 * 3. All advertising materials mentioning features or use of this software
15
 *    must display the following acknowledgement:
16
 *	This product includes software developed by Bill Paul.
17
 * 4. Neither the name of the author nor the names of any co-contributors
18
 *    may be used to endorse or promote products derived from this software
19
 *    without specific prior written permission.
20
 *
21
 * THIS SOFTWARE IS PROVIDED BY Bill Paul AND CONTRIBUTORS ``AS IS'' AND
22
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24
 * ARE DISCLAIMED.  IN NO EVENT SHALL Bill Paul OR CONTRIBUTORS BE LIABLE
25
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31
 * SUCH DAMAGE.
32
 *
33
 *	$FreeBSD: hash.c,v 1.4 1997/02/22 14:22:01 peter Exp $
34
 */
35
36
#include <stdio.h>
37
#include <stdlib.h>
38
#include <string.h>
39
#include <sys/types.h>
40
#include "hash.h"
41
42
/*
43
 * This hash function is stolen directly from the
44
 * Berkeley DB package. It already exists inside libc, but
45
 * it's declared static which prevents us from calling it
46
 * from here.
47
 */
48
/*
49
 * OZ's original sdbm hash
50
 */
51
static u_int32_t
52
hash(const void *keyarg, size_t len)
53
{
54
	const u_char *key;
55
	size_t loop;
56
	u_int32_t h;
57
58
#define HASHC   h = *key++ + 65599 * h
59
60
	h = 0;
61
	key = keyarg;
62
	if (len > 0) {
63
		loop = (len + 8 - 1) >> 3;
64
65
		switch (len & (8 - 1)) {
66
		case 0:
67
			do {
68
				HASHC;
69
				/* FALLTHROUGH */
70
		case 7:
71
				HASHC;
72
				/* FALLTHROUGH */
73
		case 6:
74
				HASHC;
75
				/* FALLTHROUGH */
76
		case 5:
77
				HASHC;
78
				/* FALLTHROUGH */
79
		case 4:
80
				HASHC;
81
				/* FALLTHROUGH */
82
		case 3:
83
				HASHC;
84
				/* FALLTHROUGH */
85
		case 2:
86
				HASHC;
87
				/* FALLTHROUGH */
88
		case 1:
89
				HASHC;
90
			} while (--loop);
91
		}
92
	}
93
	return (h);
94
}
95
96
/*
97
 * Generate a hash value for a given key (character string).
98
 * We mask off all but the lower 8 bits since our table array
99
 * can only hold 256 elements.
100
 */
101
static u_int32_t
102
hashkey(char *key)
103
{
104
105
	if (key == NULL)
106
		return (-1);
107
	return(hash(key, strlen(key)) & HASH_MASK);
108
}
109
110
/* Find an entry in the hash table (may be hanging off a linked list). */
111
char *
112
lookup(struct group_entry *table[], char *key)
113
{
114
	struct group_entry *cur;
115
116
	cur = table[hashkey(key)];
117
118
	while (cur) {
119
		if (!strcmp(cur->key, key))
120
			return(cur->data);
121
		cur = cur->next;
122
	}
123
124
	return(NULL);
125
}
126
127
/*
128
 * Store an entry in the main netgroup hash table. Here's how this
129
 * works: the table can only be so big when we initialize it (TABLESIZE)
130
 * but the number of netgroups in the /etc/netgroup file could easily be
131
 * much larger than the table. Since our hash values are adjusted to
132
 * never be greater than TABLESIZE too, this means it won't be long before
133
 * we find ourselves with two keys that hash to the same value.
134
 *
135
 * One way to deal with this is to malloc(2) a second table and start
136
 * doing indirection, but this is a pain in the butt and it's not worth
137
 * going to all that trouble for a dinky little program like this. Instead,
138
 * we turn each table entry into a linked list and simply link keys
139
 * with the same hash value together at the same index location within
140
 * the table.
141
 *
142
 * That's a lot of comment for such a small piece of code, isn't it.
143
 */
144
void
145
ngstore(struct group_entry *table[], char *key, char *data)
146
{
147
	struct group_entry *new;
148
	u_int32_t i;
149
150
	i = hashkey(key);
151
152
	new = malloc(sizeof(struct group_entry));
153
	new->key = strdup(key);
154
	new->data = strdup(data);
155
	new->next = table[i];
156
	table[i] = new;
157
}
158
159
/*
160
 * Store a group member entry and/or update its grouplist. This is
161
 * a bit more complicated than the previous function since we have to
162
 * maintain not only the hash table of group members, each group member
163
 * structure also has a linked list of groups hung off it. If handed
164
 * a member name that we haven't encountered before, we have to do
165
 * two things: add that member to the table (possibly hanging them
166
 * off the end of a linked list, as above), and add a group name to
167
 * the member's grouplist list. If we're handed a name that already has
168
 * an entry in the table, then we just have to do one thing, which is
169
 * to update its grouplist.
170
 */
171
void
172
mstore(struct member_entry *table[], char *key, char *data, char *domain)
173
{
174
	struct member_entry *cur, *new;
175
	struct grouplist *tmp,*p;
176
	u_int32_t i;
177
178
	i = hashkey(key);
179
	cur = table[i];
180
181
	tmp = malloc(sizeof(struct grouplist));
182
	tmp->groupname = strdup(data);
183
	tmp->next = NULL;
184
185
	/* Check if all we have to do is insert a new groupname. */
186
	while (cur) {
187
		if (!strcmp(cur->key, key) && !strcmp(cur->domain, domain)) {
188
			p = cur->groups;
189
			while (p) {
190
				if (!strcmp(p->groupname, data)) {
191
					free(tmp->groupname);
192
					free(tmp);
193
					return;
194
				}
195
				p = p->next;
196
			}
197
			tmp->next = cur->groups;
198
			cur->groups = tmp;
199
			return;
200
		}
201
		cur = cur->next;
202
	}
203
204
	/* Didn't find a match -- add the whole mess to the table. */
205
	new = malloc(sizeof(struct member_entry));
206
	new->key = strdup(key);
207
	new->domain = strdup(domain);
208
	new->groups = tmp;
209
	new->next = table[i];
210
	table[i] = new;
211
}