generic map iterator interface

diff --git a/include/hashtable.h b/include/hashtable.h
index 5ae84c11db2d670df7c44523cbf02bf2b391ee97..0a9ea209fe7ad5a8707fb1981b75235df8831e7d 100644 (file)
--- a/include/hashtable.h
+++ b/include/hashtable.h
@@ -6,7 +6,7 @@
 typedef struct ht hashtable_t;
 typedef struct ht_iter ht_iter_t;
 
 typedef struct ht hashtable_t;
 typedef struct ht_iter ht_iter_t;
 

-hashtable_t *ht_alloc (const datatype_t *key_type);
+hashtable_t * ht_alloc (const datatype_t *key_type);

 uint64_t ht_cas    (hashtable_t *ht, void *key, uint64_t expected_val, uint64_t val);
 uint64_t ht_get    (hashtable_t *ht, void *key);
 uint64_t ht_remove (hashtable_t *ht, void *key);
 uint64_t ht_cas    (hashtable_t *ht, void *key, uint64_t expected_val, uint64_t val);
 uint64_t ht_get    (hashtable_t *ht, void *key);
 uint64_t ht_remove (hashtable_t *ht, void *key);


@@ -14,15 +14,14 @@ uint64_t ht_count  (hashtable_t *ht);
 void     ht_print  (hashtable_t *ht);
 void     ht_free   (hashtable_t *ht);
 
 void     ht_print  (hashtable_t *ht);
 void     ht_free   (hashtable_t *ht);
 

-ht_iter_t *ht_iter_start (hashtable_t *ht, void *key);
-ht_iter_t *ht_iter_next  (ht_iter_t *iter);
-uint64_t   ht_iter_val   (ht_iter_t *iter);
-uint64_t   ht_iter_key   (ht_iter_t *iter);
-void       ht_iter_free  (ht_iter_t *iter);
+ht_iter_t * ht_iter_begin (hashtable_t *ht, void *key);
+uint64_t    ht_iter_next  (ht_iter_t *iter, void **key_ptr);
+void        ht_iter_free  (ht_iter_t *iter);

 
 static const map_impl_t ht_map_impl = { 
     (map_alloc_t)ht_alloc, (map_cas_t)ht_cas, (map_get_t)ht_get, (map_remove_t)ht_remove, 
 
 static const map_impl_t ht_map_impl = { 
     (map_alloc_t)ht_alloc, (map_cas_t)ht_cas, (map_get_t)ht_get, (map_remove_t)ht_remove, 

-    (map_count_t)ht_count, (map_print_t)ht_print, (map_free_t)ht_free
+    (map_count_t)ht_count, (map_print_t)ht_print, (map_free_t)ht_free, (map_iter_begin_t)ht_iter_begin,
+    (map_iter_next_t)ht_iter_next, (map_iter_free_t)ht_iter_free

 };
 
 #endif//HASHTABLE_H
 };
 
 #endif//HASHTABLE_H

diff --git a/include/list.h b/include/list.h
index e4cba2d93d7f3344497491159990d00b4f209473..69e68148281bb99ec28c8a6d85329ec0cf73e773 100644 (file)
--- a/include/list.h
+++ b/include/list.h
@@ -15,14 +15,14 @@ void     ll_print   (list_t *ll);
 void     ll_free    (list_t *ll);
 void *   ll_min_key (list_t *sl);
 
 void     ll_free    (list_t *ll);
 void *   ll_min_key (list_t *sl);
 

-ll_iter_t *ll_iter_start (list_t *ll, void *key);
-ll_iter_t *ll_iter_next  (ll_iter_t *iter);
-uint64_t   ll_iter_val   (ll_iter_t *iter);
-void *     ll_iter_key   (ll_iter_t *iter);
+ll_iter_t * ll_iter_begin (list_t *ll, void *key);
+uint64_t    ll_iter_next  (ll_iter_t *iter, void **key_ptr);
+void        ll_iter_free  (ll_iter_t *iter);

 
 static const map_impl_t ll_map_impl = { 
     (map_alloc_t)ll_alloc, (map_cas_t)ll_cas, (map_get_t)ll_lookup, (map_remove_t)ll_remove, 
 
 static const map_impl_t ll_map_impl = { 
     (map_alloc_t)ll_alloc, (map_cas_t)ll_cas, (map_get_t)ll_lookup, (map_remove_t)ll_remove, 

-    (map_count_t)ll_count, (map_print_t)ll_print, (map_free_t)ll_free
+    (map_count_t)ll_count, (map_print_t)ll_print, (map_free_t)ll_free, (map_iter_begin_t)ll_iter_begin,
+    (map_iter_next_t)ll_iter_next, (map_iter_free_t)ll_iter_free

 };
 
 #endif//LIST_H
 };
 
 #endif//LIST_H

diff --git a/include/map.h b/include/map.h
index 4d8b78f39ab22147ee12b7db5fd0f28eaa727ef6..27e8dae00008cac7afef16bdde792c3dffcfccd1 100644 (file)
--- a/include/map.h
+++ b/include/map.h
@@ -4,18 +4,23 @@
 #include "datatype.h"
 
 typedef struct map map_t;
 #include "datatype.h"
 
 typedef struct map map_t;

+typedef struct map_iter map_iter_t;

 typedef struct map_impl map_impl_t;
 
 typedef struct map_impl map_impl_t;
 

