-// NewRequestLimiter returns a RequestCounter that delegates up to
-// maxRequests at a time to the given handler, and responds 503 to all
-// incoming requests beyond that limit.
-//
-// "concurrent_requests" and "max_concurrent_requests" metrics are
-// registered with the given reg, if reg is not nil.
-func NewRequestLimiter(maxRequests int, handler http.Handler, reg *prometheus.Registry) RequestCounter {
- h := &limiterHandler{
- requests: make(chan struct{}, maxRequests),
- handler: handler,
+type heap []*qent
+
+func (h heap) Swap(i, j int) {
+ h[i], h[j] = h[j], h[i]
+ h[i].heappos, h[j].heappos = i, j
+}
+
+func (h heap) Less(i, j int) bool {
+ pi, pj := h[i].priority, h[j].priority
+ return pi > pj || (pi == pj && h[i].queued.Before(h[j].queued))
+}
+
+func (h heap) Len() int {
+ return len(h)
+}
+
+// Move element i to a correct position in the heap. When the heap is
+// empty, fix(0) is a no-op (does not crash).
+func (h heap) fix(i int) {
+ // If the initial position is a leaf (i.e., index is greater
+ // than the last node's parent index), we only need to move it
+ // up, not down.
+ uponly := i > (len(h)-2)/2
+ // Move the new entry toward the root until reaching a
+ // position where the parent already has higher priority.
+ for i > 0 {
+ parent := (i - 1) / 2
+ if h.Less(i, parent) {
+ h.Swap(i, parent)
+ i = parent
+ } else {
+ break
+ }