use generic map interface in tests
authorjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Sun, 30 Nov 2008 04:30:08 +0000 (04:30 +0000)
committerjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Sun, 30 Nov 2008 04:30:08 +0000 (04:30 +0000)
fix a few skiplist bugs caught by new tests

makefile
map/skiplist.c
test/map_test1.c [moved from test/ll_test.c with 69% similarity]
test/map_test2.c [moved from test/ht_test.c with 86% similarity]
test/sl_test.c [deleted file]

index 13364a88a8df4074ee6cb153832069542bcd2021..6baa518fff70eabcdc9d103a6cfef604e8e3ba85 100644 (file)
--- a/makefile
+++ b/makefile
@@ -7,17 +7,16 @@
 OPT       := -fwhole-program -combine -03 #-DNDEBUG
 CFLAGS := -g -Wall -Werror -std=c99 -m64 $(OPT) #-DENABLE_TRACE
 INCS   := $(addprefix -I, include)
 OPT       := -fwhole-program -combine -03 #-DNDEBUG
 CFLAGS := -g -Wall -Werror -std=c99 -m64 $(OPT) #-DENABLE_TRACE
 INCS   := $(addprefix -I, include)
-TESTS  := output/ll_test output/sl_test output/ht_test output/rcu_test
+TESTS  := output/map_test1 output/map_test2 output/rcu_test
 EXES   := $(TESTS)
 
 EXES   := $(TESTS)
 
-RUNTIME_SRCS  := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c
-MAP_SRCS      := map/map.c map/nstring.c 
-TEST_SRCS     := $(RUNTIME_SRCS) $(MAP_SRCS)
-rcu_test_SRCS := $(TEST_SRCS) test/rcu_test.c
-txn_test_SRCS := $(TEST_SRCS) txn/txn.c map/hashtable.c 
-ll_test_SRCS  := $(TEST_SRCS) test/ll_test.c map/list.c 
-sl_test_SRCS  := $(TEST_SRCS) test/sl_test.c map/skiplist.c 
-ht_test_SRCS  := $(TEST_SRCS) test/ht_test.c map/hashtable.c test/CuTest.c
+RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c
+MAP_SRCS     := map/map.c map/nstring.c map/list.c map/skiplist.c map/hashtable.c
+
+rcu_test_SRCS  := $(RUNTIME_SRCS) test/rcu_test.c
+txn_test_SRCS  := $(RUNTIME_SRCS) $(MAP_SRCS) txn/txn.c
+map_test1_SRCS := $(RUNTIME_SRCS) $(MAP_SRCS) test/map_test1.c 
+map_test2_SRCS := $(RUNTIME_SRCS) $(MAP_SRCS) test/map_test2.c test/CuTest.c
 
 tests: $(TESTS)
 
 
 tests: $(TESTS)
 
index d18ee3df4a18a954e53631774616e32f9763da3b..ec8a6ff012db11410894c67791c591990d39c07e 100644 (file)
@@ -340,7 +340,7 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_
                 // There in no need to continue linking in the item if another thread removed it.
                 node_t *old_next = ((volatile node_t *)new_item)->next[level];
                 if (IS_TAGGED(old_next))
                 // There in no need to continue linking in the item if another thread removed it.
                 node_t *old_next = ((volatile node_t *)new_item)->next[level];
                 if (IS_TAGGED(old_next))
-                    return new_val;
+                    return DOES_NOT_EXIST; // success
 
                 // Use a CAS so we do not inadvertantly stomp on a mark another thread placed on the item.
                 if (old_next == next || SYNC_CAS(&new_item->next[level], old_next, next) == old_next)
 
                 // Use a CAS so we do not inadvertantly stomp on a mark another thread placed on the item.
                 if (old_next == next || SYNC_CAS(&new_item->next[level], old_next, next) == old_next)
@@ -348,7 +348,7 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_
             } while (1);
         } while (1);
     }
             } while (1);
         } while (1);
     }
-    return new_val;
+    return DOES_NOT_EXIST; // success
 }
 
 uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len) {
 }
 
 uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len) {
@@ -379,8 +379,9 @@ uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len) {
                 TRACE("s2", "sl_remove: lost race -- %p is already marked for removal by another thread", item, 0);
                 if (level == 0)
                     return DOES_NOT_EXIST;
                 TRACE("s2", "sl_remove: lost race -- %p is already marked for removal by another thread", item, 0);
                 if (level == 0)
                     return DOES_NOT_EXIST;
+                break;
             }
             }
-        } while (!IS_TAGGED(old_next) || next != old_next);
+        } while (next != old_next);
     }
 
     // This has to be an atomic swap in case another thread is updating the item while we are removing it. 
     }
 
     // This has to be an atomic swap in case another thread is updating the item while we are removing it. 
similarity index 69%
rename from test/ll_test.c
rename to test/map_test1.c
index 490bf7d1393afec8e115a6721d50fdce0f554fda..30d7ce0e4a7121d0e4349d33bf2417e8711a6b3c 100644 (file)
@@ -75,26 +75,30 @@ int main (int argc, char **argv) {
         }
     }
 
         }
     }
 