-map_t *  map_alloc  (const map_impl_t *map_impl, const datatype_t *key_type);
-uint64_t map_get    (map_t *map, void *key);
-uint64_t map_set    (map_t *map, void *key, uint64_t new_val);
-uint64_t map_add    (map_t *map, void *key, uint64_t new_val);
-uint64_t map_cas    (map_t *map, void *key, uint64_t expected_val, uint64_t new_val);
-uint64_t map_replace(map_t *map, void *key, uint64_t new_val);
-uint64_t map_remove (map_t *map, void *key);
-uint64_t map_count  (map_t *map);
-void     map_print  (map_t *map);
-void     map_free   (map_t *map);
+map_t *  map_alloc   (const map_impl_t *map_impl, const datatype_t *key_type);
+uint64_t map_get     (map_t *map, void *key);
+uint64_t map_set     (map_t *map, void *key, uint64_t new_val);
+uint64_t map_add     (map_t *map, void *key, uint64_t new_val);
+uint64_t map_cas     (map_t *map, void *key, uint64_t expected_val, uint64_t new_val);
+uint64_t map_replace (map_t *map, void *key, uint64_t new_val);
+uint64_t map_remove  (map_t *map, void *key);
+uint64_t map_count   (map_t *map);
+void     map_print   (map_t *map);
+void     map_free    (map_t *map);
+
+map_iter_t * map_iter_begin (map_t *map, void *key);
+uint64_t     map_iter_next  (map_iter_t *iter, void **key);
+void         map_iter_free  (map_iter_t *iter);

 
 /////////////////////////////////////////////////////////////////////////////////////
 
 
 /////////////////////////////////////////////////////////////////////////////////////
 


@@ -24,12 +29,16 @@ void     map_free   (map_t *map);
 #define CAS_EXPECT_WHATEVER       (-2)
 
 typedef void *   (*map_alloc_t)  (const datatype_t *);
 #define CAS_EXPECT_WHATEVER       (-2)
 
 typedef void *   (*map_alloc_t)  (const datatype_t *);

