generic interface for map-like data structures

diff --git a/include/common.h b/include/common.h
index 205ea3402a3a937d03d1977c5828ca7616ae1c4e..bf3d04ecc17a2960298f7916fd9b235f612a2cf1 100644 (file)
--- a/include/common.h
+++ b/include/common.h
@@ -36,6 +36,11 @@
 #define IS_TAGGED(v) ((uint64_t)(v) &  TAG)
 #define STRIP_TAG(v) ((uint64_t)(v) & ~TAG)
 
 #define IS_TAGGED(v) ((uint64_t)(v) &  TAG)
 #define STRIP_TAG(v) ((uint64_t)(v) & ~TAG)
 

+#define DOES_NOT_EXIST 0
+#define ERROR_INVALID_OPTION (-1)
+#define ERROR_INVALID_ARGUMENT (-2)
+#define ERROR_UNSUPPORTED_FEATURE (-3)
+

 typedef unsigned long long uint64_t;
 typedef unsigned int       uint32_t;
 typedef unsigned char      uint8_t;
 typedef unsigned long long uint64_t;
 typedef unsigned int       uint32_t;
 typedef unsigned char      uint8_t;

diff --git a/include/map.h b/include/map.h
new file mode 100644 (file)
index 0000000..d670c35
--- /dev/null
+++ b/include/map.h
@@ -0,0 +1,20 @@
+#ifndef MAP_H
+#define MAP_H
+
+typedef struct map map_t;
+typedef enum stat { MAP_STAT_COUNT } map_stat_e;
+typedef enum { MAP_TYPE_HASHTABLE, MAP_TYPE_SKIPLIST, MAP_TYPE_LIST } map_type_e;
+
+map_t *  map_alloc  (map_type_e map_type);
+void     map_free   (map_t *map);
+void     map_print  (map_t *map);
+uint64_t map_stat   (map_t *map, map_stat_e stat_type);
+
+uint64_t map_get    (map_t *map, const void *key_data, uint32_t key_len);
+uint64_t map_set    (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val);
+uint64_t map_add    (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val);
+uint64_t map_cas    (map_t *map, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
+uint64_t map_replace(map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val);
+uint64_t map_remove (map_t *map, const void *key_data, uint32_t key_len);
+
+#endif//MAP_H

diff --git a/include/txn.h b/include/txn.h
index 54928cbac8a6e804bf8af743928da8d68c8e0bd8..c23c59b8548085e8f09aa4b07d1bd428896be634 100644 (file)
--- a/include/txn.h
+++ b/include/txn.h
@@ -4,12 +4,12 @@
  */
 #ifndef TXN_H
 #define TXN_H
  */
 #ifndef TXN_H
 #define TXN_H

-#include "struct.h"
+#include "map.h"

 
 typedef enum { TXN_READ_WRITE, TXN_READ_ONLY, TXN_BLIND_WRITE } txn_access_t;
 typedef enum { TXN_DIRTY_READ, TXN_READ_COMMITTED, TXN_REPEATABLE_READ } txn_isolation_t;
 
 typedef struct txn txn_t;
 
 
 typedef enum { TXN_READ_WRITE, TXN_READ_ONLY, TXN_BLIND_WRITE } txn_access_t;
 typedef enum { TXN_DIRTY_READ, TXN_READ_COMMITTED, TXN_REPEATABLE_READ } txn_isolation_t;
 
 typedef struct txn txn_t;
 

-txn_t *txn_begin (txn_access_t access, txn_isolation_t isolation, hashtable_t *ht);
+txn_t *txn_begin (txn_access_t access, txn_isolation_t isolation, map_t *map);

 #endif//TXN_H
 #endif//TXN_H

diff --git a/makefile b/makefile
index dfabc2db889269431a709505caf47cd89a97c932..0e22b60a769555141ffd9b556d5fae5a6ff2799e 100644 (file)
--- a/makefile
+++ b/makefile
@@ -11,12 +11,13 @@ TESTS  := output/ll_test output/sl_test output/ht_test output/rcu_test
 EXES   := $(TESTS)
 
 RUNTIME_SRCS  := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c
 EXES   := $(TESTS)
 
 RUNTIME_SRCS  := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c

-TEST_SRCS     := $(RUNTIME_SRCS)
+MAP_SRCS      := map/map.c map/hashtable.c map/list.c map/skiplist.c map/nstring.c 
+TEST_SRCS     := $(RUNTIME_SRCS) $(MAP_SRCS)

 rcu_test_SRCS := $(TEST_SRCS) test/rcu_test.c
 rcu_test_SRCS := $(TEST_SRCS) test/rcu_test.c

-txn_test_SRCS := $(TEST_SRCS) struct/hashtable.c txn/txn.c
-ll_test_SRCS  := $(TEST_SRCS) struct/list.c test/ll_test.c struct/nstring.c
-sl_test_SRCS  := $(TEST_SRCS) struct/skiplist.c test/sl_test.c struct/nstring.c
-ht_test_SRCS  := $(TEST_SRCS) struct/hashtable.c test/ht_test.c test/CuTest.c struct/nstring.c
+txn_test_SRCS := $(TEST_SRCS) txn/txn.c 
+ll_test_SRCS  := $(TEST_SRCS) test/ll_test.c 
+sl_test_SRCS  := $(TEST_SRCS) test/sl_test.c
+ht_test_SRCS  := $(TEST_SRCS) test/ht_test.c test/CuTest.c

 
 tests: $(TESTS)
 
 
 tests: $(TESTS)
 

diff --git a/struct/hashtable.c b/map/hashtable.c
similarity index 88%
rename from struct/hashtable.c
rename to map/hashtable.c
index 5406d4242c038160047df62eb9ca43682f2e3289..69583acf0c11e15b8534262d940d878276d3624b 100644 (file)
--- a/struct/hashtable.c
+++ b/map/hashtable.c
@@ -15,7 +15,7 @@
 #include "common.h"
 #include "murmur.h"
 #include "mem.h"
 #include "common.h"
 #include "murmur.h"
 #include "mem.h"

-#include "struct.h"
+#include "mlocal.h"

 #include "nstring.h"
 
 #define GET_PTR(x) ((nstring_t *)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t
 #include "nstring.h"
 
 #define GET_PTR(x) ((nstring_t *)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t


@@ -287,14 +287,14 @@ static int hti_copy_entry (hashtable_i_t *ht1, volatile entry_t *ht1_e, uint32_t
 //
 // NOTE: the returned value matches <expected> iff the set succeeds
 //
 //
 // NOTE: the returned value matches <expected> iff the set succeeds
 //

-// Certain values of <expected> have special meaning. If <expected> is EXPECT_EXISTS then any 
+// Certain values of <expected> have special meaning. If <expected> is CAS_EXPECT_EXISTS then any 

 // real value matches (i.e. not a TOMBSTONE or DOES_NOT_EXIST) as long as <key> is in the table. If
 // real value matches (i.e. not a TOMBSTONE or DOES_NOT_EXIST) as long as <key> is in the table. If

-// <expected> is EXPECT_WHATEVER then skip the test entirely.
+// <expected> is CAS_EXPECT_WHATEVER then skip the test entirely.

 //
 //

-static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, const char *key_data, 
-                                    uint32_t key_len, uint64_t expected, uint64_t new) {
-    TRACE("h1", "hti_compare_and_set: hti %p key %p", hti, key_data);
-    TRACE("h1", "hti_compare_and_set: value %p expect %p", new, expected);
+static uint64_t hti_cas (hashtable_i_t *hti, uint32_t key_hash, const char *key_data, uint32_t key_len,
+                         uint64_t expected, uint64_t new) {
+    TRACE("h1", "hti_cas: hti %p key %p", hti, key_data);
+    TRACE("h1", "hti_cas: value %p expect %p", new, expected);

     assert(hti);
     assert(new != DOES_NOT_EXIST && !IS_TAGGED(new));
     assert(key_data);
     assert(hti);
     assert(new != DOES_NOT_EXIST && !IS_TAGGED(new));
     assert(key_data);


@@ -312,8 +312,8 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons
 
     // Install <key> in the table if it doesn't exist.
     if (is_empty) {
 
     // Install <key> in the table if it doesn't exist.
     if (is_empty) {

-        TRACE("h0", "hti_compare_and_set: entry %p is empty", e, 0);
-        if (expected != EXPECT_WHATEVER && expected != EXPECT_DOES_NOT_EXIST)
+        TRACE("h0", "hti_cas: entry %p is empty", e, 0);
+        if (expected != CAS_EXPECT_WHATEVER && expected != CAS_EXPECT_DOES_NOT_EXIST)

             return DOES_NOT_EXIST;
 
         // No need to do anything, <key> is already deleted.
             return DOES_NOT_EXIST;
 
         // No need to do anything, <key> is already deleted.


@@ -329,15 +329,15 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons
 
         // Retry if another thread stole the entry out from under us.
         if (e_key != DOES_NOT_EXIST) {
 
         // Retry if another thread stole the entry out from under us.
         if (e_key != DOES_NOT_EXIST) {

-            TRACE("h0", "hti_compare_and_set: lost race to install key %p in entry %p", key, e);
-            TRACE("h0", "hti_compare_and_set: found %p instead of NULL", GET_PTR(e_key), 0);
+            TRACE("h0", "hti_cas: lost race to install key %p in entry %p", key, e);
+            TRACE("h0", "hti_cas: found %p instead of NULL", GET_PTR(e_key), 0);

             nbd_free(key);
             nbd_free(key);

-            return hti_compare_and_set(hti, key_hash, key_data, key_len, expected, new); // tail-call
+            return hti_cas(hti, key_hash, key_data, key_len, expected, new); // tail-call

         }
         }

-        TRACE("h2", "hti_compare_and_set: installed key %p in entry %p", key, e);
+        TRACE("h2", "hti_cas: installed key %p in entry %p", key, e);

     }
 
     }
 

-    TRACE("h0", "hti_compare_and_set: entry for key \"%s\" is %p", GET_PTR(e->key)->data, e);
+    TRACE("h0", "hti_cas: entry for key \"%s\" is %p", GET_PTR(e->key)->data, e);

 
     // If the entry is in the middle of a copy, the copy must be completed first.
     uint64_t e_value = e->value;
 
     // If the entry is in the middle of a copy, the copy must be completed first.
     uint64_t e_value = e->value;


@@ -347,18 +347,18 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons
             if (did_copy) {
                 SYNC_ADD(&hti->num_entries_copied, 1);
             }
             if (did_copy) {
                 SYNC_ADD(&hti->num_entries_copied, 1);
             }

-            TRACE("h0", "hti_compare_and_set: value in the middle of a copy, copy completed by %s", 
+            TRACE("h0", "hti_cas: value in the middle of a copy, copy completed by %s", 

                         (did_copy ? "self" : "other"), 0);
         }
                         (did_copy ? "self" : "other"), 0);
         }

-        TRACE("h0", "hti_compare_and_set: value copied to next table, retry on next table", 0, 0);
+        TRACE("h0", "hti_cas: value copied to next table, retry on next table", 0, 0);

         return COPIED_VALUE;
     }
 
     // Fail if the old value is not consistent with the caller's expectation.
     int old_existed = (e_value != TOMBSTONE && e_value != DOES_NOT_EXIST);
         return COPIED_VALUE;
     }
 
     // Fail if the old value is not consistent with the caller's expectation.
     int old_existed = (e_value != TOMBSTONE && e_value != DOES_NOT_EXIST);

