xref: /freebsd/sbin/dhclient/hash.c (revision 59c8e88e72633afbc47a4ace0d2170d00d51f7dc)
1 /*	$OpenBSD: hash.c,v 1.9 2004/05/10 15:30:47 deraadt Exp $	*/
2 
3 /* Routines for manipulating hash tables... */
4 
5 /*-
6  * SPDX-License-Identifier: BSD-3-Clause
7  *
8  * Copyright (c) 1995, 1996, 1997, 1998 The Internet Software Consortium.
9  * All rights reserved.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  *
15  * 1. Redistributions of source code must retain the above copyright
16  *    notice, this list of conditions and the following disclaimer.
17  * 2. Redistributions in binary form must reproduce the above copyright
18  *    notice, this list of conditions and the following disclaimer in the
19  *    documentation and/or other materials provided with the distribution.
20  * 3. Neither the name of The Internet Software Consortium nor the names
21  *    of its contributors may be used to endorse or promote products derived
22  *    from this software without specific prior written permission.
23  *
24  * THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM AND
25  * CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
26  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
27  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
28  * DISCLAIMED.  IN NO EVENT SHALL THE INTERNET SOFTWARE CONSORTIUM OR
29  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
31  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
32  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
33  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
34  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
35  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36  * SUCH DAMAGE.
37  *
38  * This software has been written for the Internet Software Consortium
39  * by Ted Lemon <mellon@fugue.com> in cooperation with Vixie
40  * Enterprises.  To learn more about the Internet Software Consortium,
41  * see ``http://www.vix.com/isc''.  To learn more about Vixie
42  * Enterprises, see ``http://www.vix.com''.
43  */
44 
45 #include <sys/cdefs.h>
46 #include "dhcpd.h"
47 
48 static int do_hash(const unsigned char *, int, int);
49 
50 struct hash_table *
51 new_hash(void)
52 {
53 	struct hash_table *rv = new_hash_table(DEFAULT_HASH_SIZE);
54 
55 	if (!rv)
56 		return (rv);
57 	memset(&rv->buckets[0], 0,
58 	    DEFAULT_HASH_SIZE * sizeof(struct hash_bucket *));
59 	return (rv);
60 }
61 
62 static int
63 do_hash(const unsigned char *name, int len, int size)
64 {
65 	const unsigned char *s = name;
66 	int accum = 0, i = len;
67 
68 	while (i--) {
69 		/* Add the character in... */
70 		accum += *s++;
71 		/* Add carry back in... */
72 		while (accum > 255)
73 			accum = (accum & 255) + (accum >> 8);
74 	}
75 	return (accum % size);
76 }
77 
78 void add_hash(struct hash_table *table, const unsigned char *name, int len,
79     unsigned char *pointer)
80 {
81 	struct hash_bucket *bp;
82 	int hashno;
83 
84 	if (!table)
85 		return;
86 	if (!len)
87 		len = strlen((const char *)name);
88 
89 	hashno = do_hash(name, len, table->hash_count);
90 	bp = new_hash_bucket();
91 
92 	if (!bp) {
93 		warning("Can't add %s to hash table.", name);
94 		return;
95 	}
96 	bp->name = name;
97 	bp->value = pointer;
98 	bp->next = table->buckets[hashno];
99 	bp->len = len;
100 	table->buckets[hashno] = bp;
101 }
102 
103 void *
104 hash_lookup(struct hash_table *table, unsigned char *name, int len)
105 {
106 	struct hash_bucket *bp;
107 	int hashno;
108 
109 	if (!table)
110 		return (NULL);
111 
112 	if (!len)
113 		len = strlen((char *)name);
114 
115 	hashno = do_hash(name, len, table->hash_count);
116 
117 	for (bp = table->buckets[hashno]; bp; bp = bp->next)
118 		if (len == bp->len && !memcmp(bp->name, name, len))
119 			return (bp->value);
120 
121 	return (NULL);
122 }
123