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 "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 }