-    if (EXPECT_FALSE(expected != EXPECT_WHATEVER && expected != e_value)) {
-        if (EXPECT_FALSE(expected != (old_existed ? EXPECT_EXISTS : EXPECT_DOES_NOT_EXIST))) {
-            TRACE("h1", "hti_compare_and_set: value %p expected by caller not found; found value %p",
+    if (EXPECT_FALSE(expected != CAS_EXPECT_WHATEVER && expected != e_value)) {
+        if (EXPECT_FALSE(expected != (old_existed ? CAS_EXPECT_EXISTS : CAS_EXPECT_DOES_NOT_EXIST))) {
+            TRACE("h1", "hti_cas: value %p expected by caller not found; found value %p",

                         expected, e_value);
             return e_value;
         }
                         expected, e_value);
             return e_value;
         }


@@ -366,15 +366,15 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons
 
     // No need to update if value is unchanged.
     if ((new == TOMBSTONE && !old_existed) || e_value == new) {
 
     // No need to update if value is unchanged.
     if ((new == TOMBSTONE && !old_existed) || e_value == new) {

-        TRACE("h1", "hti_compare_and_set: old value and new value were the same", 0, 0);
+        TRACE("h1", "hti_cas: old value and new value were the same", 0, 0);

         return e_value;
     }
 
     // CAS the value into the entry. Retry if it fails.
     uint64_t v = SYNC_CAS(&e->value, e_value, new);
     if (EXPECT_FALSE(v != e_value)) {
         return e_value;
     }
 
     // CAS the value into the entry. Retry if it fails.
     uint64_t v = SYNC_CAS(&e->value, e_value, new);
     if (EXPECT_FALSE(v != e_value)) {

-        TRACE("h0", "hti_compare_and_set: value CAS failed; expected %p found %p", e_value, v);
-        return hti_compare_and_set(hti, key_hash, key_data, key_len, expected, new); // recursive tail-call
+        TRACE("h0", "hti_cas: value CAS failed; expected %p found %p", e_value, v);
+        return hti_cas(hti, key_hash, key_data, key_len, expected, new); // recursive tail-call

     }
 
     // The set succeeded. Adjust the value count.
     }
 
     // The set succeeded. Adjust the value count.


@@ -385,7 +385,7 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons
     }
 
     // Return the previous value.
     }
 
     // Return the previous value.

