From: jdybnis Date: Tue, 16 Dec 2008 06:30:37 +0000 (+0000) Subject: introduce some more typedefs and conversion functions to improve portability X-Git-Url: https://pd.if.org/git/?p=nbds;a=commitdiff_plain;h=4ae7c1069667d8f067258d89676126f9b44226d6 introduce some more typedefs and conversion functions to improve portability --- diff --git a/include/common.h b/include/common.h index 9abf743..a799eac 100644 --- 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 uint64_t markable_t; + #include "lwt.h" #endif //COMMON_H diff --git a/include/hashtable.h b/include/hashtable.h index 880f2a4..3fb5d6c 100644 --- 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); -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); -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 = { diff --git a/include/list.h b/include/list.h index 7eb815e..0274066 100644 --- 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_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); diff --git a/include/skiplist.h b/include/skiplist.h index 5c707fc..484c64c 100644 --- 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_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); diff --git a/makefile b/makefile index 82d921e..6ca5843 100644 --- 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) +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 ################################################################################################### @@ -62,4 +70,4 @@ $(addsuffix .d, $(EXES)) : output/%.d : -include $(addsuffix .d, $(EXES)) -.PHONY: clean test tags +.PHONY: clean test tags asm diff --git a/map/hashtable.c b/map/hashtable.c index a757cfc..b229d43 100644 --- a/map/hashtable.c +++ b/map/hashtable.c @@ -18,10 +18,10 @@ #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 { - uint64_t key; + map_key_t key; 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)); - 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)); @@ -98,7 +98,7 @@ static volatile entry_t *hti_lookup (hti_t *hti, map_key_t key, uint32_t key_has // Compare 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; } @@ -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)) { - 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; } @@ -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 - 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 @@ -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. - 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)) { - nbd_defer_free((void *)(size_t)key); + nbd_defer_free((void *)key); } 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) - : ht1->ht->key_type->hash((void *)(size_t)key); + : ht1->ht->key_type->hash((void *)key); } 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) { - 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); @@ -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 . - 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 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) { @@ -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) { - 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; - 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<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; - 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; @@ -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; - 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) @@ -538,9 +540,9 @@ map_val_t ht_remove (hashtable_t *ht, map_key_t key) { } // Returns the number of key-values pairs in -uint64_t ht_count (hashtable_t *ht) { +size_t ht_count (hashtable_t *ht) { hti_t *hti = ht->hti; - uint64_t count = 0; + size_t count = 0; 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; - 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]; - 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); @@ -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) - : 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); } diff --git a/map/list.c b/map/list.c index 250e406..98522c3 100644 --- a/map/list.c +++ b/map/list.c @@ -14,9 +14,9 @@ #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 { @@ -28,6 +28,12 @@ struct ll { const datatype_t *key_type; }; +// Marking the 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; @@ -44,40 +50,40 @@ list_t *ll_alloc (const datatype_t *key_type) { } 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; } } -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) { - if (!IS_TAGGED(item->next, TAG1)) { + if (!HAS_MARK(item->next)) { 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; - 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) { - 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) { - 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); @@ -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); - 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); - 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. + node_t *unlinked = GET_NODE(other); 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); - if (IS_TAGGED(other, TAG1)) + if (HAS_MARK(other)) 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; } } @@ -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)) { - d = (uint64_t)item->key - (uint64_t)key; + d = item->key - key; } 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); } @@ -143,7 +150,7 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, map_key_ } pred = item; - item = (node_t *)(size_t)next; + item = GET_NODE(next); } // is not in . @@ -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); - 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); - 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 @@ -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) { - nbd_free((void *)(size_t)new_key); + nbd_free((void *)new_key); } nbd_free(new_item); continue; // retry @@ -256,18 +261,18 @@ map_val_t ll_remove (list_t *ll, map_key_t key) { } // Mark 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; - 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); - 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. @@ -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); - 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) { - 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); @@ -294,13 +299,13 @@ map_val_t ll_remove (list_t *ll, map_key_t key) { } 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) { - if (IS_TAGGED(next, TAG1)) { + if (HAS_MARK(next)) { 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); @@ -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; - 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; } - 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; } diff --git a/map/skiplist.c b/map/skiplist.c index e81a896..5366d91 100644 --- 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; - uint64_t next[]; + markable_t next[]; } node_t; struct sl_iter { @@ -44,6 +44,19 @@ struct sl { const datatype_t *key_type; }; +// Marking the 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) @@ -76,25 +89,25 @@ skiplist_t *sl_alloc (const datatype_t *key_type) { } 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) { - 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) { - nbd_free((void *)(size_t)item->key); + nbd_free((void *)item->key); } 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) { - if (!IS_TAGGED(item->next[0], TAG1)) { + if (!HAS_MARK(item->next[0])) { count++; } - item = (node_t *)(size_t)STRIP_TAG(item->next[0], TAG1); + item = STRIP_MARK(item->next[0]); } 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 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 } + item = GET_NODE(next); 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. - while (EXPECT_FALSE(IS_TAGGED(next, TAG1))) { + while (EXPECT_FALSE(HAS_MARK(next))) { // 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]; @@ -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); - 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) { + node_t *unlinked = GET_NODE(other); 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); - if (IS_TAGGED(other, TAG1)) + if (HAS_MARK(other)) 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; } } @@ -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); - 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)) { - d = (uint64_t)item->key - (uint64_t)key; + d = item->key - key; } 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) { @@ -187,7 +202,7 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl } pred = item; - item = (node_t *)(size_t)next; + item = GET_NODE(next); } // 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) { - node_t *item = (node_t *)(size_t)sl->head->next[0]; + node_t *item = GET_NODE(sl->head->next[0]); 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; - item = (node_t *)(size_t)STRIP_TAG(next, TAG1); + item = STRIP_MARK(next); } 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 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]; - 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) { - 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) { - nbd_free((void *)(size_t)new_key); + nbd_free((void *)new_key); } 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 into 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); - 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 @@ -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]; - next = (uint64_t)(size_t)nexts[level]; + next = (markable_t)nexts[level]; // Update '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. @@ -365,21 +378,21 @@ map_val_t sl_remove (skiplist_t *sl, map_key_t key) { // Mark and unlink at each level of 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; - 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: 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. @@ -387,12 +400,12 @@ map_val_t sl_remove (skiplist_t *sl, map_key_t key) { continue; // points past 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)) { - d = (uint64_t)item->key - (uint64_t)other_key; + d = item->key - other_key; } 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) { @@ -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; - 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; } @@ -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: 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) { - nbd_defer_free((void *)(size_t)item->key); + nbd_defer_free((void *)item->key); } nbd_defer_free(item); } @@ -442,9 +455,9 @@ void sl_print (skiplist_t *sl) { 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; @@ -456,23 +469,23 @@ void sl_print (skiplist_t *sl) { 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) { - 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); - item = (node_t *)(size_t)STRIP_TAG(item->next[0], TAG1); + item = STRIP_MARK(item->next[0]); 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; - 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; } - 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; } diff --git a/test/map_test1.c b/test/map_test1.c index 1aa13d2..9ba7f4a 100644 --- a/test/map_test1.c +++ b/test/map_test1.c @@ -11,7 +11,7 @@ #include "skiplist.h" #include "hashtable.h" -#define NUM_ITERATIONS 1000000 +#define NUM_ITERATIONS 10000000 //#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(); - 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)) { - map_set(map_, key_str, 1); + map_set(map_, (map_key_t)key_str, 1); } else { - map_remove(map_, key_str); + map_remove(map_, (map_key_t)key_str); } #else if (r & (1 << 8)) { diff --git a/test/map_test2.c b/test/map_test2.c index 831ecad..f08a374 100644 --- 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 uint64_t iterator_size (map_t *map) { +static size_t iterator_size (map_t *map) { 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++; } @@ -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; - uint64_t d = wd->id; + int d = wd->id; 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) { - 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); @@ -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. } - 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); + snprintf(key->data, key->len, "%u", i); #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) ); - 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); @@ -282,7 +282,7 @@ void big_iteration_test (CuTest* tc) { 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; diff --git a/txn/txn.c b/txn/txn.c index 2893d35..ef8313f 100644 --- 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 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; }; @@ -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; - 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; @@ -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. - 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; @@ -234,20 +234,20 @@ txn_state_e txn_commit (txn_t *txn) { } // 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. - 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 = (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. @@ -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. - 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 @@ -289,13 +289,13 @@ uint64_t txn_map_get (txn_t *txn, map_key_t key) { 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)) { - 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) { // (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; - temp = (update_t *)(size_t)STRIP_TAG(next, TAG2); + temp = (update_t *)STRIP_TAG(next, TAG2); 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; - temp = (update_t *)(size_t)STRIP_TAG(next, TAG2); + temp = (update_t *)STRIP_TAG(next, TAG2); nbd_free(update); } } @@ -348,21 +348,21 @@ uint64_t txn_map_get (txn_t *txn, map_key_t key) { 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; - update->version = TAG_VALUE((uint64_t)(size_t)txn, TAG1); + update->version = TAG_VALUE((uint64_t)txn, TAG1); // push the new update record onto '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 to the write set for commit-time validation if (txn->writes_count == txn->writes_size) {