-    map_ = map_alloc(MAP_TYPE_LIST);
+    map_type_t map_types[] = { MAP_TYPE_LIST, MAP_TYPE_SKIPLIST, MAP_TYPE_HASHTABLE };
+    for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) {
+        map_ = map_alloc(map_types[i]);
 
 
-    struct timeval tv1, tv2;
-    gettimeofday(&tv1, NULL);
+        struct timeval tv1, tv2;
+        gettimeofday(&tv1, NULL);
 
 
-    wait_ = num_threads_;
+        wait_ = num_threads_;
 
 
-    for (int i = 0; i < num_threads_; ++i) {
-        int rc = nbd_thread_create(thread + i, i, worker, (void*)(size_t)i);
-        if (rc != 0) { perror("pthread_create"); return rc; }
-    }
+        for (int i = 0; i < num_threads_; ++i) {
+            int rc = nbd_thread_create(thread + i, i, worker, (void*)(size_t)i);
+            if (rc != 0) { perror("pthread_create"); return rc; }
+        }
 
 
-    for (int i = 0; i < num_threads_; ++i) {
-        pthread_join(thread[i], NULL);
-    }
+        for (int i = 0; i < num_threads_; ++i) {
+            pthread_join(thread[i], NULL);
+        }
 
 
-    gettimeofday(&tv2, NULL);
-    int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
-    map_print(map_);
-    printf("Th:%ld Time:%dms\n", num_threads_, ms);
+        gettimeofday(&tv2, NULL);
+        int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
+        map_print(map_);
+        printf("Th:%ld Time:%dms\n", num_threads_, ms);
+        fflush(stdout);
+    }
 
     return 0;
 }
 
     return 0;
 }
similarity index 86%
rename from test/ht_test.c
rename to test/map_test2.c
index e6ec9ff46727993a3a983d01b18678621663fc74..7d31c87ff1b35e9beb9c0679d873beef22081bb7 100644 (file)
@@ -20,10 +20,12 @@ typedef struct worker_data {
     int *wait;
 } worker_data_t;
 
     int *wait;
 } worker_data_t;
 
+static map_type_t map_type_;
+
 // Test some basic stuff; add a few keys, remove a few keys
 void basic_test (CuTest* tc) {
 
 // Test some basic stuff; add a few keys, remove a few keys
 void basic_test (CuTest* tc) {
 
-    map_t *ht = map_alloc(MAP_TYPE_HASHTABLE);
+    map_t *ht = map_alloc(map_type_);
 
     ASSERT_EQUAL( 0,              map_count(ht)            );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"a",2,10)     );
 
     ASSERT_EQUAL( 0,              map_count(ht)            );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"a",2,10)     );
@@ -83,7 +85,7 @@ void *simple_worker (void *arg) {
     map_t *ht = wd->ht;
     CuTest* tc = wd->tc;
     uint64_t d = wd->id;
     map_t *ht = wd->ht;
     CuTest* tc = wd->tc;
     uint64_t d = wd->id;
-    int iters = 1000000;
+    int iters = map_type_ == MAP_TYPE_LIST ? 100 : 1000000;
 
     SYNC_ADD(wd->wait, -1);
     do { } while (*((volatile worker_data_t *)wd)->wait); // wait for all workers to be ready
 
     SYNC_ADD(wd->wait, -1);
     do { } while (*((volatile worker_data_t *)wd)->wait); // wait for all workers to be ready
@@ -94,14 +96,15 @@ void *simple_worker (void *arg) {
             sprintf(key, "k%u", i); 
             TRACE("t0", "test map_add() iteration (%llu, %llu)", j, i);
             CuAssertIntEquals_Msg(tc, key, DOES_NOT_EXIST, map_add(ht, key, strlen(key)+1, d+1) );
             sprintf(key, "k%u", i); 
             TRACE("t0", "test map_add() iteration (%llu, %llu)", j, i);
             CuAssertIntEquals_Msg(tc, key, DOES_NOT_EXIST, map_add(ht, key, strlen(key)+1, d+1) );
+            rcu_update();
         }
         for (int i = d; i < iters; i+=2) {
             char key[10];
             sprintf(key, "k%u", i); 
             TRACE("t0", "test map_remove() iteration (%llu, %llu)", j, i);
             CuAssertIntEquals_Msg(tc, key, d+1, map_remove(ht, key, strlen(key)+1) );
         }
         for (int i = d; i < iters; i+=2) {
             char key[10];
             sprintf(key, "k%u", i); 
             TRACE("t0", "test map_remove() iteration (%llu, %llu)", j, i);
             CuAssertIntEquals_Msg(tc, key, d+1, map_remove(ht, key, strlen(key)+1) );
+            rcu_update();
         }
         }
-        rcu_update();
     }
     return NULL;
 }
     }
     return NULL;
 }
