introduce some more typedefs and conversion functions to improve portability

diff --git a/include/common.h b/include/common.h
index 9abf743face43c88fd48a0be811ced272819e56b..a799eac3d6f253b4b4d326d8a57600447d224ecf 100644 (file)
--- a/include/common.h
+++ b/include/common.h
@@ -48,5 +48,7 @@ typedef unsigned long long uint64_t;
 typedef unsigned int       uint32_t;
 typedef unsigned char      uint8_t;
 
 typedef unsigned int       uint32_t;
 typedef unsigned char      uint8_t;
 

+typedef uint64_t markable_t;
+

 #include "lwt.h"
 #endif //COMMON_H
 #include "lwt.h"
 #endif //COMMON_H

diff --git a/include/hashtable.h b/include/hashtable.h
index 880f2a49dea90a11f5cfaa23fc6e44982ed4977d..3fb5d6cff3ff3844a1d367e31208a139ffba3c30 100644 (file)
--- a/include/hashtable.h
+++ b/include/hashtable.h
@@ -7,15 +7,15 @@ typedef struct ht hashtable_t;
 typedef struct ht_iter ht_iter_t;
 
 hashtable_t * ht_alloc (const datatype_t *key_type);
 typedef struct ht_iter ht_iter_t;
 
 hashtable_t * ht_alloc (const datatype_t *key_type);

-uint64_t ht_cas    (hashtable_t *ht, map_key_t key, uint64_t expected_val, uint64_t val);
-uint64_t ht_get    (hashtable_t *ht, map_key_t key);
-uint64_t ht_remove (hashtable_t *ht, map_key_t key);
-uint64_t ht_count  (hashtable_t *ht);
-void     ht_print  (hashtable_t *ht);
-void     ht_free   (hashtable_t *ht);
+map_val_t ht_cas    (hashtable_t *ht, map_key_t key, map_val_t expected_val, map_val_t val);
+map_val_t ht_get    (hashtable_t *ht, map_key_t key);
+map_val_t ht_remove (hashtable_t *ht, map_key_t key);
+size_t    ht_count  (hashtable_t *ht);
+void      ht_print  (hashtable_t *ht);
+void      ht_free   (hashtable_t *ht);

 
 ht_iter_t * ht_iter_begin (hashtable_t *ht, map_key_t key);
 
 ht_iter_t * ht_iter_begin (hashtable_t *ht, map_key_t key);

