1// Copyright 2024 Google Inc. 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// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package uniquelist 16 17import ( 18 "iter" 19 "slices" 20 "unique" 21) 22 23// UniqueList is a workaround for Go limitation that slices are not comparable and 24// thus can't be used with unique.Make. It interns slices by storing them in an 25// unrolled linked list, where each node has a fixed size array, which are comparable 26// and can be stored using the unique package. A UniqueList is immutable. 27type UniqueList[T comparable] struct { 28 handle unique.Handle[node[T]] 29} 30 31// Len returns the length of the slice that was originally passed to Make. It returns 32// a stored value and does not require iterating the linked list. 33func (s UniqueList[T]) Len() int { 34 var zeroList unique.Handle[node[T]] 35 if s.handle == zeroList { 36 return 0 37 } 38 39 return s.handle.Value().len 40} 41 42// ToSlice returns a slice containing a shallow copy of the list. 43func (s UniqueList[T]) ToSlice() []T { 44 return s.AppendTo(nil) 45} 46 47// Iter returns a iter.Seq that iterates the elements of the list. 48func (s UniqueList[T]) Iter() iter.Seq[T] { 49 var zeroSlice unique.Handle[node[T]] 50 51 return func(yield func(T) bool) { 52 cur := s.handle 53 for cur != zeroSlice { 54 impl := cur.Value() 55 for _, v := range impl.elements[:min(nodeSize, impl.len)] { 56 if !yield(v) { 57 return 58 } 59 } 60 cur = impl.next 61 } 62 } 63} 64 65// iterNodes returns an iter.Seq that iterates each node of the 66// unrolled linked list, returning a slice that contains all the 67// elements in a node at once. 68func (s UniqueList[T]) iterNodes() iter.Seq[[]T] { 69 var zeroSlice unique.Handle[node[T]] 70 71 return func(yield func([]T) bool) { 72 cur := s.handle 73 for cur != zeroSlice { 74 impl := cur.Value() 75 l := min(impl.len, len(impl.elements)) 76 if !yield(impl.elements[:l]) { 77 return 78 } 79 cur = impl.next 80 } 81 } 82} 83 84// AppendTo appends the contents of the list to the given slice and returns 85// the results. 86func (s UniqueList[T]) AppendTo(slice []T) []T { 87 // TODO: should this grow by more than s.Len() to amortize reallocation costs? 88 slice = slices.Grow(slice, s.Len()) 89 for chunk := range s.iterNodes() { 90 slice = append(slice, chunk...) 91 } 92 return slice 93} 94 95// node is a node in an unrolled linked list object that holds a group of elements of a 96// list in a fixed size array in order to satisfy the comparable constraint. 97type node[T comparable] struct { 98 // elements is a group of up to nodeSize elements of a list. 99 elements [nodeSize]T 100 101 // len is the length of the list stored in this node and any transitive linked nodes. 102 // If len is less than nodeSize then only the first len values in the elements array 103 // are part of the list. If len is greater than nodeSize then next will point to the 104 // next node in the unrolled linked list. 105 len int 106 107 // next is the next node in the linked list. If it is the zero value of unique.Handle 108 // then this is the last node. 109 next unique.Handle[node[T]] 110} 111 112// nodeSize is the number of list elements stored in each node. The value 6 was chosen to make 113// the size of node 64 bytes to match the cache line size. 114const nodeSize = 6 115 116// Make returns a UniqueList for the given slice. Two calls to UniqueList with the same slice contents 117// will return identical UniqueList objects. 118func Make[T comparable](slice []T) UniqueList[T] { 119 if len(slice) == 0 { 120 return UniqueList[T]{} 121 } 122 123 var last unique.Handle[node[T]] 124 l := 0 125 126 // Iterate backwards through the lists in chunks of nodeSize, with the first chunk visited 127 // being the partial chunk if the length of the slice is not a multiple of nodeSize. 128 // 129 // For each chunk, create an unrolled linked list node with a chunk of slice elements and a 130 // pointer to the previously created node, uniquified through unique.Make. 131 for chunk := range chunkReverse(slice, nodeSize) { 132 var node node[T] 133 copy(node.elements[:], chunk) 134 node.next = last 135 l += len(chunk) 136 node.len = l 137 last = unique.Make(node) 138 } 139 140 return UniqueList[T]{last} 141} 142 143// chunkReverse is similar to slices.Chunk, except that it returns the chunks in reverse 144// order. If the length of the slice is not a multiple of n then the first chunk returned 145// (which is the last chunk of the input slice) is a partial chunk. 146func chunkReverse[T any](slice []T, n int) iter.Seq[[]T] { 147 return func(yield func([]T) bool) { 148 l := len(slice) 149 lastPartialChunkSize := l % n 150 if lastPartialChunkSize > 0 { 151 if !yield(slice[l-lastPartialChunkSize : l : l]) { 152 return 153 } 154 } 155 for i := l - lastPartialChunkSize - n; i >= 0; i -= n { 156 if !yield(slice[i : i+n : i+n]) { 157 return 158 } 159 } 160 } 161} 162