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
28 DE_DECLARE_POOL_HASH_SET(deTestHashSet, deInt16, int);
29 DE_IMPLEMENT_POOL_HASH_SET(deTestHashSet, deInt16, int, deInt16Hash, deInt16Equal, deInt32Hash, deInt32Equal);
30
dePoolHashSet_selfTest(void)31 void 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