-uint64_t    ht_iter_next  (ht_iter_t *iter, map_key_t *key_ptr);
+map_val_t   ht_iter_next  (ht_iter_t *iter, map_key_t *key_ptr);

 void        ht_iter_free  (ht_iter_t *iter);
 
 static const map_impl_t ht_map_impl = { 
 void        ht_iter_free  (ht_iter_t *iter);
 
 static const map_impl_t ht_map_impl = { 

diff --git a/include/list.h b/include/list.h
index 7eb815e95b9fa08caa2e2d6dd1643654fb53a7ba..0274066c731a1b42eeb9b8a63f8f4a336c8f3249 100644 (file)
--- a/include/list.h
+++ b/include/list.h
@@ -10,7 +10,7 @@ list_t *   ll_alloc   (const datatype_t *key_type);
 map_val_t  ll_cas     (list_t *ll, map_key_t key, map_val_t expected_val, map_val_t new_val);
 map_val_t  ll_lookup  (list_t *ll, map_key_t key);
 map_val_t  ll_remove  (list_t *ll, map_key_t key);
 map_val_t  ll_cas     (list_t *ll, map_key_t key, map_val_t expected_val, map_val_t new_val);
 map_val_t  ll_lookup  (list_t *ll, map_key_t key);
 map_val_t  ll_remove  (list_t *ll, map_key_t key);

-map_val_t  ll_count   (list_t *ll);
+size_t     ll_count   (list_t *ll);

 void       ll_print   (list_t *ll);
 void       ll_free    (list_t *ll);
 map_key_t  ll_min_key (list_t *sl);
 void       ll_print   (list_t *ll);
 void       ll_free    (list_t *ll);
 map_key_t  ll_min_key (list_t *sl);

diff --git a/include/skiplist.h b/include/skiplist.h
index 5c707fc2968a5af8ef6c814cdc1fe170d58da94c..484c64caaa750236278eefd88f984e13e9b64fb2 100644 (file)
--- a/include/skiplist.h
+++ b/include/skiplist.h
@@ -10,7 +10,7 @@ skiplist_t * sl_alloc (const datatype_t *key_type);
 map_val_t  sl_cas     (skiplist_t *sl, map_key_t key, map_val_t expected_val, map_val_t new_val);
 map_val_t  sl_lookup  (skiplist_t *sl, map_key_t key);
 map_val_t  sl_remove  (skiplist_t *sl, map_key_t key);
 map_val_t  sl_cas     (skiplist_t *sl, map_key_t key, map_val_t expected_val, map_val_t new_val);
 map_val_t  sl_lookup  (skiplist_t *sl, map_key_t key);
 map_val_t  sl_remove  (skiplist_t *sl, map_key_t key);

-map_val_t  sl_count   (skiplist_t *sl);
+size_t     sl_count   (skiplist_t *sl);

 void       sl_print   (skiplist_t *sl);
 void       sl_free    (skiplist_t *sl);
 map_key_t  sl_min_key (skiplist_t *sl);
 void       sl_print   (skiplist_t *sl);
 void       sl_free    (skiplist_t *sl);
 map_key_t  sl_min_key (skiplist_t *sl);

diff --git a/makefile b/makefile
index 82d921ebd2b15365a28b456437c50cd94c42e188..6ca58432c4e992e87144f8f451f09b8bf5685a1d 100644 (file)
--- a/makefile
+++ b/makefile
@@ -43,6 +43,14 @@ $(EXES): output/% : output/%.d makefile
        gcc $(CFLAGS:-combine:) $(INCS) -MM -MT $@ $($*_SRCS) > $@.d
        gcc $(CFLAGS) $(INCS) -o $@ $($*_SRCS)
 
        gcc $(CFLAGS:-combine:) $(INCS) -MM -MT $@ $($*_SRCS) > $@.d
        gcc $(CFLAGS) $(INCS) -o $@ $($*_SRCS)
 

+asm: $(addsuffix .s, $(EXES))
+
+$(addsuffix .s, $(EXES)): output/%.s : output/%.d makefile
+       gcc $(CFLAGS:-combine:) $(INCS) -MM -MT $@ $($*_SRCS) > output/$*.d
+       gcc $(CFLAGS) $(INCS) -S -o $@.temp $($*_SRCS)
+       grep -v "^L[BFM]\|^LCF" $@.temp > $@
+       rm $@.temp
+

 ###################################################################################################
 # tags file for vi
 ###################################################################################################
 ###################################################################################################
 # tags file for vi
 ###################################################################################################


@@ -62,4 +70,4 @@ $(addsuffix .d, $(EXES)) : output/%.d :
 
 -include $(addsuffix .d, $(EXES))
 
 
 -include $(addsuffix .d, $(EXES))
 

-.PHONY: clean test tags
+.PHONY: clean test tags asm

diff --git a/map/hashtable.c b/map/hashtable.c
index a757cfc928633f91c8e0ff54f3699057495dbbd3..b229d431eab0504228182c295d44f63f4b4d6c26 100644 (file)
--- a/map/hashtable.c
+++ b/map/hashtable.c
@@ -18,10 +18,10 @@
 #include "mem.h"
 #include "hashtable.h"
 
 #include "mem.h"
 #include "hashtable.h"
 

-#define GET_PTR(x) ((void *)(size_t)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t
+#define GET_PTR(x) ((void *)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t

 
 typedef struct entry {
 
 typedef struct entry {

-    uint64_t  key;
+    map_key_t key;

     map_val_t val;
 } entry_t;
 
     map_val_t val;
 } entry_t;
 


@@ -87,7 +87,7 @@ static volatile entry_t *hti_lookup (hti_t *hti, map_key_t key, uint32_t key_has
         for (int j = 0; j < ENTRIES_PER_BUCKET; ++j) {
             volatile entry_t *ent = bucket + ((ndx + j) & (ENTRIES_PER_BUCKET-1));
 
         for (int j = 0; j < ENTRIES_PER_BUCKET; ++j) {
             volatile entry_t *ent = bucket + ((ndx + j) & (ENTRIES_PER_BUCKET-1));
 

-            uint64_t ent_key = ent->key;
+            map_key_t ent_key = ent->key;

             if (ent_key == DOES_NOT_EXIST) {
                 TRACE("h1", "hti_lookup: entry %p for key %p is empty", ent, 
                             (hti->ht->key_type == NULL) ? (void *)ent_key : GET_PTR(ent_key));
             if (ent_key == DOES_NOT_EXIST) {
                 TRACE("h1", "hti_lookup: entry %p for key %p is empty", ent, 
                             (hti->ht->key_type == NULL) ? (void *)ent_key : GET_PTR(ent_key));


@@ -98,7 +98,7 @@ static volatile entry_t *hti_lookup (hti_t *hti, map_key_t key, uint32_t key_has
             // Compare <key> with the key in the entry. 
             if (EXPECT_TRUE(hti->ht->key_type == NULL)) {
                 // fast path for integer keys
             // Compare <key> with the key in the entry. 
             if (EXPECT_TRUE(hti->ht->key_type == NULL)) {
                 // fast path for integer keys

-                if (ent_key == (uint64_t)key) {
+                if (ent_key == key) {

                     TRACE("h1", "hti_lookup: found entry %p with key %p", ent, ent_key);
                     return ent;
                 }
                     TRACE("h1", "hti_lookup: found entry %p with key %p", ent, ent_key);
                     return ent;
                 }


@@ -107,7 +107,7 @@ static volatile entry_t *hti_lookup (hti_t *hti, map_key_t key, uint32_t key_has
                 // high-order 16 bits are taken from the hash. The bits from the hash are used as a
                 // quick check to rule out non-equal keys without doing a complete compare.
                 if ((key_hash >> 16) == (ent_key >> 48)) {
                 // high-order 16 bits are taken from the hash. The bits from the hash are used as a
                 // quick check to rule out non-equal keys without doing a complete compare.
                 if ((key_hash >> 16) == (ent_key >> 48)) {

-                    if (hti->ht->key_type->cmp(GET_PTR(ent_key), (void *)(size_t)key) == 0) {
+                    if (hti->ht->key_type->cmp(GET_PTR(ent_key), (void *)key) == 0) {

                         TRACE("h1", "hti_lookup: found entry %p with key %p", ent, GET_PTR(ent_key));
                         return ent;
                     }
                         TRACE("h1", "hti_lookup: found entry %p with key %p", ent, GET_PTR(ent_key));
                         return ent;
                     }


@@ -157,7 +157,7 @@ static void hti_start_copy (hti_t *hti) {
     TRACE("h0", "hti_start_copy(hti %p scale %llu)", hti, hti->scale);
 
     // heuristics to determine the size of the new table
     TRACE("h0", "hti_start_copy(hti %p scale %llu)", hti, hti->scale);
 
     // heuristics to determine the size of the new table

-    uint64_t count = ht_count(hti->ht);
+    size_t count = ht_count(hti->ht);

     unsigned int new_scale = hti->scale;
     new_scale += (count > (1 << (new_scale - 2))); // double size if more than 1/4 full
     new_scale += (count > (1 << (new_scale - 2))); // double size again if more than 1/2 full
     unsigned int new_scale = hti->scale;
     new_scale += (count > (1 << (new_scale - 2))); // double size if more than 1/4 full
     new_scale += (count > (1 << (new_scale - 2))); // double size again if more than 1/2 full


@@ -215,15 +215,15 @@ static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_h
     }
 
     // Install the key in the new table.
     }
 
     // Install the key in the new table.

-    uint64_t ht1_ent_key = ht1_ent->key;
-    map_key_t key = (ht1->ht->key_type == NULL) ? (map_key_t)ht1_ent_key : (map_key_t)(size_t)GET_PTR(ht1_ent_key);
+    map_key_t ht1_ent_key = ht1_ent->key;
+    map_key_t key = (ht1->ht->key_type == NULL) ? (map_key_t)ht1_ent_key : (map_key_t)GET_PTR(ht1_ent_key);

 
     // The old table's dead entries don't need to be copied to the new table, but their keys need to be freed.
     assert(COPIED_VALUE == TAG_VALUE(TOMBSTONE, TAG1));
     if (ht1_ent_val == TOMBSTONE) {
         TRACE("h1", "hti_copy_entry: entry %p old value was deleted, now freeing key %p", ht1_ent, key);
         if (EXPECT_FALSE(ht1->ht->key_type != NULL)) {
 
     // The old table's dead entries don't need to be copied to the new table, but their keys need to be freed.
     assert(COPIED_VALUE == TAG_VALUE(TOMBSTONE, TAG1));
     if (ht1_ent_val == TOMBSTONE) {
         TRACE("h1", "hti_copy_entry: entry %p old value was deleted, now freeing key %p", ht1_ent, key);
         if (EXPECT_FALSE(ht1->ht->key_type != NULL)) {

-            nbd_defer_free((void *)(size_t)key);
+            nbd_defer_free((void *)key);

         }
         return TRUE; 
     }
         }
         return TRUE; 
     }


@@ -233,7 +233,7 @@ static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_h
     if (key_hash == 0) { 
         key_hash = (ht1->ht->key_type == NULL) 
                  ? murmur32_8b(ht1_ent_key) 
     if (key_hash == 0) { 
         key_hash = (ht1->ht->key_type == NULL) 
                  ? murmur32_8b(ht1_ent_key) 

-                 : ht1->ht->key_type->hash((void *)(size_t)key);
+                 : ht1->ht->key_type->hash((void *)key);

     }
 
     int ht2_ent_is_empty;
     }
 
     int ht2_ent_is_empty;


@@ -250,7 +250,7 @@ static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_h
     }
 
     if (ht2_ent_is_empty) {
     }
 
     if (ht2_ent_is_empty) {

-        uint64_t old_ht2_ent_key = SYNC_CAS(&ht2_ent->key, DOES_NOT_EXIST, ht1_ent_key);
+        map_key_t old_ht2_ent_key = SYNC_CAS(&ht2_ent->key, DOES_NOT_EXIST, ht1_ent_key);

         if (old_ht2_ent_key != DOES_NOT_EXIST) {
             TRACE("h0", "hti_copy_entry: lost race to CAS key %p into new entry; found %p",
                     ht1_ent_key, old_ht2_ent_key);
         if (old_ht2_ent_key != DOES_NOT_EXIST) {
             TRACE("h0", "hti_copy_entry: lost race to CAS key %p into new entry; found %p",
                     ht1_ent_key, old_ht2_ent_key);


@@ -327,14 +327,16 @@ static map_val_t hti_cas (hti_t *hti, map_key_t key, uint32_t key_hash, map_val_
             return DOES_NOT_EXIST;
 
         // Allocate <new_key>.
             return DOES_NOT_EXIST;
 
         // Allocate <new_key>.

-        uint64_t new_key = (uint64_t)((hti->ht->key_type == NULL) ? key : (map_key_t)(size_t)hti->ht->key_type->clone((void *)(size_t)key));
+        map_key_t new_key = (hti->ht->key_type == NULL) 
+                          ? (map_key_t)key 
+                          : (map_key_t)hti->ht->key_type->clone((void *)key);

         if (EXPECT_FALSE(hti->ht->key_type != NULL)) {
             // Combine <new_key> pointer with bits from its hash 
             new_key = ((uint64_t)(key_hash >> 16) << 48) | new_key; 
         }
 
         // CAS the key into the table.
         if (EXPECT_FALSE(hti->ht->key_type != NULL)) {
             // Combine <new_key> pointer with bits from its hash 
             new_key = ((uint64_t)(key_hash >> 16) << 48) | new_key; 
         }
 
         // CAS the key into the table.

-        uint64_t old_ent_key = SYNC_CAS(&ent->key, DOES_NOT_EXIST, new_key);
+        map_key_t old_ent_key = SYNC_CAS(&ent->key, DOES_NOT_EXIST, new_key);

 
         // Retry if another thread stole the entry out from under us.
         if (old_ent_key != DOES_NOT_EXIST) {
 
         // Retry if another thread stole the entry out from under us.
         if (old_ent_key != DOES_NOT_EXIST) {


@@ -436,17 +438,17 @@ static map_val_t hti_get (hti_t *hti, map_key_t key, uint32_t key_hash) {
 
 //
 map_val_t ht_get (hashtable_t *ht, map_key_t key) {
 
 //
 map_val_t ht_get (hashtable_t *ht, map_key_t key) {

-    uint32_t hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)(size_t)key);
+    uint32_t hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)key);

     return hti_get(ht->hti, key, hash);
 }
 
 // returns TRUE if copy is done
 int hti_help_copy (hti_t *hti) {
     volatile entry_t *ent;
     return hti_get(ht->hti, key, hash);
 }
 
 // returns TRUE if copy is done
 int hti_help_copy (hti_t *hti) {
     volatile entry_t *ent;

-    uint64_t limit; 
-    uint64_t total_copied = hti->num_entries_copied;
-    uint64_t num_copied = 0;
-    uint64_t x = hti->copy_scan; 
+    size_t limit; 
+    size_t total_copied = hti->num_entries_copied;
+    size_t num_copied = 0;
+    size_t 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)) {
 
     TRACE("h1", "ht_cas: help copy. scan is %llu, size is %llu", x, 1<<hti->scale);
     if (total_copied != (1 << hti->scale)) {


@@ -512,7 +514,7 @@ map_val_t ht_cas (hashtable_t *ht, map_key_t key, map_val_t expected_val, map_va
     }
 
     map_val_t old_val;
     }
 
     map_val_t old_val;

-    uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)(size_t)key);
+    uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)key);

     while ((old_val = hti_cas(hti, key, key_hash, expected_val, new_val)) == COPIED_VALUE) {
         assert(hti->next);
         hti = hti->next;
     while ((old_val = hti_cas(hti, key, key_hash, expected_val, new_val)) == COPIED_VALUE) {
         assert(hti->next);
         hti = hti->next;


@@ -526,7 +528,7 @@ map_val_t ht_cas (hashtable_t *ht, map_key_t key, map_val_t expected_val, map_va
 map_val_t ht_remove (hashtable_t *ht, map_key_t key) {
     hti_t *hti = ht->hti;
     map_val_t val;
 map_val_t ht_remove (hashtable_t *ht, map_key_t key) {
     hti_t *hti = ht->hti;
     map_val_t val;

-    uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)(size_t)key);
+    uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)key);

     do {
         val = hti_cas(hti, key, key_hash, CAS_EXPECT_WHATEVER, DOES_NOT_EXIST);
         if (val != COPIED_VALUE)
     do {
         val = hti_cas(hti, key, key_hash, CAS_EXPECT_WHATEVER, DOES_NOT_EXIST);
         if (val != COPIED_VALUE)


@@ -538,9 +540,9 @@ map_val_t ht_remove (hashtable_t *ht, map_key_t key) {
 }
 
 // Returns the number of key-values pairs in <ht>
 }
 
 // Returns the number of key-values pairs in <ht>

-uint64_t ht_count (hashtable_t *ht) {
+size_t ht_count (hashtable_t *ht) {

     hti_t *hti = ht->hti;
     hti_t *hti = ht->hti;

-    uint64_t count = 0;
+    size_t count = 0;

     while (hti) {
         count += hti->count;
         hti = hti->next; 
     while (hti) {
         count += hti->count;
         hti = hti->next; 


@@ -619,14 +621,14 @@ map_val_t ht_iter_next (ht_iter_t *iter, map_key_t *key_ptr) {
     volatile entry_t *ent;
     map_key_t key;
     map_val_t val;
     volatile entry_t *ent;
     map_key_t key;
     map_val_t val;

-    uint64_t table_size = (1 << iter->hti->scale);
+    size_t table_size = (1 << iter->hti->scale);

     do {
         iter->idx++;
         if (iter->idx == table_size) {
             return DOES_NOT_EXIST;
         }
         ent = &iter->hti->table[iter->idx];
     do {
         iter->idx++;
         if (iter->idx == table_size) {
             return DOES_NOT_EXIST;
         }
         ent = &iter->hti->table[iter->idx];

-        key = (iter->hti->ht->key_type == NULL) ? (map_key_t)ent->key : (map_key_t)(size_t)GET_PTR(ent->key);
+        key = (iter->hti->ht->key_type == NULL) ? (map_key_t)ent->key : (map_key_t)GET_PTR(ent->key);

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


@@ -637,7 +639,7 @@ map_val_t ht_iter_next (ht_iter_t *iter, map_key_t *key_ptr) {
     if (val == COPIED_VALUE) {
         uint32_t hash = (iter->hti->ht->key_type == NULL) 
                       ? murmur32_8b((uint64_t)key)
     if (val == COPIED_VALUE) {
         uint32_t hash = (iter->hti->ht->key_type == NULL) 
                       ? murmur32_8b((uint64_t)key)

-                      : iter->hti->ht->key_type->hash((void *)(size_t)key);
+                      : iter->hti->ht->key_type->hash((void *)key);

         val = hti_get(iter->hti->next, (map_key_t)ent->key, hash);
     } 
 
         val = hti_get(iter->hti->next, (map_key_t)ent->key, hash);
     } 
 

diff --git a/map/list.c b/map/list.c
index 250e40687d0ef565f7b057595ffa4128934581dc..98522c3b1b7f033567a9de274c79f40901865844 100644 (file)
--- a/map/list.c
+++ b/map/list.c
@@ -14,9 +14,9 @@
 #include "mem.h"
 
 typedef struct node {
 #include "mem.h"
 
 typedef struct node {

-    map_key_t key;
-    map_val_t val;
-    uint64_t next; // next node
+    map_key_t  key;
+    map_val_t  val;
+    markable_t next; // next node

 } node_t;
 
 struct ll_iter {
 } node_t;
 
 struct ll_iter {


@@ -28,6 +28,12 @@ struct ll {
     const datatype_t *key_type;
 };
 
     const datatype_t *key_type;
 };
 

+// Marking the <next> field of a node logically removes it from the list
+#define  MARK_NODE(x) TAG_VALUE((markable_t)(x), TAG1)
+#define   HAS_MARK(x) (IS_TAGGED((x), TAG1) == TAG1)
+#define   GET_NODE(x) ((node_t *)(x))
+#define STRIP_MARK(x) ((node_t *)STRIP_TAG((x), TAG1))
+

 static node_t *node_alloc (map_key_t key, map_val_t val) {
     node_t *item = (node_t *)nbd_malloc(sizeof(node_t));
     item->key = key;
 static node_t *node_alloc (map_key_t key, map_val_t val) {
     node_t *item = (node_t *)nbd_malloc(sizeof(node_t));
     item->key = key;


@@ -44,40 +50,40 @@ list_t *ll_alloc (const datatype_t *key_type) {
 }
 
 void ll_free (list_t *ll) {
 }
 
 void ll_free (list_t *ll) {

-    node_t *item = (node_t *)(size_t)ll->head->next; // the head can't be tagged
-    while (item) {
-        node_t *next = (node_t *)(size_t)STRIP_TAG(item->next, TAG1);
+    node_t *item = STRIP_MARK(ll->head->next);
+    while (item != NULL) {
+        node_t *next = STRIP_MARK(item->next);

         nbd_free(item);
         item = next;
     }
 }
 
         nbd_free(item);
         item = next;
     }
 }
 

-uint64_t ll_count (list_t *ll) {
-    uint64_t count = 0;
-    node_t *item = (node_t *)(size_t)ll->head->next;
+size_t ll_count (list_t *ll) {
+    size_t count = 0;
+    node_t *item = STRIP_MARK(ll->head->next);

     while (item) {
     while (item) {

-        if (!IS_TAGGED(item->next, TAG1)) {
+        if (!HAS_MARK(item->next)) {

             count++;
         }
             count++;
         }

-        item = (node_t *)(size_t)STRIP_TAG(item->next, TAG1);
+        item = STRIP_MARK(item->next);

     }
     return count;
 }
 
 static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, map_key_t key, int help_remove) {
     node_t *pred = ll->head;
     }
     return count;
 }
 
 static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, map_key_t key, int help_remove) {
     node_t *pred = ll->head;

-    node_t *item = (node_t *)(size_t)pred->next;
+    node_t *item = GET_NODE(pred->next);

     TRACE("l2", "find_pred: searching for key %p in list (head is %p)", key, pred);
 
     while (item != NULL) {
     TRACE("l2", "find_pred: searching for key %p in list (head is %p)", key, pred);
 
     while (item != NULL) {

-        uint64_t next = item->next;
+        markable_t next = item->next;

 
 

-        // A tag means an item is logically removed but not physically unlinked yet.
-        while (EXPECT_FALSE(IS_TAGGED(next, TAG1))) {
+        // A mark means the node is logically removed but not physically unlinked yet.
+        while (EXPECT_FALSE(HAS_MARK(next))) {

 
             // Skip over logically removed items.
             if (!help_remove) {
 
             // Skip over logically removed items.
             if (!help_remove) {

-                item = (node_t *)(size_t)STRIP_TAG(item->next, TAG1);
+                item = STRIP_MARK(item->next);

                 if (EXPECT_FALSE(item == NULL))
                     break;
                 TRACE("l3", "find_pred: skipping marked item %p (next is %p)", item, next);
                 if (EXPECT_FALSE(item == NULL))
                     break;
                 TRACE("l3", "find_pred: skipping marked item %p (next is %p)", item, next);


@@ -88,24 +94,25 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, map_key_
             // Unlink logically removed items.
             TRACE("l3", "find_pred: unlinking marked item %p next is %p", item, next);
 
             // Unlink logically removed items.
             TRACE("l3", "find_pred: unlinking marked item %p next is %p", item, next);
 

-            uint64_t other = SYNC_CAS(&pred->next, (uint64_t)(size_t)item, STRIP_TAG(next, TAG1));
-            if (other == (uint64_t)(size_t)item) {
+            markable_t other = SYNC_CAS(&pred->next, item, STRIP_MARK(next));
+            if (other == (markable_t)item) {

                 TRACE("l2", "find_pred: unlinked item %p from pred %p", item, pred);
                 TRACE("l2", "find_pred: unlinked item %p from pred %p", item, pred);

-                item = (node_t *)(size_t)STRIP_TAG(next, TAG1);
+                item = STRIP_MARK(next);

                 next = (item != NULL) ? item->next : DOES_NOT_EXIST;
                 TRACE("l3", "find_pred: now current item is %p next is %p", item, next);
 
                 // The thread that completes the unlink should free the memory.
                 next = (item != NULL) ? item->next : DOES_NOT_EXIST;
                 TRACE("l3", "find_pred: now current item is %p next is %p", item, next);
 
                 // The thread that completes the unlink should free the memory.

+                node_t *unlinked = GET_NODE(other);

                 if (ll->key_type != NULL) {
                 if (ll->key_type != NULL) {

-                    nbd_defer_free((void *)(size_t)((node_t *)(size_t)other)->key);
+                    nbd_defer_free((void *)unlinked->key);

                 }
                 }

-                nbd_defer_free(((node_t *)(size_t)other));
+                nbd_defer_free(unlinked);

             } else {
                 TRACE("l2", "find_pred: lost a race to unlink item %p from pred %p", item, pred);
                 TRACE("l2", "find_pred: pred's link changed to %p", other, 0);
             } else {
                 TRACE("l2", "find_pred: lost a race to unlink item %p from pred %p", item, pred);
                 TRACE("l2", "find_pred: pred's link changed to %p", other, 0);

-                if (IS_TAGGED(other, TAG1))
+                if (HAS_MARK(other))

                     return find_pred(pred_ptr, item_ptr, ll, key, help_remove); // retry
                     return find_pred(pred_ptr, item_ptr, ll, key, help_remove); // retry

-                item = (node_t *)(size_t)other;
+                item = GET_NODE(other);

                 next = (item != NULL) ? item->next : DOES_NOT_EXIST;
             }
         }
                 next = (item != NULL) ? item->next : DOES_NOT_EXIST;
             }
         }


@@ -118,12 +125,12 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, map_key_
 
         int d;
         if (EXPECT_TRUE(ll->key_type == NULL)) {
 
         int d;
         if (EXPECT_TRUE(ll->key_type == NULL)) {

-            d = (uint64_t)item->key - (uint64_t)key;
+            d = item->key - key;

         } else {
         } else {

-            d = ll->key_type->cmp((void *)(size_t)item->key, (void *)(size_t)key);
+            d = ll->key_type->cmp((void *)item->key, (void *)key);

         }
 
         }
 

-        if (next != DOES_NOT_EXIST && ((node_t *)next)->key < item->key) {
+        if (next != DOES_NOT_EXIST && GET_NODE(next)->key < item->key) {

             lwt_halt();
             assert(0);
         }
             lwt_halt();
             assert(0);
         }


@@ -143,7 +150,7 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, map_key_
         }
 
         pred = item;
         }
 
         pred = item;

-        item = (node_t *)(size_t)next;
+        item = GET_NODE(next);

     }
 
     // <key> is not in <ll>.
     }
 
     // <key> is not in <ll>.


@@ -194,12 +201,10 @@ map_val_t ll_cas (list_t *ll, map_key_t key, map_val_t expectation, map_val_t ne
 
             // 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);

-            map_key_t new_key = (ll->key_type == NULL) 
-                              ? key 
-                              : (map_key_t)(size_t)ll->key_type->clone((void *)(size_t)key);
+            map_key_t new_key = ll->key_type == NULL ? key : (map_key_t)ll->key_type->clone((void *)key);

             node_t *new_item = node_alloc(new_key, new_val);
             node_t *new_item = node_alloc(new_key, new_val);

-            uint64_t next = new_item->next = (uint64_t)(size_t)old_item;
-            uint64_t other = SYNC_CAS(&pred->next, next, new_item);
+            markable_t next = new_item->next = (markable_t)old_item;
+            markable_t other = SYNC_CAS(&pred->next, next, new_item);

             if (other == next) {
                 TRACE("l1", "ll_cas: successfully inserted new item %p", new_item, 0);
                 return DOES_NOT_EXIST; // success
             if (other == next) {
                 TRACE("l1", "ll_cas: successfully inserted new item %p", new_item, 0);
                 return DOES_NOT_EXIST; // success


@@ -208,7 +213,7 @@ map_val_t ll_cas (list_t *ll, map_key_t key, map_val_t expectation, map_val_t ne
             // Lost a race. Failed to insert the new item into the list.
             TRACE("l1", "ll_cas: lost a race. CAS failed. expected pred's link to be %p but found %p", next, other);
             if (ll->key_type != NULL) {
             // Lost a race. Failed to insert the new item into the list.
             TRACE("l1", "ll_cas: lost a race. CAS failed. expected pred's link to be %p but found %p", next, other);
             if (ll->key_type != NULL) {

-                nbd_free((void *)(size_t)new_key);
+                nbd_free((void *)new_key);

             }
             nbd_free(new_item);
             continue; // retry
             }
             nbd_free(new_item);
             continue; // retry


@@ -256,18 +261,18 @@ map_val_t ll_remove (list_t *ll, map_key_t key) {
     }
 
     // Mark <item> removed. If multiple threads try to remove the same item only one of them should succeed.
     }
 
     // Mark <item> removed. If multiple threads try to remove the same item only one of them should succeed.

-    uint64_t next;
-    uint64_t old_next = item->next;
+    markable_t next;
+    markable_t old_next = item->next;

     do {
         next     = old_next;
     do {
         next     = old_next;

-        old_next = SYNC_CAS(&item->next, next, TAG_VALUE(next, TAG1));
-        if (IS_TAGGED(old_next, TAG1)) {
+        old_next = SYNC_CAS(&item->next, next, MARK_NODE(STRIP_MARK(next)));
+        if (HAS_MARK(old_next)) {

             TRACE("l1", "ll_remove: lost a race -- %p is already marked for removal by another thread", item, 0);
             return DOES_NOT_EXIST;
         }
     } while (next != old_next);
     TRACE("l2", "ll_remove: logically removed item %p", item, 0);
             TRACE("l1", "ll_remove: lost a race -- %p is already marked for removal by another thread", item, 0);
             return DOES_NOT_EXIST;
         }
     } while (next != old_next);
     TRACE("l2", "ll_remove: logically removed item %p", item, 0);

-    ASSERT(IS_TAGGED(((volatile node_t *)item)->next, TAG1));
+    ASSERT(HAS_MARK(((volatile node_t *)item)->next));

 
     // Atomically swap out the item's value in case another thread is updating the item while we are 
     // removing it. This establishes which operation occurs first logically, the update or the remove. 
 
     // Atomically swap out the item's value in case another thread is updating the item while we are 
     // removing it. This establishes which operation occurs first logically, the update or the remove. 


@@ -278,15 +283,15 @@ map_val_t ll_remove (list_t *ll, map_key_t key) {
     // item logically removed for a later call (or some other thread) to physically unlink. By marking the
     // item earlier, we logically removed it. 
     TRACE("l2", "ll_remove: unlink the item by linking its pred %p to its successor %p", pred, next);
     // item logically removed for a later call (or some other thread) to physically unlink. By marking the
     // item earlier, we logically removed it. 
     TRACE("l2", "ll_remove: unlink the item by linking its pred %p to its successor %p", pred, next);

-    uint64_t other;
-    if ((other = SYNC_CAS(&pred->next, (uint64_t)(size_t)item, next)) != (uint64_t)(size_t)item) {
+    markable_t other;
+    if ((other = SYNC_CAS(&pred->next, item, next)) != (markable_t)item) {

         TRACE("l1", "ll_remove: unlink failed; pred's link changed from %p to %p", item, other);
         return val;
     } 
 
     // The thread that completes the unlink should free the memory.
     if (ll->key_type != NULL) {
         TRACE("l1", "ll_remove: unlink failed; pred's link changed from %p to %p", item, other);
         return val;
     } 
 
     // The thread that completes the unlink should free the memory.
     if (ll->key_type != NULL) {

-        nbd_defer_free((void *)(size_t)item->key);
+        nbd_defer_free((void *)item->key);

     }
     nbd_defer_free(item);
     TRACE("l1", "ll_remove: successfully unlinked item %p from the list", item, 0);
     }
     nbd_defer_free(item);
     TRACE("l1", "ll_remove: successfully unlinked item %p from the list", item, 0);


@@ -294,13 +299,13 @@ map_val_t ll_remove (list_t *ll, map_key_t key) {
 }
 
 void ll_print (list_t *ll) {
 }
 
 void ll_print (list_t *ll) {

-    uint64_t next = ll->head->next;
+    markable_t next = ll->head->next;

     int i = 0;
     while (next != DOES_NOT_EXIST) {
     int i = 0;
     while (next != DOES_NOT_EXIST) {

-        if (IS_TAGGED(next, TAG1)) {
+        if (HAS_MARK(next)) {

             printf("*");
         }
             printf("*");
         }

-        node_t *item = (node_t *)(size_t)STRIP_TAG(next, TAG1);
+        node_t *item = STRIP_MARK(next);

         if (item == NULL)
             break;
         printf("%p:0x%llx ", item, item->key);
         if (item == NULL)
             break;
         printf("%p:0x%llx ", item, item->key);


@@ -323,14 +328,14 @@ ll_iter_t *ll_iter_begin (list_t *ll, map_key_t key) {
 map_val_t ll_iter_next (ll_iter_t *iter, map_key_t *key_ptr) {
     assert(iter);
     node_t *item = iter->next;
 map_val_t ll_iter_next (ll_iter_t *iter, map_key_t *key_ptr) {
     assert(iter);
     node_t *item = iter->next;

-    while (item != NULL && IS_TAGGED(item->next, TAG1)) {
-        item = (node_t *)(size_t)STRIP_TAG(item->next, TAG1);
+    while (item != NULL && HAS_MARK(item->next)) {
+        item = STRIP_MARK(item->next);

     }
     if (item == NULL) {
         iter->next = NULL;
         return DOES_NOT_EXIST;
     }
     }
     if (item == NULL) {
         iter->next = NULL;
         return DOES_NOT_EXIST;
     }

-    iter->next = (node_t *)(size_t)STRIP_TAG(item->next, TAG1);
+    iter->next = STRIP_MARK(item->next);

     if (key_ptr != NULL) {
         *key_ptr = item->key;
     }
     if (key_ptr != NULL) {
         *key_ptr = item->key;
     }

diff --git a/map/skiplist.c b/map/skiplist.c
index e81a89680154e3ef3b6e55edd9f75c17efe85f89..5366d91adae9bcef2c5caa6f91cd95f6c61c8b47 100644 (file)
--- a/map/skiplist.c
+++ b/map/skiplist.c
@@ -32,7 +32,7 @@ typedef struct node {
     map_key_t key;
     map_val_t val;
     int top_level;
     map_key_t key;
     map_val_t val;
     int top_level;

-    uint64_t next[];
+    markable_t next[];

 } node_t;
 
 struct sl_iter {
 } node_t;
 
 struct sl_iter {


@@ -44,6 +44,19 @@ struct sl {
     const datatype_t *key_type;
 };
 
     const datatype_t *key_type;
 };
 

+// Marking the <next> field of a node logically removes it from the list
+#if 0
+static inline markable_t  MARK_NODE(node_t * x) { return TAG_VALUE((markable_t)x, TAG1); }
+static inline int        HAS_MARK(markable_t x) { return (IS_TAGGED(x, TAG1) == TAG1); }
+static inline node_t *   GET_NODE(markable_t x) { assert(!HAS_MARK(x)); return (node_t *)x; }
+static inline node_t * STRIP_MARK(markable_t x) { return ((node_t *)STRIP_TAG(x, TAG1)); }
+#else
+#define  MARK_NODE(x) TAG_VALUE((markable_t)(x), TAG1)
+#define   HAS_MARK(x) (IS_TAGGED((x), TAG1) == TAG1)
+#define   GET_NODE(x) ((node_t *)(x))
+#define STRIP_MARK(x) ((node_t *)STRIP_TAG((x), TAG1))
+#endif
+

 static int random_level (void) {
     unsigned r = nbd_rand();
     if (r & 1)
 static int random_level (void) {
     unsigned r = nbd_rand();
     if (r & 1)


@@ -76,25 +89,25 @@ skiplist_t *sl_alloc (const datatype_t *key_type) {
 }
 
 void sl_free (skiplist_t *sl) {
 }
 
 void sl_free (skiplist_t *sl) {

-    node_t *item = (node_t *)(size_t)sl->head->next[0];
+    node_t *item = GET_NODE(sl->head->next[0]);

     while (item) {
     while (item) {

-        node_t *next = (node_t *)(size_t)STRIP_TAG(item->next[0], TAG1);
+        node_t *next = STRIP_MARK(item->next[0]);

         if (sl->key_type != NULL) {
         if (sl->key_type != NULL) {

-            nbd_free((void *)(size_t)item->key);
+            nbd_free((void *)item->key);

         }
         nbd_free(item);
         item = next;
     }
 }
 
         }
         nbd_free(item);
         item = next;
     }
 }
 

-uint64_t sl_count (skiplist_t *sl) {
-    uint64_t count = 0;
-    node_t *item = (node_t *)(size_t)sl->head->next[0];
+size_t sl_count (skiplist_t *sl) {
+    size_t count = 0;
+    node_t *item = GET_NODE(sl->head->next[0]);

     while (item) {
     while (item) {

-        if (!IS_TAGGED(item->next[0], TAG1)) {
+        if (!HAS_MARK(item->next[0])) {

             count++;
         }
             count++;
         }

-        item = (node_t *)(size_t)STRIP_TAG(item->next[0], TAG1);
+        item = STRIP_MARK(item->next[0]);

     }
     return count;
 }
     }
     return count;
 }


@@ -123,20 +136,21 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl
     // Traverse the levels of <sl> from the top level to the bottom
     for (int level = start_level; level >= 0; --level) {
         TRACE("s3", "find_preds: level %llu", level, 0);
     // Traverse the levels of <sl> from the top level to the bottom
     for (int level = start_level; level >= 0; --level) {
         TRACE("s3", "find_preds: level %llu", level, 0);

-        item = (node_t *)pred->next[level];
-        if (EXPECT_FALSE(IS_TAGGED((uint64_t)item, TAG1))) {
-            TRACE("s2", "find_preds: pred %p is marked for removal (item %p); retry", pred, item);
+        markable_t next = pred->next[level];
+        if (EXPECT_FALSE(HAS_MARK(next))) {
+            TRACE("s2", "find_preds: pred %p is marked for removal (next %p); retry", pred, next);

             return find_preds(preds, succs, n, sl, key, help_remove); // retry
         }
             return find_preds(preds, succs, n, sl, key, help_remove); // retry
         }

+        item = GET_NODE(next);

         while (item != NULL) {
         while (item != NULL) {

-            uint64_t next = item->next[level];
+            next = item->next[level];

 
             // A tag means an item is logically removed but not physically unlinked yet.
 
             // A tag means an item is logically removed but not physically unlinked yet.

-            while (EXPECT_FALSE(IS_TAGGED(next, TAG1))) {
+            while (EXPECT_FALSE(HAS_MARK(next))) {

 
                 // Skip over logically removed items.
                 if (!help_remove) {
 
                 // Skip over logically removed items.
                 if (!help_remove) {

-                    item = (node_t *)(size_t)STRIP_TAG(next, TAG1);
+                    item = STRIP_MARK(next);

                     if (EXPECT_FALSE(item == NULL))
                         break;
                     next = item->next[level];
                     if (EXPECT_FALSE(item == NULL))
                         break;
                     next = item->next[level];


@@ -146,25 +160,26 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl
 
                 // Unlink logically removed items.
                 TRACE("s3", "find_preds: unlinking marked item %p; next is 0x%llx", item, next);
 
                 // Unlink logically removed items.
                 TRACE("s3", "find_preds: unlinking marked item %p; next is 0x%llx", item, next);

-                uint64_t other = SYNC_CAS(&pred->next[level], (uint64_t)(size_t)item, STRIP_TAG(next, TAG1));
-                if (other == (uint64_t)(size_t)item) {
-                    item = (node_t *)(size_t)STRIP_TAG(next, TAG1);
+                markable_t other = SYNC_CAS(&pred->next[level], item, STRIP_MARK(next));
+                if (other == (markable_t)item) {
+                    item = STRIP_MARK(next);

                     next = (item != NULL) ? item->next[level] : DOES_NOT_EXIST;
                     TRACE("s3", "find_preds: now the current item is %p next is 0x%llx", item, next);
 
                     // The thread that completes the unlink should free the memory.
                     if (level == 0) {
                     next = (item != NULL) ? item->next[level] : DOES_NOT_EXIST;
                     TRACE("s3", "find_preds: now the current item is %p next is 0x%llx", item, next);
 
                     // The thread that completes the unlink should free the memory.
                     if (level == 0) {

+                        node_t *unlinked = GET_NODE(other);

                         if (sl->key_type != NULL) {
                         if (sl->key_type != NULL) {

-                            nbd_defer_free((void *)(size_t)((node_t *)(size_t)other)->key);
+                            nbd_defer_free((void *)unlinked->key);

                         }
                         }

-                        nbd_defer_free(((node_t *)(size_t)other));
+                        nbd_defer_free(unlinked);

                     }
                 } else {
                     TRACE("s3", "find_preds: lost race to unlink item %p from pred %p", item, pred);
                     TRACE("s3", "find_preds: pred's link changed to %p", other, 0);
                     }
                 } else {
                     TRACE("s3", "find_preds: lost race to unlink item %p from pred %p", item, pred);
                     TRACE("s3", "find_preds: pred's link changed to %p", other, 0);

-                    if (IS_TAGGED(other, TAG1))
+                    if (HAS_MARK(other))

                         return find_preds(preds, succs, n, sl, key, help_remove); // retry
                         return find_preds(preds, succs, n, sl, key, help_remove); // retry

-                    item = (node_t *)(size_t)other;
+                    item = GET_NODE(other);

                     next = (item != NULL) ? item->next[level] : DOES_NOT_EXIST;
                 }
             }
                     next = (item != NULL) ? item->next[level] : DOES_NOT_EXIST;
                 }
             }


@@ -173,12 +188,12 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl
                 break;
 
             TRACE("s4", "find_preds: visiting item %p (next is %p)", item, next);
                 break;
 
             TRACE("s4", "find_preds: visiting item %p (next is %p)", item, next);

-            TRACE("s4", "find_preds: key %p val %p", STRIP_TAG(item->key, TAG1), item->val);
+            TRACE("s4", "find_preds: key %p val %p", STRIP_MARK(item->key), item->val);

 
             if (EXPECT_TRUE(sl->key_type == NULL)) {
 
             if (EXPECT_TRUE(sl->key_type == NULL)) {

-                d = (uint64_t)item->key - (uint64_t)key;
+                d = item->key - key;

             } else {
             } else {

-                d = sl->key_type->cmp((void *)(size_t)item->key, (void *)(size_t)key);
+                d = sl->key_type->cmp((void *)item->key, (void *)key);

             }
 
             if (d >= 0) {
             }
 
             if (d >= 0) {


@@ -187,7 +202,7 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl
             }
 
             pred = item;
             }
 
             pred = item;

-            item = (node_t *)(size_t)next;
+            item = GET_NODE(next);

         }
 
         // The cast to unsigned is for the case when n is -1.
         }
 
         // The cast to unsigned is for the case when n is -1.


@@ -236,12 +251,12 @@ map_val_t sl_lookup (skiplist_t *sl, map_key_t key) {
 }
 
 map_key_t sl_min_key (skiplist_t *sl) {
 }
 
 map_key_t sl_min_key (skiplist_t *sl) {

-    node_t *item = (node_t *)(size_t)sl->head->next[0];
+    node_t *item = GET_NODE(sl->head->next[0]);

     while (item != NULL) {
     while (item != NULL) {

-        uint64_t next = item->next[0];
-        if (!IS_TAGGED(next, TAG1))
+        markable_t next = item->next[0];
+        if (!HAS_MARK(next))

             return item->key;
             return item->key;

-        item = (node_t *)(size_t)STRIP_TAG(next, TAG1);
+        item = STRIP_MARK(next);

     }
     return DOES_NOT_EXIST;
 }
     }
     return DOES_NOT_EXIST;
 }


@@ -269,23 +284,21 @@ map_val_t sl_cas (skiplist_t *sl, map_key_t key, map_val_t expectation, map_val_
 
             // 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]);

-            map_key_t new_key = (sl->key_type == NULL) 
-                              ? key 
-                              : (map_key_t)(size_t)sl->key_type->clone((void *)(size_t)key);
+            map_key_t new_key = sl->key_type == NULL ? key : (map_key_t)sl->key_type->clone((void *)key);

             new_item = node_alloc(n, new_key, new_val);
             node_t *pred = preds[0];
             new_item = node_alloc(n, new_key, new_val);
             node_t *pred = preds[0];

-            uint64_t next = new_item->next[0] = (uint64_t)(size_t)nexts[0];
+            markable_t next = new_item->next[0] = (markable_t)nexts[0];

             for (int level = 1; level <= new_item->top_level; ++level) {
             for (int level = 1; level <= new_item->top_level; ++level) {

-                new_item->next[level] = (uint64_t)(size_t)nexts[level];
+                new_item->next[level] = (markable_t)nexts[level];

             }
             }

-            uint64_t other = SYNC_CAS(&pred->next[0], next, (uint64_t)(size_t)new_item);
+            markable_t other = SYNC_CAS(&pred->next[0], next, new_item);

             if (other == next) {
                 TRACE("s3", "sl_cas: successfully inserted item %p at level 0", new_item, 0);
                 break; // success
             }
             TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other);
             if (sl->key_type != NULL) {
             if (other == next) {
                 TRACE("s3", "sl_cas: successfully inserted item %p at level 0", new_item, 0);
                 break; // success
             }
             TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other);
             if (sl->key_type != NULL) {

-                nbd_free((void *)(size_t)new_key);
+                nbd_free((void *)new_key);

             }
             nbd_free(new_item);
             continue;
             }
             nbd_free(new_item);
             continue;


@@ -324,10 +337,10 @@ map_val_t sl_cas (skiplist_t *sl, map_key_t key, map_val_t expectation, map_val_
     // Link <new_item> into <sl> from the bottom up.
     for (int level = 1; level <= new_item->top_level; ++level) {
         node_t *pred = preds[level];
     // Link <new_item> into <sl> from the bottom up.
     for (int level = 1; level <= new_item->top_level; ++level) {
         node_t *pred = preds[level];

-        uint64_t next = (uint64_t)(size_t)nexts[level];
+        markable_t next = (markable_t)nexts[level];

         do {
             TRACE("s3", "sl_cas: attempting to insert item between %p and %p", pred, next);
         do {
             TRACE("s3", "sl_cas: attempting to insert item between %p and %p", pred, next);

-            uint64_t other = SYNC_CAS(&pred->next[level], next, (uint64_t)(size_t)new_item);
+            markable_t other = SYNC_CAS(&pred->next[level], next, (markable_t)new_item);

             if (other == next) {
                 TRACE("s3", "sl_cas: successfully inserted item %p at level %llu", new_item, level);
                 break; // success
             if (other == next) {
                 TRACE("s3", "sl_cas: successfully inserted item %p at level %llu", new_item, level);
                 break; // success


@@ -335,13 +348,13 @@ map_val_t sl_cas (skiplist_t *sl, map_key_t key, map_val_t expectation, map_val_
             TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other);
             find_preds(preds, nexts, new_item->top_level, sl, key, TRUE);
             pred = preds[level];
             TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other);
             find_preds(preds, nexts, new_item->top_level, sl, key, TRUE);
             pred = preds[level];

-            next = (uint64_t)(size_t)nexts[level];
+            next = (markable_t)nexts[level];

 
             // Update <new_item>'s next pointer
             do {
                 // There in no need to continue linking in the item if another thread removed it.
 
             // Update <new_item>'s next pointer
             do {
                 // There in no need to continue linking in the item if another thread removed it.

-                uint64_t old_next = ((volatile node_t *)new_item)->next[level];
-                if (IS_TAGGED(old_next, TAG1))
+                markable_t old_next = ((volatile node_t *)new_item)->next[level];
+                if (HAS_MARK(old_next))

                     return DOES_NOT_EXIST; // success
 
                 // Use a CAS so we do not inadvertantly stomp on a mark another thread placed on the item.
                     return DOES_NOT_EXIST; // success
 
                 // Use a CAS so we do not inadvertantly stomp on a mark another thread placed on the item.


@@ -365,21 +378,21 @@ map_val_t sl_remove (skiplist_t *sl, map_key_t key) {
     // Mark and unlink <item> at each level of <sl> from the top down. If multiple threads try to concurrently remove
     // the same item only one of them should succeed. Marking the bottom level establishes which of them succeeds.
     for (int level = item->top_level; level > 0; --level) {
     // Mark and unlink <item> at each level of <sl> from the top down. If multiple threads try to concurrently remove
     // the same item only one of them should succeed. Marking the bottom level establishes which of them succeeds.
     for (int level = item->top_level; level > 0; --level) {

-        uint64_t next;
-        uint64_t old_next = item->next[level];
+        markable_t next;
+        markable_t old_next = item->next[level];

         do {
             next = old_next;
         do {
             next = old_next;

-            old_next = SYNC_CAS(&item->next[level], next, TAG_VALUE(next, TAG1));
-            if (IS_TAGGED(old_next, TAG1)) {
+            old_next = SYNC_CAS(&item->next[level], next, MARK_NODE((node_t *)next));
+            if (HAS_MARK(old_next)) {

                 TRACE("s2", "sl_remove: %p is already marked for removal by another thread at level %llu", item, level);
                 break;
             }
         } while (next != old_next);
 
         node_t *pred = preds[level];
                 TRACE("s2", "sl_remove: %p is already marked for removal by another thread at level %llu", item, level);
                 break;
             }
         } while (next != old_next);
 
         node_t *pred = preds[level];

-        TRACE("s2", "sl_remove: linking the item's pred %p to the item's successor %p", pred, STRIP_TAG(next, TAG1));
-        uint64_t other = SYNC_CAS(&pred->next[level], (uint64_t)(size_t)item, STRIP_TAG(next, TAG1));
-        if (other != (uint64_t)(size_t)item) {
+        TRACE("s2", "sl_remove: linking the item's pred %p to the item's successor %p", pred, STRIP_MARK(next));
+        markable_t other = SYNC_CAS(&pred->next[level], item, STRIP_MARK(next));
+        if (other != (markable_t)item) {

             TRACE("s1", "sl_remove: unlink failed; pred's link changed from %p to %p", item, other);
             // If our former predecessor now points past us we know another thread unlinked us. Otherwise, we need
             // to search for a new set of preds.
             TRACE("s1", "sl_remove: unlink failed; pred's link changed from %p to %p", item, other);
             // If our former predecessor now points past us we know another thread unlinked us. Otherwise, we need
             // to search for a new set of preds.


@@ -387,12 +400,12 @@ map_val_t sl_remove (skiplist_t *sl, map_key_t key) {
                 continue; // <pred> points past <item> to the end of the list; go on to the next level.
 
             int d = -1;
                 continue; // <pred> points past <item> to the end of the list; go on to the next level.
 
             int d = -1;

-            if (!IS_TAGGED(other, TAG1)) {
-                map_key_t other_key = ((node_t *)(size_t)other)->key;
+            if (!HAS_MARK(other)) {
+                map_key_t other_key = GET_NODE(other)->key;

                 if (EXPECT_TRUE(sl->key_type == NULL)) {
                 if (EXPECT_TRUE(sl->key_type == NULL)) {

-                    d = (uint64_t)item->key - (uint64_t)other_key;
+                    d = item->key - other_key;

                 } else {
                 } else {

-                    d = sl->key_type->cmp((void *)(size_t)item->key, (void *)(size_t)other_key);
+                    d = sl->key_type->cmp((void *)item->key, (void *)other_key);

                 }
             }
             if (d > 0) {
                 }
             }
             if (d > 0) {


@@ -404,12 +417,12 @@ map_val_t sl_remove (skiplist_t *sl, map_key_t key) {
         }
     }
 
         }
     }
 

-    uint64_t next;
-    uint64_t old_next = item->next[0];
+    markable_t next;
+    markable_t old_next = item->next[0];

     do {
         next = old_next;
     do {
         next = old_next;

-        old_next = SYNC_CAS(&item->next[0], next, TAG_VALUE(next, TAG1));
-        if (IS_TAGGED(old_next, TAG1)) {
+        old_next = SYNC_CAS(&item->next[0], next, MARK_NODE((node_t *)next));
+        if (HAS_MARK(old_next)) {

             TRACE("s2", "sl_remove: %p is already marked for removal by another thread at level 0", item, 0);
             return DOES_NOT_EXIST;
         }
             TRACE("s2", "sl_remove: %p is already marked for removal by another thread at level 0", item, 0);
             return DOES_NOT_EXIST;
         }


@@ -422,12 +435,12 @@ map_val_t sl_remove (skiplist_t *sl, map_key_t key) {
     TRACE("s2", "sl_remove: replaced item %p's value with DOES_NOT_EXIT", item, 0);
 
     node_t *pred = preds[0];
     TRACE("s2", "sl_remove: replaced item %p's value with DOES_NOT_EXIT", item, 0);
 
     node_t *pred = preds[0];

-    TRACE("s2", "sl_remove: linking the item's pred %p to the item's successor %p", pred, STRIP_TAG(next, TAG1));
-    if (SYNC_CAS(&pred->next[0], item, STRIP_TAG(next, TAG1))) {
+    TRACE("s2", "sl_remove: linking the item's pred %p to the item's successor %p", pred, STRIP_MARK(next));
+    if (SYNC_CAS(&pred->next[0], item, STRIP_MARK(next))) {

         TRACE("s2", "sl_remove: unlinked item %p from the skiplist at level 0", item, 0);
         // The thread that completes the unlink should free the memory.
         if (sl->key_type != NULL) {
         TRACE("s2", "sl_remove: unlinked item %p from the skiplist at level 0", item, 0);
         // The thread that completes the unlink should free the memory.
         if (sl->key_type != NULL) {

-            nbd_defer_free((void *)(size_t)item->key);
+            nbd_defer_free((void *)item->key);

         }
         nbd_defer_free(item);
     }
         }
         nbd_defer_free(item);
     }


@@ -442,9 +455,9 @@ void sl_print (skiplist_t *sl) {
         printf("(%d) ", level);
         int i = 0;
         while (item) {
         printf("(%d) ", level);
         int i = 0;
         while (item) {

-            uint64_t next = item->next[level];
-            printf("%s%p ", IS_TAGGED(next, TAG1) ? "*" : "", item);
-            item = (node_t *)(size_t)STRIP_TAG(next, TAG1);
+            markable_t next = item->next[level];
+            printf("%s%p ", HAS_MARK(next) ? "*" : "", item);
+            item = STRIP_MARK(next);

             if (i++ > 30) {
                 printf("...");
                 break;
             if (i++ > 30) {
                 printf("...");
                 break;


@@ -456,23 +469,23 @@ void sl_print (skiplist_t *sl) {
     node_t *item = sl->head;
     int i = 0;
     while (item) {
     node_t *item = sl->head;
     int i = 0;
     while (item) {

-        int is_marked = IS_TAGGED(item->next[0], TAG1);
-        printf("%s%p:0x%llx ", is_marked ? "*" : "", item, (uint64_t)(size_t)item->key);
+        int is_marked = HAS_MARK(item->next[0]);
+        printf("%s%p:0x%llx ", is_marked ? "*" : "", item, (map_key_t)item->key);

         if (item != sl->head) {
             printf("[%d]", item->top_level);
         } else {
             printf("[HEAD]");
         }
         for (int level = 1; level <= item->top_level; ++level) {
         if (item != sl->head) {
             printf("[%d]", item->top_level);
         } else {
             printf("[HEAD]");
         }
         for (int level = 1; level <= item->top_level; ++level) {

-            node_t *next = (node_t *)(size_t)STRIP_TAG(item->next[level], TAG1);
-            is_marked = IS_TAGGED(item->next[0], TAG1);
+            node_t *next = STRIP_MARK(item->next[level]);
+            is_marked = HAS_MARK(item->next[0]);

             printf(" %p%s", next, is_marked ? "*" : "");
             if (item == sl->head && item->next[level] == DOES_NOT_EXIST)
                 break;
         }
         printf("\n");
         fflush(stdout);
             printf(" %p%s", next, is_marked ? "*" : "");
             if (item == sl->head && item->next[level] == DOES_NOT_EXIST)
                 break;
         }
         printf("\n");
         fflush(stdout);

-        item = (node_t *)(size_t)STRIP_TAG(item->next[0], TAG1);
+        item = STRIP_MARK(item->next[0]);

         if (i++ > 30) {
             printf("...\n");
             break;
         if (i++ > 30) {
             printf("...\n");
             break;


@@ -489,14 +502,14 @@ sl_iter_t *sl_iter_begin (skiplist_t *sl, map_key_t key) {
 map_val_t sl_iter_next (sl_iter_t *iter, map_key_t *key_ptr) {
     assert(iter);
     node_t *item = iter->next;
 map_val_t sl_iter_next (sl_iter_t *iter, map_key_t *key_ptr) {
     assert(iter);
     node_t *item = iter->next;

-    while (item != NULL && IS_TAGGED(item->next[0], TAG1)) {
-        item = (node_t *)(size_t)STRIP_TAG(item->next[0], TAG1);
+    while (item != NULL && HAS_MARK(item->next[0])) {
+        item = STRIP_MARK(item->next[0]);

     }
     if (item == NULL) {
         iter->next = NULL;
         return DOES_NOT_EXIST;
     }
     }
     if (item == NULL) {
         iter->next = NULL;
         return DOES_NOT_EXIST;
     }

-    iter->next = (node_t *)(size_t)STRIP_TAG(item->next[0], TAG1);
+    iter->next = STRIP_MARK(item->next[0]);

     if (key_ptr != NULL) {
         *key_ptr = item->key;
     }
     if (key_ptr != NULL) {
         *key_ptr = item->key;
     }

diff --git a/test/map_test1.c b/test/map_test1.c
index 1aa13d26a396bc6713be8bc889067c600cb35f9f..9ba7f4a8487221a067aa6d7ff73f357901a73527 100644 (file)
--- a/test/map_test1.c
+++ b/test/map_test1.c
@@ -11,7 +11,7 @@
 #include "skiplist.h"
 #include "hashtable.h"
 
 #include "skiplist.h"
 #include "hashtable.h"
 

-#define NUM_ITERATIONS 1000000
+#define NUM_ITERATIONS 10000000

 
 //#define TEST_STRING_KEYS
 
 
 //#define TEST_STRING_KEYS
 


@@ -31,14 +31,14 @@ void *worker (void *arg) {
 
     for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) {
         unsigned r = nbd_rand();
 
     for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) {
         unsigned r = nbd_rand();

-        uint64_t key = r & 0xF;
+        int key = r & 0xF;

 #ifdef TEST_STRING_KEYS
         key_str->len = sprintf(key_str->data, "%llX", key) + 1;
         assert(key_str->len <= 10);
         if (r & (1 << 8)) {
 #ifdef TEST_STRING_KEYS
         key_str->len = sprintf(key_str->data, "%llX", key) + 1;
         assert(key_str->len <= 10);
         if (r & (1 << 8)) {

-            map_set(map_, key_str, 1);
+            map_set(map_, (map_key_t)key_str, 1);

         } else {
         } else {

-            map_remove(map_, key_str);
+            map_remove(map_, (map_key_t)key_str);

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

diff --git a/test/map_test2.c b/test/map_test2.c
index 831ecad1dda955997cf5a104630a06ac8111e824..f08a37433abbe9025bda0f49c342cf8f73465346 100644 (file)
--- a/test/map_test2.c
+++ b/test/map_test2.c
@@ -33,9 +33,9 @@ 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) {
+static size_t iterator_size (map_t *map) {

     map_iter_t *iter = map_iter_begin(map, 0);
     map_iter_t *iter = map_iter_begin(map, 0);

-    uint64_t count = 0;
+    size_t count = 0;

     while (map_iter_next(iter, NULL) != DOES_NOT_EXIST) {
         count++;
     }
     while (map_iter_next(iter, NULL) != DOES_NOT_EXIST) {
         count++;
     }


@@ -129,7 +129,7 @@ void *add_remove_worker (void *arg) {
     worker_data_t *wd = (worker_data_t *)arg;
     map_t *map = wd->map;
     CuTest* tc = wd->tc;
     worker_data_t *wd = (worker_data_t *)arg;
     map_t *map = wd->map;
     CuTest* tc = wd->tc;

-    uint64_t d = wd->id;
+    int d = wd->id;

     int iters = 10000;
 
     SYNC_ADD(wd->wait, -1);
     int iters = 10000;
 
     SYNC_ADD(wd->wait, -1);


@@ -142,7 +142,7 @@ void *add_remove_worker (void *arg) {
 #endif
 
     for (int j = 0; j < 10; ++j) {
 #endif
 
     for (int j = 0; j < 10; ++j) {

-        for (uint64_t i = d+1; i < iters; i+=2) {
+        for (int i = d+1; i < iters; i+=2) {

 #ifdef TEST_STRING_KEYS
             memset(key->data, 0, key->len);
             snprintf(key->data, key->len, "%llu", i);
 #ifdef TEST_STRING_KEYS
             memset(key->data, 0, key->len);
             snprintf(key->data, key->len, "%llu", i);


@@ -153,10 +153,10 @@ void *add_remove_worker (void *arg) {
             ASSERT_EQUAL(DOES_NOT_EXIST, map_add(map, key, d+1) );
             rcu_update(); // In a quiecent state.
         }
             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) {
+        for (int i = d+1; i < iters; i+=2) {

 #ifdef TEST_STRING_KEYS
             memset(key->data, 0, key->len);
 #ifdef TEST_STRING_KEYS
             memset(key->data, 0, key->len);

-            snprintf(key->data, key->len, "%llu", i);
+            snprintf(key->data, key->len, "%u", i);

 #else
             key = (map_key_t)i;
 #endif
 #else
             key = (map_key_t)i;
 #endif


@@ -231,7 +231,7 @@ void basic_iteration_test (CuTest* tc) {
     ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k1,1) );
     ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k2,2) );
 
     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_val_t x_v, y_v;

     map_iter_t *iter = map_iter_begin(map, 0);
     x_v = map_iter_next(iter, &x_k);
     y_v = map_iter_next(iter, &y_k);
     map_iter_t *iter = map_iter_begin(map, 0);
     x_v = map_iter_next(iter, &x_k);
     y_v = map_iter_next(iter, &y_k);


@@ -282,7 +282,7 @@ void big_iteration_test (CuTest* tc) {
     ASSERT_EQUAL( n, iterator_size(map) );
 
     uint64_t sum = 0;
     ASSERT_EQUAL( n, iterator_size(map) );
 
     uint64_t sum = 0;

-    uint64_t val;
+    map_val_t val;

     map_iter_t *iter = map_iter_begin(map, 0);
     while ((val = map_iter_next(iter, NULL)) != DOES_NOT_EXIST) {
         sum += val;
     map_iter_t *iter = map_iter_begin(map, 0);
     while ((val = map_iter_next(iter, NULL)) != DOES_NOT_EXIST) {
         sum += val;

diff --git a/txn/txn.c b/txn/txn.c
index 2893d35dbcfb40ec5152775146f59224cb96034d..ef8313f56aaa5fe4c4796f4b200b21c727b9894d 100644 (file)
--- a/txn/txn.c
+++ b/txn/txn.c
@@ -29,9 +29,9 @@ struct txn {
     uint64_t wv;
     map_t *map;
     write_rec_t *writes;
     uint64_t wv;
     map_t *map;
     write_rec_t *writes;

-    uint64_t writes_size;
-    uint64_t writes_count;
-    uint64_t writes_scan;
+    size_t writes_size;
+    size_t writes_count;
+    size_t writes_scan;

     txn_state_e state;
 };
 
     txn_state_e state;
 };
 


@@ -65,7 +65,7 @@ static txn_state_e validate_key (txn_t *txn, map_key_t key) {
         // will eventually conflict with it and abort.
         if (!IS_TAGGED(val, TAG2))
             return TXN_VALIDATED;
         // will eventually conflict with it and abort.
         if (!IS_TAGGED(val, TAG2))
             return TXN_VALIDATED;

-        update = (update_t *)(size_t)STRIP_TAG(val, TAG2);
+        update = (update_t *)STRIP_TAG(val, TAG2);

         if (!IS_TAGGED(update->version, TAG1)) 
             return (update->version <= txn->rv) ? TXN_VALIDATED : TXN_ABORTED;
 
         if (!IS_TAGGED(update->version, TAG1)) 
             return (update->version <= txn->rv) ? TXN_VALIDATED : TXN_ABORTED;
 


@@ -77,7 +77,7 @@ static txn_state_e validate_key (txn_t *txn, map_key_t key) {
             continue;
 
         // The update's transaction is still in progress. Access its txn_t.
             continue;
 
         // The update's transaction is still in progress. Access its txn_t.

-        txn_t *writer = (txn_t *)(size_t)STRIP_TAG(update->version, TAG1);
+        txn_t *writer = (txn_t *)STRIP_TAG(update->version, TAG1);

         if (writer == txn)
             continue; // Skip our own updates.
         txn_state_e writer_state = writer->state;
         if (writer == txn)
             continue; // Skip our own updates.
         txn_state_e writer_state = writer->state;


@@ -234,20 +234,20 @@ 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 txn_map_get (txn_t *txn, map_key_t key) {
+map_val_t txn_map_get (txn_t *txn, map_key_t key) {

     if (txn->state != TXN_RUNNING)
         return ERROR_TXN_NOT_RUNNING;
 
     // Iterate through the update records to find the latest committed version prior to our read version. 
     if (txn->state != TXN_RUNNING)
         return ERROR_TXN_NOT_RUNNING;
 
     // Iterate through the update records to find the latest committed version prior to our read version. 

-    uint64_t newest_val = map_get(txn->map, key);
-    uint64_t val = newest_val;
+    map_val_t newest_val = map_get(txn->map, key);
+    map_val_t val = newest_val;

     update_t *update = NULL;
     for ( ; ; val = update->next) {
 
         if (!IS_TAGGED(val, TAG2))
             return val;
 
     update_t *update = NULL;
     for ( ; ; val = update->next) {
 
         if (!IS_TAGGED(val, TAG2))
             return val;
 

-        update = (update_t *)(size_t)STRIP_TAG(val, TAG2);
+        update = (update_t *)STRIP_TAG(val, TAG2);

         assert(update != NULL);
 
         // If the update's version is not tagged it means the update is committed.
         assert(update != NULL);
 
         // If the update's version is not tagged it means the update is committed.


@@ -265,7 +265,7 @@ uint64_t txn_map_get (txn_t *txn, map_key_t key) {
             continue;
 
         // The update's transaction is still in progress. Access its txn_t.
             continue;
 
         // The update's transaction is still in progress. Access its txn_t.

-        txn_t *writer = (txn_t *)(size_t)STRIP_TAG(update->version, TAG1);
+        txn_t *writer = (txn_t *)STRIP_TAG(update->version, TAG1);

         if (writer == txn) // found our own update
             break; // success 
 
         if (writer == txn) // found our own update
             break; // success 
 


@@ -289,13 +289,13 @@ uint64_t txn_map_get (txn_t *txn, map_key_t key) {
         break; // success
     }
 
         break; // success
     }
 

-    uint64_t value = update->value;
+    map_val_t value = update->value;

 
     // collect some garbage
     uint64_t min_active_version = UNDETERMINED_VERSION;
     update_t *next_update = NULL;
     if (IS_TAGGED(update->next, TAG2)) {
 
     // collect some garbage
     uint64_t min_active_version = UNDETERMINED_VERSION;
     update_t *next_update = NULL;
     if (IS_TAGGED(update->next, TAG2)) {

-        next_update = (update_t *)(size_t)STRIP_TAG(update->next, TAG2);
+        next_update = (update_t *)STRIP_TAG(update->next, TAG2);

         min_active_version = (uint64_t)sl_min_key(active_);
         if (next_update->version < min_active_version) {
             // <next_update> (and all update records following it [execpt if it is aborted]) is old enough that it is
         min_active_version = (uint64_t)sl_min_key(active_);
         if (next_update->version < min_active_version) {
             // <next_update> (and all update records following it [execpt if it is aborted]) is old enough that it is


@@ -309,7 +309,7 @@ uint64_t txn_map_get (txn_t *txn, map_key_t key) {
                 if (!IS_TAGGED(next, TAG2))
                     break;
 
                 if (!IS_TAGGED(next, TAG2))
                     break;
 

-                temp = (update_t *)(size_t)STRIP_TAG(next, TAG2);
+                temp = (update_t *)STRIP_TAG(next, TAG2);

                 if (temp->version >= min_active_version)
                     return value;
             }
                 if (temp->version >= min_active_version)
                     return value;
             }


@@ -326,7 +326,7 @@ uint64_t txn_map_get (txn_t *txn, map_key_t key) {
                 if (!IS_TAGGED(next, TAG2))
                     break;
 
                 if (!IS_TAGGED(next, TAG2))
                     break;
 

-                temp = (update_t *)(size_t)STRIP_TAG(next, TAG2);
+                temp = (update_t *)STRIP_TAG(next, TAG2);

                 nbd_free(update);
             }
         }
                 nbd_free(update);
             }
         }


@@ -348,21 +348,21 @@ uint64_t txn_map_get (txn_t *txn, map_key_t key) {
     return value;
 }
 
     return value;
 }
 

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

     if (txn->state != TXN_RUNNING)
         return; // TODO: return some sort of error code
 
     // create a new update record
     update_t *update = alloc_update_rec();
     update->value = value;
     if (txn->state != TXN_RUNNING)
         return; // TODO: return some sort of error code
 
     // create a new update record
     update_t *update = alloc_update_rec();
     update->value = value;

-    update->version = TAG_VALUE((uint64_t)(size_t)txn, TAG1);
+    update->version = TAG_VALUE((uint64_t)txn, TAG1);

 
     // push the new update record onto <key>'s update list
     uint64_t old_update;
     do {
         old_update = map_get(txn->map, key);
         update->next = old_update;
 
     // push the new update record onto <key>'s update list
     uint64_t old_update;
     do {
         old_update = map_get(txn->map, key);
         update->next = old_update;

-    } while (map_cas(txn->map, key, old_update, TAG_VALUE((uint64_t)(size_t)update, TAG2)) != old_update);
+    } while (map_cas(txn->map, key, old_update, TAG_VALUE((uint64_t)update, TAG2)) != old_update);

 
     // add <key> to the write set for commit-time validation
     if (txn->writes_count == txn->writes_size) {
 
     // add <key> to the write set for commit-time validation
     if (txn->writes_count == txn->writes_size) {