-typedef uint64_t (*map_cas_t)    (void *, void *, uint64_t, uint64_t);
-typedef uint64_t (*map_get_t)    (void *, void *);
-typedef uint64_t (*map_remove_t) (void *, void *);
-typedef uint64_t (*map_count_t)  (void *);
-typedef void     (*map_print_t)  (void *);
-typedef void     (*map_free_t)   (void *);
+typedef uint64_t (*map_cas_t)    (map_impl_t *, void *, uint64_t, uint64_t);
+typedef uint64_t (*map_get_t)    (map_impl_t *, void *);
+typedef uint64_t (*map_remove_t) (map_impl_t *, void *);
+typedef uint64_t (*map_count_t)  (map_impl_t *);
+typedef void     (*map_print_t)  (map_impl_t *);
+typedef void     (*map_free_t)   (map_impl_t *);
+
+typedef map_iter_t * (*map_iter_begin_t) (map_impl_t *, void *);
+typedef uint64_t     (*map_iter_next_t)  (map_iter_t *, void **);
+typedef void         (*map_iter_free_t)  (map_iter_t *);

 
 struct map_impl {
     map_alloc_t  alloc;
 
 struct map_impl {
     map_alloc_t  alloc;


@@ -39,6 +48,10 @@ struct map_impl {
     map_count_t  count;
     map_print_t  print;
     map_free_t   free_;
     map_count_t  count;
     map_print_t  print;
     map_free_t   free_;

+
+    map_iter_begin_t iter_begin;
+    map_iter_next_t  iter_next;
+    map_iter_free_t  iter_free;

 };
 
 #endif//MAP_H
 };
 
 #endif//MAP_H

diff --git a/include/murmur.h b/include/murmur.h
index 84d713580015d474a5c2d3a035b7f8cf3c9b4013..1d79652a53a4d4d3e09ce21fc877038cfb8f53c9 100644 (file)
--- a/include/murmur.h
+++ b/include/murmur.h
@@ -64,5 +64,42 @@ static inline unsigned int murmur32 (const char *key, int len)
 
 static inline unsigned int murmur32_8b (uint64_t key)
 {
 
 static inline unsigned int murmur32_8b (uint64_t key)
 {

-    return murmur32((char *)&key, 8);
+    // 'm' and 'r' are mixing constants generated offline.
+    // They're not really 'magic', they just happen to work well.
+
+    const unsigned int m = 0x5bd1e995;
+    const int r = 24;
+
+    // Initialize the hash to a 'random' value
+    unsigned int h = 8;
+
+    const unsigned char *data = (const unsigned char *)key;
+
+    uint32_t k1 = *(uint32_t *)&data;
+    data += 4;
+    uint32_t k2 = *(uint32_t *)&data;
+
+    k1 *= m; 
+    k1 ^= k1 >> r; 
+    k1 *= m; 
+
+    k2 *= m; 
+    k2 ^= k2 >> r; 
+    k2 *= m; 
+
+    // Mix 4 bytes at a time into the hash
+
+    h *= m; 
+    h ^= k1;
+    h *= m; 
+    h ^= k2;
+
+    // Do a few final mixes of the hash to ensure the last few
+    // bytes are well-incorporated.
+
+    h ^= h >> 13;
+    h *= m;
+    h ^= h >> 15;
+
+    return h;

 }
 }

diff --git a/include/skiplist.h b/include/skiplist.h
index cf70656245da2efaf8b9b82d75837a61f037bcea..8df577ab5b690281859aa92eedf65fcaafaf7636 100644 (file)
--- a/include/skiplist.h
+++ b/include/skiplist.h
@@ -6,7 +6,7 @@
 typedef struct sl skiplist_t;
 typedef struct sl_iter sl_iter_t;
 
 typedef struct sl skiplist_t;
 typedef struct sl_iter sl_iter_t;
 

-skiplist_t *sl_alloc (const datatype_t *key_type);
+skiplist_t * sl_alloc (const datatype_t *key_type);

 uint64_t sl_cas     (skiplist_t *sl, void *key, uint64_t expected_val, uint64_t new_val);
 uint64_t sl_lookup  (skiplist_t *sl, void *key);
 uint64_t sl_remove  (skiplist_t *sl, void *key);
 uint64_t sl_cas     (skiplist_t *sl, void *key, uint64_t expected_val, uint64_t new_val);
 uint64_t sl_lookup  (skiplist_t *sl, void *key);
 uint64_t sl_remove  (skiplist_t *sl, void *key);


@@ -15,14 +15,14 @@ void     sl_print   (skiplist_t *sl);
 void     sl_free    (skiplist_t *sl);
 void *   sl_min_key (skiplist_t *sl);
 
 void     sl_free    (skiplist_t *sl);
 void *   sl_min_key (skiplist_t *sl);
 

-sl_iter_t *sl_iter_start (skiplist_t *sl, void *key);
-sl_iter_t *sl_iter_next  (sl_iter_t *iter);
-uint64_t   sl_iter_val   (sl_iter_t *iter);
-void *     sl_iter_key   (sl_iter_t *iter);
+sl_iter_t * sl_iter_begin (skiplist_t *sl, void *key);
+uint64_t    sl_iter_next  (sl_iter_t *iter, void **key_ptr);
+void        sl_iter_free  (sl_iter_t *iter);

 
 static const map_impl_t sl_map_impl = { 
     (map_alloc_t)sl_alloc, (map_cas_t)sl_cas, (map_get_t)sl_lookup, (map_remove_t)sl_remove, 
 
 static const map_impl_t sl_map_impl = { 
     (map_alloc_t)sl_alloc, (map_cas_t)sl_cas, (map_get_t)sl_lookup, (map_remove_t)sl_remove, 

-    (map_count_t)sl_count, (map_print_t)sl_print, (map_free_t)sl_free
+    (map_count_t)sl_count, (map_print_t)sl_print, (map_free_t)sl_free, (map_iter_begin_t)sl_iter_begin,
+    (map_iter_next_t)sl_iter_next, (map_iter_free_t)sl_iter_free

 };
 
 #endif//SKIPLIST_H
 };
 
 #endif//SKIPLIST_H

diff --git a/include/txn.h b/include/txn.h
index fc6b6912e0eb464abeacedb4c1b269981a7f9975..339a3e5a3b292fcd5ab5b5f567d434cfef4caba7 100644 (file)
--- a/include/txn.h
+++ b/include/txn.h
@@ -7,18 +7,17 @@
 
 #include "map.h"
 
 
 #include "map.h"
 

-typedef enum { TXN_REPEATABLE_READ, TXN_READ_COMMITTED, TXN_READ_ONLY  } txn_type_e;

 typedef enum { TXN_RUNNING, TXN_VALIDATING, TXN_VALIDATED, TXN_ABORTED } txn_state_e;
 
 typedef struct txn txn_t;
 
 void txn_init (void);
 
 typedef enum { TXN_RUNNING, TXN_VALIDATING, TXN_VALIDATED, TXN_ABORTED } txn_state_e;
 
 typedef struct txn txn_t;
 
 void txn_init (void);
 

-txn_t *     txn_begin  (txn_type_e type, map_t *map);
+txn_t *     txn_begin  (map_t *map);

 void        txn_abort  (txn_t *txn);
 txn_state_e txn_commit (txn_t *txn);
 
 void        txn_abort  (txn_t *txn);
 txn_state_e txn_commit (txn_t *txn);
 

-uint64_t    tm_get (txn_t *txn, void *key);
-void        tm_set (txn_t *txn, void *key, uint64_t value);
+uint64_t    txn_map_get (txn_t *txn, void *key);
+void        txn_map_set (txn_t *txn, void *key, uint64_t value);

 
 #endif//TXN_H
 
 #endif//TXN_H

diff --git a/map/hashtable.c b/map/hashtable.c
index b4d7a5de3976db050fa9cf89a6c84b833b79fe24..a853b4ca37202455388e8e246a8f2801aa90afab 100644 (file)
--- a/map/hashtable.c
+++ b/map/hashtable.c
@@ -447,7 +447,7 @@ int hti_help_copy (hti_t *hti) {
     int x = hti->copy_scan; 
 
     TRACE("h1", "ht_cas: help copy. scan is %llu, size is %llu", x, 1<<hti->scale);
     int x = hti->copy_scan; 
 
     TRACE("h1", "ht_cas: help copy. scan is %llu, size is %llu", x, 1<<hti->scale);

-    if (total_copied == (1 << hti->scale)) {
+    if (total_copied != (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) {


@@ -464,8 +464,8 @@ int hti_help_copy (hti_t *hti) {
         } else {
             TRACE("h1", "ht_cas: help copy panic", 0, 0);
             // scan the whole table
         } else {
             TRACE("h1", "ht_cas: help copy panic", 0, 0);
             // scan the whole table

-            limit = (1 << hti->scale);

             ent = hti->table;
             ent = hti->table;

+            limit = (1 << hti->scale);

         }
 
         // Copy the entries
         }
 
         // Copy the entries


@@ -588,7 +588,8 @@ void ht_print (hashtable_t *ht) {
     }
 }
 
     }
 }
 

-ht_iter_t *ht_iter_start (hashtable_t *ht, void *key) {
+ht_iter_t *ht_iter_begin (hashtable_t *ht, void *key) {
+    assert(key == NULL);

     hti_t *hti = ht->hti;
     int rcount;
     do {
     hti_t *hti = ht->hti;
     int rcount;
     do {


@@ -613,44 +614,36 @@ ht_iter_t *ht_iter_start (hashtable_t *ht, void *key) {
     return iter;
 }
 
     return iter;
 }
 

-ht_iter_t *ht_iter_next (ht_iter_t *iter) {
+uint64_t ht_iter_next (ht_iter_t *iter, void **key_ptr) {

     volatile entry_t *ent;
     uint64_t key;
     uint64_t val;
     uint64_t table_size = (1 << iter->hti->scale);
     do {
     volatile entry_t *ent;
     uint64_t key;
     uint64_t val;
     uint64_t table_size = (1 << iter->hti->scale);
     do {

-        if (++iter->idx == table_size) {
-            ht_iter_free(iter);
-            return NULL;
+        iter->idx++;
+        if (iter->idx == table_size) {
+            return DOES_NOT_EXIST;

         }
         }

-        ent = &iter->hti->table[++iter->idx];
+        ent = &iter->hti->table[iter->idx];

         key = ent->key;
         val = ent->val;
 
     } while (key == DOES_NOT_EXIST || val == DOES_NOT_EXIST || val == TOMBSTONE);
 
         key = ent->key;
         val = ent->val;
 
     } while (key == DOES_NOT_EXIST || val == DOES_NOT_EXIST || val == TOMBSTONE);
 

-    iter->key = key;
+    if (key_ptr) {
+        *key_ptr = (void *)key;
+    }

     if (val == COPIED_VALUE) {
         uint32_t hash = (iter->hti->ht->key_type == NULL) 
                       ? murmur32_8b(key)
                       : iter->hti->ht->key_type->hash((void *)key);
     if (val == COPIED_VALUE) {
         uint32_t hash = (iter->hti->ht->key_type == NULL) 
                       ? murmur32_8b(key)
                       : iter->hti->ht->key_type->hash((void *)key);

-        iter->val = hti_get(iter->hti->next, (void *)ent->key, hash);
-    } else {
-        iter->val = val;
-    }
+        val = hti_get(iter->hti->next, (void *)ent->key, hash);
+    } 

 
 

-    return iter;
-}
-
-uint64_t ht_iter_val (ht_iter_t *iter) {
-    return iter->val;
-}
-
-uint64_t ht_iter_key (ht_iter_t *iter) {
-    return iter->key;
+    return val;

 }
 
 void ht_iter_free (ht_iter_t *iter) {
     SYNC_ADD(&iter->hti->references, -1);
 }
 
 void ht_iter_free (ht_iter_t *iter) {
     SYNC_ADD(&iter->hti->references, -1);

+    nbd_free(iter);

 }
 }

-

diff --git a/map/list.c b/map/list.c
index 9e66787c2be4ef54c4c9b043b691b203d71d820f..f2e9c82c0e65fe85888721bed1145947af79ef73 100644 (file)
--- a/map/list.c
+++ b/map/list.c
@@ -307,29 +307,29 @@ void ll_print (list_t *ll) {
     printf("\n");
 }
 
     printf("\n");
 }
 

-ll_iter_t *ll_iter_start (list_t *ll, void *key) {
-    node_t *item;
-    find_pred(NULL, &item, ll, key, FALSE);
-    return item;
+ll_iter_t *ll_iter_begin (list_t *ll, void *key) {
+    node_t *iter = node_alloc(0,0);
+    find_pred(NULL, &iter->next, ll, key, FALSE);
+    return iter;

 }
 
 }
 

-ll_iter_t *ll_iter_next (ll_iter_t *iter) {
+uint64_t ll_iter_next (ll_iter_t *iter, void **key_ptr) {

     assert(iter);
     assert(iter);

-    if (EXPECT_FALSE(!iter))
-        return NULL;
-
-    node_t *next = iter->next;
-    while (next != NULL && IS_TAGGED(next->next, TAG1)) {
-        next = (node_t *)STRIP_TAG(next->next, TAG1);
+    node_t *item = iter->next;
+    while (item != NULL && IS_TAGGED(item->next, TAG1)) {
+        item = (node_t *)STRIP_TAG(item->next, TAG1);

     }
     }

-
-    return next;
-}
-
-uint64_t ll_iter_val (ll_iter_t *iter) {
-    return iter->val;
+    if (item == NULL) {
+        iter->next = NULL;
+        return DOES_NOT_EXIST;
+    }
+    iter->next = item->next;
+    if (key_ptr != NULL) {
+        *key_ptr = item->key;
+    }
+    return item->val;

 }
 
 }
 

-void *ll_iter_key (ll_iter_t *iter) {
-    return iter->key;
+void ll_iter_free (ll_iter_t *iter) {
+    nbd_free(iter);

 }
 }

diff --git a/map/map.c b/map/map.c
index 0db50bdbcd3185ee275089f2ea6aef97b301fa4d..fcd9f830c438240568543865a96f3ac0f9fc2f77 100644 (file)
--- a/map/map.c
+++ b/map/map.c
@@ -14,6 +14,11 @@ struct map {
     void *data;
 };
 
     void *data;
 };
 

+struct map_iter {
+    const map_impl_t *impl;
+    void *state;
+};
+

 map_t *map_alloc (const map_impl_t *map_impl, const datatype_t *key_type) { 
     map_t *map = nbd_malloc(sizeof(map_t)); 
     map->impl  = map_impl;
 map_t *map_alloc (const map_impl_t *map_impl, const datatype_t *key_type) { 
     map_t *map = nbd_malloc(sizeof(map_t)); 
     map->impl  = map_impl;


@@ -56,3 +61,19 @@ uint64_t map_replace(map_t *map, void *key, uint64_t new_val) {
 uint64_t map_remove (map_t *map, void *key) {
     return map->impl->remove(map->data, key);
 }
 uint64_t map_remove (map_t *map, void *key) {
     return map->impl->remove(map->data, key);
 }

+
+map_iter_t * map_iter_begin (map_t *map, void *key) {
+    map_iter_t *iter = nbd_malloc(sizeof(map_iter_t));
+    iter->impl  = map->impl;
+    iter->state = map->impl->iter_begin(map->data, key);
+    return iter;
+}
+
+uint64_t map_iter_next (map_iter_t *iter, void **key_ptr) {
+    return iter->impl->iter_next(iter->state, key_ptr);
+}
+
+void map_iter_free (map_iter_t *iter) {
+    iter->impl->iter_free(iter->state);
+    nbd_free(iter);
+}

diff --git a/map/skiplist.c b/map/skiplist.c
index 16f7538b9d3f3304d885bf1fb944bea6b2129bb9..1f608b47700d2352faaf57acbb094bd70f4e2bb0 100644 (file)
--- a/map/skiplist.c
+++ b/map/skiplist.c
@@ -475,29 +475,29 @@ void sl_print (skiplist_t *sl) {
     }
 }
 
     }
 }
 

-sl_iter_t *sl_iter_start (skiplist_t *sl, void *key) {
-    node_t *item;
-    find_preds(NULL, &item, 0, sl, key, FALSE);
-    return item;
+sl_iter_t *sl_iter_begin (skiplist_t *sl, void *key) {
+    node_t *iter = node_alloc(0, 0, 0);
+    find_preds(NULL, &iter->next[0], 0, sl, key, FALSE);
+    return iter;

 }
 
 }
 

-sl_iter_t *sl_iter_next (sl_iter_t *iter) {
+uint64_t sl_iter_next (sl_iter_t *iter, void **key_ptr) {

     assert(iter);
     assert(iter);

-    if (EXPECT_FALSE(!iter))
-        return NULL;
-
-    node_t *next = iter->next[0];
-    while (next != NULL && IS_TAGGED(next->next[0], TAG1)) {
-        next = (node_t *)STRIP_TAG(next->next[0], TAG1);
+    node_t *item = iter->next[0];
+    while (item != NULL && IS_TAGGED(item->next[0], TAG1)) {
+        item = (node_t *)STRIP_TAG(item->next[0], TAG1);

     }
     }

-
-    return next;
-}
-
-uint64_t sl_iter_val (sl_iter_t *iter) {
-    return iter->val;
+    if (item == NULL) {
+        iter->next[0] = NULL;
+        return DOES_NOT_EXIST;
+    }
+    iter->next[0] = item->next[0];
+    if (key_ptr != NULL) {
+        *key_ptr = item->key;
+    }
+    return item->val;

 }
 
 }
 

-void *sl_iter_key (sl_iter_t *iter) {
-    return iter->key;
+void sl_iter_free (sl_iter_t *iter) {
+    nbd_free(iter);

 }
 }

diff --git a/test/map_test1.c b/test/map_test1.c
index 6639359c69340c497b97bc5d3c56e15ca9ad08ca..f380918944c88ab6b1e9ee3b2abc5cc44e9554ae 100644 (file)
--- a/test/map_test1.c
+++ b/test/map_test1.c
@@ -13,7 +13,7 @@
 
 #define NUM_ITERATIONS 10000000
 
 
 #define NUM_ITERATIONS 10000000
 

-#define TEST_STRING_KEYS
+//#define TEST_STRING_KEYS

 
 static volatile int wait_;
 static long num_threads_;
 
 static volatile int wait_;
 static long num_threads_;

diff --git a/test/map_test2.c b/test/map_test2.c
index 51b17b3f10cbf7f75eabdb8cbc7ea1260198f216..1ba4e42b91e75faa510a255b6df255684025bdb7 100644 (file)
--- a/test/map_test2.c
+++ b/test/map_test2.c
@@ -19,7 +19,7 @@
 
 #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
 
 
 #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
 

-#define TEST_STRING_KEYS
+//#define TEST_STRING_KEYS

 
 typedef struct worker_data {
     int id;
 
 typedef struct worker_data {
     int id;


@@ -30,8 +30,18 @@ typedef struct worker_data {
 
 static const map_impl_t *map_type_;
 
 
 static const map_impl_t *map_type_;
 

+static uint64_t iterator_size (map_t *map) {
+    map_iter_t *iter = map_iter_begin(map, NULL);
+    uint64_t count = 0;
+    while (map_iter_next(iter, NULL) != DOES_NOT_EXIST) {
+        count++;
+    }
+    map_iter_free(iter);
+    return count;
+}
+

 // Test some basic stuff; add a few keys, remove a few keys
 // Test some basic stuff; add a few keys, remove a few keys

-void simple (CuTest* tc) {
+void basic_test (CuTest* tc) {

 
 #ifdef TEST_STRING_KEYS
     map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
 
 #ifdef TEST_STRING_KEYS
     map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);


@@ -50,29 +60,37 @@ void simple (CuTest* tc) {
     ASSERT_EQUAL( 0,              map_count  (map)        );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k1,10) );
     ASSERT_EQUAL( 1,              map_count  (map)        );
     ASSERT_EQUAL( 0,              map_count  (map)        );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k1,10) );
     ASSERT_EQUAL( 1,              map_count  (map)        );

+    ASSERT_EQUAL( 1,              iterator_size(map)      );

     ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k2,20) );
     ASSERT_EQUAL( 2,              map_count  (map)        );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k2,20) );
     ASSERT_EQUAL( 2,              map_count  (map)        );

