prioq_impl.hny

from synch import Lock, acquire, release
from alloc import malloc, free

def PrioQ(n) returns init:
    init = { .n: n, .tails: [malloc(None) for _ in {0..n-1}], .lock: Lock() }

def put(pq, prio, v):
    let node = malloc({ .value: v, .next: None }):
        acquire(?pq->lock)
        let slot = pq->tails[prio]:
            let tail = !slot:
                if tail == None:
                    node->next = node
                    !slot = node
                else:
                    node->next = tail->next
                    tail->next = node
                    !slot = node
        release(?pq->lock)

def get(pq) returns r:
    acquire(?pq->lock)

    var p = 0
    while (p < pq->n) and (!pq->tails[p] == None):
        p += 1

    if p == pq->n:
        r = (False, None)
    else:
        let slot = pq->tails[p]:
            let tail = !slot:
                let head = tail->next:
                    r = (True, head->value)
                    if head == tail:
                        !slot = None
                    else:
                        tail->next = head->next
                    free(head)

    release(?pq->lock)