# 2022q1 Homework5 (quiz6)
contributed by < `kdnvt` >

## Problem `2`

When putting new key/value pair in hash table, it replaces the key/value pair with the same key.

digraph foo {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> bucket[index] | <ref>  }", width=1.2]
        b [label="{ <data> k1 |<data> A | <ref>  }"];
        c [label="{ <data> k2 |<data> B | <ref>  }"];
         
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
         
}

digraph foo {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> bucket[index] | <ref>  }", width=1.2]
        b [label="{ <data> k1 |<data> A | <ref>  }"];
        c [label="{ <data> k2 |<data> B | <ref>  }"];
        d [label="{ <data> k1 |<data> C | <ref>  }"];
         
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
         
}

digraph foo {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> bucket[index] | <ref>  }", width=1.2]
        b [label="{ <data> k1 |<data> A | <ref>  }"];
        c [label="{ <data> k2 |<data> B | <ref>  }"];
        d [label="{ <data> k1 |<data> C | <ref>  }"];
         
        a:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2, color=red];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
         
}

However, consider the situation which another thread delete the previous node right before the insertion of \<k1:c>.

digraph foo {
        rankdir=LR;
        node [shape=record];
        
        z [label="{ <data> k0 |<data> Z | <ref>  }"];
        
        a [label="{ <data> bucket[index] | <ref>  }", width=1.2]
        b [label="{ <data> k1 |<data> A | <ref>  }"];
        c [label="{ <data> k2 |<data> B | <ref>  }"];
        d [label="{ <data> k1 |<data> C | <ref>  }"];
         
        a:ref:c -> z:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        z:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
         
}

digraph foo {
        rankdir=LR;
        node [shape=record];
        
        z [label="{ <data> k0 |<data> Z | <ref>  }"];
        
        a [label="{ <data> bucket[index] | <ref>  }", width=1.2]
        b [label="{ <data> k1 |<data> A | <ref>  }"];
        c [label="{ <data> k2 |<data> B | <ref>  }"];
        d [label="{ <data> k1 |<data> C | <ref>  }"];
         
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2, color=red];
        z:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
         
}

digraph foo {
        rankdir=LR;
        node [shape=record];
        
        z [label="{ <data> k0 |<data> Z | <ref>  }"];
        
        a [label="{ <data> bucket[index] | <ref>  }", width=1.2]
        b [label="{ <data> k1 |<data> A | <ref>  }"];
        c [label="{ <data> k2 |<data> B | <ref>  }"];
        d [label="{ <data> k1 |<data> C | <ref>  }"];
         
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2 ];
        z:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
         
}

The result will be wrong.

In addition to the bug, I think the code have many redundent part, so using the technique of indirect pointer to make it more concise.

bool hashmap_put(hashmap_t *map, const void *key, void *value)
{
    if (!map)
        return NULL;

    /* hash to convert key to a bucket index where value would be stored */
    uint32_t bucket_index = map->hash(key) % map->n_buckets;

    hashmap_kv_t *kv = NULL, **prev = NULL;

    /* known head and next entry to add to the list */
    hashmap_kv_t *head = NULL, *next = NULL;
    printf("%p , %p\n",key,value);
    while (true) {
        /* copy the head of the list before checking entries for equality */
        head = map->buckets[bucket_index];

        /* find any existing matches to this key */
        prev = &map->buckets[bucket_index];
        
        if (head) {
            for (kv = *prev; kv; kv = kv->next ) {
                if (map->cmp(key, kv->key) == 0)
                    break;
                 
                prev = &(*prev)->next;
            }
        }

        if (kv) {      /* if the key exists, update and return it */
            if (!next) /* lazy make the next key-value pair to append */
                next = map->create_node(map->opaque, key, value);

            /* ensure the linked list's existing node chain persists */
            next->next = kv->next;

            if (__atomic_compare_exchange(prev, &kv, &next, false,
                                          __ATOMIC_SEQ_CST,
                                          __ATOMIC_SEQ_CST)) {
                /* this node, key and value are never again used by this */
                map->destroy_node(map->opaque, kv);
                return true;
            }
            hashmap_put_replace_fail += 1;
            
        } else {       /* if the key does not exist, try adding it */
            if (!next) /* make the next key-value pair to append */
                next = map->create_node(map->opaque, key, value);
            next->next = head;
            
            if (__atomic_compare_exchange(&map->buckets[bucket_index], &head,
                                          &next, false, __ATOMIC_SEQ_CST,
                                          __ATOMIC_SEQ_CST)) {
                __atomic_fetch_add(&map->length, 1, __ATOMIC_SEQ_CST);
                return false;
            }

            /* failure means another thead updated head before this.
             * track the CAS failure for tests -- non-atomic to minimize
             * thread contention
             */
            hashmap_put_retries += 1;
        }
    }
}

bool hashmap_del(hashmap_t *map, const void *key)
{
    if (!map)
        return false;

    uint32_t bucket_index = map->hash(key) % map->n_buckets;

    /* try to find a match, loop in case a delete attempt fails */
    while (true) {
        hashmap_kv_t *match, **prev = &map->buckets[bucket_index];
        for (match = *prev; match; match = match->next,prev = &(*prev)->next) {
            if ((*map->cmp)(key, match->key) == 0)
                break;
        }

        /* exit if no match was found */
        if (!match)
            return false;

        /* previous means this not the head but a link in the list */
        volatile uint32_t *fail = &map->buckets[bucket_index]==prev? &hashmap_del_fail_new_head:&hashmap_del_fail;

        if (__atomic_compare_exchange(prev, &match, &match->next,
                                      false, __ATOMIC_SEQ_CST,
                                      __ATOMIC_SEQ_CST)) {
            __atomic_fetch_sub(&map->length, 1, __ATOMIC_SEQ_CST);
            map->destroy_node(map->opaque, match);
            return true;
        }
        *fail += 1;
    }

    return false;
}