+    ASSERT_EQUAL( 2,              iterator_size(map)      );

     ASSERT_EQUAL( 20,             map_get    (map, k2)    );
     ASSERT_EQUAL( 10,             map_set    (map, k1,11) );
     ASSERT_EQUAL( 20,             map_set    (map, k2,21) );
     ASSERT_EQUAL( 2,              map_count  (map)        );
     ASSERT_EQUAL( 20,             map_get    (map, k2)    );
     ASSERT_EQUAL( 10,             map_set    (map, k1,11) );
     ASSERT_EQUAL( 20,             map_set    (map, k2,21) );
     ASSERT_EQUAL( 2,              map_count  (map)        );

+    ASSERT_EQUAL( 2,              iterator_size(map)      );

     ASSERT_EQUAL( 21,             map_add    (map, k2,22) );
     ASSERT_EQUAL( 11,             map_remove (map, k1)    );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k1)    );
     ASSERT_EQUAL( 1,              map_count  (map)        );
     ASSERT_EQUAL( 21,             map_add    (map, k2,22) );
     ASSERT_EQUAL( 11,             map_remove (map, k1)    );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k1)    );
     ASSERT_EQUAL( 1,              map_count  (map)        );

+    ASSERT_EQUAL( 1,              iterator_size(map)      );

     ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k1)    );
     ASSERT_EQUAL( 21,             map_remove (map, k2)    );
     ASSERT_EQUAL( 0,              map_count  (map)        );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k1)    );
     ASSERT_EQUAL( 21,             map_remove (map, k2)    );
     ASSERT_EQUAL( 0,              map_count  (map)        );