-    TRACE("h0", "hti_compare_and_set: CAS succeeded; old value %p new value %p", e_value, new);
+    TRACE("h0", "hti_cas: CAS succeeded; old value %p new value %p", e_value, new);

     return e_value;
 }
 
     return e_value;
 }
 


@@ -429,11 +429,10 @@ uint64_t ht_get (hashtable_t *ht, const char *key_data, uint32_t key_len) {
 }
 
 //
 }
 
 //

-uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_data, uint32_t key_len, 
-                            uint64_t expected_val, uint64_t new_val) {
+uint64_t ht_cas (hashtable_t *ht, const char *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val) {

 
 

-    TRACE("h2", "ht_compare_and_set: key %p len %u", key_data, key_len);
-    TRACE("h2", "ht_compare_and_set: expected val %p new val %p", expected_val, new_val);
+    TRACE("h2", "ht_cas: key %p len %u", key_data, key_len);
+    TRACE("h2", "ht_cas: expected val %p new val %p", expected_val, new_val);

     assert(key_data);
     assert(!IS_TAGGED(new_val) && new_val != DOES_NOT_EXIST);
 
     assert(key_data);
     assert(!IS_TAGGED(new_val) && new_val != DOES_NOT_EXIST);
 


@@ -446,7 +445,7 @@ uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_data, uint32_t key
         int num_copied = 0;
         int x = hti->scan; 
 
         int num_copied = 0;
         int x = hti->scan; 
 

-        TRACE("h1", "ht_compare_and_set: help copy. scan is %llu, size is %llu", x, 1<<hti->scale);
+        TRACE("h1", "ht_cas: help copy. scan is %llu, size is %llu", x, 1<<hti->scale);

         // Panic if we've been around the array twice and still haven't finished the copy.
         int panic = (x >= (1 << (hti->scale + 1))); 
         if (!panic) {
         // Panic if we've been around the array twice and still haven't finished the copy.
         int panic = (x >= (1 << (hti->scale + 1))); 
         if (!panic) {


@@ -461,7 +460,7 @@ uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_data, uint32_t key
             // the table.
             e = hti->table + (x & MASK(hti->scale));
         } else {
             // the table.
             e = hti->table + (x & MASK(hti->scale));
         } else {

-            TRACE("h1", "ht_compare_and_set: help copy panic", 0, 0);
+            TRACE("h1", "ht_cas: help copy panic", 0, 0);

             // scan the whole table
             limit = (1 << hti->scale);
             e = hti->table;
             // scan the whole table
             limit = (1 << hti->scale);
             e = hti->table;


@@ -487,7 +486,7 @@ uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_data, uint32_t key
 
     uint64_t old_val;
     uint32_t key_hash = murmur32(key_data, key_len);
 
     uint64_t old_val;
     uint32_t key_hash = murmur32(key_data, key_len);

-    while ((old_val = hti_compare_and_set(hti, key_hash, key_data, key_len, expected_val, new_val)) 
+    while ((old_val = hti_cas(hti, key_hash, key_data, key_len, expected_val, new_val)) 

            == COPIED_VALUE) {
         assert(hti->next);
         hti = hti->next;
            == COPIED_VALUE) {
         assert(hti->next);
         hti = hti->next;


@@ -503,7 +502,7 @@ uint64_t ht_remove (hashtable_t *ht, const char *key_data, uint32_t key_len) {
     uint64_t val;
     uint32_t key_hash = murmur32(key_data, key_len);
     do {
     uint64_t val;
     uint32_t key_hash = murmur32(key_data, key_len);
     do {

-        val = hti_compare_and_set(hti, key_hash, key_data, key_len, EXPECT_WHATEVER, TOMBSTONE);
+        val = hti_cas(hti, key_hash, key_data, key_len, CAS_EXPECT_WHATEVER, TOMBSTONE);

         if (val != COPIED_VALUE)
             return val == TOMBSTONE ? DOES_NOT_EXIST : val;
         assert(hti->next);
         if (val != COPIED_VALUE)
             return val == TOMBSTONE ? DOES_NOT_EXIST : val;
         assert(hti->next);


@@ -546,3 +545,6 @@ void ht_free (hashtable_t *ht) {
     } while (hti);
     nbd_free(ht);
 }
     } while (hti);
     nbd_free(ht);
 }

+
+void ht_print (hashtable_t *ht) {
+}

diff --git a/struct/list.c b/map/list.c
similarity index 97%
rename from struct/list.c
rename to map/list.c
index 5849247abd9a2a59f188c3e244d97acdd472643f..a0f52a57d573a7efb7ce74f32987ce22657a0d8e 100644 (file)
--- a/struct/list.c
+++ b/map/list.c
@@ -9,7 +9,7 @@
 #include <string.h>
 
 #include "common.h"
 #include <string.h>
 
 #include "common.h"

-#include "struct.h"
+#include "mlocal.h"

 #include "nstring.h"
 #include "mem.h"
 
 #include "nstring.h"
 #include "mem.h"
 


@@ -55,6 +55,9 @@ list_t *ll_alloc (void) {
     return ll;
 }
 
     return ll;
 }
 

+void ll_free (list_t *ll) {
+}
+

 static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const void *key_data, uint32_t key_len, int help_remove) {
     node_t *pred = ll->head;
     node_t *item = pred->next;
 static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const void *key_data, uint32_t key_len, int help_remove) {
     node_t *pred = ll->head;
     node_t *item = pred->next;


@@ -174,12 +177,12 @@ uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t ex
         if (!find_pred(&pred, &old_item, ll, key_data, key_len, TRUE)) {
 
             // There was not an item in the list that matches the key. 
         if (!find_pred(&pred, &old_item, ll, key_data, key_len, TRUE)) {
 
             // There was not an item in the list that matches the key. 

-            if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == EXPECT_EXISTS)) {
+            if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == CAS_EXPECT_EXISTS)) {

                 TRACE("l1", "ll_cas: the expectation was not met, the list was not changed", 0, 0);
                 return DOES_NOT_EXIST; // failure
             }
 
                 TRACE("l1", "ll_cas: the expectation was not met, the list was not changed", 0, 0);
                 return DOES_NOT_EXIST; // failure
             }
 

-            ASSERT(expectation == EXPECT_DOES_NOT_EXIST || expectation == EXPECT_WHATEVER);
+            ASSERT(expectation == CAS_EXPECT_DOES_NOT_EXIST || expectation == CAS_EXPECT_WHATEVER);

 
             // Create a new item and insert it into the list.
             TRACE("l2", "ll_cas: attempting to insert item between %p and %p", pred, pred->next);
 
             // Create a new item and insert it into the list.
             TRACE("l2", "ll_cas: attempting to insert item between %p and %p", pred, pred->next);


@@ -206,7 +209,7 @@ uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t ex
                 break; // retry
             }
 
                 break; // retry
             }
 

-            if (EXPECT_FALSE(expectation == EXPECT_DOES_NOT_EXIST)) {
+            if (EXPECT_FALSE(expectation == CAS_EXPECT_DOES_NOT_EXIST)) {

                 TRACE("l1", "ll_cas: found an item %p in the list that matched the key. the expectation was "
                         "not met, the list was not changed", old_item, old_item_val);
                 return old_item_val; // failure
                 TRACE("l1", "ll_cas: found an item %p in the list that matched the key. the expectation was "
                         "not met, the list was not changed", old_item, old_item_val);
                 return old_item_val; // failure

diff --git a/include/struct.h b/map/mlocal.h
similarity index 75%
rename from include/struct.h
rename to map/mlocal.h
index 9d12f73f120dc3beb466d72411050dd7f3400b09..548a49fdaa05ac918be10397ba1eb132f4babb31 100644 (file)
--- a/include/struct.h
+++ b/map/mlocal.h
@@ -1,18 +1,17 @@
 #ifndef STRUCT_H
 #define STRUCT_H
 
 #ifndef STRUCT_H
 #define STRUCT_H
 

-#define DOES_NOT_EXIST 0
-
-#define EXPECT_DOES_NOT_EXIST ( 0)
-#define EXPECT_EXISTS         (-1)
-#define EXPECT_WHATEVER       (-2)
+#define CAS_EXPECT_DOES_NOT_EXIST ( 0)
+#define CAS_EXPECT_EXISTS         (-1)
+#define CAS_EXPECT_WHATEVER       (-2)

 
 typedef struct ht hashtable_t;
 hashtable_t *ht_alloc (void);
 
 typedef struct ht hashtable_t;
 hashtable_t *ht_alloc (void);

-uint64_t ht_compare_and_set (hashtable_t *ht, const char *key, uint32_t key_len, uint64_t expected_val, uint64_t val);
+uint64_t ht_cas    (hashtable_t *ht, const char *key, uint32_t key_len, uint64_t expected_val, uint64_t val);

 uint64_t ht_get    (hashtable_t *ht, const char *key, uint32_t len);
 uint64_t ht_remove (hashtable_t *ht, const char *key, uint32_t len);
 uint64_t ht_count  (hashtable_t *ht);
 uint64_t ht_get    (hashtable_t *ht, const char *key, uint32_t len);
 uint64_t ht_remove (hashtable_t *ht, const char *key, uint32_t len);
 uint64_t ht_count  (hashtable_t *ht);

+void     ht_print  (hashtable_t *ht);

 void     ht_free   (hashtable_t *ht);
 
 typedef struct ll list_t;
 void     ht_free   (hashtable_t *ht);
 
 typedef struct ll list_t;


@@ -21,6 +20,7 @@ uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len);
 uint64_t ll_cas    (list_t *ll, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
 uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len);
 void     ll_print  (list_t *ll);
 uint64_t ll_cas    (list_t *ll, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
 uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len);
 void     ll_print  (list_t *ll);

+void     ll_free   (list_t *ll);

 
 typedef struct sl skiplist_t;
 skiplist_t * sl_alloc (void);
 
 typedef struct sl skiplist_t;
 skiplist_t * sl_alloc (void);


@@ -28,5 +28,7 @@ uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len);
 uint64_t sl_cas    (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
 uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len);
 void     sl_print  (skiplist_t *sl);
 uint64_t sl_cas    (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
 uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len);
 void     sl_print  (skiplist_t *sl);

+void     sl_free   (list_t *sl);
+

 
 #endif//STRUCT_H
 
 #endif//STRUCT_H

diff --git a/struct/nstring.c b/map/nstring.c
similarity index 100%
rename from struct/nstring.c
rename to map/nstring.c

diff --git a/struct/nstring.h b/map/nstring.h
similarity index 100%
rename from struct/nstring.h
rename to map/nstring.h

diff --git a/struct/skiplist.c b/map/skiplist.c
similarity index 97%
rename from struct/skiplist.c
rename to map/skiplist.c
index e8060ddb3e6e820282e79d8a2032d3ebba444a2d..c0e869c25e584656c33cf452d50bcacd1797b8f6 100644 (file)
--- a/struct/skiplist.c
+++ b/map/skiplist.c
@@ -10,15 +10,15 @@
  * www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf
  *
  * This code is written for the x86 memory-model. The algorithim depends on certain stores and
  * www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf
  *
  * This code is written for the x86 memory-model. The algorithim depends on certain stores and

- * loads being ordered. Be careful, this code probably won't work correctly on platforms with
- * weaker memory models if you don't add memory barriers in the right places.
+ * loads being ordered. Be careful, this code won't work correctly on platforms with weaker memory
+ * models if you don't add memory barriers in the right places.

  */
 #include <stdio.h>
 #include <string.h>
 
 #include "common.h"
 #include "runtime.h"
  */
 #include <stdio.h>
 #include <string.h>
 
 #include "common.h"
 #include "runtime.h"

-#include "struct.h"
+#include "mlocal.h"

 #include "nstring.h"
 #include "mem.h"
 #include "tls.h"
 #include "nstring.h"
 #include "mem.h"
 #include "tls.h"


@@ -50,7 +50,7 @@ static int random_level (void) {
     return n;
 }
 
     return n;
 }
 

