1/* $NetBSD: test_hash.c,v 1.1 2011/02/11 23:44:44 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.1 2011/02/11 23:44:44 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 */ 55static 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 */ 74static size_t 75hash(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 87static int 88no_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 114static int __dead 115usage(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 123static void 124show_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 135int 136main(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