+    ASSERT_EQUAL( 0,              iterator_size(map)      );

     ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k2)    );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k3)    );
     ASSERT_EQUAL( 0,              map_count  (map)        );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k2)    );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k3)    );
     ASSERT_EQUAL( 0,              map_count  (map)        );

+    ASSERT_EQUAL( 0,              iterator_size(map)      );

     
     ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k4,40) );
     ASSERT_EQUAL( 40,             map_get    (map, k4)    );
     ASSERT_EQUAL( 1,              map_count  (map)        );
     
     ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k4,40) );
     ASSERT_EQUAL( 40,             map_get    (map, k4)    );
     ASSERT_EQUAL( 1,              map_count  (map)        );

+    ASSERT_EQUAL( 1,              iterator_size(map)      );

     ASSERT_EQUAL( 40,             map_remove (map, k4)    );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k4)    );
     ASSERT_EQUAL( 0,              map_count  (map)        );
     ASSERT_EQUAL( 40,             map_remove (map, k4)    );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k4)    );
     ASSERT_EQUAL( 0,              map_count  (map)        );

+    ASSERT_EQUAL( 0,              iterator_size(map)      );

 
     ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, k4,10) );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k4)    );
 
     ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, k4,10) );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k4)    );


@@ -82,6 +100,7 @@ void simple (CuTest* tc) {
     ASSERT_EQUAL( 41,             map_remove (map, k4)    );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k4)    );
     ASSERT_EQUAL( 0,              map_count  (map)        );
     ASSERT_EQUAL( 41,             map_remove (map, k4)    );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k4)    );
     ASSERT_EQUAL( 0,              map_count  (map)        );

