ht_test.c 9.3 KB
Newer Older
1
/*
2
 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
3
 *
4 5 6
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 8 9
 *
 * See the COPYRIGHT file distributed with this work for additional
 * information regarding copyright ownership.
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
 */

/* ! \file */

#include <config.h>

#include <atf-c.h>

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include <isc/hash.h>
#include <isc/ht.h>
#include <isc/mem.h>
25
#include <isc/print.h>
26
#include <isc/string.h>
27 28
#include <isc/util.h>

Mark Andrews's avatar
Mark Andrews committed
29 30
#include <inttypes.h>

31 32 33 34 35 36 37 38 39 40 41 42 43 44
static void *
default_memalloc(void *arg, size_t size) {
	UNUSED(arg);
	if (size == 0U)
		size = 1;
	return (malloc(size));
}

static void
default_memfree(void *arg, void *ptr) {
	UNUSED(arg);
	free(ptr);
}

45
static void test_ht_full(int bits, uintptr_t count) {
46 47 48
	isc_ht_t *ht = NULL;
	isc_result_t result;
	isc_mem_t *mctx = NULL;
49
	uintptr_t i;
50 51 52 53 54

	result = isc_mem_createx2(0, 0, default_memalloc, default_memfree,
				  NULL, &mctx, 0);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

55 56 57 58
	result = isc_ht_init(&ht, mctx, bits);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
	ATF_REQUIRE(ht != NULL);

59 60
	for (i = 1; i < count; i++) {
		/*
61 62
		 * Note: snprintf() is followed with strlcat()
		 * to ensure we are always filling the 16 byte key.
63 64
		 */
		unsigned char key[16];
Mark Andrews's avatar
Mark Andrews committed
65
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
66
		strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
67 68 69 70 71 72 73
		result = isc_ht_add(ht, key, 16, (void *) i);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
	}

	for (i = 1; i < count; i++) {
		unsigned char key[16];
		void *f = NULL;
Mark Andrews's avatar
Mark Andrews committed
74
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
75
		strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
76 77
		result = isc_ht_find(ht, key, 16, &f);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
78
		ATF_REQUIRE_EQ(i, (uintptr_t) f);
79 80 81 82
	}

	for (i = 1; i < count; i++) {
		unsigned char key[16];
Mark Andrews's avatar
Mark Andrews committed
83
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
84
		strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
85 86 87 88 89 90
		result = isc_ht_add(ht, key, 16, (void *) i);
		ATF_REQUIRE_EQ(result, ISC_R_EXISTS);
	}

	for (i = 1; i < count; i++) {
		char key[64];
91 92 93 94
		/*
		 * Note: the key size is now strlen(key) which is bigger
		 * then the keys added above.
		 */
Mark Andrews's avatar
Mark Andrews committed
95
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
96
		strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
97 98 99 100 101 102 103 104
		result = isc_ht_add(ht, (const unsigned char *) key,
				    strlen(key), (void *) i);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
	}

	for (i = 1; i < count; i++) {
		unsigned char key[16];
		void *f = NULL;
105 106 107
		/*
		 * Note: case of KEY is now in capitals,
		 */
Mark Andrews's avatar
Mark Andrews committed
108
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
109
		strlcat((char *)key, " KEY of a raw hashtable!!", sizeof(key));
110 111 112 113 114 115 116 117
		result = isc_ht_find(ht, key, 16, &f);
		ATF_REQUIRE_EQ(result, ISC_R_NOTFOUND);
		ATF_REQUIRE_EQ(f, NULL);
	}

	for (i = 1; i < count; i++) {
		char key[64];
		void *f = NULL;
Mark Andrews's avatar
Mark Andrews committed
118
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
119
		strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
120 121 122 123 124 125 126 127 128
		result = isc_ht_find(ht, (const unsigned char *) key,
				     strlen(key), &f);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
		ATF_REQUIRE_EQ(f, (void *) i);
	}

	for (i = 1; i < count; i++) {
		unsigned char key[16];
		void *f = NULL;
Mark Andrews's avatar
Mark Andrews committed
129
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
130
		strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
131 132 133 134 135 136 137 138 139
		result = isc_ht_delete(ht, key, 16);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
		result = isc_ht_find(ht, key, 16, &f);
		ATF_REQUIRE_EQ(result, ISC_R_NOTFOUND);
		ATF_REQUIRE_EQ(f, NULL);
	}

	for (i = 1; i < count; i++) {
		unsigned char key[16];
140 141 142
		/*
		 * Note: upper case KEY.
		 */
Mark Andrews's avatar
Mark Andrews committed
143
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
144
		strlcat((char *)key, " KEY of a raw hashtable!!", sizeof(key));
145 146 147 148 149 150 151
		result = isc_ht_add(ht, key, 16, (void *) i);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
	}

	for (i = 1; i < count; i++) {
		char key[64];
		void *f = NULL;
Mark Andrews's avatar
Mark Andrews committed
152
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
153
		strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
154 155 156 157 158 159 160 161 162 163 164 165 166
		result = isc_ht_delete(ht, (const unsigned char *) key,
				       strlen(key));
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
		result = isc_ht_find(ht, (const unsigned char *) key,
				     strlen(key), &f);
		ATF_REQUIRE_EQ(result, ISC_R_NOTFOUND);
		ATF_REQUIRE_EQ(f, NULL);
	}


	for (i = 1; i < count; i++) {
		unsigned char key[16];
		void *f = NULL;
167 168 169
		/*
		 * Note: case of KEY is now in capitals,
		 */
Mark Andrews's avatar
Mark Andrews committed
170
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
171
		strlcat((char *)key, " KEY of a raw hashtable!!", sizeof(key));
172 173
		result = isc_ht_find(ht, key, 16, &f);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
174
		ATF_REQUIRE_EQ(i, (uintptr_t) f);
175 176 177 178 179
	}

	for (i = 1; i < count; i++) {
		unsigned char key[16];
		void *f = NULL;
Mark Andrews's avatar
Mark Andrews committed
180
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
181
		strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
182 183 184 185 186 187 188 189 190
		result = isc_ht_find(ht, key, 16, &f);
		ATF_REQUIRE_EQ(result, ISC_R_NOTFOUND);
		ATF_REQUIRE_EQ(f, NULL);
	}

	isc_ht_destroy(&ht);
	ATF_REQUIRE_EQ(ht, NULL);
}

