1 /* $NetBSD: test_hash.c,v 1.2 2011/02/16 02:14:23 christos Exp $ */
2
3 /* Copyright (c) 2010 The NetBSD Foundation, Inc.
4 * All rights reserved.
5 *
6 * This code is derived from software contributed to The NetBSD Foundation
7 * by Mateusz Kocielski.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. All advertising materials mentioning features or use of this software
18 * must display the following acknowledgement:
19 * This product includes software developed by the NetBSD
20 * Foundation, Inc. and its contributors.
21 * 4. Neither the name of The NetBSD Foundation nor the names of its
22 * contributors may be used to endorse or promote products derived
23 * from this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
26 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
27 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
29 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 * POSSIBILITY OF SUCH DAMAGE.
36 */
37
38 #include <err.h>
39 #include <malloc.h>
40 #include <stdio.h>
41 #include <stdlib.h>
42 #include <string.h>
43
44 #include <saslc.h>
45
46 __RCSID("$NetBSD: test_hash.c,v 1.2 2011/02/16 02:14:23 christos Exp $");
47
48 #define MAX_HASH_SIZE 256
49
50 /*
51 * List of all property keys.
52 * NB: I did not list those used for debugging as collisions in that
53 * case don't really hurt anything.
54 */
55 static const char *keys[] = {
56 SASLC_PROP_AUTHCID,
57 SASLC_PROP_AUTHZID,
58 SASLC_PROP_BASE64IO,
59 SASLC_PROP_CIPHERMASK,
60 SASLC_PROP_DEBUG,
61 SASLC_PROP_HOSTNAME,
62 SASLC_PROP_MAXBUF,
63 SASLC_PROP_PASSWD,
64 SASLC_PROP_QOPMASK,
65 SASLC_PROP_REALM,
66 SASLC_PROP_SECURITY,
67 SASLC_PROP_SERVICE,
68 SASLC_PROP_SERVNAME
69 };
70
71 /*
72 * This must match the dict.c::saslc__dict_hashval() routine.
73 */
74 static size_t
hash(const char * cp,size_t hsize,size_t hinit,size_t shift)75 hash(const char *cp, size_t hsize, size_t hinit, size_t shift)
76 {
77 size_t hval;
78
79 hval = hinit;
80 for (/*EMPTY*/; *cp != '\0'; cp++) {
81 hval <<= shift;
82 hval += (size_t)*cp;
83 }
84 return hval % hsize;
85 }
86
87 static int
no_collision(size_t hsize,size_t hinit,size_t shift)88 no_collision(size_t hsize, size_t hinit, size_t shift)
89 {
90 const char **used;
91 size_t hval, i;
92
93 used = calloc(sizeof(*used), hsize);
94 if (used == NULL)
95 err(EXIT_FAILURE, "calloc");
96 for (i = 0; i < __arraycount(keys); i++) {
97 hval = hash(keys[i], hsize, hinit, shift);
98 if (used[hval] != 0) {
99 free(used);
100 return 0;
101 }
102 used[hval] = keys[i];
103 }
104 #if 0
105 for (i = 0; i < hsize; i++) {
106 if (used[i] != NULL)
107 printf("%02zd: %s\n", i, used[i]);
108 }
109 #endif
110 free(used);
111 return 1;
112 }
113
114 static int __dead
usage(int rval)115 usage(int rval)
116 {
117
118 printf("%s [<min hash size> [<max hash size>]]\n", getprogname());
119 printf("min and max hash size must be >= %zu\n", __arraycount(keys));
120 exit(rval);
121 }
122
123 static void
show_result(int brief,size_t h,size_t i,size_t s)124 show_result(int brief, size_t h, size_t i, size_t s)
125 {
126 if (brief)
127 printf("no collisions: hsize=%zu hinit=%zu shift=%zu\n", h, i, s);
128 else {
129 printf("#define HASH_SIZE\t%zu\n", h);
130 printf("#define HASH_INIT\t%zu\n", i);
131 printf("#define HASH_SHIFT\t%zu\n", s);
132 }
133 }
134
135 int
main(int argc,char ** argv)136 main(int argc, char **argv)
137 {
138 char *p;
139 size_t i, h, s;
140 size_t h_min, h_max;
141 int brief;
142
143 brief = argc != 1;
144 h_min = 0;
145 h_max = 0;
146 switch (argc) {
147 case 1:
148 h_min = __arraycount(keys);
149 h_max = MAX_HASH_SIZE;
150 break;
151 case 3:
152 h = strtol(argv[2], &p, 0);
153 if (*p != '\0' || h == 0)
154 usage(-1);
155 h_max = h;
156 /*FALLTHROUGH*/
157 case 2:
158 h = strtol(argv[1], &p, 0);
159 if (*p != '\0' || h == 0)
160 usage(-1);
161 h_min = h;
162 if (argc == 2)
163 h_max = h;
164 break;
165 default:
166 usage(0);
167 }
168 if (h_max < __arraycount(keys) ||
169 h_min < __arraycount(keys) ||
170 h_max < h_min)
171 usage(-1);
172
173 for (h = h_min; h <= h_max; h++) {
174 for (s = 0; s < 32; s++) {
175 for (i = 0; i < h; i++) {
176 if (no_collision(h, i, s)) {
177 show_result(brief, h, i, s);
178 if (argc == 1)
179 return 0;
180 }
181 }
182 }
183 }
184 return 0;
185 }
186