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