# 2024-06-28

int mpmc_queue_push(struct mpmc_queue *q, void *ptr)
{
    struct mpmc_queue_cell *cell;
    size_t pos = atomic_load_explicit(&q->tail, memory_order_relaxed);
    for (;;) {
        cell = &q->buffer[pos & q->buffer_mask];
        size_t seq =
            atomic_load_explicit(&cell->sequence, memory_order_acquire);
        intptr_t diff = (intptr_t) seq - (intptr_t) pos;

        if (diff == 0) {
            if (atomic_compare_exchange_weak_explicit(&q->tail, &pos, pos + 1,
                                                      memory_order_relaxed,
                                                      memory_order_seq_cst))
                break;
        }
        if (diff < 0)
            return 0;
        /* Your code here */
    }

    cell->data = ptr;
    /* Your code here */

    return 1;
}

int mpmc_queue_pull(struct mpmc_queue *q, void **ptr)
{
    struct mpmc_queue_cell *cell;
    size_t pos;

    pos = atomic_load_explicit(&q->head, memory_order_relaxed);
    for (;;) {
        cell = &q->buffer[pos & q->buffer_mask];

        size_t seq =
            atomic_load_explicit(&cell->sequence, memory_order_acquire);
        intptr_t diff = (intptr_t) seq - (intptr_t) (pos + 1);

        if (diff == 0) {
            if (atomic_compare_exchange_weak_explicit(&q->head, &pos, pos + 1,
                                                      memory_order_relaxed,
                                                      memory_order_seq_cst))
                break;
        }
        if (diff < 0)
            return 0;
        pos = atomic_load_explicit(&q->head, memory_order_relaxed);
    }

    *ptr = cell->data;
    /* Your code here */

    return 1;
}

Q: Multiple-Producer Multiple-consumer (MPMC) 要考慮什麼因素？

SPSC
https://hackmd.io/@sysprog/linux2024-quiz19

ring buffer

---

https://github.com/sysprog21/lab0-c/blob/master/list.h
quick sort

Node:

struct list_node {
    int data;
    struct list_head list;
};

Initialize 100 nodes with random values

struct list_head *head = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(head);

srand(time(0));

for (int i = 0; i < 100; i++) {
    struct list_node *node = malloc(sizeof(struct list_node));
    /* set the data between 0 and 499 */
    node->data = rand() % 500;
    list_add_tail(&node->list, head);
}

Run quick sort on 100 nodes of given linked list

void quicksort(struct list_head *head, int (*cmp)(int, int)) 
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    /* set the last element pivot */
    int pi = list_entry(head->prev, struct list_node, list)->data;
    struct list_head *curr = head;

    struct list_node *entry, *safe;
    list_for_each_entry_safe(entry, safe, head, list) {
        if (cmp(entry->data, pi)) {
            curr = curr->next;
            swap(curr, &entry->list);
            curr = &entry->list;
        }
    }

    struct list_head *low = malloc(sizeof(struct list_head));
    INIT_LIST_HEAD(low);
    struct list_head *high = malloc(sizeof(struct list_head));
    INIT_LIST_HEAD(high);

    list_cut_position(low, head, curr->prev);
    list_cut_position(high, curr, head->prev);

    quicksort(low, cmp);
    quicksort(high, cmp);
    
    list_splice(low, head);
    list_splice_tail(high, head);

    free(low);
    free(high);
}

comparator (descending)

int cmp1(int a, int b) 
{
    return a >= b;
}

comparator (ascending)

int cmp2(int a, int b) 
{
    return a <= b;
}

swap

void swap(struct list_head *a, struct list_head *b) 
{
    struct list_head *temp;
    temp = a->prev;
    list_move(a, b);
    list_move(a->prev, temp);
}

誠實面對自己
* function pointer 的宣告

---

TODO: 針對 Linux-like circular doubly-linked list 進行快速排序 (第一週的進度)
TODO: 實作 MPMC (第八週的進度)