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