Support 32 bit x86

diff --git a/include/common.h b/include/common.h
index a799eac3d6f253b4b4d326d8a57600447d224ecf..a4fc7e3c0e27459d777821cfe59411e2b97c56a8 100644 (file)
--- a/include/common.h
+++ b/include/common.h
@@ -32,8 +32,13 @@
 #define TRUE  1
 #define FALSE 0
 
 #define TRUE  1
 #define FALSE 0
 

+#ifdef NBD32
+#define TAG1         (1U << 31)
+#define TAG2         (1U << 30)
+#else

 #define TAG1         (1ULL << 63)
 #define TAG2         (1ULL << 62)
 #define TAG1         (1ULL << 63)
 #define TAG2         (1ULL << 62)

+#endif

 #define TAG_VALUE(v, tag) ((v) |  tag)
 #define IS_TAGGED(v, tag) ((v) &  tag)
 #define STRIP_TAG(v, tag) ((v) & ~tag)
 #define TAG_VALUE(v, tag) ((v) |  tag)
 #define IS_TAGGED(v, tag) ((v) &  tag)
 #define STRIP_TAG(v, tag) ((v) & ~tag)


@@ -48,7 +53,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;
+typedef size_t markable_t;

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

diff --git a/include/map.h b/include/map.h
index b74974482db1f98bbdad114dffc629f1be06198e..0f847aa7e49385afbba45465c7e8238532e3b7a1 100644 (file)
--- a/include/map.h
+++ b/include/map.h
@@ -7,8 +7,13 @@ typedef struct map map_t;
 typedef struct map_iter map_iter_t;
 typedef struct map_impl map_impl_t;
 
 typedef struct map_iter map_iter_t;
 typedef struct map_impl map_impl_t;
 

+#ifdef NBD32
+typedef uint32_t map_key_t;
+typedef uint32_t map_val_t;
+#else

 typedef uint64_t map_key_t;
 typedef uint64_t map_val_t;
 typedef uint64_t map_key_t;
 typedef uint64_t map_val_t;

+#endif

 
 map_t *   map_alloc   (const map_impl_t *map_impl, const datatype_t *key_type);
 map_val_t map_get     (map_t *map, map_key_t key);
 
 map_t *   map_alloc   (const map_impl_t *map_impl, const datatype_t *key_type);
 map_val_t map_get     (map_t *map, map_key_t key);


@@ -22,7 +27,7 @@ void      map_print   (map_t *map);
 void      map_free    (map_t *map);
 
 map_iter_t * map_iter_begin (map_t *map, map_key_t key);
 void      map_free    (map_t *map);
 
 map_iter_t * map_iter_begin (map_t *map, map_key_t key);

-map_val_t     map_iter_next  (map_iter_t *iter, map_key_t *key);
+map_val_t    map_iter_next  (map_iter_t *iter, map_key_t *key);

 void         map_iter_free  (map_iter_t *iter);
 
 /////////////////////////////////////////////////////////////////////////////////////
 void         map_iter_free  (map_iter_t *iter);
 
 /////////////////////////////////////////////////////////////////////////////////////


@@ -32,14 +37,14 @@ void         map_iter_free  (map_iter_t *iter);
 #define CAS_EXPECT_WHATEVER       (-2)
 
 typedef void *    (*map_alloc_t)  (const datatype_t *);
 #define CAS_EXPECT_WHATEVER       (-2)
 
 typedef void *    (*map_alloc_t)  (const datatype_t *);

-typedef map_val_t (*map_cas_t)    (map_impl_t *, map_key_t , map_val_t, map_val_t);
-typedef map_val_t (*map_get_t)    (map_impl_t *, map_key_t );
-typedef map_val_t (*map_remove_t) (map_impl_t *, map_key_t );
-typedef map_val_t (*map_count_t)  (map_impl_t *);
-typedef void      (*map_print_t)  (map_impl_t *);
-typedef void      (*map_free_t)   (map_impl_t *);
-
-typedef map_iter_t * (*map_iter_begin_t) (map_impl_t *, map_key_t );
+typedef map_val_t (*map_cas_t)    (void *, map_key_t , map_val_t, map_val_t);
+typedef map_val_t (*map_get_t)    (void *, map_key_t );
+typedef map_val_t (*map_remove_t) (void *, map_key_t );
+typedef size_t    (*map_count_t)  (void *);
+typedef void      (*map_print_t)  (void *);
+typedef void      (*map_free_t)   (void *);
+
+typedef map_iter_t * (*map_iter_begin_t) (void *, map_key_t);

 typedef map_val_t    (*map_iter_next_t)  (map_iter_t *, map_key_t *);
 typedef void         (*map_iter_free_t)  (map_iter_t *);
 
 typedef map_val_t    (*map_iter_next_t)  (map_iter_t *, map_key_t *);
 typedef void         (*map_iter_free_t)  (map_iter_t *);
 

