pd.if.org Git - nbds/blob - test/ht_test.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 "runtime.h"
   8 #include "CuTest.h"
   9 #include "common.h"
  10 #include "ht.h"
  11 #include "mem.h"
  12 #include "lwt.h"
  13
  14 #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
  15
  16 typedef struct worker_data {
  17     int id;
  18     CuTest *tc;
  19     hash_table_t *ht;
  20     int *wait;
  21 } worker_data_t;
  22
  23 int64_t ht_set (hash_table_t *ht, const char *key, uint32_t key_len, int64_t val) {
  24     return ht_compare_and_set(ht, key, key_len, HT_EXPECT_WHATEVER, val);
  25 }
  26
  27 int64_t ht_add (hash_table_t *ht, const char *key, uint32_t key_len, int64_t val) {
  28     return ht_compare_and_set(ht, key, key_len, HT_EXPECT_NOT_EXISTS, val);
  29 }
  30
  31 int64_t ht_replace (hash_table_t *ht, const char *key, uint32_t key_len, int64_t val) {
  32     return ht_compare_and_set(ht, key, key_len, HT_EXPECT_EXISTS, val);
  33 }
  34
  35 // Test some basic stuff; add a few keys, remove a few keys
  36 void basic_test (CuTest* tc) {
  37
  38     hash_table_t *ht = ht_alloc();
  39
  40     ASSERT_EQUAL( 0,              ht_count(ht)          );
  41     ASSERT_EQUAL( DOES_NOT_EXIST, ht_add(ht,"a",2,10)     );
  42     ASSERT_EQUAL( 1,              ht_count(ht)          );
  43     ASSERT_EQUAL( DOES_NOT_EXIST, ht_add(ht,"b",2,20)     );
  44     ASSERT_EQUAL( 2,              ht_count(ht)          );
  45     ASSERT_EQUAL( 20,             ht_get(ht,"b",2)        );
  46     ASSERT_EQUAL( 10,             ht_set(ht,"a",2,11)     );
  47     ASSERT_EQUAL( 20,             ht_set(ht,"b",2,21)     );
  48     ASSERT_EQUAL( 2,              ht_count(ht)          );
  49     ASSERT_EQUAL( 21,             ht_add(ht,"b",2,22)     );
  50     ASSERT_EQUAL( 11,             ht_remove(ht,"a",2)     );
  51     ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"a",2)        );
  52     ASSERT_EQUAL( 1,              ht_count(ht)          );
  53     ASSERT_EQUAL( DOES_NOT_EXIST, ht_remove(ht,"a",2)     );
  54     ASSERT_EQUAL( 21,             ht_remove(ht,"b",2)     );
  55     ASSERT_EQUAL( 0,              ht_count(ht)          );
  56     ASSERT_EQUAL( DOES_NOT_EXIST, ht_remove(ht,"b",2)     );
  57     ASSERT_EQUAL( DOES_NOT_EXIST, ht_remove(ht,"c",2)     );
  58     ASSERT_EQUAL( 0,              ht_count(ht)          );
  59
  60     ASSERT_EQUAL( DOES_NOT_EXIST, ht_add(ht,"d",2,40)     );
  61     ASSERT_EQUAL( 40,             ht_get(ht,"d",2)        );
  62     ASSERT_EQUAL( 1,              ht_count(ht)          );
  63     ASSERT_EQUAL( 40,             ht_remove(ht,"d",2)     );
  64     ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"d",2)        );
  65     ASSERT_EQUAL( 0,              ht_count(ht)          );
  66
  67     ASSERT_EQUAL( DOES_NOT_EXIST, ht_replace(ht,"d",2,10) );
  68     ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"d",2)        );
  69     ASSERT_EQUAL( DOES_NOT_EXIST, ht_set(ht,"d",2,40)     );
  70     ASSERT_EQUAL( 40,             ht_replace(ht,"d",2,41) );
  71     ASSERT_EQUAL( 41,             ht_get(ht,"d",2)        );
  72     ASSERT_EQUAL( 41,             ht_remove(ht,"d",2)     );
  73     ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"d",2)        );
  74     ASSERT_EQUAL( 0,              ht_count(ht)          );
  75
  76     ASSERT_EQUAL( DOES_NOT_EXIST, ht_replace(ht,"b",2,20) );
  77     ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"b",2)        );
  78     // In the end, all members should be removed
  79     ASSERT_EQUAL( DOES_NOT_EXIST, ht_set(ht,"b",2,20)     );
  80     ASSERT_EQUAL( 20,             ht_replace(ht,"b",2,21) );
  81     ASSERT_EQUAL( 21,             ht_get(ht,"b",2)        );
  82     ASSERT_EQUAL( 21,             ht_remove(ht,"b",2)     );
  83     ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"b",2)        );
  84     ASSERT_EQUAL( 0,              ht_count(ht)          );
  85
  86     ht_free(ht);
  87
  88     // In a quiecent state; it is safe to free.
  89     rcu_update();
  90 }
  91
  92 void *simple_worker (void *arg) {
  93     worker_data_t *wd = (worker_data_t *)arg;
  94     hash_table_t *ht = wd->ht;
  95     CuTest* tc = wd->tc;
  96     uint64_t d = wd->id;
  97     int iters = 1000000;
  98
  99     SYNC_ADD(wd->wait, -1);
 100     do { } while (*((volatile worker_data_t *)wd)->wait); // wait for all workers to be ready
 101
 102     for (int j = 0; j < 10; ++j) {
 103         for (int i = d; i < iters; i+=2) {
 104             char key[10];
 105             sprintf(key, "k%u", i);
 106             TRACE("t0", "test ht_add() iteration (%llu, %llu)", j, i);
 107             CuAssertIntEquals_Msg(tc, key, DOES_NOT_EXIST, ht_add(ht, key, strlen(key)+1, d+1) );
 108         }
 109         for (int i = d; i < iters; i+=2) {
 110             char key[10];
 111             sprintf(key, "k%u", i);
 112             TRACE("t0", "test ht_remove() iteration (%llu, %llu)", j, i);
 113             CuAssertIntEquals_Msg(tc, key, d+1, ht_remove(ht, key, strlen(key)+1) );
 114         }
 115         rcu_update();
 116     }
 117     return NULL;
 118 }
 119
 120 // Do some simple concurrent testing
 121 void simple_add_remove (CuTest* tc) {
 122
 123     pthread_t thread[2];
 124     worker_data_t wd[2];
 125     int wait = 2;
 126     hash_table_t *ht = ht_alloc();
 127
 128     // In 2 threads, add & remove even & odd elements concurrently
 129     int i;
 130     for (i = 0; i < 2; ++i) {
 131         wd[i].id = i;
 132         wd[i].tc = tc;
 133         wd[i].ht = ht;
 134         wd[i].wait = &wait;
 135         int rc = nbd_thread_create(thread + i, i, simple_worker, wd + i);
 136         if (rc != 0) { perror("nbd_thread_create"); return; }
 137     }
 138     for (i = 0; i < 2; ++i) {
 139         pthread_join(thread[i], NULL);
 140     }
 141
 142     // In the end, all members should be removed
 143     ASSERT_EQUAL( 0, ht_count(ht) );
 144
 145     // In a quiecent state; it is safe to free.
 146     ht_free(ht);
 147 }
 148
 149
 150 void *inserter_worker (void *arg) {
 151     //pthread_t thread[NUM_THREADS];
 152
 153     //hash_table_t *ht = ht_alloc();
 154     return NULL;
 155 }
 156
 157 // Concurrent insertion
 158 void concurrent_insert (CuTest* tc) {
 159 }
 160
 161 int main (void) {
 162
 163     nbd_init();
 164     //lwt_set_trace_level("h0");
 165
 166     // Create and run test suite
 167         CuString *output = CuStringNew();
 168         CuSuite* suite = CuSuiteNew();
 169
 170     SUITE_ADD_TEST(suite, basic_test);
 171     SUITE_ADD_TEST(suite, simple_add_remove);
 172
 173         CuSuiteRun(suite);
 174         CuSuiteSummary(suite, output);
 175         CuSuiteDetails(suite, output);
 176         printf("%s\n", output->buffer);
 177
 178     return 0;
 179 }