-node_t *node_alloc (int level, const void *key_data, uint32_t key_len, uint64_t val) {
+static node_t *node_alloc (int level, const void *key_data, uint32_t key_len, uint64_t val) {

     assert(level >= 0 && level <= MAX_LEVEL);
     size_t sz = sizeof(node_t) + (level + 1) * sizeof(node_t *);
     node_t *item = (node_t *)nbd_malloc(sz);
     assert(level >= 0 && level <= MAX_LEVEL);
     size_t sz = sizeof(node_t) + (level + 1) * sizeof(node_t *);
     node_t *item = (node_t *)nbd_malloc(sz);


@@ -85,6 +85,9 @@ skiplist_t *sl_alloc (void) {
     return sl;
 }
 
     return sl;
 }
 

+void ll_free (list_t *ll) {
+}
+

 static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl, const void *key_data, uint32_t key_len, int help_remove) {
     node_t *pred = sl->head;
     node_t *item = NULL;
 static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl, const void *key_data, uint32_t key_len, int help_remove) {
     node_t *pred = sl->head;
     node_t *item = NULL;


@@ -237,12 +240,12 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_
         if (old_item == NULL) {
 
             // There was not an item in the skiplist that matches the key. 
         if (old_item == NULL) {
 
             // There was not an item in the skiplist that matches the key. 

-            if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == EXPECT_EXISTS)) {
+            if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == CAS_EXPECT_EXISTS)) {

                 TRACE("l1", "sl_cas: the expectation was not met, the skiplist was not changed", 0, 0);
                 return DOES_NOT_EXIST; // failure
             }
 
                 TRACE("l1", "sl_cas: the expectation was not met, the skiplist was not changed", 0, 0);
                 return DOES_NOT_EXIST; // failure
             }
 