diff --git a/include/txn.h b/include/txn.h
index 34a385758271dc1f8d6fd28ae784913f3ca153d2..7cc40d0c42344f1a53aa003f79253ce5b1b0abfa 100644 (file)
--- a/include/txn.h
+++ b/include/txn.h
@@ -17,7 +17,7 @@ txn_t *     txn_begin  (map_t *map);
 void        txn_abort  (txn_t *txn);
 txn_state_e txn_commit (txn_t *txn);
 
 void        txn_abort  (txn_t *txn);
 txn_state_e txn_commit (txn_t *txn);
 

-uint64_t    txn_map_get (txn_t *txn, map_key_t key);
+map_val_t   txn_map_get (txn_t *txn, map_key_t key);

 void        txn_map_set (txn_t *txn, map_key_t key, map_val_t value);
 
 #endif//TXN_H
 void        txn_map_set (txn_t *txn, map_key_t key, map_val_t value);
 
 #endif//TXN_H

diff --git a/makefile b/makefile
index 6ca58432c4e992e87144f8f451f09b8bf5685a1d..92aa921eb3c97d36607631ca1590452e46b6c58d 100644 (file)
--- a/makefile
+++ b/makefile
@@ -5,7 +5,7 @@
 # Makefile for building programs with whole-program interfile optimization
 ###################################################################################################
 OPT       := -fwhole-program -combine -03 #-DNDEBUG
 # Makefile for building programs with whole-program interfile optimization
 ###################################################################################################
 OPT       := -fwhole-program -combine -03 #-DNDEBUG

-CFLAGS := -g -Wall -Werror -std=c99 -m64 $(OPT) #-DENABLE_TRACE
+CFLAGS := -g -Wall -Werror -std=c99 $(OPT) -m64 #-DNBD32 #-DENABLE_TRACE

 INCS   := $(addprefix -I, include)
 TESTS  := output/map_test1 output/map_test2 output/txn_test
 EXES   := $(TESTS)
 INCS   := $(addprefix -I, include)
 TESTS  := output/map_test1 output/map_test2 output/txn_test
 EXES   := $(TESTS)

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

+#ifndef NBD32

 #define GET_PTR(x) ((void *)((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

+#else
+#define GET_PTR(x) ((void *)(x))
+#endif

 
 typedef struct entry {
     map_key_t key;
 
 typedef struct entry {
     map_key_t key;


@@ -103,14 +107,18 @@ static volatile entry_t *hti_lookup (hti_t *hti, map_key_t key, uint32_t key_has
                     return ent;
                 }
             } else {
                     return ent;
                 }
             } else {

+#ifndef NBD32

                 // The key in <ent> is made up of two parts. The 48 low-order bits are a pointer. The
                 // 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)) {
                 // The key in <ent> is made up of two parts. The 48 low-order bits are a pointer. The
                 // 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)) {

+#endif

                     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;
                     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;

+#ifndef NBD32

                     }
                     }

+#endif

                 }
             }
         }
                 }
             }
         }


@@ -184,7 +192,9 @@ static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_h
     assert(ht1->next);
     assert(ht2);
     assert(ht1_ent >= ht1->table && ht1_ent < ht1->table + (1 << ht1->scale));
     assert(ht1->next);
     assert(ht2);
     assert(ht1_ent >= ht1->table && ht1_ent < ht1->table + (1 << ht1->scale));

+#ifndef NBD32

     assert(key_hash == 0 || ht1->ht->key_type == NULL || (key_hash >> 16) == (ht1_ent->key >> 48));
     assert(key_hash == 0 || ht1->ht->key_type == NULL || (key_hash >> 16) == (ht1_ent->key >> 48));