+    ASSERT_EQUAL( 0,              iterator_size(map)      );

 
     ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, k2,20) );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k2)    );
 
     ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, k2,20) );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k2)    );


@@ -93,11 +112,14 @@ void simple (CuTest* tc) {
     ASSERT_EQUAL( 21,             map_remove (map, k2)    );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k2)    );
     ASSERT_EQUAL( 0,              map_count  (map)        );
     ASSERT_EQUAL( 21,             map_remove (map, k2)    );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k2)    );
     ASSERT_EQUAL( 0,              map_count  (map)        );

+    ASSERT_EQUAL( 0,              iterator_size(map)      );

 
     map_free(map);
 
 
     map_free(map);
 

-    // In a quiecent state; it is safe to free.
-    rcu_update();
+    rcu_update(); // In a quiecent state.
+#ifdef TEST_STRING_KEYS
+    nbd_free(k1); nbd_free(k2); nbd_free(k3); nbd_free(k4);
+#endif

 }
 
 void *add_remove_worker (void *arg) {
 }
 
 void *add_remove_worker (void *arg) {


@@ -125,8 +147,8 @@ void *add_remove_worker (void *arg) {
             key = (void *)i;
 #endif
             TRACE("t0", "test map_add() iteration (%llu, %llu)", j, i);
             key = (void *)i;
 #endif
             TRACE("t0", "test map_add() iteration (%llu, %llu)", j, i);

-            CuAssertIntEquals_Msg(tc, (void *)i, DOES_NOT_EXIST, map_add(map, key, d+1) );
-            rcu_update();
+            ASSERT_EQUAL(DOES_NOT_EXIST, map_add(map, key, d+1) );
+            rcu_update(); // In a quiecent state.

         }
         for (uint64_t i = d+1; i < iters; i+=2) {
 #ifdef TEST_STRING_KEYS
         }
         for (uint64_t i = d+1; i < iters; i+=2) {
 #ifdef TEST_STRING_KEYS


@@ -136,15 +158,15 @@ void *add_remove_worker (void *arg) {
             key = (void *)i;
 #endif
             TRACE("t0", "test map_remove() iteration (%llu, %llu)", j, i);
             key = (void *)i;
 #endif
             TRACE("t0", "test map_remove() iteration (%llu, %llu)", j, i);

-            CuAssertIntEquals_Msg(tc, (void *)i, d+1, map_remove(map, key) );
-            rcu_update();
+            ASSERT_EQUAL(d+1, map_remove(map, key) );
+            rcu_update(); // In a quiecent state.

         }
     }
     return NULL;
 }
 
 // Do some simple concurrent testing
         }
     }
     return NULL;
 }
 
 // Do some simple concurrent testing

-void add_remove (CuTest* tc) {
+void concurrent_add_remove_test (CuTest* tc) {

 
     pthread_t thread[2];
     worker_data_t wd[2];
 
     pthread_t thread[2];
     worker_data_t wd[2];


@@ -181,20 +203,101 @@ void add_remove (CuTest* tc) {
 
     // In the end, all members should be removed
     ASSERT_EQUAL( 0, map_count(map) );
 
     // In the end, all members should be removed
     ASSERT_EQUAL( 0, map_count(map) );

+    ASSERT_EQUAL( 0, iterator_size(map) );

 
     // In a quiecent state; it is safe to free.
     map_free(map);
 }
 
 
     // In a quiecent state; it is safe to free.
     map_free(map);
 }
 

-void *inserter_worker (void *arg) {
-    //pthread_t thread[NUM_THREADS];
+void basic_iteration_test (CuTest* tc) {
+#ifdef TEST_STRING_KEYS
+    map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
+    nstring_t *k1 = ns_alloc(3); strcpy(k1->data, "k1");
+    nstring_t *k2 = ns_alloc(3); strcpy(k1->data, "k2");
+    nstring_t *x_k;
+    nstring_t *y_k;
+#else
+    map_t *map = map_alloc(map_type_, NULL);
+    void *k1 = (void *)1;
+    void *k2 = (void *)2;
+    void *x_k;
+    void *y_k;
+#endif

 
 

-    //map_t *map = map_alloc(map_type_);
-    return NULL;
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k1,1) );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k2,2) );
+
+    uint64_t x_v, y_v;
+    map_iter_t *iter = map_iter_begin(map, NULL);
+    x_v = map_iter_next(iter, &x_k);
+    y_v = map_iter_next(iter, &y_k);
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_iter_next(iter, NULL) );
+    map_iter_free(iter);
+#ifdef TEST_STRING_KEYS
+    ASSERT_EQUAL( TRUE, (ns_cmp(x_k, k1) == 0 && x_v == 1) || (ns_cmp(y_k, k1) == 0 && y_v == 1) );
+    ASSERT_EQUAL( TRUE, (ns_cmp(x_k, k2) == 0 && x_v == 2) || (ns_cmp(y_k, k2) == 0 && y_v == 2) );
+    nbd_free(k1);
+    nbd_free(k2);
+#else
+    ASSERT_EQUAL( TRUE, (x_k == k1 && x_v == 1) || (y_k == k1 && y_v == 1) );
+    ASSERT_EQUAL( TRUE, (x_k == k2 && x_v == 2) || (y_k == k2 && y_v == 2) );
+#endif
+
+    map_free(map);

 }
 
 }
 

