Debian Codegraph @

pkg/util/flowcontrol/fairqueuing/queueset/fifo_list.go

raw
1 /*
2 Copyright 2021 The Kubernetes Authors.
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 package queueset
18
19 import (
20 "container/list"
21 )
22
23 // removeFromFIFOFunc removes a designated element from the list
24 // if that element is in the list.
25 // The complexity of the runtime cost is O(1).
26 // The returned value is the element removed, if indeed one was removed,
27 // otherwise `nil`.
28 type removeFromFIFOFunc func() *request
29
30 // walkFunc is called for each request in the list in the
31 // oldest -> newest order.
32 // ok: if walkFunc returns false then the iteration stops immediately.
33 // walkFunc may remove the given request from the fifo,
34 // but may not mutate the fifo in any othe way.
35 type walkFunc func(*request) (ok bool)
36
37 // Internal interface to abstract out the implementation details
38 // of the underlying list used to maintain the requests.
39 //
40 // Note that a fifo, including the removeFromFIFOFuncs returned from Enqueue,
41 // is not safe for concurrent use by multiple goroutines.
42 type fifo interface {
43 // Enqueue enqueues the specified request into the list and
44 // returns a removeFromFIFOFunc function that can be used to remove the
45 // request from the list
46 Enqueue(*request) removeFromFIFOFunc
47
48 // Dequeue pulls out the oldest request from the list.
49 Dequeue() (*request, bool)
50
51 // Peek returns the oldest request without removing it.
52 Peek() (*request, bool)
53
54 // Length returns the number of requests in the list.
55 Length() int
56
57 // QueueSum returns the sum of initial seats, final seats, and
58 // additional latency aggregated from all requests in this queue.
59 QueueSum() queueSum
60
61 // Walk iterates through the list in order of oldest -> newest
62 // and executes the specified walkFunc for each request in that order.
63 //
64 // if the specified walkFunc returns false the Walk function
65 // stops the walk an returns immediately.
66 Walk(walkFunc)
67 }
68
69 // the FIFO list implementation is not safe for concurrent use by multiple
70 // goroutines.
71 type requestFIFO struct {
72 *list.List
73
74 sum queueSum
75 }
76
77 func newRequestFIFO() fifo {
78 return &requestFIFO{
79 List: list.New(),
80 }
81 }
82
83 func (l *requestFIFO) Length() int {
84 return l.Len()
85 }
86
87 func (l *requestFIFO) QueueSum() queueSum {
88 return l.sum
89 }
90
91 func (l *requestFIFO) Enqueue(req *request) removeFromFIFOFunc {
92 e := l.PushBack(req)
93 addToQueueSum(&l.sum, req)
94
95 return func() *request {
96 if e.Value == nil {
97 return nil
98 }
99 l.Remove(e)
100 e.Value = nil
101 deductFromQueueSum(&l.sum, req)
102 return req
103 }
104 }
105
106 func (l *requestFIFO) Dequeue() (*request, bool) {
107 return l.getFirst(true)
108 }
109
110 func (l *requestFIFO) Peek() (*request, bool) {
111 return l.getFirst(false)
112 }
113
114 func (l *requestFIFO) getFirst(remove bool) (*request, bool) {
115 e := l.Front()
116 if e == nil {
117 return nil, false
118 }
119
120 if remove {
121 defer func() {
122 l.Remove(e)
123 e.Value = nil
124 }()
125 }
126
127 request, ok := e.Value.(*request)
128 if remove && ok {
129 deductFromQueueSum(&l.sum, request)
130 }
131 return request, ok
132 }
133
134 func (l *requestFIFO) Walk(f walkFunc) {
135 var next *list.Element
136 for current := l.Front(); current != nil; current = next {
137 next = current.Next() // f is allowed to remove current
138 if r, ok := current.Value.(*request); ok {
139 if !f(r) {
140 return
141 }
142 }
143 }
144 }
145
146 func addToQueueSum(sum *queueSum, req *request) {
147 sum.InitialSeatsSum += req.InitialSeats()
148 sum.MaxSeatsSum += req.MaxSeats()
149 sum.TotalWorkSum += req.totalWork()
150 }
151
152 func deductFromQueueSum(sum *queueSum, req *request) {
153 sum.InitialSeatsSum -= req.InitialSeats()
154 sum.MaxSeatsSum -= req.MaxSeats()
155 sum.TotalWorkSum -= req.totalWork()
156 }