-            ASSERT(expectation == EXPECT_DOES_NOT_EXIST || expectation == EXPECT_WHATEVER);
+            ASSERT(expectation == CAS_EXPECT_DOES_NOT_EXIST || expectation == CAS_EXPECT_WHATEVER);

 
             // First insert <new_item> into the bottom level.
             TRACE("s3", "sl_cas: attempting to insert item between %p and %p", preds[0], nexts[0]);
 
             // First insert <new_item> into the bottom level.
             TRACE("s3", "sl_cas: attempting to insert item between %p and %p", preds[0], nexts[0]);


@@ -271,7 +274,7 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_
                 break; // retry
             }
 
                 break; // retry
             }
 

-            if (EXPECT_FALSE(expectation == EXPECT_DOES_NOT_EXIST)) {
+            if (EXPECT_FALSE(expectation == CAS_EXPECT_DOES_NOT_EXIST)) {

                 TRACE("s1", "sl_cas: found an item %p in the skiplist that matched the key. the expectation was "
                         "not met, the skiplist was not changed", old_item, old_item_val);
                 return old_item_val; // failure
                 TRACE("s1", "sl_cas: found an item %p in the skiplist that matched the key. the expectation was "
                         "not met, the skiplist was not changed", old_item, old_item_val);
                 return old_item_val; // failure

diff --git a/test/ht_test.c b/test/ht_test.c
index a334db2ce485b599393a774a5eb6d8d08b4ab4ed..f90caeda9120a38112909390818107719dce9c38 100644 (file)
--- a/test/ht_test.c
+++ b/test/ht_test.c
@@ -7,7 +7,7 @@
 #include "runtime.h"
 #include "CuTest.h"
 #include "common.h"
 #include "runtime.h"
 #include "CuTest.h"
 #include "common.h"

-#include "struct.h"
+#include "map.h"

 #include "mem.h"
 #include "lwt.h"
 
 #include "mem.h"
 #include "lwt.h"
 


@@ -16,74 +16,62 @@
 typedef struct worker_data {
     int id;
     CuTest *tc;
 typedef struct worker_data {
     int id;
     CuTest *tc;

-    hashtable_t *ht;
+    map_t *ht;

     int *wait;
 } worker_data_t;
 
     int *wait;
 } worker_data_t;
 

-int64_t ht_set (hashtable_t *ht, const char *key, uint32_t key_len, int64_t val) {
-    return ht_compare_and_set(ht, key, key_len, EXPECT_WHATEVER, val);
-}
-
-int64_t ht_add (hashtable_t *ht, const char *key, uint32_t key_len, int64_t val) {
-    return ht_compare_and_set(ht, key, key_len, EXPECT_DOES_NOT_EXIST, val);
-}
-
-int64_t ht_replace (hashtable_t *ht, const char *key, uint32_t key_len, int64_t val) {
-    return ht_compare_and_set(ht, key, key_len, EXPECT_EXISTS, val);
-}
-

 // 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) {
 

-    hashtable_t *ht = ht_alloc();
-
-    ASSERT_EQUAL( 0,              ht_count(ht)          );
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_add(ht,"a",2,10)     );
-    ASSERT_EQUAL( 1,              ht_count(ht)          );
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_add(ht,"b",2,20)     );
-    ASSERT_EQUAL( 2,              ht_count(ht)          );
-    ASSERT_EQUAL( 20,             ht_get(ht,"b",2)        );
-    ASSERT_EQUAL( 10,             ht_set(ht,"a",2,11)     );
-    ASSERT_EQUAL( 20,             ht_set(ht,"b",2,21)     );
-    ASSERT_EQUAL( 2,              ht_count(ht)          );
-    ASSERT_EQUAL( 21,             ht_add(ht,"b",2,22)     );
-    ASSERT_EQUAL( 11,             ht_remove(ht,"a",2)     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"a",2)        );
-    ASSERT_EQUAL( 1,              ht_count(ht)          );
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_remove(ht,"a",2)     );
-    ASSERT_EQUAL( 21,             ht_remove(ht,"b",2)     );
-    ASSERT_EQUAL( 0,              ht_count(ht)          );
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_remove(ht,"b",2)     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_remove(ht,"c",2)     );
-    ASSERT_EQUAL( 0,              ht_count(ht)          );
+    map_t *ht = map_alloc(MAP_TYPE_HASHTABLE);
+
+    ASSERT_EQUAL( 0,              map_stat(ht, MAP_STAT_COUNT) );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"a",2,10)         );
+    ASSERT_EQUAL( 1,              map_stat(ht, MAP_STAT_COUNT) );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"b",2,20)         );
+    ASSERT_EQUAL( 2,              map_stat(ht, MAP_STAT_COUNT) );
+    ASSERT_EQUAL( 20,             map_get(ht,"b",2)            );
+    ASSERT_EQUAL( 10,             map_set(ht,"a",2,11)         );
+    ASSERT_EQUAL( 20,             map_set(ht,"b",2,21)         );
+    ASSERT_EQUAL( 2,              map_stat(ht, MAP_STAT_COUNT) );
+    ASSERT_EQUAL( 21,             map_add(ht,"b",2,22)         );
+    ASSERT_EQUAL( 11,             map_remove(ht,"a",2)         );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"a",2)            );
+    ASSERT_EQUAL( 1,              map_stat(ht, MAP_STAT_COUNT) );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"a",2)         );
+    ASSERT_EQUAL( 21,             map_remove(ht,"b",2)         );
+    ASSERT_EQUAL( 0,              map_stat(ht, MAP_STAT_COUNT) );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"b",2)         );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"c",2)         );
+    ASSERT_EQUAL( 0,              map_stat(ht, MAP_STAT_COUNT) );

     
     

