1 /*****************************************************************
2 |
3 | Maps Test Program 1
4 |
5 | (c) 2005-2006 Gilles Boccon-Gibod
6 | Author: Gilles Boccon-Gibod (bok@bok.net)
7 |
8 ****************************************************************/
9
10 /*----------------------------------------------------------------------
11 | includes
12 +---------------------------------------------------------------------*/
13 #include <stdlib.h>
14 #include <stdio.h>
15 #include <string.h>
16 #include "Neptune.h"
17 #include "NptDebug.h"
18
19 /*----------------------------------------------------------------------
20 | globals
21 +---------------------------------------------------------------------*/
22 static unsigned int A_Count = 0;
23
24 /*----------------------------------------------------------------------
25 | types
26 +---------------------------------------------------------------------*/
27 class A {
28 public:
A()29 A() : _a(0), _b(0), _c(&_a) {
30 A_Count++;
31 }
A(int a,char b)32 A(int a, char b) : _a(a), _b(b), _c(&_a) {
33 A_Count++;
34 }
A(const A & other)35 A(const A& other) : _a(other._a), _b(other._b), _c(&_a) {
36 A_Count++;
37 }
~A()38 ~A() {
39 A_Count--;
40 }
Check()41 bool Check() { return _c == &_a; }
operator ==(const A & other) const42 bool operator==(const A& other) const {
43 return _a == other._a && _b == other._b;
44 }
45 int _a;
46 char _b;
47 int* _c;
48 };
49
50 #define CHECK(x) { \
51 if (!(x)) { \
52 printf("TEST FAILED line %d\n", __LINE__); \
53 return 1; \
54 } \
55 }
56
57 /*----------------------------------------------------------------------
58 | TestPerformance
59 +---------------------------------------------------------------------*/
60 static void
TestPerformance()61 TestPerformance()
62 {
63 for (unsigned int i=1; i<10000; i += 1000) {
64 NPT_TimeStamp before;
65 NPT_System::GetCurrentTimeStamp(before);
66 for (unsigned int j=0; j<10; j++) {
67 NPT_Map<NPT_String, NPT_String> map;
68 for (unsigned int k=0; k<i; k++) {
69 char key[64] = "blablabliblibloublou";
70 unsigned int run = NPT_System::GetRandomInteger()%8;
71 for (unsigned int x=0; x<run; x++) {
72 key[x] = 'A'+NPT_System::GetRandomInteger()%32;
73 }
74 map[key] = "hello";
75 }
76 }
77 NPT_TimeStamp after;
78 NPT_System::GetCurrentTimeStamp(after);
79 NPT_UInt64 duration = (after.ToNanos()-before.ToNanos())/10;
80 printf("LinearMap insert: %d\t%d ns\t\t%d ns/item\n", i, (NPT_UInt32)duration, (NPT_UInt32)(duration/i));
81 }
82
83 for (unsigned int i=1; i<10000; i += 1000) {
84 NPT_TimeStamp before;
85 NPT_System::GetCurrentTimeStamp(before);
86 for (unsigned int j=0; j<100; j++) {
87 NPT_HashMap<NPT_String, NPT_String> map;
88 for (unsigned int k=0; k<i; k++) {
89 char key[64] = "blablabliblibloublou";
90 unsigned int run = NPT_System::GetRandomInteger()%8;
91 for (unsigned int x=0; x<run; x++) {
92 key[x] = 'A'+NPT_System::GetRandomInteger()%32;
93 }
94 map[key] = "hello";
95 }
96 }
97 NPT_TimeStamp after;
98 NPT_System::GetCurrentTimeStamp(after);
99 NPT_UInt64 duration = (after.ToNanos()-before.ToNanos())/100;
100 printf("HashMap insert: %d\t%d ns\t\t%d ns/item\n", i, (NPT_UInt32)duration, (NPT_UInt32)(duration/i));
101 }
102
103 for (unsigned int i=1; i<10000; i += 1000) {
104 NPT_TimeStamp before;
105 NPT_System::GetCurrentTimeStamp(before);
106 for (unsigned int j=0; j<100; j++) {
107 NPT_HashMap<NPT_String, NPT_String> map;
108 for (unsigned int k=0; k<i; k++) {
109 char key[64] = "blablabliblibloublou";
110 unsigned int run = NPT_System::GetRandomInteger()%8;
111 for (unsigned int x=0; x<run; x++) {
112 key[x] = 'A'+NPT_System::GetRandomInteger()%32;
113 }
114 map[key] = "hello";
115 }
116 for (unsigned int k=0; k<i; k++) {
117 char key[64] = "blablabliblibloublou";
118 unsigned int run = NPT_System::GetRandomInteger()%8;
119 for (unsigned int x=0; x<run; x++) {
120 key[x] = 'A'+NPT_System::GetRandomInteger()%32;
121 }
122 map.Erase(key);
123 }
124 }
125 NPT_TimeStamp after;
126 NPT_System::GetCurrentTimeStamp(after);
127 NPT_UInt64 duration = (after.ToNanos()-before.ToNanos())/100;
128 printf("HashMap insert+erase: %d\t%d ns\t\t%d ns/item\n", i, (NPT_UInt32)duration, (NPT_UInt32)(duration/i));
129 }
130 }
131
132 /*----------------------------------------------------------------------
133 | TestMap
134 +---------------------------------------------------------------------*/
135 static int
TestMap()136 TestMap()
137 {
138 NPT_Map<NPT_String,A> a_map;
139 A* a = NULL;
140
141 CHECK(a_map.GetEntryCount() == 0);
142 CHECK(a_map.HasKey("hello") == false);
143 CHECK(!a_map.HasValue(A(1,2)));
144 CHECK(NPT_FAILED(a_map.Get("bla", a)));
145 CHECK(a == NULL);
146
147 a_map.Put("hello", A(1,2));
148 CHECK(a_map.GetEntryCount() == 1);
149 CHECK(NPT_SUCCEEDED(a_map.Get("hello", a)));
150 CHECK(*a == A(1,2));
151 CHECK(a_map.HasKey("hello"));
152 CHECK(a_map.HasValue(A(1,2)));
153 CHECK(a_map["hello"] == A(1,2));
154
155 CHECK(a_map["bla"] == A());
156 CHECK(a_map.GetEntryCount() == 2);
157 a_map["bla"] = A(3,4);
158 CHECK(a_map["bla"] == A(3,4));
159 CHECK(a_map.GetEntryCount() == 2);
160
161 NPT_Map<NPT_String,A> b_map;
162 b_map["hello"] = A(1,2);
163 b_map["bla"] = A(3,4);
164 CHECK(a_map == b_map);
165
166 NPT_Map<NPT_String,A> c_map = a_map;
167 CHECK(c_map["hello"] == a_map["hello"]);
168 CHECK(c_map["bla"] == a_map["bla"]);
169
170 CHECK(NPT_SUCCEEDED(a_map.Put("bla", A(5,6))));
171 CHECK(NPT_SUCCEEDED(a_map.Get("bla", a)));
172 CHECK(*a == A(5,6));
173 CHECK(NPT_FAILED(a_map.Get("youyou", a)));
174
175 b_map.Clear();
176 CHECK(b_map.GetEntryCount() == 0);
177
178 a_map["youyou"] = A(6,7);
179 CHECK(NPT_FAILED(a_map.Erase("coucou")));
180 CHECK(NPT_SUCCEEDED(a_map.Erase("bla")));
181 CHECK(!a_map.HasKey("bla"));
182
183 CHECK(!(a_map == c_map));
184 CHECK(c_map != a_map);
185
186 c_map = a_map;
187 NPT_Map<NPT_String,A> d_map(c_map);
188 CHECK(d_map == c_map);
189
190 NPT_Map<int,int> i_map;
191 i_map[5] = 6;
192 i_map[6] = 7;
193 i_map[9] = 0;
194 CHECK(i_map[0] == 0 || i_map[0] != 0); // unknown value (will cause a valgrind warning)
195 CHECK(i_map.GetEntryCount() == 4);
196
197 NPT_Map<NPT_String,A> a1_map;
198 NPT_Map<NPT_String,A> a2_map;
199 a1_map["hello"] = A(1,2);
200 a1_map["bla"] = A(2,3);
201 a1_map["youyou"]= A(3,4);
202 a2_map["bla"] = A(2,3);
203 a2_map["youyou"]= A(3,4);
204 a2_map["hello"] = A(1,2);
205 CHECK(a1_map == a2_map);
206 a1_map["foo"] = A(0,0);
207 CHECK(a1_map != a2_map);
208 a2_map["foo"] = A(0,0);
209 CHECK(a1_map == a2_map);
210 a2_map["foo"] = A(7,8);
211 CHECK(a1_map != a2_map);
212 a2_map["foo"] = A(0,0);
213 a1_map["bir"] = A(0,0);
214 a2_map["bar"] = A(0,0);
215 CHECK(a1_map.GetEntryCount() == a2_map.GetEntryCount());
216 CHECK(a1_map != a2_map);
217 CHECK(!(a1_map == a2_map));
218
219 NPT_Map<NPT_String, NPT_String*> p_map;
220 p_map["1"] = new NPT_String("hello");
221 p_map["2"] = new NPT_String("good bye");
222 p_map.GetEntries().Apply(NPT_MapEntryValueDeleter<NPT_Map<NPT_String, NPT_String*>::Entry>());
223
224 return 0;
225 }
226
227 struct Hasher {
operator ()Hasher228 NPT_UInt32 operator()(const NPT_String& /*key*/) const { return 0; }
229 };
230
231 /*----------------------------------------------------------------------
232 | TestHashMap
233 +---------------------------------------------------------------------*/
234 static int
TestHashMap()235 TestHashMap()
236 {
237 NPT_HashMap<NPT_String,A> a_map;
238 A* a = NULL;
239
240 CHECK(a_map.GetEntryCount() == 0);
241 CHECK(a_map.HasKey("hello") == false);
242 CHECK(!a_map.HasValue(A(1,2)));
243 CHECK(NPT_FAILED(a_map.Get("bla", a)));
244 CHECK(a == NULL);
245
246 a_map.Put("hello", A(1,2));
247 CHECK(a_map.GetEntryCount() == 1);
248 CHECK(NPT_SUCCEEDED(a_map.Get("hello", a)));
249 CHECK(*a == A(1,2));
250 CHECK(a_map.HasKey("hello"));
251 CHECK(a_map.HasValue(A(1,2)));
252 CHECK(a_map["hello"] == A(1,2));
253
254 CHECK(a_map["bla"] == A());
255 CHECK(a_map.GetEntryCount() == 2);
256 a_map["bla"] = A(3,4);
257 CHECK(a_map["bla"] == A(3,4));
258 CHECK(a_map.GetEntryCount() == 2);
259
260 NPT_HashMap<NPT_String,A> b_map;
261 b_map["hello"] = A(1,2);
262 b_map["bla"] = A(3,4);
263 CHECK(a_map == b_map);
264
265 NPT_HashMap<NPT_String,A> c_map = a_map;
266 CHECK(c_map["hello"] == a_map["hello"]);
267 CHECK(c_map["bla"] == a_map["bla"]);
268
269 CHECK(NPT_SUCCEEDED(a_map.Put("bla", A(5,6))));
270 CHECK(NPT_SUCCEEDED(a_map.Get("bla", a)));
271 CHECK(*a == A(5,6));
272 CHECK(NPT_FAILED(a_map.Get("youyou", a)));
273
274 b_map.Clear();
275 CHECK(b_map.GetEntryCount() == 0);
276
277 a_map["youyou"] = A(6,7);
278 CHECK(NPT_FAILED(a_map.Erase("coucou")));
279 CHECK(NPT_SUCCEEDED(a_map.Erase("bla")));
280 CHECK(!a_map.HasKey("bla"));
281
282 CHECK(!(a_map == c_map));
283 CHECK(c_map != a_map);
284
285 c_map = a_map;
286 NPT_HashMap<NPT_String,A> d_map(c_map);
287 CHECK(d_map == c_map);
288
289 NPT_HashMap<int,int> i_map;
290 i_map[5] = 6;
291 i_map[6] = 7;
292 i_map[9] = 0;
293 CHECK(i_map[0] == 0 || i_map[0] != 0); // unknown value (will cause a valgrind warning)
294 CHECK(i_map.GetEntryCount() == 4);
295
296 NPT_HashMap<NPT_String,A> a1_map;
297 NPT_HashMap<NPT_String,A> a2_map;
298 a1_map["hello"] = A(1,2);
299 a1_map["bla"] = A(2,3);
300 a1_map["youyou"]= A(3,4);
301 a2_map["bla"] = A(2,3);
302 a2_map["youyou"]= A(3,4);
303 a2_map["hello"] = A(1,2);
304 CHECK(a1_map == a2_map);
305 a1_map["foo"] = A(0,0);
306 CHECK(a1_map != a2_map);
307 a2_map["foo"] = A(0,0);
308 CHECK(a1_map == a2_map);
309 a2_map["foo"] = A(7,8);
310 CHECK(a1_map != a2_map);
311 a2_map["foo"] = A(0,0);
312 a1_map["bir"] = A(0,0);
313 a2_map["bar"] = A(0,0);
314 CHECK(a1_map.GetEntryCount() == a2_map.GetEntryCount());
315 CHECK(a1_map != a2_map);
316 CHECK(!(a1_map == a2_map));
317
318 NPT_HashMap<NPT_String, NPT_String> smap;
319 for (unsigned int i=0; i<24; i++) {
320 NPT_String s = NPT_String::Format("blabla%d", i);
321 smap[s] = "1234";
322 CHECK(smap[s] == "1234");
323 }
324 for (unsigned int i=0; i<24; i++) {
325 NPT_String s = NPT_String::Format("blabla%d", i);
326 CHECK(smap[s] == "1234");
327 }
328 for (unsigned int i=0; i<24; i++) {
329 NPT_String s = NPT_String::Format("blabla%d", i);
330 CHECK(NPT_SUCCEEDED(smap.Erase(s)));
331 CHECK(!smap.HasKey(s));
332 }
333 CHECK(smap.GetEntryCount() == 0);
334
335 Hasher hasher;
336 NPT_HashMap<NPT_String, int, Hasher> zmap(hasher);
337 for (unsigned int i=0; i<1024; i++) {
338 NPT_String s = NPT_String::Format("blabla%d", i);
339 zmap[s] = 1234;
340 CHECK(zmap[s] == 1234);
341 }
342 for (unsigned int i=0; i<1024; i++) {
343 NPT_String s = NPT_String::Format("blabla%d", i);
344 CHECK(zmap[s] == 1234);
345 }
346 for (unsigned int i=0; i<1024; i++) {
347 NPT_String s = NPT_String::Format("blabla%d", i);
348 CHECK(NPT_SUCCEEDED(zmap.Erase(s)));
349 CHECK(!zmap.HasKey(s));
350 }
351 CHECK(zmap.GetEntryCount() == 0);
352
353 NPT_HashMap<NPT_String, int> imap;
354 for (int i=0; i<1024; i++) {
355 NPT_String s = NPT_String::Format("blabla%d", i);
356 imap[s] = i;
357 CHECK(imap[s] == i);
358 }
359 unsigned int zz = 1024;
360 for (NPT_HashMap<NPT_String, int>::Iterator it = imap.GetEntries();
361 it;
362 ++it) {
363 CHECK(imap.HasKey((*it).GetKey()));
364 CHECK(imap.HasValue((*it).GetValue()));
365 --zz;
366 }
367 CHECK(zz==0);
368
369 NPT_HashMap<NPT_String, NPT_String*> p_map;
370 p_map["1"] = new NPT_String("hello");
371 p_map["2"] = new NPT_String("good bye");
372 p_map.Apply(NPT_MapEntryValueDeleter<NPT_HashMap<NPT_String, NPT_String*>::Entry>());
373
374 return 0;
375 }
376
377 /*----------------------------------------------------------------------
378 | main
379 +---------------------------------------------------------------------*/
380 int
main(int,char **)381 main(int /*argc*/, char** /*argv*/)
382 {
383
384 int result;
385
386 result = TestMap();
387 if (result) return result;
388
389 result = TestHashMap();
390 if (result) return result;
391
392 TestPerformance();
393
394 return 0;
395 }
396