generic map iterator interface
[nbds] / test / map_test2.c
1 /* 
2  * Written by Josh Dybnis and released to the public domain, as explained at
3  * http://creativecommons.org/licenses/publicdomain
4  */
5 #include <stdio.h>
6 #include <pthread.h>
7 #include <sys/time.h>
8
9 #include "CuTest.h"
10
11 #include "common.h"
12 #include "runtime.h"
13 #include "nstring.h"
14 #include "map.h"
15 #include "list.h"
16 #include "skiplist.h"
17 #include "hashtable.h"
18 #include "lwt.h"
19
20 #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
21
22 //#define TEST_STRING_KEYS
23
24 typedef struct worker_data {
25     int id;
26     CuTest *tc;
27     map_t *map;
28     volatile int *wait;
29 } worker_data_t;
30
31 static const map_impl_t *map_type_;
32
33 static uint64_t iterator_size (map_t *map) {
34     map_iter_t *iter = map_iter_begin(map, NULL);
35     uint64_t count = 0;
36     while (map_iter_next(iter, NULL) != DOES_NOT_EXIST) {
37         count++;
38     }
39     map_iter_free(iter);
40     return count;
41 }
42
43 // Test some basic stuff; add a few keys, remove a few keys
44 void basic_test (CuTest* tc) {
45
46 #ifdef TEST_STRING_KEYS
47     map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
48     nstring_t *k1 = ns_alloc(3); strcpy(k1->data, "k1");
49     nstring_t *k2 = ns_alloc(3); strcpy(k1->data, "k2");
50     nstring_t *k3 = ns_alloc(3); strcpy(k1->data, "k3");
51     nstring_t *k4 = ns_alloc(3); strcpy(k1->data, "k4");
52 #else
53     map_t *map = map_alloc(map_type_, NULL);
54     void *k1 = (void *)1;
55     void *k2 = (void *)2;
56     void *k3 = (void *)3;
57     void *k4 = (void *)4;
58 #endif
59
60     ASSERT_EQUAL( 0,              map_count  (map)        );
61     ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k1,10) );
62     ASSERT_EQUAL( 1,              map_count  (map)        );
63     ASSERT_EQUAL( 1,              iterator_size(map)      );
64     ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k2,20) );
65     ASSERT_EQUAL( 2,              map_count  (map)        );
66     ASSERT_EQUAL( 2,              iterator_size(map)      );
67     ASSERT_EQUAL( 20,             map_get    (map, k2)    );
68     ASSERT_EQUAL( 10,             map_set    (map, k1,11) );
69     ASSERT_EQUAL( 20,             map_set    (map, k2,21) );
70     ASSERT_EQUAL( 2,              map_count  (map)        );
71     ASSERT_EQUAL( 2,              iterator_size(map)      );
72     ASSERT_EQUAL( 21,             map_add    (map, k2,22) );
73     ASSERT_EQUAL( 11,             map_remove (map, k1)    );
74     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k1)    );
75     ASSERT_EQUAL( 1,              map_count  (map)        );
76     ASSERT_EQUAL( 1,              iterator_size(map)      );
77     ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k1)    );
78     ASSERT_EQUAL( 21,             map_remove (map, k2)    );
79     ASSERT_EQUAL( 0,              map_count  (map)        );
80     ASSERT_EQUAL( 0,              iterator_size(map)      );
81     ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k2)    );
82     ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k3)    );
83     ASSERT_EQUAL( 0,              map_count  (map)        );
84     ASSERT_EQUAL( 0,              iterator_size(map)      );
85     
86     ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k4,40) );
87     ASSERT_EQUAL( 40,             map_get    (map, k4)    );
88     ASSERT_EQUAL( 1,              map_count  (map)        );
89     ASSERT_EQUAL( 1,              iterator_size(map)      );
90     ASSERT_EQUAL( 40,             map_remove (map, k4)    );
91     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k4)    );
92     ASSERT_EQUAL( 0,              map_count  (map)        );
93     ASSERT_EQUAL( 0,              iterator_size(map)      );
94
95     ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, k4,10) );
96     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k4)    );
97     ASSERT_EQUAL( DOES_NOT_EXIST, map_set    (map, k4,40) );
98     ASSERT_EQUAL( 40,             map_replace(map, k4,41) );
99     ASSERT_EQUAL( 41,             map_get    (map, k4)    );
100     ASSERT_EQUAL( 41,             map_remove (map, k4)    );
101     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k4)    );
102     ASSERT_EQUAL( 0,              map_count  (map)        );
103     ASSERT_EQUAL( 0,              iterator_size(map)      );
104
105     ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, k2,20) );
106     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k2)    );
107
108     // In the end, all entries should be removed
109     ASSERT_EQUAL( DOES_NOT_EXIST, map_set    (map, k2,20) );
110     ASSERT_EQUAL( 20,             map_replace(map, k2,21) );
111     ASSERT_EQUAL( 21,             map_get    (map, k2)    );
112     ASSERT_EQUAL( 21,             map_remove (map, k2)    );
113     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k2)    );
114     ASSERT_EQUAL( 0,              map_count  (map)        );
115     ASSERT_EQUAL( 0,              iterator_size(map)      );
116
117     map_free(map);
118
119     rcu_update(); // In a quiecent state.
120 #ifdef TEST_STRING_KEYS
121     nbd_free(k1); nbd_free(k2); nbd_free(k3); nbd_free(k4);
122 #endif
123 }
124
125 void *add_remove_worker (void *arg) {
126     worker_data_t *wd = (worker_data_t *)arg;
127     map_t *map = wd->map;
128     CuTest* tc = wd->tc;
129     uint64_t d = wd->id;
130     int iters = 10000;
131
132     SYNC_ADD(wd->wait, -1);
133     do { } while (*wd->wait); // wait for all workers to be ready
134
135 #ifdef TEST_STRING_KEYS
136     nstring_t *key = ns_alloc(9);
137 #else
138     void *key;
139 #endif
140
141     for (int j = 0; j < 10; ++j) {
142         for (uint64_t i = d+1; i < iters; i+=2) {
143 #ifdef TEST_STRING_KEYS
144             memset(key->data, 0, key->len);
145             snprintf(key->data, key->len, "%llu", i);
146 #else
147             key = (void *)i;
148 #endif
149             TRACE("t0", "test map_add() iteration (%llu, %llu)", j, i);
150             ASSERT_EQUAL(DOES_NOT_EXIST, map_add(map, key, d+1) );
151             rcu_update(); // In a quiecent state.
152         }
153         for (uint64_t i = d+1; i < iters; i+=2) {
154 #ifdef TEST_STRING_KEYS
155             memset(key->data, 0, key->len);
156             snprintf(key->data, key->len, "%llu", i);
157 #else
158             key = (void *)i;
159 #endif
160             TRACE("t0", "test map_remove() iteration (%llu, %llu)", j, i);
161             ASSERT_EQUAL(d+1, map_remove(map, key) );
162             rcu_update(); // In a quiecent state.
163         }
164     }
165     return NULL;
166 }
167
168 // Do some simple concurrent testing
169 void concurrent_add_remove_test (CuTest* tc) {
170
171     pthread_t thread[2];
172     worker_data_t wd[2];
173     volatile int wait = 2;
174 #ifdef TEST_STRING_KEYS
175     map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
176 #else
177     map_t *map = map_alloc(map_type_, NULL);
178 #endif
179
180     struct timeval tv1, tv2;
181     gettimeofday(&tv1, NULL);
182
183     // In 2 threads, add & remove even & odd elements concurrently
184     int i;
185     for (i = 0; i < 2; ++i) {
186         wd[i].id = i;
187         wd[i].tc = tc;
188         wd[i].map = map;
189         wd[i].wait = &wait;
190         int rc = nbd_thread_create(thread + i, i, add_remove_worker, wd + i);
191         if (rc != 0) { perror("nbd_thread_create"); return; }
192     }
193
194     for (i = 0; i < 2; ++i) {
195         pthread_join(thread[i], NULL);
196     }
197
198     gettimeofday(&tv2, NULL);
199     int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
200     map_print(map);
201     printf("Th:%d Time:%dms\n", 2, ms);
202     fflush(stdout);
203
204     // In the end, all members should be removed
205     ASSERT_EQUAL( 0, map_count(map) );
206     ASSERT_EQUAL( 0, iterator_size(map) );
207
208     // In a quiecent state; it is safe to free.
209     map_free(map);
210 }
211
212 void basic_iteration_test (CuTest* tc) {
213 #ifdef TEST_STRING_KEYS
214     map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
215     nstring_t *k1 = ns_alloc(3); strcpy(k1->data, "k1");
216     nstring_t *k2 = ns_alloc(3); strcpy(k1->data, "k2");
217     nstring_t *x_k;
218     nstring_t *y_k;
219 #else
220     map_t *map = map_alloc(map_type_, NULL);
221     void *k1 = (void *)1;
222     void *k2 = (void *)2;
223     void *x_k;
224     void *y_k;
225 #endif
226
227     ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k1,1) );
228     ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k2,2) );
229
230     uint64_t x_v, y_v;
231     map_iter_t *iter = map_iter_begin(map, NULL);
232     x_v = map_iter_next(iter, &x_k);
233     y_v = map_iter_next(iter, &y_k);
234     ASSERT_EQUAL( DOES_NOT_EXIST, map_iter_next(iter, NULL) );
235     map_iter_free(iter);
236 #ifdef TEST_STRING_KEYS
237     ASSERT_EQUAL( TRUE, (ns_cmp(x_k, k1) == 0 && x_v == 1) || (ns_cmp(y_k, k1) == 0 && y_v == 1) );
238     ASSERT_EQUAL( TRUE, (ns_cmp(x_k, k2) == 0 && x_v == 2) || (ns_cmp(y_k, k2) == 0 && y_v == 2) );
239     nbd_free(k1);
240     nbd_free(k2);
241 #else
242     ASSERT_EQUAL( TRUE, (x_k == k1 && x_v == 1) || (y_k == k1 && y_v == 1) );
243     ASSERT_EQUAL( TRUE, (x_k == k2 && x_v == 2) || (y_k == k2 && y_v == 2) );
244 #endif
245
246     map_free(map);
247 }
248
249 void big_iteration_test (CuTest* tc) {
250     static const int n = 10000;
251     
252 #ifdef TEST_STRING_KEYS
253     map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
254     nstring_t *key = ns_alloc(9);
255     nstring_t *k3 = ns_alloc(3); strcpy(k1->data, "k3");
256     nstring_t *k4 = ns_alloc(3); strcpy(k1->data, "k4");
257 #else
258     map_t *map = map_alloc(map_type_, NULL);
259     void *k3 = (void *)3;
260     void *k4 = (void *)4;
261     void *key;
262 #endif
263
264     for (size_t i = 1; i <= n; ++i) {
265 #ifdef TEST_STRING_KEYS
266         memset(key->data, 0, key->len);
267         snprintf(key->data, key->len, "k%llu", i);
268 #else
269         key = (void *)i;
270 #endif
271         ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, key)    );
272         ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map, key, i) );
273         ASSERT_EQUAL( i,              map_get(map, key)    );
274         rcu_update(); // In a quiecent state.
275     }
276
277     ASSERT_EQUAL( n, map_count(map) );
278     ASSERT_EQUAL( n, iterator_size(map) );
279
280     uint64_t sum = 0;
281     uint64_t val;
282     map_iter_t *iter = map_iter_begin(map, NULL);
283     while ((val = map_iter_next(iter, NULL)) != DOES_NOT_EXIST) {
284         sum += val;
285     }
286     map_iter_free(iter);
287     ASSERT_EQUAL(n*(n+1)/2, sum);
288     ASSERT_EQUAL(3, map_remove(map, k3));
289     ASSERT_EQUAL(4, map_remove(map, k4));
290     sum = 0;
291     iter = map_iter_begin(map, NULL);
292     while ((val = map_iter_next(iter, NULL)) != DOES_NOT_EXIST) {
293         sum += val;
294     }
295     map_iter_free(iter);
296     ASSERT_EQUAL(n*(n+1)/2 - (3+4), sum);
297         
298 #ifdef TEST_STRING_KEYS
299     nbd_free(key);
300 #endif
301 }
302
303 int main (void) {
304
305     nbd_init();
306     lwt_set_trace_level("h3");
307
308     static const map_impl_t *map_types[] = { &ll_map_impl, &sl_map_impl, &ht_map_impl };
309     for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) {
310         map_type_ = map_types[i];
311
312         // Create and run test suite
313         CuString *output = CuStringNew();
314         CuSuite* suite = CuSuiteNew();
315
316         SUITE_ADD_TEST(suite, basic_test);
317         SUITE_ADD_TEST(suite, concurrent_add_remove_test);
318         SUITE_ADD_TEST(suite, basic_iteration_test);
319         SUITE_ADD_TEST(suite, big_iteration_test);
320
321         CuSuiteRun(suite);
322         CuSuiteDetails(suite, output);
323         printf("%s\n", output->buffer);
324     }
325
326     return 0;
327 }