# Skip List or doubly Linked List on `mimalloc`
## page-queue ( take `push` as example )
### mimalloc

static void mi_page_queue_push(mi_heap_t* heap, mi_page_queue_t* queue, mi_page_t* page) {
  mi_assert_internal(page->heap == NULL);
  mi_assert_internal(!mi_page_queue_contains(queue, page));
  mi_assert_internal(page->block_size == queue->block_size || (page->block_size > MI_LARGE_SIZE_MAX && mi_page_queue_is_huge(queue)) || (page->flags.in_full && mi_page_queue_is_full(queue)));

  page->flags.in_full = mi_page_queue_is_full(queue);
  page->heap = heap;
  page->next = queue->first;
  page->prev = NULL;
  if (queue->first != NULL) {
    mi_assert_internal(queue->first->prev == NULL);
    queue->first->prev = page;
    queue->first = page;
  }
  else {
    queue->first = queue->last = page;
  }

  // update direct
  mi_heap_queue_first_update(heap, queue);
  heap->page_count++;
}

* lock-free
### Simple Lock Free Linked List (stack implementation)

typedef struct Node{
    Val val;
    Node* next
} Node;

typedef struct Stack{
    _Atomic Node* head;
    _Atomic size_t size;
}Stack;

void push( Val val){
    Node* newhead;
    newhead = (Node *)malloc(sizeof(Node));
    newhead -> val = val;
    Node* oldhead = atomic_load(stack -> head);
    do{
        newhead->next = oldhead;
   } while (!atomic_compare_exchange_weak(stack->head,&oldhead, newhead))
}

* lock-free
* concurrency 處理

### java ConcurrentSkipListMap

     private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {
        // Track next level to insert in case of retries
        int insertionLevel = indexLevel;
        Comparable<K> key = comparable(idx.key);

        // Similar to findPredecessor, but adding index nodes along
        // path to key.
        for (;;) {
            Index<K,V> q = h;
            Index<K,V> t = idx;
            int j = h.level;
            for (;;) {
                Index<K,V> r = q.right;
                if (r != null) {
                    // compare before deletion check avoids needing recheck
                    int c = key.compareTo(r.key);
                    if (r.indexesDeletedNode()) {
                        if (q.unlink(r))
                            continue;
                        else
                            break;
                    }
                    if (c > 0) {
                        q = r;
                        continue;
                    }
                }

                if (j == insertionLevel) {
                    // Don't insert index if node already deleted
                    if (t.indexesDeletedNode()) {
                        findNode(key); // cleans up
                        return;
                    }
                    if (!q.link(r, t))
                        break; // restart
                    if (--insertionLevel == 0) {
                        // need final deletion check before return
                        if (t.indexesDeletedNode())
                            findNode(key);
                        return;
                    }
                }

                if (j > insertionLevel && j <= indexLevel)
                    t = t.down;
                q = q.down;
                --j;
            }
        }
    }

* lock-free
* concurrency 處理
* 檢索加速

### 可以改進的部分

> The beauty of the sharded thread free list is that it also reduces contention among threads since threads freeing in different pages do not contend with each other. On current architectures, uncontended atomic operations are very efficient and usually implemented as part of the cache consistency protocol (Schweizer et al., 2015)

  if (queue->first != NULL) {
    mi_assert_internal(queue->first->prev == NULL);
    queue->first->prev = page;
    queue->first = page;
  }
  else {
    queue->first = queue->last = page;
  }

`page-queue` 的函式（如：push 等）看似沒有做 concurrency 的處理，但其實已經先用 `thread free heap` 、 `thread free list` 等手法考慮 concurrency 。


typedef struct mi_page_queue_s {
  mi_page_t* first;
  mi_page_t* last;
  size_t     block_size; //all pages are the same size
} mi_page_queue_t;

對於檢索速度方面，修改為 skip list 的情況，我認為比較大的議題在於 ` page-queue ` 中 `page` 的 ` block size ` 皆相同，如果要找出一個比較好的 index 做為檢索依據，可能會以 ` 記憶體位置 ` 為準，但是這樣又會導致程式變得複雜，可能不符合 ` mimalloc ` 的宗旨。

> One clear goal for mimalloc is to stay "lean and mean" (and under 5kLOC) and I am very hesitant to add code that makes things less clear without a very clear advantage.

所以在檢索速度方面，在嘗試修改為 skip list 之前，我會再了解有沒有其他更加適合的選項。

### 檢索 Optimization
嘗試修改 mimalloc 中的 page 存放/檢索機制。以下列舉修改目標資料結構/函式。

#### mimalloc-types.h
* mi_page_queue_s
* 修改 first, last 等紀錄指標。
* mi_page_s
* 修改 next, prev 等檢索指標。

#### page-queue.c
* mi_heap_contains_queue
* mi_page_queue_remove
* mi_page_queue_push
* mi_page_queue_enqueue_from
* _mi_page_queue_append
* 註：合併

###### tags: `Cprogramming`