191
static void test_ht_iterator() {
192 193 194
	isc_ht_t *ht = NULL;
	isc_result_t result;
	isc_mem_t *mctx = NULL;
195
	isc_ht_iter_t * iter = NULL;
196 197 198
	uintptr_t i;
	void *v;
	uintptr_t count = 10000;
199 200 201 202
	isc_uint32_t walked;
	unsigned char key[16];
	unsigned char *tkey;
	size_t tksize;
203 204 205 206 207 208 209 210 211 212 213 214 215

	result = isc_mem_createx2(0, 0, default_memalloc, default_memfree,
				  NULL, &mctx, 0);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	result = isc_ht_init(&ht, mctx, 16);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
	ATF_REQUIRE(ht != NULL);
	for (i = 1; i <= count; i++) {
		/*
		 * Note that the string we're snprintfing is always > 16 bytes
		 * so we are always filling the key.
		 */
Mark Andrews's avatar
Mark Andrews committed
216
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
217
		strlcat((char *)key, "key of a raw hashtable!!", sizeof(key));
218 219 220 221 222
		result = isc_ht_add(ht, key, 16, (void *) i);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
	}

	walked = 0;
223
	result = isc_ht_iter_create(ht, &iter);
224 225
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

226 227 228 229
	for (result = isc_ht_iter_first(iter);
	     result == ISC_R_SUCCESS;
	     result = isc_ht_iter_next(iter))
	{
230
		isc_ht_iter_current(iter, &v);
231 232
		isc_ht_iter_currentkey(iter, &tkey, &tksize);
		ATF_REQUIRE_EQ(tksize, 16);
233 234
		i = (uintptr_t)v;
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
235
		strlcat((char *)key, "key of a raw hashtable!!", sizeof(key));
236 237 238 239 240
		ATF_REQUIRE_EQ(memcmp(key, tkey, 16), 0);
		walked++;
	}
	ATF_REQUIRE_EQ(walked, count);
	ATF_REQUIRE_EQ(result, ISC_R_NOMORE);
241

242
	/* erase odd */
243
	walked = 0;
244 245
	result = isc_ht_iter_first(iter);
	while (result == ISC_R_SUCCESS) {
246
		isc_ht_iter_current(iter, &v);
247 248
		isc_ht_iter_currentkey(iter, &tkey, &tksize);
		ATF_REQUIRE_EQ(tksize, 16);
249 250
		i = (uintptr_t)v;
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
251
		strlcat((char *)key, "key of a raw hashtable!!", sizeof(key));
252
		ATF_REQUIRE_EQ(memcmp(key, tkey, 16), 0);
253
		if ((uintptr_t)v % 2 == 0) {
254 255 256 257 258 259 260
			result = isc_ht_iter_delcurrent_next(iter);
		} else {
			result = isc_ht_iter_next(iter);
		}
		walked++;
	}
	ATF_REQUIRE_EQ(result, ISC_R_NOMORE);
261 262
	ATF_REQUIRE_EQ(walked, count);

263
	/* erase even */
264
	walked = 0;
265 266
	result = isc_ht_iter_first(iter);
	while (result == ISC_R_SUCCESS) {
267
		isc_ht_iter_current(iter, &v);
268 269
		isc_ht_iter_currentkey(iter, &tkey, &tksize);
		ATF_REQUIRE_EQ(tksize, 16);
270 271
		i = (uintptr_t)v;
		snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
272
		strlcat((char *)key, "key of a raw hashtable!!", sizeof(key));
273
		ATF_REQUIRE_EQ(memcmp(key, tkey, 16), 0);
274
		if ((uintptr_t)v % 2 == 1) {
275 276 277 278 279 280 281
			result = isc_ht_iter_delcurrent_next(iter);
		} else {
			result = isc_ht_iter_next(iter);
		}
		walked++;
	}
	ATF_REQUIRE_EQ(result, ISC_R_NOMORE);
282 283 284
	ATF_REQUIRE_EQ(walked, count/2);

	walked = 0;
285 286 287 288 289 290 291 292
	for (result = isc_ht_iter_first(iter);
	     result == ISC_R_SUCCESS;
	     result = isc_ht_iter_next(iter))
	{
		walked++;
	}

	ATF_REQUIRE_EQ(result, ISC_R_NOMORE);
293 294 295 296 297 298 299 300
	ATF_REQUIRE_EQ(walked, 0);

	isc_ht_destroy(&ht);
	ATF_REQUIRE_EQ(ht, NULL);
}

