all structures now support arbitrary type keys with a fast path for integers
[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 "map.h"
14 #include "lwt.h"
15
16 #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
17
18 typedef struct worker_data {
19     int id;
20     CuTest *tc;
21     map_t *map;
22     volatile int *wait;
23 } worker_data_t;
24
25 static map_type_t map_type_;
26
27 // Test some basic stuff; add a few keys, remove a few keys
28 void simple (CuTest* tc) {
29
30     map_t *map = map_alloc(map_type_, NULL, NULL, NULL);
31
32     ASSERT_EQUAL( 0,              map_count(map)            );
33     ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map, (void *)'a',10)     );
34     ASSERT_EQUAL( 1,              map_count(map)            );
35     ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map, (void *)'b',20)     );
36     ASSERT_EQUAL( 2,              map_count(map)            );
37     ASSERT_EQUAL( 20,             map_get(map, (void *)'b')        );
38     ASSERT_EQUAL( 10,             map_set(map, (void *)'a',11)     );
39     ASSERT_EQUAL( 20,             map_set(map, (void *)'b',21)     );
40     ASSERT_EQUAL( 2,              map_count(map)            );
41     ASSERT_EQUAL( 21,             map_add(map, (void *)'b',22)     );
42     ASSERT_EQUAL( 11,             map_remove(map, (void *)'a')     );
43     ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'a')        );
44     ASSERT_EQUAL( 1,              map_count(map)            );
45     ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map, (void *)'a')     );
46     ASSERT_EQUAL( 21,             map_remove(map, (void *)'b')     );
47     ASSERT_EQUAL( 0,              map_count(map)            );
48     ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map, (void *)'b')     );
49     ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map, (void *)'c')     );
50     ASSERT_EQUAL( 0,              map_count(map)            );
51     
52     ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map, (void *)'d',40)     );
53     ASSERT_EQUAL( 40,             map_get(map, (void *)'d')        );
54     ASSERT_EQUAL( 1,              map_count(map)            );
55     ASSERT_EQUAL( 40,             map_remove(map, (void *)'d')     );
56     ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'d')        );
57     ASSERT_EQUAL( 0,              map_count(map)            );
58
59     ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, (void *)'d',10) );
60     ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'d')        );
61     ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map, (void *)'d',40)     );
62     ASSERT_EQUAL( 40,             map_replace(map, (void *)'d',41) );
63     ASSERT_EQUAL( 41,             map_get(map, (void *)'d')        );
64     ASSERT_EQUAL( 41,             map_remove(map, (void *)'d')     );
65     ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'d')        );
66     ASSERT_EQUAL( 0,              map_count(map)            );
67
68     ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, (void *)'b',20) );
69     ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'b')        );
70
71     // In the end, all entries should be removed
72     ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map, (void *)'b',20)     );
73     ASSERT_EQUAL( 20,             map_replace(map, (void *)'b',21) );
74     ASSERT_EQUAL( 21,             map_get(map, (void *)'b')        );
75     ASSERT_EQUAL( 21,             map_remove(map, (void *)'b')     );
76     ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'b')        );
77     ASSERT_EQUAL( 0,              map_count(map)            );
78
79     map_free(map);
80
81     // In a quiecent state; it is safe to free.
82     rcu_update();
83 }
84
85 void *add_remove_worker (void *arg) {
86     worker_data_t *wd = (worker_data_t *)arg;
87     map_t *map = wd->map;
88     CuTest* tc = wd->tc;
89     uint64_t d = wd->id;
90     int iters = (map_type_ == MAP_TYPE_LIST) ? 5000 : 500000;
91
92     SYNC_ADD(wd->wait, -1);
93     do { } while (*wd->wait); // wait for all workers to be ready
94
95     for (int j = 0; j < 10; ++j) {
96         for (uint64_t i = d+1; i < iters; i+=2) {
97             TRACE("t0", "test map_add() iteration (%llu, %llu)", j, i);
98             CuAssertIntEquals_Msg(tc, (void *)i, DOES_NOT_EXIST, map_add(map, (void *)i, d+1) );
99             rcu_update();
100         }
101         for (uint64_t i = d+1; i < iters; i+=2) {
102             TRACE("t0", "test map_remove() iteration (%llu, %llu)", j, i);
103             CuAssertIntEquals_Msg(tc, (void *)i, d+1, map_remove(map, (void *)i) );
104             rcu_update();
105         }
106     }
107     return NULL;
108 }
109
110 // Do some simple concurrent testing
111 void add_remove (CuTest* tc) {
112
113     pthread_t thread[2];
114     worker_data_t wd[2];
115     volatile int wait = 2;
116     map_t *map = map_alloc(map_type_, NULL, NULL, NULL);
117
118     struct timeval tv1, tv2;
119     gettimeofday(&tv1, NULL);
120
121     // In 2 threads, add & remove even & odd elements concurrently
122     int i;
123     for (i = 0; i < 2; ++i) {
124         wd[i].id = i;
125         wd[i].tc = tc;
126         wd[i].map = map;
127         wd[i].wait = &wait;
128         int rc = nbd_thread_create(thread + i, i, add_remove_worker, wd + i);
129         if (rc != 0) { perror("nbd_thread_create"); return; }
130     }
131
132     for (i = 0; i < 2; ++i) {
133         pthread_join(thread[i], NULL);
134     }
135
136     gettimeofday(&tv2, NULL);
137     int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
138     map_print(map);
139     printf("Th:%d Time:%dms\n", 2, ms);
140     fflush(stdout);
141
142     // In the end, all members should be removed
143     ASSERT_EQUAL( 0, map_count(map) );
144
145     // In a quiecent state; it is safe to free.
146     map_free(map);
147 }
148
149 void *inserter_worker (void *arg) {
150     //pthread_t thread[NUM_THREADS];
151
152     //map_t *map = map_alloc(map_type_);
153     return NULL;
154 }
155
156 // Concurrent insertion
157 void concurrent_insert (CuTest* tc) {
158 }
159
160 int main (void) {
161
162     nbd_init();
163     lwt_set_trace_level("h3");
164
165     map_type_t map_types[] = { MAP_TYPE_LIST, MAP_TYPE_SKIPLIST, MAP_TYPE_HASHTABLE };
166     for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) {
167         map_type_ = map_types[i];
168
169         // Create and run test suite
170         CuString *output = CuStringNew();
171         CuSuite* suite = CuSuiteNew();
172
173         SUITE_ADD_TEST(suite, simple);
174         SUITE_ADD_TEST(suite, add_remove);
175
176         CuSuiteRun(suite);
177         CuSuiteDetails(suite, output);
178         printf("%s\n", output->buffer);
179     }
180
181     return 0;
182 }