hash.c 6.28 KB
Newer Older
Ted Lemon's avatar
Ted Lemon committed
1
2
3
4
5
/* hash.c

   Routines for manipulating hash tables... */

/*
Ted Lemon's avatar
Ted Lemon committed
6
7
 * Copyright (c) 1995-2000 Internet Software Consortium.
 * All rights reserved.
Ted Lemon's avatar
Ted Lemon committed
8
 *
Ted Lemon's avatar
Ted Lemon committed
9
10
11
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
Ted Lemon's avatar
Ted Lemon committed
12
 *
Ted Lemon's avatar
Ted Lemon committed
13
14
15
16
17
18
19
20
 * 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. Neither the name of The Internet Software Consortium nor the names
 *    of its contributors may be used to endorse or promote products derived
 *    from this software without specific prior written permission.
Ted Lemon's avatar
Ted Lemon committed
21
 *
Ted Lemon's avatar
Ted Lemon committed
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 * THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM 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 THE INTERNET SOFTWARE CONSORTIUM 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.
 *
 * This software has been written for the Internet Software Consortium
 * by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc.
 * To learn more about the Internet Software Consortium, see
 * ``http://www.isc.org/''.  To learn more about Vixie Enterprises,
 * see ``http://www.vix.com''.   To learn more about Nominum, Inc., see
 * ``http://www.nominum.com''.
Ted Lemon's avatar
Ted Lemon committed
42
43
44
45
 */

#ifndef lint
static char copyright[] =
46
"$Id: hash.c,v 1.20 2000/03/18 03:31:39 mellon Exp $ Copyright (c) 1995-2000 The Internet Software Consortium.  All rights reserved.\n";
Ted Lemon's avatar
Ted Lemon committed
47
48
49
#endif /* not lint */

#include "dhcpd.h"
50
#include <ctype.h>
Ted Lemon's avatar
Ted Lemon committed
51

52
53
static int do_hash PROTO ((const unsigned char *, unsigned, unsigned));
static int do_case_hash PROTO ((const unsigned char *, unsigned, unsigned));
54

55
struct hash_table *new_hash (hash_reference referencer,
56
57
			     hash_dereference dereferencer,
			     int casep)
Ted Lemon's avatar
Ted Lemon committed
58
{
59
	struct hash_table *rv = new_hash_table (DEFAULT_HASH_SIZE, MDL);
Ted Lemon's avatar
Ted Lemon committed
60
61
	if (!rv)
		return rv;
Ted Lemon's avatar
Ted Lemon committed
62
	memset (&rv -> buckets [0], 0,
Ted Lemon's avatar
Ted Lemon committed
63
		DEFAULT_HASH_SIZE * sizeof (struct hash_bucket *));
64
65
	rv -> referencer = referencer;
	rv -> dereferencer = dereferencer;
66
67
68
69
70
71
72
	if (casep) {
		rv -> cmp = casecmp;
		rv -> do_hash = do_case_hash;
	} else {
		rv -> cmp = memcmp;
		rv -> do_hash = do_hash;
	}
Ted Lemon's avatar
Ted Lemon committed
73
74
75
	return rv;
}

76
static int do_case_hash (name, len, size)
77
78
79
	const unsigned char *name;
	unsigned len;
	unsigned size;
Ted Lemon's avatar
Ted Lemon committed
80
81
{
	register int accum = 0;
82
	register const unsigned char *s = (const unsigned char *)name;
Ted Lemon's avatar
Ted Lemon committed
83
	int i = len;
84
85
86
87
88
89
90
91
92
	register unsigned c;

	while (i--) {
		/* Make the hash case-insensitive. */
		c = *s++;
		if (isascii (c) && isupper (c))
			c = tolower (c);

		/* Add the character in... */
93
		accum += c;
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
		/* Add carry back in... */
		while (accum > 255) {
			accum = (accum & 255) + (accum >> 8);
		}
	}
	return accum % size;
}

static int do_hash (name, len, size)
	const unsigned char *name;
	unsigned len;
	unsigned size;
{
	register int accum = 0;
	register const unsigned char *s = (const unsigned char *)name;
	int i = len;

111
112
113
114
115
116
	while (i--) {
		/* Add the character in... */
		accum += *s++;
		/* Add carry back in... */
		while (accum > 255) {
			accum = (accum & 255) + (accum >> 8);
Ted Lemon's avatar
Ted Lemon committed
117
118
119
120
121
122
123
		}
	}
	return accum % size;
}

