// Copyright 2016 The Vanadium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package nsync

import "math"
import "sync/atomic"
import "time"

// --------------------------------

// A dll represents a doubly-linked list of waiters.
type dll struct {
	next *dll
	prev *dll
	elem *waiter // points to the waiter struct this dll struct is embedded in, or nil if none.
}

// MakeEmpty() makes list *l empty.
// Requires that *l is currently not part of a non-empty list.
func (l *dll) MakeEmpty() {
	l.next = l
	l.prev = l
}

// IsEmpty() returns whether list *l is empty.
// Requires that *l is currently part of a list, or the zero dll element.
func (l *dll) IsEmpty() bool {
	return l.next == l
}

// InsertAfter() inserts element *e into the list after position *p.
// Requires that *e is currently not part of a list and that *p is part of a list.
func (e *dll) InsertAfter(p *dll) {
	e.next = p.next
	e.prev = p
	e.next.prev = e
	e.prev.next = e
}

// Remove() removes *e from the list it is currently in.
// Requires that *e is currently part of a list.
func (e *dll) Remove() {
	e.next.prev = e.prev
	e.prev.next = e.next
}

// IsInList() returns whether element e can be found in list l.
func (e *dll) IsInList(l *dll) bool {
	p := l.next
	for p != e && p != l {
		p = p.next
	}
	return p == e
}

// --------------------------------

// A waiter represents a single waiter on a CV or a Mu.
//
// To wait:
// Allocate a waiter struct *w with newWaiter(), set w.waiting=1, and
// w.cvMu=nil or to the associated Mu if waiting on a condition variable, then
// queue w.dll on some queue, and then wait using:
//    for atomic.LoadUint32(&w.waiting) != 0 { w.sem.P() }
// Return *w to the freepool by calling freeWaiter(w).
//
// To wakeup:
// Remove *w from the relevant queue then:
//  atomic.Store(&w.waiting, 0)
//  w.sem.V()
type waiter struct {
	q             dll             // Doubly-linked list element.
	sem           binarySemaphore // Thread waits on this semaphore.
	deadlineTimer *time.Timer     // Used for waits with deadlines.

	// If this waiter is waiting on a CV associated with a Mu, mu is a
	// pointer to that Mu, otherwise nil
	cvMu *Mu

	// non-zero <=> the waiter is waiting (read and written atomically)
	waiting uint32
}

var freeWaiters dll      // freeWaiters is a doubly-linked list of free waiter structs.
var freeWaitersMu uint32 // spinlock protects freeWaiters

// newWaiter() returns a pointer to an unused waiter struct.
// Ensures that the enclosed timer is stopped and its channel drained.
func newWaiter() (w *waiter) {
	spinTestAndSet(&freeWaitersMu, 1, 1)
	if freeWaiters.next == nil { // first time through, initialize the free list.
		freeWaiters.MakeEmpty()
	}
	if !freeWaiters.IsEmpty() { // If free list is non-empty, dequeue an item.
		var q *dll = freeWaiters.next
		q.Remove()
		w = q.elem
	}
	atomic.StoreUint32(&freeWaitersMu, 0) // release store
	if w == nil {                         // If free list was empty, allocate an item.
		w = new(waiter)
		w.sem.Init()
		w.deadlineTimer = time.NewTimer(time.Duration(math.MaxInt64))
		w.deadlineTimer.Stop()
		w.q.elem = w
	}
	return w
}

// freeWaiter() returns an unused waiter struct *w to the free pool.
func freeWaiter(w *waiter) {
	spinTestAndSet(&freeWaitersMu, 1, 1)
	w.q.InsertAfter(&freeWaiters)
	atomic.StoreUint32(&freeWaitersMu, 0) // release store
}