static struct {

#include <u.h>
#include <libc.h>

static struct {
QLp *p;
QLp x[1024];
} ql = {
ql.x
};

enum
{
Queuing,
QueuingR,
QueuingW,
};

static ulong (*_rendezvousp)(ulong, ulong) = rendezvous;

/* this gets called by the thread library ONLY to get us to use its rendezvous */
void
_qlockinit(ulong (*r)(ulong, ulong))
{
_rendezvousp = r;
}

/* find a free shared memory location to queue ourselves in */
static QLp*
getqlp(void)
{
QLp *p, *op;

op = ql.p;
for(p = op+1; ; p++){
if(p == &ql.x[nelem(ql.x)])
p = ql.x;
if(p == op)
abort();
if(_tas(&(p->inuse)) == 0){
ql.p = p;
p->next = nil;
break;
}
}
return p;
}

void
qlock(QLock *q)
{
QLp *p, *mp;

lock(&q->lock);
if(!q->locked){
q->locked = 1;
unlock(&q->lock);
return;
}

/* chain into waiting list */
mp = getqlp();
p = q->tail;
if(p == nil)
q->head = mp;
else
p->next = mp;
q->tail = mp;
mp->state = Queuing;
unlock(&q->lock);

/* wait */
(*_rendezvousp)((ulong)mp, 1);
mp->inuse = 0;
}

void
qunlock(QLock *q)
{
QLp *p;

lock(&q->lock);
p = q->head;
if(p != nil){
/* wakeup head waiting process */
q->head = p->next;
if(q->head == nil)
q->tail = nil;
unlock(&q->lock);
(*_rendezvousp)((ulong)p, 0x12345);
return;
}
q->locked = 0;
unlock(&q->lock);
}

int
canqlock(QLock *q)
{
lock(&q->lock);
if(!q->locked){
q->locked = 1;
unlock(&q->lock);
return 1;
}
unlock(&q->lock);
return 0;
}

void
rlock(RWLock *q)
{
QLp *p, *mp;

lock(&q->lock);
if(q->writer == 0 && q->head == nil){
/* no writer, go for it */
q->readers++;
unlock(&q->lock);
return;
}

mp = getqlp();
p = q->tail;
if(p == 0)
q->head = mp;
else
p->next = mp;
q->tail = mp;
mp->next = nil;
mp->state = QueuingR;
unlock(&q->lock);

/* wait in kernel */
(*_rendezvousp)((ulong)mp, 1);
mp->inuse = 0;
}

void
runlock(RWLock *q)
{
QLp *p;

lock(&q->lock);
p = q->head;
if(--(q->readers) > 0 || p == nil){
unlock(&q->lock);
return;
}

/* start waiting writer */
if(p->state != QueuingW)
abort();
q->head = p->next;
if(q->head == 0)
q->tail = 0;
q->writer = 1;
unlock(&q->lock);

/* wakeup waiter */
(*_rendezvousp)((ulong)p, 0);
}

void
wlock(RWLock *q)
{
QLp *p, *mp;

lock(&q->lock);
if(q->readers == 0 && q->writer == 0){
/* noone waiting, go for it */
q->writer = 1;
unlock(&q->lock);
return;
}

/* wait */
p = q->tail;
mp = getqlp();
if(p == nil)
q->head = mp;
else
p->next = mp;
q->tail = mp;
mp->next = nil;
mp->state = QueuingW;
unlock(&q->lock);

/* wait in kernel */
(*_rendezvousp)((ulong)mp, 1);
mp->inuse = 0;
}

void
wunlock(RWLock *q)
{
QLp *p;

lock(&q->lock);
p = q->head;
if(p == nil){
q->writer = 0;
unlock(&q->lock);
return;
}
if(p->state == QueuingW){
/* start waiting writer */
q->head = p->next;
if(q->head == nil)
q->tail = nil;
unlock(&q->lock);
(*_rendezvousp)((ulong)p, 0);

return;
}

if(p->state != QueuingR)
abort();

/* waken waiting readers */
while(q->head != nil && q->head->state == QueuingR){
p = q->head;
q->head = p->next;
q->readers++;
(*_rendezvousp)((ulong)p, 0);
}
if(q->head == nil)
q->tail = nil;
q->writer = 0;
unlock(&q->lock);
}