evictingqueue.go (2620B)
1 // Copyright 2017-present The Hugo Authors. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13
14 // Package types contains types shared between packages in Hugo.
15 package types
16
17 import (
18 "sync"
19 )
20
21 // EvictingStringQueue is a queue which automatically evicts elements from the head of
22 // the queue when attempting to add new elements onto the queue and it is full.
23 // This queue orders elements LIFO (last-in-first-out). It throws away duplicates.
24 // Note: This queue currently does not contain any remove (poll etc.) methods.
25 type EvictingStringQueue struct {
26 size int
27 vals []string
28 set map[string]bool
29 mu sync.Mutex
30 }
31
32 // NewEvictingStringQueue creates a new queue with the given size.
33 func NewEvictingStringQueue(size int) *EvictingStringQueue {
34 return &EvictingStringQueue{size: size, set: make(map[string]bool)}
35 }
36
37 // Add adds a new string to the tail of the queue if it's not already there.
38 func (q *EvictingStringQueue) Add(v string) {
39 q.mu.Lock()
40 if q.set[v] {
41 q.mu.Unlock()
42 return
43 }
44
45 if len(q.set) == q.size {
46 // Full
47 delete(q.set, q.vals[0])
48 q.vals = append(q.vals[:0], q.vals[1:]...)
49 }
50 q.set[v] = true
51 q.vals = append(q.vals, v)
52 q.mu.Unlock()
53 }
54
55 // Contains returns whether the queue contains v.
56 func (q *EvictingStringQueue) Contains(v string) bool {
57 q.mu.Lock()
58 defer q.mu.Unlock()
59 return q.set[v]
60 }
61
62 // Peek looks at the last element added to the queue.
63 func (q *EvictingStringQueue) Peek() string {
64 q.mu.Lock()
65 l := len(q.vals)
66 if l == 0 {
67 q.mu.Unlock()
68 return ""
69 }
70 elem := q.vals[l-1]
71 q.mu.Unlock()
72 return elem
73 }
74
75 // PeekAll looks at all the elements in the queue, with the newest first.
76 func (q *EvictingStringQueue) PeekAll() []string {
77 q.mu.Lock()
78 vals := make([]string, len(q.vals))
79 copy(vals, q.vals)
80 q.mu.Unlock()
81 for i, j := 0, len(vals)-1; i < j; i, j = i+1, j-1 {
82 vals[i], vals[j] = vals[j], vals[i]
83 }
84 return vals
85 }
86
87 // PeekAllSet returns PeekAll as a set.
88 func (q *EvictingStringQueue) PeekAllSet() map[string]bool {
89 all := q.PeekAll()
90 set := make(map[string]bool)
91 for _, v := range all {
92 set[v] = true
93 }
94
95 return set
96 }