void add_hash (table, name, len, pointer)
	struct hash_table *table;
124
125
	unsigned len;
	const unsigned char *name;
126
	void *pointer;
Ted Lemon's avatar
Ted Lemon committed
127
{
128
129
	int hashno;
	struct hash_bucket *bp;
130
	void *foo;
131
132
133
134

	if (!table)
		return;

135
	if (!len)
136
		len = strlen ((const char *)name);
137

138
	hashno = (*table -> do_hash) (name, len, table -> hash_count);
139
	bp = new_hash_bucket (MDL);
140

Ted Lemon's avatar
Ted Lemon committed
141
	if (!bp) {
142
		log_error ("Can't add %s to hash table.", name);
Ted Lemon's avatar
Ted Lemon committed
143
144
		return;
	}
Ted Lemon's avatar
Ted Lemon committed
145
	bp -> name = name;
146
147
148
149
150
	if (table -> referencer) {
		foo = &bp -> value;
		(*(table -> referencer)) (foo, pointer, MDL);
	} else
		bp -> value = pointer;
Ted Lemon's avatar
Ted Lemon committed
151
	bp -> next = table -> buckets [hashno];
152
	bp -> len = len;
Ted Lemon's avatar
Ted Lemon committed
153
154
155
156
157
	table -> buckets [hashno] = bp;
}

void delete_hash_entry (table, name, len)
	struct hash_table *table;
158
159
	unsigned len;
	const unsigned char *name;
Ted Lemon's avatar
Ted Lemon committed
160
{
161
	int hashno;
Ted Lemon's avatar
Ted Lemon committed
162
	struct hash_bucket *bp, *pbp = (struct hash_bucket *)0;
163
	void *foo;
Ted Lemon's avatar
Ted Lemon committed
164

165
166
167
	if (!table)
		return;

168
	if (!len)
169
		len = strlen ((const char *)name);
170

171
	hashno = (*table -> do_hash) (name, len, table -> hash_count);
172

Ted Lemon's avatar
Ted Lemon committed
173
174
175
	/* Go through the list looking for an entry that matches;
	   if we find it, delete it. */
	for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
176
		if ((!bp -> len &&
177
		     !strcmp ((const char *)bp -> name, (const char *)name)) ||
Ted Lemon's avatar
Ted Lemon committed
178
		    (bp -> len == len &&
179
		     !(*table -> cmp) (bp -> name, name, len))) {
Ted Lemon's avatar
Ted Lemon committed
180
181
182
183
184
			if (pbp) {
				pbp -> next = bp -> next;
			} else {
				table -> buckets [hashno] = bp -> next;
			}
185
186
187
188
			if (table -> dereferencer) {
				foo = &bp -> value;
				(*(table -> dereferencer)) (foo, MDL);
			}
189
			free_hash_bucket (bp, MDL);
Ted Lemon's avatar
Ted Lemon committed
190
191
			break;
		}
192
		pbp = bp;	/* jwg, 9/6/96 - nice catch! */
Ted Lemon's avatar
Ted Lemon committed
193
194
195
	}
}

196
void *hash_lookup (table, name, len)
Ted Lemon's avatar
Ted Lemon committed
197
	struct hash_table *table;
198
199
	const unsigned char *name;
	unsigned len;
Ted Lemon's avatar
Ted Lemon committed
200
{
201
	int hashno;
Ted Lemon's avatar
Ted Lemon committed
202
203
	struct hash_bucket *bp;

204
205
	if (!table)
		return (unsigned char *)0;
206
	if (!len)
207
		len = strlen ((const char *)name);
208

209
	hashno = (*table -> do_hash) (name, len, table -> hash_count);
210

211
212
	for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
		if (len == bp -> len
213
		    && !(*table -> cmp) (bp -> name, name, len))
214
			return bp -> value;
Ted Lemon's avatar
Ted Lemon committed
215
216
217
218
	}
	return (unsigned char *)0;
}

219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
int casecmp (const void *v1, const void *v2, unsigned len)
{
	unsigned i;
	const char *s = v1;
	const char *t = v2;
	
	for (i = 0; i < len; i++)
	{
		int c1, c2;
		if (isascii (s [i]) && isupper (s [i]))
			c1 = tolower (s [i]);
		else
			c1 = s [i];
		
		if (isascii (t [i]) && isupper (t [i]))
			c2 = tolower (t [i]);
		else
			c2 = t [i];
		
		if (c1 < c2)
			return -1;
		if (c1 > c2)
			return 1;
	}
	return 0;
}