-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_add(ht,"d",2,40)     );
-    ASSERT_EQUAL( 40,             ht_get(ht,"d",2)        );
-    ASSERT_EQUAL( 1,              ht_count(ht)          );
-    ASSERT_EQUAL( 40,             ht_remove(ht,"d",2)     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"d",2)        );
-    ASSERT_EQUAL( 0,              ht_count(ht)          );
-
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_replace(ht,"d",2,10) );
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"d",2)        );
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_set(ht,"d",2,40)     );
-    ASSERT_EQUAL( 40,             ht_replace(ht,"d",2,41) );
-    ASSERT_EQUAL( 41,             ht_get(ht,"d",2)        );
-    ASSERT_EQUAL( 41,             ht_remove(ht,"d",2)     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"d",2)        );
-    ASSERT_EQUAL( 0,              ht_count(ht)          );
-
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_replace(ht,"b",2,20) );
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"b",2)        );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"d",2,40)         );
+    ASSERT_EQUAL( 40,             map_get(ht,"d",2)            );
+    ASSERT_EQUAL( 1,              map_stat(ht, MAP_STAT_COUNT) );
+    ASSERT_EQUAL( 40,             map_remove(ht,"d",2)         );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2)            );
+    ASSERT_EQUAL( 0,              map_stat(ht, MAP_STAT_COUNT) );
+
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(ht,"d",2,10)     );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2)            );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_set(ht,"d",2,40)         );
+    ASSERT_EQUAL( 40,             map_replace(ht,"d",2,41)     );
+    ASSERT_EQUAL( 41,             map_get(ht,"d",2)            );
+    ASSERT_EQUAL( 41,             map_remove(ht,"d",2)         );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2)            );
+    ASSERT_EQUAL( 0,              map_stat(ht, MAP_STAT_COUNT) );
+
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(ht,"b",2,20)     );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"b",2)            );

     // In the end, all members should be removed
     // In the end, all members should be removed