ATF_TC(isc_ht_20);
ATF_TC_HEAD(isc_ht_20, tc) {
Evan Hunt's avatar
Evan Hunt committed
301
	atf_tc_set_md_var(tc, "descr", "20 bit, 200K elements test");
302 303 304 305
}

ATF_TC_BODY(isc_ht_20, tc) {
	UNUSED(tc);
Evan Hunt's avatar
Evan Hunt committed
306
	test_ht_full(20, 200000);
307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329
}


ATF_TC(isc_ht_8);
ATF_TC_HEAD(isc_ht_8, tc) {
	atf_tc_set_md_var(tc, "descr", "8 bit, 20000 elements crowded test");
}

ATF_TC_BODY(isc_ht_8, tc) {
	UNUSED(tc);
	test_ht_full(8, 20000);
}

ATF_TC(isc_ht_1);
ATF_TC_HEAD(isc_ht_1, tc) {
	atf_tc_set_md_var(tc, "descr", "1 bit, 100 elements corner case test");
}

ATF_TC_BODY(isc_ht_1, tc) {
	UNUSED(tc);
	test_ht_full(1, 100);
}

330 331
/* xxxwpk we should limit the size of hashtable, 32bit doesn't make sense */
#if 0
332 333 334 335 336 337 338 339 340
ATF_TC(isc_ht_32);
ATF_TC_HEAD(isc_ht_32, tc) {
	atf_tc_set_md_var(tc, "descr", "32 bit, 10000 elements corner case test");
}

ATF_TC_BODY(isc_ht_32, tc) {
	UNUSED(tc);
	test_ht_full(32, 10000);
}
341
#endif
342

343 344 345
ATF_TC(isc_ht_iterator);
ATF_TC_HEAD(isc_ht_iterator, tc) {
	atf_tc_set_md_var(tc, "descr", "hashtable iterator");
346 347
}

348
ATF_TC_BODY(isc_ht_iterator, tc) {
349
	UNUSED(tc);
350
	test_ht_iterator();
351 352 353 354 355 356 357 358 359
}

/*
 * Main
 */
ATF_TP_ADD_TCS(tp) {
	ATF_TP_ADD_TC(tp, isc_ht_20);
	ATF_TP_ADD_TC(tp, isc_ht_8);
	ATF_TP_ADD_TC(tp, isc_ht_1);
360
/*	ATF_TP_ADD_TC(tp, isc_ht_32); */
361
	ATF_TP_ADD_TC(tp, isc_ht_iterator);
362 363
	return (atf_no_error());
}