+#endif

 
     map_val_t ht1_ent_val = ht1_ent->val;
     if (EXPECT_FALSE(ht1_ent_val == COPIED_VALUE)) {
 
     map_val_t ht1_ent_val = ht1_ent->val;
     if (EXPECT_FALSE(ht1_ent_val == COPIED_VALUE)) {


@@ -582,7 +592,7 @@ void ht_print (hashtable_t *ht) {
         printf("hti:%p scale:%u count:%d copied:%d\n", hti, hti->scale, hti->count, hti->num_entries_copied);
         for (int i = 0; i < (1 << hti->scale); ++i) {
             volatile entry_t *ent = hti->table + i;
         printf("hti:%p scale:%u count:%d copied:%d\n", hti, hti->scale, hti->count, hti->num_entries_copied);
         for (int i = 0; i < (1 << hti->scale); ++i) {
             volatile entry_t *ent = hti->table + i;

-            printf("[0x%x] 0x%llx:0x%llx\n", i, (uint64_t)ent->key, ent->val);
+            printf("[0x%x] 0x%llx:0x%llx\n", i, (uint64_t)ent->key, (uint64_t)ent->val);

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

diff --git a/map/list.c b/map/list.c
index 98522c3b1b7f033567a9de274c79f40901865844..f91b4184410bf16cdebdac7fada3ea13232112d3 100644 (file)
--- a/map/list.c
+++ b/map/list.c
@@ -130,11 +130,6 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, map_key_
             d = ll->key_type->cmp((void *)item->key, (void *)key);
         }
 
             d = ll->key_type->cmp((void *)item->key, (void *)key);
         }
 

-        if (next != DOES_NOT_EXIST && GET_NODE(next)->key < item->key) {
-            lwt_halt();
-            assert(0);
-        }
-

         // If we reached the key (or passed where it should be), we found the right predesssor
         if (d >= 0) {
             if (pred_ptr != NULL) {
         // If we reached the key (or passed where it should be), we found the right predesssor
         if (d >= 0) {
             if (pred_ptr != NULL) {


@@ -192,13 +187,11 @@ map_val_t ll_cas (list_t *ll, map_key_t key, map_val_t expectation, map_val_t ne
         if (!found) {
 
             // There was not an item in the list that matches the key. 
         if (!found) {
 
             // There was not an item in the list that matches the key. 

-            if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == CAS_EXPECT_EXISTS)) {
+            if (EXPECT_FALSE(expectation != CAS_EXPECT_DOES_NOT_EXIST && expectation != CAS_EXPECT_WHATEVER)) {

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

-            ASSERT(expectation == CAS_EXPECT_DOES_NOT_EXIST || expectation == CAS_EXPECT_WHATEVER);
-

             // Create a new item and insert it into the list.
             TRACE("l2", "ll_cas: attempting to insert item between %p and %p", pred, pred->next);
             map_key_t new_key = ll->key_type == NULL ? key : (map_key_t)ll->key_type->clone((void *)key);
             // 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)ll->key_type->clone((void *)key);


@@ -308,7 +301,7 @@ void ll_print (list_t *ll) {
         node_t *item = STRIP_MARK(next);
         if (item == NULL)
             break;
         node_t *item = STRIP_MARK(next);
         if (item == NULL)
             break;

-        printf("%p:0x%llx ", item, item->key);
+        printf("%p:0x%llx ", item, (uint64_t)item->key);

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


@@ -321,7 +314,11 @@ void ll_print (list_t *ll) {
 
 ll_iter_t *ll_iter_begin (list_t *ll, map_key_t key) {
     ll_iter_t *iter = (ll_iter_t *)nbd_malloc(sizeof(ll_iter_t));
 
 ll_iter_t *ll_iter_begin (list_t *ll, map_key_t key) {
     ll_iter_t *iter = (ll_iter_t *)nbd_malloc(sizeof(ll_iter_t));

-    find_pred(NULL, &iter->next, ll, key, FALSE);
+    if (key != DOES_NOT_EXIST) {
+        find_pred(NULL, &iter->next, ll, key, FALSE);
+    } else {
+        iter->next = GET_NODE(ll->head->next);
+    }

     return iter;
 }
 
     return iter;
 }
 

diff --git a/map/skiplist.c b/map/skiplist.c
index 5366d91adae9bcef2c5caa6f91cd95f6c61c8b47..e9c9b55d55a46e14d066a1d7209e6fdb65d23771 100644 (file)
--- a/map/skiplist.c
+++ b/map/skiplist.c
@@ -275,13 +275,11 @@ map_val_t sl_cas (skiplist_t *sl, map_key_t key, map_val_t expectation, map_val_
         if (old_item == NULL) {
 
             // There was not an item in the skiplist that matches the key. 
         if (old_item == NULL) {
 
             // There was not an item in the skiplist that matches the key. 

-            if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == CAS_EXPECT_EXISTS)) {
+            if (EXPECT_FALSE(expectation != CAS_EXPECT_DOES_NOT_EXIST && expectation != CAS_EXPECT_WHATEVER)) {

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

-            ASSERT(expectation == CAS_EXPECT_DOES_NOT_EXIST || expectation == CAS_EXPECT_WHATEVER);
-

             // First insert <new_item> into the bottom level.
             TRACE("s3", "sl_cas: attempting to insert item between %p and %p", preds[0], nexts[0]);
             map_key_t new_key = sl->key_type == NULL ? key : (map_key_t)sl->key_type->clone((void *)key);
             // 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)sl->key_type->clone((void *)key);


@@ -470,7 +468,7 @@ void sl_print (skiplist_t *sl) {
     int i = 0;
     while (item) {
         int is_marked = HAS_MARK(item->next[0]);
     int i = 0;
     while (item) {
         int is_marked = HAS_MARK(item->next[0]);

-        printf("%s%p:0x%llx ", is_marked ? "*" : "", item, (map_key_t)item->key);
+        printf("%s%p:0x%llx ", is_marked ? "*" : "", item, (uint64_t)item->key);

         if (item != sl->head) {
             printf("[%d]", item->top_level);
         } else {
         if (item != sl->head) {
             printf("[%d]", item->top_level);
         } else {


@@ -495,7 +493,11 @@ void sl_print (skiplist_t *sl) {
 
 sl_iter_t *sl_iter_begin (skiplist_t *sl, map_key_t key) {
     sl_iter_t *iter = (sl_iter_t *)nbd_malloc(sizeof(sl_iter_t));
 
 sl_iter_t *sl_iter_begin (skiplist_t *sl, map_key_t key) {
     sl_iter_t *iter = (sl_iter_t *)nbd_malloc(sizeof(sl_iter_t));

-    find_preds(NULL, &iter->next, 0, sl, key, FALSE);
+    if (key != DOES_NOT_EXIST) {
+        find_preds(NULL, &iter->next, 0, sl, key, FALSE);
+    } else {
+        iter->next = GET_NODE(sl->head->next[0]);
+    }

     return iter;
 }
 
     return iter;
 }
 

diff --git a/test/map_test1.c b/test/map_test1.c
index 9ba7f4a8487221a067aa6d7ff73f357901a73527..a6a7192b1626fbf06e540e8ff033e6c2aa4c89f8 100644 (file)
--- a/test/map_test1.c
+++ b/test/map_test1.c
@@ -26,14 +26,14 @@ void *worker (void *arg) {
     do {} while (wait_); 
 
 #ifdef TEST_STRING_KEYS
     do {} while (wait_); 
 
 #ifdef TEST_STRING_KEYS

-        nstring_t *key_str = ns_alloc(10);
+    nstring_t *key_str = ns_alloc(10);

 #endif
 
     for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) {
         unsigned r = nbd_rand();
         int key = r & 0xF;
 #ifdef TEST_STRING_KEYS
 #endif
 
     for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) {
         unsigned r = nbd_rand();
         int key = r & 0xF;
 #ifdef TEST_STRING_KEYS

-        key_str->len = sprintf(key_str->data, "%llX", key) + 1;
+        key_str->len = sprintf(key_str->data, "%X", key) + 1;

         assert(key_str->len <= 10);
         if (r & (1 << 8)) {
             map_set(map_, (map_key_t)key_str, 1);
         assert(key_str->len <= 10);
         if (r & (1 << 8)) {
             map_set(map_, (map_key_t)key_str, 1);


@@ -66,7 +66,7 @@ int main (int argc, char **argv) {
         return -1;
     }
 
         return -1;
     }
 

-    num_threads_ = 2;
+    num_threads_ = 1;

     if (argc == 2)
     {
         errno = 0;
     if (argc == 2)
     {
         errno = 0;

diff --git a/test/map_test2.c b/test/map_test2.c
index f08a37433abbe9025bda0f49c342cf8f73465346..f9444ca0077999c18a1f58f2dea19283219112c9 100644 (file)
--- a/test/map_test2.c
+++ b/test/map_test2.c
@@ -19,6 +19,7 @@
 #include "skiplist.h"
 #include "hashtable.h"
 #include "lwt.h"
 #include "skiplist.h"
 #include "hashtable.h"
 #include "lwt.h"

+#include "mem.h"

 
 #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
 
 
 #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
 


@@ -48,10 +49,14 @@ void basic_test (CuTest* tc) {
 
 #ifdef TEST_STRING_KEYS
     map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
 
 #ifdef TEST_STRING_KEYS
     map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);

-    nstring_t *k1 = ns_alloc(3); strcpy(k1->data, "k1");
-    nstring_t *k2 = ns_alloc(3); strcpy(k1->data, "k2");
-    nstring_t *k3 = ns_alloc(3); strcpy(k1->data, "k3");
-    nstring_t *k4 = ns_alloc(3); strcpy(k1->data, "k4");
+    nstring_t *s1 = ns_alloc(3); strcpy(s1->data, "k1");
+    nstring_t *s2 = ns_alloc(3); strcpy(s2->data, "k2");
+    nstring_t *s3 = ns_alloc(3); strcpy(s3->data, "k3");
+    nstring_t *s4 = ns_alloc(3); strcpy(s4->data, "k4");
+    map_key_t k1 = (map_key_t)s1;
+    map_key_t k2 = (map_key_t)s2;
+    map_key_t k3 = (map_key_t)s3;
+    map_key_t k4 = (map_key_t)s4;

 #else
     map_t *map = map_alloc(map_type_, NULL);
     map_key_t k1 = (map_key_t)1;
 #else
     map_t *map = map_alloc(map_type_, NULL);
     map_key_t k1 = (map_key_t)1;


@@ -121,7 +126,7 @@ void basic_test (CuTest* tc) {
 
     rcu_update(); // In a quiecent state.
 #ifdef TEST_STRING_KEYS
 
     rcu_update(); // In a quiecent state.
 #ifdef TEST_STRING_KEYS

-    nbd_free(k1); nbd_free(k2); nbd_free(k3); nbd_free(k4);
+    nbd_free(s1); nbd_free(s2); nbd_free(s3); nbd_free(s4);

 #endif
 }
 
 #endif
 }
 


@@ -135,17 +140,16 @@ void *add_remove_worker (void *arg) {
     SYNC_ADD(wd->wait, -1);
     do { } while (*wd->wait); // wait for all workers to be ready
 
     SYNC_ADD(wd->wait, -1);
     do { } while (*wd->wait); // wait for all workers to be ready
 

-#ifdef TEST_STRING_KEYS
-    nstring_t *key = ns_alloc(9);
-#else

     map_key_t key;
     map_key_t key;

+#ifdef TEST_STRING_KEYS
+    nstring_t *s = ns_alloc(9);
+    key = (map_key_t)s;

 #endif
 
     for (int j = 0; j < 10; ++j) {
         for (int i = d+1; i < iters; i+=2) {
 #ifdef TEST_STRING_KEYS
 #endif
 
     for (int j = 0; j < 10; ++j) {
         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);
+            s->len = 1 + snprintf(s->data, 9, "%u", i);

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


@@ -155,8 +159,7 @@ void *add_remove_worker (void *arg) {
         }
         for (int i = d+1; i < iters; i+=2) {
 #ifdef TEST_STRING_KEYS
         }
         for (int i = d+1; i < iters; i+=2) {
 #ifdef TEST_STRING_KEYS

-            memset(key->data, 0, key->len);
-            snprintf(key->data, key->len, "%u", i);
+            s->len = 1 + snprintf(s->data, 9, "%u", i);

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


@@ -165,6 +168,9 @@ void *add_remove_worker (void *arg) {
             rcu_update(); // In a quiecent state.
         }
     }
             rcu_update(); // In a quiecent state.
         }
     }

+#ifdef TEST_STRING_KEYS
+    nbd_free(s);
+#endif

     return NULL;
 }
 
     return NULL;
 }
 


@@ -216,8 +222,10 @@ void concurrent_add_remove_test (CuTest* tc) {
 void basic_iteration_test (CuTest* tc) {
 #ifdef TEST_STRING_KEYS
     map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
 void basic_iteration_test (CuTest* tc) {
 #ifdef TEST_STRING_KEYS
     map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);

-    nstring_t *k1 = ns_alloc(3); strcpy(k1->data, "k1");
-    nstring_t *k2 = ns_alloc(3); strcpy(k1->data, "k2");
+    nstring_t *s1 = ns_alloc(3); strcpy(s1->data, "k1");
+    nstring_t *s2 = ns_alloc(3); strcpy(s2->data, "k2");
+    map_key_t k1 = (map_key_t)s1;
+    map_key_t k2 = (map_key_t)s2;

     nstring_t *x_k;
     nstring_t *y_k;
 #else
     nstring_t *x_k;
     nstring_t *y_k;
 #else


@@ -233,15 +241,15 @@ void basic_iteration_test (CuTest* tc) {
 
     map_val_t x_v, y_v;
     map_iter_t *iter = map_iter_begin(map, 0);
 
     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);
+    x_v = map_iter_next(iter, (map_key_t *)&x_k);
+    y_v = map_iter_next(iter, (map_key_t *)&y_k);

     ASSERT_EQUAL( DOES_NOT_EXIST, map_iter_next(iter, NULL) );
     map_iter_free(iter);
 #ifdef TEST_STRING_KEYS
     ASSERT_EQUAL( DOES_NOT_EXIST, map_iter_next(iter, NULL) );
     map_iter_free(iter);
 #ifdef TEST_STRING_KEYS

-    ASSERT_EQUAL( TRUE, (ns_cmp(x_k, k1) == 0 && x_v == 1) || (ns_cmp(y_k, k1) == 0 && y_v == 1) );
-    ASSERT_EQUAL( TRUE, (ns_cmp(x_k, k2) == 0 && x_v == 2) || (ns_cmp(y_k, k2) == 0 && y_v == 2) );
-    nbd_free(k1);
-    nbd_free(k2);
+    ASSERT_EQUAL( TRUE, (ns_cmp(x_k, s1) == 0 && x_v == 1) || (ns_cmp(y_k, s1) == 0 && y_v == 1) );
+    ASSERT_EQUAL( TRUE, (ns_cmp(x_k, s2) == 0 && x_v == 2) || (ns_cmp(y_k, s2) == 0 && y_v == 2) );
+    nbd_free(s1);
+    nbd_free(s2);

 #else
     ASSERT_EQUAL( TRUE, (x_k == k1 && x_v == 1) || (y_k == k1 && y_v == 1) );
     ASSERT_EQUAL( TRUE, (x_k == k2 && x_v == 2) || (y_k == k2 && y_v == 2) );
 #else
     ASSERT_EQUAL( TRUE, (x_k == k1 && x_v == 1) || (y_k == k1 && y_v == 1) );
     ASSERT_EQUAL( TRUE, (x_k == k2 && x_v == 2) || (y_k == k2 && y_v == 2) );


@@ -255,9 +263,12 @@ void big_iteration_test (CuTest* tc) {
     
 #ifdef TEST_STRING_KEYS
     map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
     
 #ifdef TEST_STRING_KEYS
     map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);

-    nstring_t *key = ns_alloc(9);
-    nstring_t *k3 = ns_alloc(3); strcpy(k1->data, "k3");
-    nstring_t *k4 = ns_alloc(3); strcpy(k1->data, "k4");
+    nstring_t *s = ns_alloc(9);
+    nstring_t *s3 = ns_alloc(3); strcpy(s3->data, "k3");
+    nstring_t *s4 = ns_alloc(3); strcpy(s4->data, "k4");
+    map_key_t k3 = (map_key_t)s3;
+    map_key_t k4 = (map_key_t)s4;
+    map_key_t key = (map_key_t)s;

 #else
     map_t *map = map_alloc(map_type_, NULL);
     map_key_t k3 = (map_key_t)3;
 #else
     map_t *map = map_alloc(map_type_, NULL);
     map_key_t k3 = (map_key_t)3;


@@ -265,10 +276,9 @@ void big_iteration_test (CuTest* tc) {
     map_key_t key;
 #endif
 
     map_key_t key;
 #endif
 

-    for (size_t i = 1; i <= n; ++i) {
+    for (int i = 1; i <= n; ++i) {

 #ifdef TEST_STRING_KEYS
 #ifdef TEST_STRING_KEYS

-        memset(key->data, 0, key->len);
-        snprintf(key->data, key->len, "k%llu", i);
+        s->len = 1 + snprintf(s->data, 9, "k%d", i);

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


@@ -300,7 +310,7 @@ void big_iteration_test (CuTest* tc) {
     ASSERT_EQUAL(n*(n+1)/2 - (3+4), sum);
         
 #ifdef TEST_STRING_KEYS
     ASSERT_EQUAL(n*(n+1)/2 - (3+4), sum);
         
 #ifdef TEST_STRING_KEYS

-    nbd_free(key);
+    nbd_free(s);

 #endif
 }
 
 #endif
 }
 

diff --git a/todo b/todo
index e73a5a9ad71809da4a988096d56071a1c9753ea0..66ed49c7e1fbf868c3c01534cd1551d7aca606e3 100644 (file)
--- a/todo
+++ b/todo
@@ -7,12 +7,14 @@
 + optimize integer keys
 + ht_print()
 + iterators
 + optimize integer keys
 + ht_print()
 + iterators

++ 32 bit support

 
 memory manangement
 ------------------
 - make rcu yield when its buffer gets full instead of throwing an assert
 - alternate memory reclamation schemes: hazard pointers and/or reference counting
 - verify the key management in list, skiplist, and hashtable
 
 memory manangement
 ------------------
 - make rcu yield when its buffer gets full instead of throwing an assert
 - alternate memory reclamation schemes: hazard pointers and/or reference counting
 - verify the key management in list, skiplist, and hashtable

+- seperate nbd_malloc/nbd_free into general purpose malloc/free replacement

 
 quality
 -------
 
 quality
 -------


@@ -33,7 +35,4 @@ optimization
 
 features
 --------
 
 features
 --------

-- a version of hashtable for 32bit keys and values
-- verify correctness on 32 bit platforms

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

-- seperate nbd_malloc/nbd_free into general purpose malloc/free replacement

diff --git a/txn/txn.c b/txn/txn.c
index ef8313f56aaa5fe4c4796f4b200b21c727b9894d..5648d16abbba2b2d11b3f0b75bbbb267251746cb 100644 (file)
--- a/txn/txn.c
+++ b/txn/txn.c
@@ -12,9 +12,10 @@
 #define INITIAL_WRITES_SIZE  4
 
 typedef struct update_rec update_t;
 #define INITIAL_WRITES_SIZE  4
 
 typedef struct update_rec update_t;

+typedef map_key_t version_t;

 
 struct update_rec {
 
 struct update_rec {

-    uint64_t version;
+    version_t version;

     map_val_t value;
     map_val_t next; // an earlier update
 };
     map_val_t value;
     map_val_t next; // an earlier update
 };


@@ -25,8 +26,8 @@ typedef struct write_rec {
 } write_rec_t;
 
 struct txn {
 } write_rec_t;
 
 struct txn {

-    uint64_t rv;
-    uint64_t wv;
+    version_t rv;
+    version_t wv;

     map_t *map;
     write_rec_t *writes;
     size_t writes_size;
     map_t *map;
     write_rec_t *writes;
     size_t writes_size;


@@ -37,7 +38,7 @@ struct txn {
 
 static txn_state_e txn_validate (txn_t *txn);
 
 
 static txn_state_e txn_validate (txn_t *txn);
 

-static uint64_t version_ = 1;
+static version_t version_ = 1;

 
 static skiplist_t *active_ = NULL;
 
 
 static skiplist_t *active_ = NULL;
 


@@ -118,7 +119,7 @@ static txn_state_e txn_validate (txn_t *txn) {
 
         case TXN_VALIDATING:
             if (txn->wv == UNDETERMINED_VERSION) {
 
         case TXN_VALIDATING:
             if (txn->wv == UNDETERMINED_VERSION) {

-                uint64_t wv = SYNC_ADD(&version_, 1);
+                version_t wv = SYNC_ADD(&version_, 1);

                 SYNC_CAS(&txn->wv, UNDETERMINED_VERSION, wv);
             }
 
                 SYNC_CAS(&txn->wv, UNDETERMINED_VERSION, wv);
             }
 


@@ -165,11 +166,11 @@ txn_t *txn_begin (map_t *map) {
     do {
         txn->rv = version_;
 
     do {
         txn->rv = version_;
 

-        uint64_t old_count;
-        uint64_t temp = 0;
+        unsigned old_count;
+        unsigned temp = 0;

         do {
             old_count = temp;
         do {
             old_count = temp;

-            temp = (uint64_t)sl_cas(active_, (map_key_t)txn->rv, old_count, old_count + 1);
+            temp = sl_cas(active_, txn->rv, old_count, old_count + 1);

         } while (temp != old_count);
 
         if (txn->rv == version_)
         } while (temp != old_count);
 
         if (txn->rv == version_)


@@ -208,7 +209,7 @@ txn_state_e txn_commit (txn_t *txn) {
     txn_state_e state = txn_validate(txn);
 
     // Detach <txn> from its updates.
     txn_state_e state = txn_validate(txn);
 
     // Detach <txn> from its updates.

-    uint64_t wv = (txn->state == TXN_ABORTED) ? ABORTED_VERSION : txn->wv;
+    version_t wv = (txn->state == TXN_ABORTED) ? ABORTED_VERSION : txn->wv;

     int i;
     for (i = 0; i < txn->writes_count; ++i) {
         update_t *update = (update_t *)txn->writes[i].rec;
     int i;
     for (i = 0; i < txn->writes_count; ++i) {
         update_t *update = (update_t *)txn->writes[i].rec;


@@ -216,8 +217,8 @@ txn_state_e txn_commit (txn_t *txn) {
     }
 
     // Lower the reference count for <txn>'s read version
     }
 
     // Lower the reference count for <txn>'s read version

-    uint64_t temp = 2;
-    uint64_t old_count;
+    unsigned temp = 2;
+    unsigned old_count;

     do {
         old_count = temp;
         temp = sl_cas(active_, (map_key_t)txn->rv, old_count, old_count - 1);
     do {
         old_count = temp;
         temp = sl_cas(active_, (map_key_t)txn->rv, old_count, old_count - 1);


@@ -292,11 +293,11 @@ map_val_t txn_map_get (txn_t *txn, map_key_t key) {
     map_val_t value = update->value;
 
     // collect some garbage
     map_val_t value = update->value;
 
     // collect some garbage

-    uint64_t min_active_version = UNDETERMINED_VERSION;
+    version_t min_active_version = UNDETERMINED_VERSION;

     update_t *next_update = NULL;
     if (IS_TAGGED(update->next, TAG2)) {
         next_update = (update_t *)STRIP_TAG(update->next, TAG2);
     update_t *next_update = NULL;
     if (IS_TAGGED(update->next, TAG2)) {
         next_update = (update_t *)STRIP_TAG(update->next, TAG2);

-        min_active_version = (uint64_t)sl_min_key(active_);
+        min_active_version = (version_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
             // not visible to any active transaction. We can safely free it.
         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
             // not visible to any active transaction. We can safely free it.


@@ -305,7 +306,7 @@ map_val_t txn_map_get (txn_t *txn, map_key_t key) {
             update_t *temp = next_update;
             while (temp->version == ABORTED_VERSION) {
                 assert(!IS_TAGGED(temp->version, TAG1));
             update_t *temp = next_update;
             while (temp->version == ABORTED_VERSION) {
                 assert(!IS_TAGGED(temp->version, TAG1));

-                uint64_t next = next_update->next;
+                map_val_t next = next_update->next;

                 if (!IS_TAGGED(next, TAG2))
                     break;
 
                 if (!IS_TAGGED(next, TAG2))
                     break;
 


@@ -317,7 +318,7 @@ map_val_t txn_map_get (txn_t *txn, map_key_t key) {
             // free <next> and all the update records following it
             temp = next_update;
             while (1) {
             // free <next> and all the update records following it
             temp = next_update;
             while (1) {

-                uint64_t next = SYNC_SWAP(&temp->next, DOES_NOT_EXIST);
+                map_val_t next = SYNC_SWAP(&temp->next, DOES_NOT_EXIST);

 
                 // if we find ourself in a race just back off and let the other thread take care of it
                 if (next == DOES_NOT_EXIST) 
 
                 // if we find ourself in a race just back off and let the other thread take care of it
                 if (next == DOES_NOT_EXIST) 


@@ -336,7 +337,7 @@ map_val_t txn_map_get (txn_t *txn, map_key_t key) {
     // There is no need for an update record.
     if (next_update == NULL && val == newest_val) {
         if (min_active_version == UNDETERMINED_VERSION) {
     // There is no need for an update record.
     if (next_update == NULL && val == newest_val) {
         if (min_active_version == UNDETERMINED_VERSION) {

-            min_active_version = (uint64_t)sl_min_key(active_);
+            min_active_version = (version_t)sl_min_key(active_);

         }
         if (update->version <= min_active_version) {
             if (map_cas(txn->map, key, TAG_VALUE(val, TAG2), value) == TAG_VALUE(val, TAG2)) {
         }
         if (update->version <= min_active_version) {
             if (map_cas(txn->map, key, TAG_VALUE(val, TAG2), value) == TAG_VALUE(val, TAG2)) {


@@ -355,14 +356,14 @@ void txn_map_set (txn_t *txn, map_key_t key, map_val_t value) {
     // create a new update record
     update_t *update = alloc_update_rec();
     update->value = value;
     // create a new update record
     update_t *update = alloc_update_rec();
     update->value = value;

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

 
     // push the new update record onto <key>'s update list
 
     // push the new update record onto <key>'s update list

-    uint64_t old_update;
+    map_val_t old_update;

     do {
         old_update = map_get(txn->map, key);
         update->next = 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)update, TAG2)) != old_update);
+    } while (map_cas(txn->map, key, old_update, TAG_VALUE((map_val_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) {