-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_set(ht,"b",2,20)     );
-    ASSERT_EQUAL( 20,             ht_replace(ht,"b",2,21) );
-    ASSERT_EQUAL( 21,             ht_get(ht,"b",2)        );
-    ASSERT_EQUAL( 21,             ht_remove(ht,"b",2)     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"b",2)        );
-    ASSERT_EQUAL( 0,              ht_count(ht)          );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_set(ht,"b",2,20)         );
+    ASSERT_EQUAL( 20,             map_replace(ht,"b",2,21)     );
+    ASSERT_EQUAL( 21,             map_get(ht,"b",2)            );
+    ASSERT_EQUAL( 21,             map_remove(ht,"b",2)         );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"b",2)            );
+    ASSERT_EQUAL( 0,              map_stat(ht, MAP_STAT_COUNT) );

 
 

-    ht_free(ht);
+    map_free(ht);

 
     // In a quiecent state; it is safe to free.
     rcu_update();
 
     // In a quiecent state; it is safe to free.
     rcu_update();


@@ -91,7 +79,7 @@ void basic_test (CuTest* tc) {
 
 void *simple_worker (void *arg) {
     worker_data_t *wd = (worker_data_t *)arg;
 
 void *simple_worker (void *arg) {
     worker_data_t *wd = (worker_data_t *)arg;

-    hashtable_t *ht = wd->ht;
+    map_t *ht = wd->ht;

     CuTest* tc = wd->tc;
     uint64_t d = wd->id;
     int iters = 1000000;
     CuTest* tc = wd->tc;
     uint64_t d = wd->id;
     int iters = 1000000;


@@ -103,14 +91,14 @@ void *simple_worker (void *arg) {
         for (int i = d; i < iters; i+=2) {
             char key[10];
             sprintf(key, "k%u", i); 
         for (int i = d; i < iters; i+=2) {
             char key[10];
             sprintf(key, "k%u", i); 

-            TRACE("t0", "test ht_add() iteration (%llu, %llu)", j, i);
-            CuAssertIntEquals_Msg(tc, key, DOES_NOT_EXIST, ht_add(ht, key, strlen(key)+1, d+1) );
+            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) );

         }
         for (int i = d; i < iters; i+=2) {
             char key[10];
             sprintf(key, "k%u", i); 
         }
         for (int i = d; i < iters; i+=2) {
             char key[10];
             sprintf(key, "k%u", i); 

-            TRACE("t0", "test ht_remove() iteration (%llu, %llu)", j, i);
-            CuAssertIntEquals_Msg(tc, key, d+1, ht_remove(ht, key, strlen(key)+1) );
+            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();
     }


@@ -123,7 +111,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;

-    hashtable_t *ht = ht_alloc();
+    map_t *ht = map_alloc(MAP_TYPE_HASHTABLE);

 
     // In 2 threads, add & remove even & odd elements concurrently
     int i;
 
     // In 2 threads, add & remove even & odd elements concurrently
     int i;


@@ -140,17 +128,17 @@ void simple_add_remove (CuTest* tc) {
     }
 
     // In the end, all members should be removed
     }
 
     // In the end, all members should be removed

-    ASSERT_EQUAL( 0, ht_count(ht) );
+    ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );

 
     // In a quiecent state; it is safe to free.
 
     // In a quiecent state; it is safe to free.

-    ht_free(ht);
+    map_free(ht);

 }
 
 
 void *inserter_worker (void *arg) {
     //pthread_t thread[NUM_THREADS];
 
 }
 
 
 void *inserter_worker (void *arg) {
     //pthread_t thread[NUM_THREADS];
 

-    //hashtable_t *ht = ht_alloc();
+    //map_t *ht = map_alloc(MAP_TYPE_HASHTABLE);

     return NULL;
 }
 
     return NULL;
 }
 

diff --git a/test/ll_test.c b/test/ll_test.c
index 03bc81f4a26661a2f25de6e00495955243193f7a..490bf7d1393afec8e115a6721d50fdce0f554fda 100644 (file)
--- a/test/ll_test.c
+++ b/test/ll_test.c
@@ -5,13 +5,13 @@
 
 #include "common.h"
 #include "runtime.h"
 
 #include "common.h"
 #include "runtime.h"

