pd.if.org Git - nbds/blob - 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 }