generalize list into an updatable list-based map

[nbds] / struct / hashtable.c

diff --git a/struct/hashtable.c b/struct/hashtable.c
index 0e9c57e4fdfb4ce71a477c271bb72a0b85cd72b7..5406d4242c038160047df62eb9ca43682f2e3289 100644 (file)
--- a/struct/hashtable.c
+++ b/struct/hashtable.c
@@ -37,6 +37,10 @@ typedef struct hti {
     int scan;
 } hashtable_i_t;
 
+struct ht {
+    hashtable_i_t *hti;
+};
+
 static const uint64_t COPIED_VALUE           = -1;
 static const uint64_t TOMBSTONE              = STRIP_TAG(-1);
 
@@ -90,14 +94,14 @@ static volatile entry_t *hti_lookup (hashtable_i_t *hti, uint32_t key_hash, cons
 
             uint64_t e_key = e->key;
             if (e_key == DOES_NOT_EXIST) {
-                TRACE("h1", "hti_lookup: entry %p for key \"%s\" is empty", e, ns_data(GET_PTR(e_key)));
+                TRACE("h1", "hti_lookup: entry %p for key \"%s\" is empty", e, GET_PTR(e_key)->data);
                 *is_empty = 1; // indicate an empty so the caller avoids an expensive ht_key_equals
                 return e;
             }
 
             if (ht_key_equals(e_key, key_hash, key_data, key_len)) {
-                TRACE("h1", "hti_lookup: entry %p key \"%s\"", e, ns_data(GET_PTR(e_key)));
-                TRACE("h2", "hti_lookup: entry key len %llu, value %p", ns_len(GET_PTR(e_key)), e->value);
+                TRACE("h1", "hti_lookup: entry %p key \"%s\"", e, GET_PTR(e_key)->data);
+                TRACE("h2", "hti_lookup: entry key len %llu, value %p", GET_PTR(e_key)->len, e->value);
                 return e;
             }
         }
@@ -222,11 +226,11 @@ static int hti_copy_entry (hashtable_i_t *ht1, volatile entry_t *ht1_e, uint32_t
     // We use 0 to indicate that <key_hash> isn't initiallized. Occasionally the <key_hash> will
     // really be 0 and we will waste time recomputing it. That is rare enough that it is OK. 
     if (key_hash == 0) { 
-        key_hash = murmur32(ns_data(key_string), ns_len(key_string));
+        key_hash = murmur32(key_string->data, key_string->len);
     }
 
     int is_empty;
-    volatile entry_t *ht2_e = hti_lookup(ht2, key_hash, ns_data(key_string), ns_len(key_string), &is_empty);
+    volatile entry_t *ht2_e = hti_lookup(ht2, key_hash, key_string->data, key_string->len, &is_empty);
     TRACE("h0", "hti_copy_entry: copy entry %p to entry %p", ht1_e, ht2_e);
 
     // it is possible that there is not any room in the new table either
@@ -262,7 +266,7 @@ static int hti_copy_entry (hashtable_i_t *ht1, volatile entry_t *ht1_e, uint32_t
 
     // Update the count if we were the one that completed the copy.
     if (old_ht2_e_value == DOES_NOT_EXIST) {
-        TRACE("h0", "hti_copy_entry: key \"%s\" value %p copied to new entry", ns_data(key_string), value);
+        TRACE("h0", "hti_copy_entry: key \"%s\" value %p copied to new entry", key_string->data, value);
         SYNC_ADD(&ht1->count, -1);
         SYNC_ADD(&ht2->count, 1);
         return TRUE;
@@ -333,7 +337,7 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons
         TRACE("h2", "hti_compare_and_set: installed key %p in entry %p", key, e);
     }
 
-    TRACE("h0", "hti_compare_and_set: entry for key \"%s\" is %p", ns_data(GET_PTR(e->key)), e);
+    TRACE("h0", "hti_compare_and_set: entry for key \"%s\" is %p", GET_PTR(e->key)->data, e);
 
     // If the entry is in the middle of a copy, the copy must be completed first.
     uint64_t e_value = e->value;
@@ -421,7 +425,7 @@ static uint64_t hti_get (hashtable_i_t *hti, uint32_t key_hash, const char *key_
 
 //
 uint64_t ht_get (hashtable_t *ht, const char *key_data, uint32_t key_len) {
-    return hti_get(*ht, murmur32(key_data, key_len), key_data, key_len);
+    return hti_get(ht->hti, murmur32(key_data, key_len), key_data, key_len);
 }
 
 //
@@ -433,7 +437,7 @@ uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_data, uint32_t key
     assert(key_data);
     assert(!IS_TAGGED(new_val) && new_val != DOES_NOT_EXIST);
 
-    hashtable_i_t *hti = *ht;
+    hashtable_i_t *hti = ht->hti;
 
     // Help with an ongoing copy.
     if (EXPECT_FALSE(hti->next != NULL)) {
@@ -475,7 +479,7 @@ uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_data, uint32_t key
         // Dispose of fully copied tables.
         if (hti->num_entries_copied == (1 << hti->scale) || panic) {
             assert(hti->next);
-            if (SYNC_CAS(ht, hti, hti->next) == hti) {
+            if (SYNC_CAS(&ht->hti, hti, hti->next) == hti) {
                 nbd_defer_free(hti); 
             }
         }
@@ -495,7 +499,7 @@ uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_data, uint32_t key
 // Remove the value in <ht> associated with <key_data>. Returns the value removed, or 
 // DOES_NOT_EXIST if there was no value for that key.
 uint64_t ht_remove (hashtable_t *ht, const char *key_data, uint32_t key_len) {
-    hashtable_i_t *hti = *ht;
+    hashtable_i_t *hti = ht->hti;
     uint64_t val;
     uint32_t key_hash = murmur32(key_data, key_len);
     do {
@@ -510,7 +514,7 @@ uint64_t ht_remove (hashtable_t *ht, const char *key_data, uint32_t key_len) {
 
 // Returns the number of key-values pairs in <ht>
 uint64_t ht_count (hashtable_t *ht) {
-    hashtable_i_t *hti = *ht;
+    hashtable_i_t *hti = ht->hti;
     uint64_t count = 0;
     while (hti) {
         count += hti->count;
@@ -522,13 +526,13 @@ uint64_t ht_count (hashtable_t *ht) {
 // Allocate and initialize a new hash table.
 hashtable_t *ht_alloc (void) {
     hashtable_t *ht = nbd_malloc(sizeof(hashtable_t));
-    *ht = (hashtable_i_t *)hti_alloc(ht, MIN_SCALE);
+    ht->hti = (hashtable_i_t *)hti_alloc(ht, MIN_SCALE);
     return ht;
 }
 
 // Free <ht> and its internal structures.
 void ht_free (hashtable_t *ht) {
-    hashtable_i_t *hti = *ht;
+    hashtable_i_t *hti = ht->hti;
     do {
         for (uint32_t i = 0; i < (1 << hti->scale); ++i) {
             assert(hti->table[i].value == COPIED_VALUE || !IS_TAGGED(hti->table[i].value));