Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.sbin/ypserv/revnetgroup/hash.c	Lines:	0	52	0.0 %
Date:	2017-11-07	Branches:	0	29	0.0 %


/* $OpenBSD: hash.c,v 1.7 2009/10/27 23:59:58 deraadt Exp $ */
/*
 * Copyright (c) 1995
 *	Bill Paul <wpaul@ctr.columbia.edu>.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by Bill Paul.
 * 4. Neither the name of the author nor the names of any co-contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY Bill Paul AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL Bill Paul OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	$FreeBSD: hash.c,v 1.4 1997/02/22 14:22:01 peter Exp $
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include "hash.h"

/*
 * This hash function is stolen directly from the
 * Berkeley DB package. It already exists inside libc, but
 * it's declared static which prevents us from calling it
 * from here.
 */
/*
 * OZ's original sdbm hash
 */
static u_int32_t
hash(const void *keyarg, size_t len)
{
	const u_char *key;
	size_t loop;
	u_int32_t h;

#define HASHC   h = *key++ + 65599 * h

	h = 0;
	key = keyarg;
	if (len > 0) {
		loop = (len + 8 - 1) >> 3;

		switch (len & (8 - 1)) {
		case 0:
			do {
				HASHC;
				/* FALLTHROUGH */
		case 7:
				HASHC;
				/* FALLTHROUGH */
		case 6:
				HASHC;
				/* FALLTHROUGH */
		case 5:
				HASHC;
				/* FALLTHROUGH */
		case 4:
				HASHC;
				/* FALLTHROUGH */
		case 3:
				HASHC;
				/* FALLTHROUGH */
		case 2:
				HASHC;
				/* FALLTHROUGH */
		case 1:
				HASHC;
			} while (--loop);
		}
	}
	return (h);
}

/*
 * Generate a hash value for a given key (character string).
 * We mask off all but the lower 8 bits since our table array
 * can only hold 256 elements.
 */
static u_int32_t
hashkey(char *key)
{

	if (key == NULL)
		return (-1);
	return(hash(key, strlen(key)) & HASH_MASK);
}

/* Find an entry in the hash table (may be hanging off a linked list). */
char *
lookup(struct group_entry *table[], char *key)
{
	struct group_entry *cur;

	cur = table[hashkey(key)];

	while (cur) {
		if (!strcmp(cur->key, key))
			return(cur->data);
		cur = cur->next;
	}

	return(NULL);
}

/*
 * Store an entry in the main netgroup hash table. Here's how this
 * works: the table can only be so big when we initialize it (TABLESIZE)
 * but the number of netgroups in the /etc/netgroup file could easily be
 * much larger than the table. Since our hash values are adjusted to
 * never be greater than TABLESIZE too, this means it won't be long before
 * we find ourselves with two keys that hash to the same value.
 *
 * One way to deal with this is to malloc(2) a second table and start
 * doing indirection, but this is a pain in the butt and it's not worth
 * going to all that trouble for a dinky little program like this. Instead,
 * we turn each table entry into a linked list and simply link keys
 * with the same hash value together at the same index location within
 * the table.
 *
 * That's a lot of comment for such a small piece of code, isn't it.
 */
void
ngstore(struct group_entry *table[], char *key, char *data)
{
	struct group_entry *new;
	u_int32_t i;

	i = hashkey(key);

	new = malloc(sizeof(struct group_entry));
	new->key = strdup(key);
	new->data = strdup(data);
	new->next = table[i];
	table[i] = new;
}

/*
 * Store a group member entry and/or update its grouplist. This is
 * a bit more complicated than the previous function since we have to
 * maintain not only the hash table of group members, each group member
 * structure also has a linked list of groups hung off it. If handed
 * a member name that we haven't encountered before, we have to do
 * two things: add that member to the table (possibly hanging them
 * off the end of a linked list, as above), and add a group name to
 * the member's grouplist list. If we're handed a name that already has
 * an entry in the table, then we just have to do one thing, which is
 * to update its grouplist.
 */
void
mstore(struct member_entry *table[], char *key, char *data, char *domain)
{
	struct member_entry *cur, *new;
	struct grouplist *tmp,*p;
	u_int32_t i;

	i = hashkey(key);
	cur = table[i];

	tmp = malloc(sizeof(struct grouplist));
	tmp->groupname = strdup(data);
	tmp->next = NULL;

	/* Check if all we have to do is insert a new groupname. */
	while (cur) {
		if (!strcmp(cur->key, key) && !strcmp(cur->domain, domain)) {
			p = cur->groups;
			while (p) {
				if (!strcmp(p->groupname, data)) {
					free(tmp->groupname);
					free(tmp);
					return;
				}
				p = p->next;
			}
			tmp->next = cur->groups;
			cur->groups = tmp;
			return;
		}
		cur = cur->next;
	}

	/* Didn't find a match -- add the whole mess to the table. */
	new = malloc(sizeof(struct member_entry));
	new->key = strdup(key);
	new->domain = strdup(domain);
	new->groups = tmp;
	new->next = table[i];
	table[i] = new;
}


Generated by: GCOVR (Version 3.3)

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			}