1/*-------------------------------------------------------------------------
2 * drawElements Memory Pool Library
3 * --------------------------------
4 *
5 * Copyright 2014 The Android Open Source Project
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 *      http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 *
19 *//*!
20 * \file
21 * \brief Memory pool hash-set class.
22 *//*--------------------------------------------------------------------*/
23
24#include "dePoolHashSet.h"
25
26#include <string.h>
27
28DE_DECLARE_POOL_HASH_SET(deTestHashSet, deInt16, int);
29DE_IMPLEMENT_POOL_HASH_SET(deTestHashSet, deInt16, int, deInt16Hash, deInt16Equal, deInt32Hash, deInt32Equal);
30
31void dePoolHashSet_selfTest (void)
32{
33	deMemPool*		pool	= deMemPool_createRoot(DE_NULL, 0);
34	deTestHashSet*	hashSet	= deTestHashSet_create(pool);
35	int				i;
36
37	/* Insert a bunch of values. */
38	DE_TEST_ASSERT(deTestHashSet_getNumElements(hashSet) == 0);
39	for (i = 0; i < 20; i++)
40	{
41		int j;
42		for (j = 0; j < i; j++)
43			deTestHashSet_insert(hashSet, (deInt16)i, 2*j + 5);
44	}
45	DE_TEST_ASSERT(deTestHashSet_getNumElements(hashSet) == 19);
46
47	/* delete(). */
48	for (i = 0; i < 20; i++)
49	{
50		int j;
51		for (j = 0; j < i; j += 2)
52			deTestHashSet_delete(hashSet, (deInt16)i, 2*j + 5);
53	}
54	DE_TEST_ASSERT(deTestHashSet_getNumElements(hashSet) == 19);
55
56#if 0
57	/* Test find() on empty hash. */
58	DE_TEST_ASSERT(deTestHash_getNumElements(hashSet) == 0);
59	for (i = 0; i < 15000; i++)
60	{
61		const int* val = deTestHash_find(hash, (deInt16)i);
62		DE_TEST_ASSERT(!val);
63	}
64
65	/* Test insert(). */
66	for (i = 0; i < 5000; i++)
67	{
68		deTestHash_insert(hash, (deInt16)i, -i);
69	}
70
71	DE_TEST_ASSERT(deTestHash_getNumElements(hash) == 5000);
72	for (i = 0; i < 5000; i++)
73	{
74		const int* val = deTestHash_find(hash, (deInt16)i);
75		DE_TEST_ASSERT(val && (*val == -i));
76	}
77
78	/* Test delete(). */
79	for (i = 0; i < 1000; i++)
80		deTestHash_delete(hash, (deInt16)i);
81
82	DE_TEST_ASSERT(deTestHash_getNumElements(hash) == 4000);
83	for (i = 0; i < 25000; i++)
84	{
85		const int* val = deTestHash_find(hash, (deInt16)i);
86		if (deInBounds32(i, 1000, 5000))
87			DE_TEST_ASSERT(val && (*val == -i));
88		else
89			DE_TEST_ASSERT(!val);
90	}
91
92	/* Test insert() after delete(). */
93	for (i = 10000; i < 12000; i++)
94		deTestHash_insert(hash, (deInt16)i, -i);
95
96	for (i = 0; i < 25000; i++)
97	{
98		const int* val = deTestHash_find(hash, (deInt16)i);
99		if (deInBounds32(i, 1000, 5000) || deInBounds32(i, 10000, 12000))
100			DE_TEST_ASSERT(val && (*val == -i));
101		else
102			DE_TEST_ASSERT(!val);
103	}
104
105	/* Test iterator. */
106	{
107		deTestHashIter	iter;
108		int				numFound = 0;
109
110		for (deTestHashIter_init(hash, &iter); deTestHashIter_hasItem(&iter); deTestHashIter_next(&iter))
111		{
112			deInt16	key	= deTestHashIter_getKey(&iter);
113			int		val	= deTestHashIter_getValue(&iter);
114			DE_TEST_ASSERT(deInBounds32(key, 1000, 5000) || deInBounds32(key, 10000, 12000));
115			DE_TEST_ASSERT(*deTestHash_find(hash, key) == -key);
116			DE_TEST_ASSERT(val == -key);
117			numFound++;
118		}
119
120		DE_TEST_ASSERT(numFound == deTestHash_getNumElements(hash));
121	}
122
123	/* Test copy-to-array. */
124	{
125		deTestInt16Array*	keyArray	= deTestInt16Array_create(pool);
126		deTestIntArray*		valueArray	= deTestIntArray_create(pool);
127		int					numElements	= deTestHash_getNumElements(hash);
128		int					ndx;
129
130		deTestHash_copyToArray(hash, keyArray, DE_NULL);
131		DE_TEST_ASSERT(deTestInt16Array_getNumElements(keyArray) == numElements);
132
133		deTestHash_copyToArray(hash, DE_NULL, valueArray);
134		DE_TEST_ASSERT(deTestIntArray_getNumElements(valueArray) == numElements);
135
136		deTestInt16Array_setSize(keyArray, 0);
137		deTestIntArray_setSize(valueArray, 0);
138		deTestHash_copyToArray(hash, keyArray, valueArray);
139		DE_TEST_ASSERT(deTestInt16Array_getNumElements(keyArray) == numElements);
140		DE_TEST_ASSERT(deTestIntArray_getNumElements(valueArray) == numElements);
141
142		for (ndx = 0; ndx < numElements; ndx++)
143		{
144			deInt16 key = deTestInt16Array_get(keyArray, ndx);
145			int		val = deTestIntArray_get(valueArray, ndx);
146
147			DE_TEST_ASSERT(val == -key);
148			DE_TEST_ASSERT(*deTestHash_find(hash, key) == val);
149		}
150	}
151#endif
152
153	deMemPool_destroy(pool);
154}
155