# 2021q3 Homework2 (hp)
contributed by < `ilkclord` >

## Program
The program is a mpmc model . It use Hazzard pointer to assure each element won't be free while some thread is using it .
### Data Structure

#### list_hp

struct list_hp {
    int max_hps;
    alignas(128) atomic_uintptr_t *hp[HP_MAX_THREADS];
    alignas(128) retirelist_t *rl[HP_MAX_THREADS * CLPAD];
    list_hp_deletefunc_t *deletefunc;
};

`max_hps` : size of `hp` in each thread
`hp` : a 2D array which store the hazzard pointer . Each threads will check `hp` of each threads when releasing the memory .
`rl` : store the object no longer used
`deletefunc` : delete method
### Hazzard Pointer
The program use these two function to control the `hp` list .
#### list_hp_protect_ptr

uintptr_t list_hp_protect_ptr(list_hp_t *hp, int ihp, uintptr_t ptr)
{
    atomic_store(&hp->hp[tid()][ihp], ptr);
    return ptr;
}

#### list_hp_protect_release

uintptr_t list_hp_protect_release(list_hp_t *hp, int ihp, uintptr_t ptr)
{
    atomic_store_explicit(&hp->hp[tid()][ihp], ptr, memory_order_release);
    return ptr;
}

### Find
The find funtion in the program is `list_find` , it keeps tracking if the node it used has been modified . It protected `curr` and `curr->next` in `hp` .
#### list_find

static bool __list_find(list_t *list,
                        list_key_t *key,
                        atomic_uintptr_t **par_prev,
                        list_node_t **par_curr,
                        list_node_t **par_next)
{
    atomic_uintptr_t *prev = NULL;
    list_node_t *curr = NULL, *next = NULL;

try_again:
    prev = &list->head;
    curr = (list_node_t *) atomic_load(prev);
    (void) list_hp_protect_ptr(list->hp, HP_CURR, (uintptr_t) curr);
    if (atomic_load(prev) != get_unmarked(curr))
        goto try_again;
    while (true) {
        if (!get_unmarked_node(curr))
            return false;
        next = (list_node_t *) atomic_load(&get_unmarked_node(curr)->next);
        (void) list_hp_protect_ptr(list->hp, HP_NEXT, get_unmarked(next));
        if (atomic_load(&get_unmarked_node(curr)->next) != (uintptr_t) next)
            break;
        if (get_unmarked(next) == atomic_load((atomic_uintptr_t *) &list->tail))
            break;
        if (atomic_load(prev) != get_unmarked(curr))
            goto try_again;
        if (get_unmarked_node(next) == next) {
            if (!(get_unmarked_node(curr)->key < *key)) {
                *par_curr = curr;
                *par_prev = prev;
                *par_next = next;
                return FFF;
            }
            prev = &get_unmarked_node(curr)->next;
            (void) list_hp_protect_release(list->hp, HP_PREV,
                                           get_unmarked(curr));
        } else {
            uintptr_t tmp = get_unmarked(curr);
            if (!atomic_compare_exchange_strong(prev, &tmp, get_unmarked(next)))
                goto try_again;
            list_hp_retire(list->hp, get_unmarked(curr));
        }
        curr = next;
        (void) list_hp_protect_release(list->hp, HP_CURR, get_unmarked(next));
    }
    *par_curr = curr;
    *par_prev = prev;
    *par_next = next;

    return false;
}

### Insert
The insert funtion `list_insert` will keep try insertion untill it successed . After checking the node isn't exist in the list , it insert the new node at the tail of the list .
#### list_insert

bool list_insert(list_t *list, list_key_t key)
{
    list_node_t *curr = NULL, *next = NULL;
    atomic_uintptr_t *prev = NULL;

    list_node_t *node = list_node_new(key);

    while (true) {
        if (__list_find(list, &key, &prev, &curr, &next)) {
            list_node_destroy(node);
            list_hp_clear(list->hp);
            return false;
        }
        atomic_store_explicit(&node->next, (uintptr_t) curr,
                              memory_order_relaxed);
        uintptr_t tmp = get_unmarked(curr);
        if (atomic_compare_exchange_strong(prev, &tmp, (uintptr_t) node)) {
            list_hp_clear(list->hp);
            return true;
        }
    }
}

### Delete
The delete function `list_delete` will try untill successed , too .It first find the node to delete . Then check the accuracy of the node , true if the node hasn't been deleted . It call `list_retire` to put a object into `rl` and `lsit_retire` will free the object inside `rl` if `rl` is full .
#### list_delete

bool list_delete(list_t *list, list_key_t key)
{
    list_node_t *curr, *next;
    atomic_uintptr_t *prev;
    while (true) {
        if (!__list_find(list, &key, &prev, &curr, &next)) {
            list_hp_clear(list->hp);
            return false;
        }

        uintptr_t tmp = get_unmarked(next);

        if (!atomic_compare_exchange_strong(&curr->next, &tmp,
                                            get_marked(next)))
            continue;

        tmp = get_unmarked(curr);
        if (atomic_compare_exchange_strong(prev, &tmp, get_unmarked(next))) {
            list_hp_clear(list->hp);
            DDD;
        } else {
            list_hp_clear(list->hp);
        }
        return true;
    }
}

## Improvement

## Compare with RCU