-// Concurrent insertion
-void concurrent_insert (CuTest* tc) {
+void big_iteration_test (CuTest* tc) {
+    static const int n = 10000;
+    
+#ifdef TEST_STRING_KEYS
+    map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
+    nstring_t *key = ns_alloc(9);
+    nstring_t *k3 = ns_alloc(3); strcpy(k1->data, "k3");
+    nstring_t *k4 = ns_alloc(3); strcpy(k1->data, "k4");
+#else
+    map_t *map = map_alloc(map_type_, NULL);
+    void *k3 = (void *)3;
+    void *k4 = (void *)4;
+    void *key;
+#endif
+
+    for (size_t i = 1; i <= n; ++i) {
+#ifdef TEST_STRING_KEYS
+        memset(key->data, 0, key->len);
+        snprintf(key->data, key->len, "k%llu", i);
+#else
+        key = (void *)i;
+#endif
+        ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, key)    );
+        ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map, key, i) );
+        ASSERT_EQUAL( i,              map_get(map, key)    );
+        rcu_update(); // In a quiecent state.
+    }
+
+    ASSERT_EQUAL( n, map_count(map) );
+    ASSERT_EQUAL( n, iterator_size(map) );
+
+    uint64_t sum = 0;
+    uint64_t val;
+    map_iter_t *iter = map_iter_begin(map, NULL);
+    while ((val = map_iter_next(iter, NULL)) != DOES_NOT_EXIST) {
+        sum += val;
+    }
+    map_iter_free(iter);
+    ASSERT_EQUAL(n*(n+1)/2, sum);
+    ASSERT_EQUAL(3, map_remove(map, k3));
+    ASSERT_EQUAL(4, map_remove(map, k4));
+    sum = 0;
+    iter = map_iter_begin(map, NULL);
+    while ((val = map_iter_next(iter, NULL)) != DOES_NOT_EXIST) {
+        sum += val;
+    }
+    map_iter_free(iter);
+    ASSERT_EQUAL(n*(n+1)/2 - (3+4), sum);
+        
+#ifdef TEST_STRING_KEYS
+    nbd_free(key);
+#endif

 }
 
 int main (void) {
 }
 
 int main (void) {


@@ -210,8 +313,10 @@ int main (void) {
         CuString *output = CuStringNew();
         CuSuite* suite = CuSuiteNew();
 
         CuString *output = CuStringNew();
         CuSuite* suite = CuSuiteNew();
 

-        SUITE_ADD_TEST(suite, simple);
-        SUITE_ADD_TEST(suite, add_remove);
+        SUITE_ADD_TEST(suite, basic_test);
+        SUITE_ADD_TEST(suite, concurrent_add_remove_test);
+        SUITE_ADD_TEST(suite, basic_iteration_test);
+        SUITE_ADD_TEST(suite, big_iteration_test);

 
         CuSuiteRun(suite);
         CuSuiteDetails(suite, output);
 
         CuSuiteRun(suite);
         CuSuiteDetails(suite, output);

diff --git a/test/txn_test.c b/test/txn_test.c
index b721f2d8a353699b27209bc0411842406693cc48..80b8f93dd3dd8550a33673b1a1a774828a985c8c 100644 (file)
--- a/test/txn_test.c
+++ b/test/txn_test.c
@@ -11,15 +11,15 @@
 
 void test1 (CuTest* tc) {
     map_t *map = map_alloc(&ht_map_impl, NULL);
 
 void test1 (CuTest* tc) {
     map_t *map = map_alloc(&ht_map_impl, NULL);

-    txn_t *t1 = txn_begin(TXN_REPEATABLE_READ, map);
-    txn_t *t2 = txn_begin(TXN_REPEATABLE_READ, map);
+    txn_t *t1 = txn_begin(map);
+    txn_t *t2 = txn_begin(map);

     void *k1 = (void *)1;
     void *k1 = (void *)1;

-    tm_set(t1, k1, 2);
-    tm_set(t1, k1, 3);
-    ASSERT_EQUAL( DOES_NOT_EXIST, tm_get(t2, k1) );
-    tm_set(t2, k1, 4);
-    ASSERT_EQUAL( 3, tm_get(t1, k1) );
-    ASSERT_EQUAL( 4, tm_get(t2, k1) );
+    txn_map_set(t1, k1, 2);
+    txn_map_set(t1, k1, 3);
+    ASSERT_EQUAL( DOES_NOT_EXIST, txn_map_get(t2, k1) );
+    txn_map_set(t2, k1, 4);
+    ASSERT_EQUAL( 3, txn_map_get(t1, k1) );
+    ASSERT_EQUAL( 4, txn_map_get(t2, k1) );

     ASSERT_EQUAL( TXN_VALIDATED, txn_commit(t2));
     ASSERT_EQUAL( TXN_ABORTED,   txn_commit(t1));
 }
     ASSERT_EQUAL( TXN_VALIDATED, txn_commit(t2));
     ASSERT_EQUAL( TXN_ABORTED,   txn_commit(t1));
 }

diff --git a/todo b/todo
index fef96ad708dcd519b509fc24aa57d360c70858b6..807a31a35e9d2131743fe711675ed4a6f6bd046a 100644 (file)
--- a/todo
+++ b/todo
@@ -1,17 +1,26 @@
-- make rcu try yielding when its buffer gets full, instead of throwing an assert

 + fix makefile to compute dependency info as a side-effect of compilation (-MF)
 + fix makefile to compute dependency info as a side-effect of compilation (-MF)

-- investigate 16 byte CAS; ht can store GUIDs inline instead of pointers to actual keys 
-- testing, testing, testing

 + support integer keys for ht
 + support integer keys for ht

-- validate arguments to interface functions

 + optimize tracing code, still too much overhead
 + use NULL instead of a sentinal node in skiplist and list
 + make the interfaces for all data structures consistent 
 + make list and skiplist use string keys
 + optimize integer keys
 + ht_print()
 + optimize tracing code, still too much overhead
 + use NULL instead of a sentinal node in skiplist and list
 + make the interfaces for all data structures consistent 
 + make list and skiplist use string keys
 + optimize integer keys
 + ht_print()

-- iterators
-- characterize performance of data structures
-- experiment with the performance impact of not passing the hash between functions
-- experiment with embedding keys in the list/skiplist nodes
++ iterators
+- make rcu yield when its buffer gets full instead of throwing an assert
+- alternate memory reclamation schemes, hazard pointers and/or reference count
+- investigate 16 byte CAS; ht can store GUIDs inline instead of pointers to actual keys 
+- document usage
+- document algorithms
+- port tests from lib-high-scale
+- 32 bit version of hashtable
+- verify list and skiplist work on 32 bit platforms
+- transaction tests
+- validate the arguments to interface functions
+- shortcut from write-set to entries/nodes
+- use a shared scan for write-set validation, similar to ht copy logic
+- characterize the performance of hashtable, list and skiplist
+- experiment with the performance impact of not passing the hash between functions in ht
+- experiment with embedding the keys in the list/skiplist nodes

 - allow values of 0 to be inserted into maps (change DOES_NOT_EXIST to something else)
 - allow values of 0 to be inserted into maps (change DOES_NOT_EXIST to something else)

+- see if it's possible to rename nbd_malloc to malloc

diff --git a/txn/txn.c b/txn/txn.c
index 26e0209408c4c6a72ceda7916fcec3634d12197b..bb304b3921fe40a86c25715059b3524e52481f01 100644 (file)
--- a/txn/txn.c
+++ b/txn/txn.c
@@ -32,7 +32,6 @@ struct txn {
     uint32_t writes_size;
     uint32_t writes_count;
     uint32_t writes_scan;
     uint32_t writes_size;
     uint32_t writes_count;
     uint32_t writes_scan;

-    txn_type_e type;

     txn_state_e state;
 };
 
     txn_state_e state;
 };
 


@@ -52,7 +51,7 @@ void txn_init (void) {
 // If we encounter a potential conflict with a transaction that is in the process of validating, we help it 
 // complete validating. It must be finished before we can decide to rollback or commit.
 //
 // If we encounter a potential conflict with a transaction that is in the process of validating, we help it 
 // complete validating. It must be finished before we can decide to rollback or commit.
 //

-static txn_state_e tm_validate_key (txn_t *txn, void *key) {
+static txn_state_e validate_key (txn_t *txn, void *key) {

     assert(txn->state != TXN_RUNNING);
     
     update_t *update = (update_t *) map_get(txn->map, key);
     assert(txn->state != TXN_RUNNING);
     
     update_t *update = (update_t *) map_get(txn->map, key);


@@ -123,7 +122,7 @@ static txn_state_e txn_validate (txn_t *txn) {
             }
 
             for (i = 0; i < txn->writes_count; ++i) {
             }
 
             for (i = 0; i < txn->writes_count; ++i) {

-                txn_state_e s = tm_validate_key(txn, txn->writes[i].key);
+                txn_state_e s = validate_key(txn, txn->writes[i].key);

                 if (s == TXN_ABORTED) {
                     txn->state = TXN_ABORTED;
                     break;
                 if (s == TXN_ABORTED) {
                     txn->state = TXN_ABORTED;
                     break;


@@ -152,17 +151,14 @@ static update_t *alloc_update_rec (void) {
     return u;
 }
 
     return u;
 }
 

-txn_t *txn_begin (txn_type_e type, map_t *map) {
+txn_t *txn_begin (map_t *map) {

     txn_t *txn = (txn_t *)nbd_malloc(sizeof(txn_t));
     memset(txn, 0, sizeof(txn_t));
     txn_t *txn = (txn_t *)nbd_malloc(sizeof(txn_t));
     memset(txn, 0, sizeof(txn_t));

-    txn->type = type;

     txn->wv = UNDETERMINED_VERSION;
     txn->state = TXN_RUNNING;
     txn->map = map;
     txn->wv = UNDETERMINED_VERSION;
     txn->state = TXN_RUNNING;
     txn->map = map;

-    if (type != TXN_READ_ONLY) {
-        txn->writes = nbd_malloc(sizeof(*txn->writes) * INITIAL_WRITES_SIZE);
-        txn->writes_size = INITIAL_WRITES_SIZE;
-    }
+    txn->writes = nbd_malloc(sizeof(*txn->writes) * INITIAL_WRITES_SIZE);
+    txn->writes_size = INITIAL_WRITES_SIZE;

 
     // acquire the read version for txn. must be careful to avoid a race
     do {
 
     // acquire the read version for txn. must be careful to avoid a race
     do {


@@ -237,7 +233,7 @@ txn_state_e txn_commit (txn_t *txn) {
 }
 
 // Get most recent committed version prior to our read version.
 }
 
 // Get most recent committed version prior to our read version.

-uint64_t tm_get (txn_t *txn, void *key) {
+uint64_t txn_map_get (txn_t *txn, void *key) {

     if (txn->state != TXN_RUNNING)
         return ERROR_TXN_NOT_RUNNING;
 
     if (txn->state != TXN_RUNNING)
         return ERROR_TXN_NOT_RUNNING;
 


@@ -349,7 +345,7 @@ uint64_t tm_get (txn_t *txn, void *key) {
     return value;
 }
 
     return value;
 }
 

-void tm_set (txn_t *txn, void *key, uint64_t value) {
+void txn_map_set (txn_t *txn, void *key, uint64_t value) {

     if (txn->state != TXN_RUNNING)
         return; // TODO: return some sort of error code
 
     if (txn->state != TXN_RUNNING)
         return; // TODO: return some sort of error code