1/*
2Copyright 2021 The Kubernetes Authors.
3
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
7
8    http://www.apache.org/licenses/LICENSE-2.0
9
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15*/
16
17package queueset
18
19import (
20	"container/list"
21)
22
23// removeFromFIFOFunc removes a designated element from the list.
24// The complexity of the runtime cost is O(1)
25// It returns the request removed from the list.
26type removeFromFIFOFunc func() *request
27
28// walkFunc is called for each request in the list in the
29// oldest -> newest order.
30// ok: if walkFunc returns false then the iteration stops immediately.
31type walkFunc func(*request) (ok bool)
32
33// Internal interface to abstract out the implementation details
34// of the underlying list used to maintain the requests.
35//
36// Note that the FIFO list is not safe for concurrent use by multiple
37// goroutines without additional locking or coordination. It rests with
38// the user to ensure that the FIFO list is used with proper locking.
39type fifo interface {
40	// Enqueue enqueues the specified request into the list and
41	// returns a removeFromFIFOFunc function that can be used to remove the
42	// request from the list
43	Enqueue(*request) removeFromFIFOFunc
44
45	// Dequeue pulls out the oldest request from the list.
46	Dequeue() (*request, bool)
47
48	// Length returns the number of requests in the list.
49	Length() int
50
51	// SeatsSum returns the total number of seats of all requests
52	// in this list.
53	SeatsSum() int
54
55	// Walk iterates through the list in order of oldest -> newest
56	// and executes the specified walkFunc for each request in that order.
57	//
58	// if the specified walkFunc returns false the Walk function
59	// stops the walk an returns immediately.
60	Walk(walkFunc)
61}
62
63// the FIFO list implementation is not safe for concurrent use by multiple
64// goroutines without additional locking or coordination.
65type requestFIFO struct {
66	*list.List
67
68	seatsSum int
69}
70
71func newRequestFIFO() fifo {
72	return &requestFIFO{
73		List: list.New(),
74	}
75}
76
77func (l *requestFIFO) Length() int {
78	return l.Len()
79}
80
81func (l *requestFIFO) SeatsSum() int {
82	return l.seatsSum
83}
84
85func (l *requestFIFO) Enqueue(req *request) removeFromFIFOFunc {
86	e := l.PushBack(req)
87	l.seatsSum += req.Seats()
88
89	return func() *request {
90		if e.Value != nil {
91			l.Remove(e)
92			e.Value = nil
93			l.seatsSum -= req.Seats()
94		}
95		return req
96	}
97}
98
99func (l *requestFIFO) Dequeue() (*request, bool) {
100	e := l.Front()
101	if e == nil {
102		return nil, false
103	}
104
105	defer func() {
106		l.Remove(e)
107		e.Value = nil
108	}()
109
110	request, ok := e.Value.(*request)
111	if ok {
112		l.seatsSum -= request.Seats()
113	}
114	return request, ok
115}
116
117func (l *requestFIFO) Walk(f walkFunc) {
118	for current := l.Front(); current != nil; current = current.Next() {
119		if r, ok := current.Value.(*request); ok {
120			if !f(r) {
121				return
122			}
123		}
124	}
125}
126