@@ -112,7 +115,7 @@ void simple_add_remove (CuTest* tc) {
     pthread_t thread[2];
     worker_data_t wd[2];
     int wait = 2;
     pthread_t thread[2];
     worker_data_t wd[2];
     int wait = 2;
-    map_t *ht = map_alloc(MAP_TYPE_HASHTABLE);
+    map_t *ht = map_alloc(map_type_);
 
     // In 2 threads, add & remove even & odd elements concurrently
     int i;
 
     // In 2 threads, add & remove even & odd elements concurrently
     int i;
@@ -152,17 +155,22 @@ int main (void) {
     nbd_init();
     //lwt_set_trace_level("h0");
 
     nbd_init();
     //lwt_set_trace_level("h0");
 
-    // Create and run test suite
-       CuString *output = CuStringNew();
-       CuSuite* suite = CuSuiteNew();
+    map_type_t map_types[] = { MAP_TYPE_LIST, MAP_TYPE_SKIPLIST, MAP_TYPE_HASHTABLE };
+    for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) {
+        map_type_ = map_types[i];
+
+        // Create and run test suite
+        CuString *output = CuStringNew();
+        CuSuite* suite = CuSuiteNew();
 
 
-    SUITE_ADD_TEST(suite, basic_test);
-    SUITE_ADD_TEST(suite, simple_add_remove);
+        SUITE_ADD_TEST(suite, basic_test);
+        SUITE_ADD_TEST(suite, simple_add_remove);
 
 
-       CuSuiteRun(suite);
-       CuSuiteSummary(suite, output);
-       CuSuiteDetails(suite, output);
-       printf("%s\n", output->buffer);
+        CuSuiteRun(suite);
+        CuSuiteSummary(suite, output);
+        CuSuiteDetails(suite, output);
+        printf("%s\n", output->buffer);
+    }
 
     return 0;
 }
 
     return 0;
 }
diff --git a/test/sl_test.c b/test/sl_test.c
deleted file mode 100644 (file)
index 00f9ac0..0000000
+++ /dev/null
@@ -1,100 +0,0 @@
-#include <stdio.h>
-#include <errno.h>
-#include <pthread.h>
-#include <sys/time.h>
-
-#include "common.h"
-#include "runtime.h"
-#include "map.h"
-
-#define NUM_ITERATIONS 10000000
-
-static volatile int wait_;
-static long num_threads_;
-static map_t *map_;
-
-void *worker (void *arg) {
-
-    // Wait for all the worker threads to be ready.
-    SYNC_ADD(&wait_, -1);
-    do {} while (wait_); 
-
-    for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) {
-        unsigned r = nbd_rand();
-        uint64_t key = r & 0xF;
-#if 1
-        char key_str[10];
-        sprintf(key_str, "%llX", key);
-        if (r & (1 << 8)) {
-            map_set(map_, key_str, strlen(key_str) + 1, (r & 0xFF)+1);
-        } else {
-            map_remove(map_, key_str, strlen(key_str) + 1);
-        }
-#else
-        if (r & (1 << 8)) {
-            map_set(map_, (void *)key, -1, (r & 0xFF)+1);
-        } else {
-            map_remove(map_, (void *)key, -1);
-        }
-#endif
-
-        rcu_update();
-    }
-
-    return NULL;
-}
-
-int main (int argc, char **argv) {
-    nbd_init();
-    //lwt_set_trace_level("s3");
-
-    char* program_name = argv[0];
-    pthread_t thread[MAX_NUM_THREADS];
-
-    if (argc > 2) {
-        fprintf(stderr, "Usage: %s num_threads\n", program_name);
-        return -1;
-    }
-
-    num_threads_ = 2;
-    if (argc == 2)
-    {
-        errno = 0;
-        num_threads_ = strtol(argv[1], NULL, 10);
-        if (errno) {
-            fprintf(stderr, "%s: Invalid argument for number of threads\n", program_name);
-            return -1;
-        }
-        if (num_threads_ <= 0) {
-            fprintf(stderr, "%s: Number of threads must be at least 1\n", program_name);
-            return -1;
-        }
-        if (num_threads_ > MAX_NUM_THREADS) {
-            fprintf(stderr, "%s: Number of threads cannot be more than %d\n", program_name, MAX_NUM_THREADS);
-            return -1;
-        }
-    }
-
-    map_ = map_alloc(MAP_TYPE_SKIPLIST);
-
-    struct timeval tv1, tv2;
-    gettimeofday(&tv1, NULL);
-
-    wait_ = num_threads_;
-
-    for (int i = 0; i < num_threads_; ++i) {
-        int rc = nbd_thread_create(thread + i, i, worker, (void*)(size_t)i);
-        if (rc != 0) { perror("pthread_create"); return rc; }
-    }
-
-    for (int i = 0; i < num_threads_; ++i) {
-        pthread_join(thread[i], NULL);
-    }
-
-    gettimeofday(&tv2, NULL);
-    int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
-    map_print(map_);
-    printf("Th:%ld Time:%dms\n", num_threads_, ms);
-
-    return 0;
-}