[apple/network_cmds.git] / revnetgroup.tproj / hash.c

/*
 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * "Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
 * Reserved.  This file contains Original Code and/or Modifications of
 * Original Code as defined in and that are subject to the Apple Public
 * Source License Version 1.0 (the 'License').  You may not use this file
 * except in compliance with the License.  Please obtain a copy of the
 * License at http://www.apple.com/publicsource and read it before using
 * this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License."
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/* $OpenBSD: hash.c,v 1.1 1997/04/15 22:06:11 maja 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"

#ifndef lint
static const char rcsid[] = "$OpenBSD: hash.c,v 1.1 1997/04/15 22:06:11 maja Exp $";
#endif

/*
 * 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
 */
u_int32_t
hash(keyarg, len)
	const void *keyarg;
	register size_t len;
{
	register const u_char *key;
	register size_t loop;
	register 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.
 */
u_int32_t hashkey(key)
	char *key;
{

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

/* Find an entry in the hash table (may be hanging off a linked list). */
char *lookup(table, key)
	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 store (table, key, data)
	struct group_entry *table[];
	char *key, *data;
{
	struct group_entry *new;
	u_int32_t i;

	i = hashkey(key);

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

	return;
}

/*
 * 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 (table, key, data, domain)
	struct member_entry *table[];
	char *key, *data, *domain;
{
	struct member_entry *cur, *new;
	struct grouplist *tmp,*p;
	u_int32_t i;

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

	tmp = (struct grouplist *)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))
					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 = (struct member_entry *)malloc(sizeof(struct member_entry));
	new->key = strdup(key);
	new->domain = strdup(domain);
	new->groups = tmp;
	new->next = table[i];
	table[i] = new;

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