hhash.c 4.62 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
/*  Copyright (C) 2013 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <string.h>
#include <assert.h>
#include <tap/basic.h>

21 22 23
#include "libknot/internal/hhash.h"
#include "libknot/internal/mempattern.h"
#include "libknot/internal/mempool.h"
24
#include "libknot/internal/macros.h"
25
#include "libknot/libknot.h"
26 27 28

/* Test defines. */
#define ELEM_COUNT 65535
29
#define KEY_LEN(x) (strlen(x)+1)
30 31 32 33 34 35

/* Random key string generator for tests. */
static const char *alphabet = "0123abcdABCDwxyzWXYZ.-_";
char *test_randstr_mm(struct mm_ctx *mm)
{
	unsigned len = (5 + rand() % 251) + 1;
36
	char *s = mm_alloc(mm, len * sizeof(char));
37 38 39 40 41 42 43 44 45 46 47 48 49 50
	for (unsigned i = 0; i < len - 1; ++i) {
		s[i] = alphabet[rand() % strlen(alphabet)];
	}
	s[len - 1] = '\0';
	return s;
}

/*! \brief Return true if 'cur' comes after 'prev'. */
static bool str_check_sort(const char *prev, const char *cur)
{
	if (prev == NULL) {
		return true;
	}

51 52
	int l1 = strlen(prev);
	int l2 = strlen(cur);
53
	int res = memcmp(prev, cur, MIN(l1, l2));
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
	if (res == 0) { /* Keys may be equal. */
		if (l1 > l2) { /* 'prev' is longer, breaks ordering. */
			return false;
		}
	} else if (res > 0){
		return false; /* Broken lexicographical order */
	}

	return true;
}

int main(int argc, char *argv[])
{
	plan(11);

	/* Create memory pool context. */
	struct mempool *pool = mp_new(64 * 1024);
71
	mm_ctx_t mm;
72
	mm.ctx = pool;
73
	mm.alloc = (mm_alloc_t)mp_alloc;
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
	mm.free = NULL;

	/* Create hashtable */
	int ret = KNOT_EOK;
	uint16_t len = 0;
	const char *key = "mykey", *cur = NULL, *prev = NULL;
	value_t val = (void*)0xdeadbeef, *rval = NULL;
	hhash_iter_t it;
	hhash_t *tbl = hhash_create_mm(ELEM_COUNT, &mm);
	ok(tbl != NULL, "hhash: create");
	if (tbl == NULL) {
		return KNOT_ERROR; /* No point in testing further on. */
	}

	/* Generate random keys. */
	char *keys[ELEM_COUNT];
	unsigned nfilled = 0;
	for (unsigned i = 0; i < ELEM_COUNT; ++i) {
		keys[i] = test_randstr_mm(&mm);
	}

	/* Insert single element. */
96
	ret = hhash_insert(tbl, key, KEY_LEN(key), val);
97 98 99 100
	ok(ret == KNOT_EOK, "hhash: insert single element");

	/* Retrieve nonexistent element. */
	cur = "nokey";
101
	rval = hhash_find(tbl, cur, KEY_LEN(cur));
102 103 104
	ok(rval == NULL, "hhash: find non-existent element");

	/* Retrieve single element. */
105
	rval = hhash_find(tbl, key, KEY_LEN(key));
106 107 108 109
	ok(rval != NULL, "hhash: find existing element");

	/* Fill the table. */
	for (unsigned i = 0; i < ELEM_COUNT; ++i) {
110
		ret = hhash_insert(tbl, keys[i], KEY_LEN(keys[i]), keys[i]);
111 112 113 114 115 116 117 118 119
		if (ret != KNOT_EOK) {
			nfilled = i;
			break;
		}
	}

	/* Check all keys integrity. */
	unsigned nfound = 0;
	for (unsigned i = 0; i < nfilled; ++i) {
120 121
		rval = hhash_find(tbl, keys[i], KEY_LEN(keys[i]));
		if (!rval || memcmp(*rval, keys[i], KEY_LEN(keys[i])) != 0) {
122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
			break; /* Mismatch */
		}
		++nfound;
	}
	is_int(nfilled, nfound, "hhash: found all inserted keys");

	/* Test keys order index. */
	hhash_build_index(tbl);
	hhash_iter_begin(tbl, &it, true);
	while (!hhash_iter_finished(&it)) {
		cur = hhash_iter_key(&it, &len);
		if (!str_check_sort(prev, cur)) {
			break;
		}
		prev = cur;
137 138
		int strl = strlen(cur);
		assert(strl + 1 == len);
139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
		hhash_iter_next(&it);
	}
	ok(hhash_iter_finished(&it), "hhash: passed order index checks");

	/* Retrieve all keys. */
	nfound = 0;
	hhash_iter_begin(tbl, &it, false);
	while (!hhash_iter_finished(&it)) {
		cur = hhash_iter_key(&it, &len);
		if (hhash_find(tbl, cur, len) == NULL) {
			break;
		} else {
			++nfound;
		}
		hhash_iter_next(&it);
	}
	ok(hhash_iter_finished(&it), "hhash: found all iterated keys");
	is_int(tbl->weight, nfound, "hhash: all iterated keys found");

	/* Test find less or equal. */
	prev = "mykey0"; /* mykey should precede it */
160
	hhash_find_leq(tbl, prev, KEY_LEN(prev), &rval);
161 162 163
	ok(rval && *rval == val, "hhash: find less or equal");

	/* Delete key and retrieve it. */
164
	ret = hhash_del(tbl, key, KEY_LEN(key));
165
	ok(ret == KNOT_EOK, "hhash: remove key");
166
	rval = hhash_find(tbl, key, KEY_LEN(key));
167 168 169 170 171 172
	ok(rval == NULL, "hhash: find removed element");

	/* Free all memory. */
	mp_delete(mm.ctx);
	return KNOT_EOK;
}