-#include "struct.h"
+#include "map.h"

 
 #define NUM_ITERATIONS 10000000
 
 static volatile int wait_;
 static long num_threads_;
 
 #define NUM_ITERATIONS 10000000
 
 static volatile int wait_;
 static long num_threads_;

-static list_t *ll_;
+static map_t *map_;

 
 void *worker (void *arg) {
 
 
 void *worker (void *arg) {
 


@@ -26,15 +26,15 @@ void *worker (void *arg) {
         char key_str[10];
         sprintf(key_str, "%llX", key);
         if (r & (1 << 8)) {
         char key_str[10];
         sprintf(key_str, "%llX", key);
         if (r & (1 << 8)) {

-            ll_cas(ll_, key_str, strlen(key_str) + 1, EXPECT_WHATEVER, 1);
+            map_set(map_, key_str, strlen(key_str) + 1, 1);

         } else {
         } else {

-            ll_remove(ll_, key_str, strlen(key_str) + 1);
+            map_remove(map_, key_str, strlen(key_str) + 1);

         }
 #else
         if (r & (1 << 8)) {
         }
 #else
         if (r & (1 << 8)) {

-            ll_cas(ll_, (void *)key, -1, EXPECT_WHATEVER, 1);
+            map_set(map_, (void *)key, -1, 1);

         } else {
         } else {

-            ll_remove(ll_, (void *)key, -1);
+            map_remove(map_, (void *)key, -1);

         }
 #endif
 
         }
 #endif
 


@@ -75,7 +75,7 @@ int main (int argc, char **argv) {
         }
     }
 
         }
     }
 

-    ll_ = ll_alloc();
+    map_ = map_alloc(MAP_TYPE_LIST);

 
     struct timeval tv1, tv2;
     gettimeofday(&tv1, NULL);
 
     struct timeval tv1, tv2;
     gettimeofday(&tv1, NULL);


@@ -93,7 +93,7 @@ int main (int argc, char **argv) {
 
     gettimeofday(&tv2, NULL);
     int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
 
     gettimeofday(&tv2, NULL);
     int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;

-    ll_print(ll_);
+    map_print(map_);

     printf("Th:%ld Time:%dms\n", num_threads_, ms);
 
     return 0;
     printf("Th:%ld Time:%dms\n", num_threads_, ms);
 
     return 0;

diff --git a/test/sl_test.c b/test/sl_test.c
index 195a5dd2f03e481895541285e8cf71d23ba23bdd..00f9ac0a63e4a1f618288c8da3c46f0ea4d2ce3b 100644 (file)
--- a/test/sl_test.c
+++ b/test/sl_test.c
@@ -5,13 +5,13 @@
 
 #include "common.h"
 #include "runtime.h"
 
 #include "common.h"
 #include "runtime.h"

-#include "struct.h"
+#include "map.h"

 
 #define NUM_ITERATIONS 10000000
 
 static volatile int wait_;
 static long num_threads_;
 
 #define NUM_ITERATIONS 10000000
 
 static volatile int wait_;
 static long num_threads_;

-static skiplist_t *sl_;
+static map_t *map_;

 
 void *worker (void *arg) {
 
 
 void *worker (void *arg) {
 


@@ -26,15 +26,15 @@ void *worker (void *arg) {
         char key_str[10];
         sprintf(key_str, "%llX", key);
         if (r & (1 << 8)) {
         char key_str[10];
         sprintf(key_str, "%llX", key);
         if (r & (1 << 8)) {

-            sl_cas(sl_, key_str, strlen(key_str) + 1, EXPECT_WHATEVER, (r & 0xFF)+1);
+            map_set(map_, key_str, strlen(key_str) + 1, (r & 0xFF)+1);

         } else {
         } else {

-            sl_remove(sl_, key_str, strlen(key_str) + 1);
+            map_remove(map_, key_str, strlen(key_str) + 1);

         }
 #else
         if (r & (1 << 8)) {
         }
 #else
         if (r & (1 << 8)) {

-            sl_cas(sl_, (void *)key, -1, EXPECT_WHATEVER, (r & 0xFF)+1);
+            map_set(map_, (void *)key, -1, (r & 0xFF)+1);

         } else {
         } else {

-            sl_remove(sl_, (void *)key, -1);
+            map_remove(map_, (void *)key, -1);

         }
 #endif
 
         }
 #endif
 


@@ -75,7 +75,7 @@ int main (int argc, char **argv) {
         }
     }
 
         }
     }
 

-    sl_ = sl_alloc();
+    map_ = map_alloc(MAP_TYPE_SKIPLIST);

 
     struct timeval tv1, tv2;
     gettimeofday(&tv1, NULL);
 
     struct timeval tv1, tv2;
     gettimeofday(&tv1, NULL);


@@ -93,7 +93,7 @@ int main (int argc, char **argv) {
 
     gettimeofday(&tv2, NULL);
     int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
 
     gettimeofday(&tv2, NULL);
     int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;

-    sl_print(sl_);
+    map_print(map_);

     printf("Th:%ld Time:%dms\n", num_threads_, ms);
 
     return 0;
     printf("Th:%ld Time:%dms\n", num_threads_, ms);
 
     return 0;

diff --git a/todo b/todo
index 86d19ab549fb2c5e742bace7cb93f4100dfaaf2e..956736ae4a078732fba04ae085fd63787c218cb4 100644 (file)
--- a/todo
+++ b/todo
@@ -7,3 +7,4 @@
 - make interfaces for all data structures consistent 
 + make list and skiplist use string keys
 + optimize integer keys
 - make interfaces for all data structures consistent 
 + make list and skiplist use string keys
 + optimize integer keys

+- sl_free() ll_free() ht_print()