podman

1
// Copyright 2021 The Go Authors. All rights reserved.
2
// Use of this source code is governed by a BSD-style
3
// license that can be found in the LICENSE file.
4

5
// Package slices defines various functions useful with slices of any type.
6
package slices
7

8
import (
9
	"unsafe"
10

11
	"golang.org/x/exp/constraints"
12
)
13

14
// Equal reports whether two slices are equal: the same length and all
15
// elements equal. If the lengths are different, Equal returns false.
16
// Otherwise, the elements are compared in increasing index order, and the
17
// comparison stops at the first unequal pair.
18
// Floating point NaNs are not considered equal.
19
func Equal[S ~[]E, E comparable](s1, s2 S) bool {
20
	if len(s1) != len(s2) {
21
		return false
22
	}
23
	for i := range s1 {
24
		if s1[i] != s2[i] {
25
			return false
26
		}
27
	}
28
	return true
29
}
30

31
// EqualFunc reports whether two slices are equal using an equality
32
// function on each pair of elements. If the lengths are different,
33
// EqualFunc returns false. Otherwise, the elements are compared in
34
// increasing index order, and the comparison stops at the first index
35
// for which eq returns false.
36
func EqualFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, eq func(E1, E2) bool) bool {
37
	if len(s1) != len(s2) {
38
		return false
39
	}
40
	for i, v1 := range s1 {
41
		v2 := s2[i]
42
		if !eq(v1, v2) {
43
			return false
44
		}
45
	}
46
	return true
47
}
48

49
// Compare compares the elements of s1 and s2, using [cmp.Compare] on each pair
50
// of elements. The elements are compared sequentially, starting at index 0,
51
// until one element is not equal to the other.
52
// The result of comparing the first non-matching elements is returned.
53
// If both slices are equal until one of them ends, the shorter slice is
54
// considered less than the longer one.
55
// The result is 0 if s1 == s2, -1 if s1 < s2, and +1 if s1 > s2.
56
func Compare[S ~[]E, E constraints.Ordered](s1, s2 S) int {
57
	for i, v1 := range s1 {
58
		if i >= len(s2) {
59
			return +1
60
		}
61
		v2 := s2[i]
62
		if c := cmpCompare(v1, v2); c != 0 {
63
			return c
64
		}
65
	}
66
	if len(s1) < len(s2) {
67
		return -1
68
	}
69
	return 0
70
}
71

72
// CompareFunc is like [Compare] but uses a custom comparison function on each
73
// pair of elements.
74
// The result is the first non-zero result of cmp; if cmp always
75
// returns 0 the result is 0 if len(s1) == len(s2), -1 if len(s1) < len(s2),
76
// and +1 if len(s1) > len(s2).
77
func CompareFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, cmp func(E1, E2) int) int {
78
	for i, v1 := range s1 {
79
		if i >= len(s2) {
80
			return +1
81
		}
82
		v2 := s2[i]
83
		if c := cmp(v1, v2); c != 0 {
84
			return c
85
		}
86
	}
87
	if len(s1) < len(s2) {
88
		return -1
89
	}
90
	return 0
91
}
92

93
// Index returns the index of the first occurrence of v in s,
94
// or -1 if not present.
95
func Index[S ~[]E, E comparable](s S, v E) int {
96
	for i := range s {
97
		if v == s[i] {
98
			return i
99
		}
100
	}
101
	return -1
102
}
103

104
// IndexFunc returns the first index i satisfying f(s[i]),
105
// or -1 if none do.
106
func IndexFunc[S ~[]E, E any](s S, f func(E) bool) int {
107
	for i := range s {
108
		if f(s[i]) {
109
			return i
110
		}
111
	}
112
	return -1
113
}
114

115
// Contains reports whether v is present in s.
116
func Contains[S ~[]E, E comparable](s S, v E) bool {
117
	return Index(s, v) >= 0
118
}
119

120
// ContainsFunc reports whether at least one
121
// element e of s satisfies f(e).
122
func ContainsFunc[S ~[]E, E any](s S, f func(E) bool) bool {
123
	return IndexFunc(s, f) >= 0
124
}
125

126
// Insert inserts the values v... into s at index i,
127
// returning the modified slice.
128
// The elements at s[i:] are shifted up to make room.
129
// In the returned slice r, r[i] == v[0],
130
// and r[i+len(v)] == value originally at r[i].
131
// Insert panics if i is out of range.
132
// This function is O(len(s) + len(v)).
133
func Insert[S ~[]E, E any](s S, i int, v ...E) S {
134
	m := len(v)
135
	if m == 0 {
136
		return s
137
	}
138
	n := len(s)
139
	if i == n {
140
		return append(s, v...)
141
	}
142
	if n+m > cap(s) {
143
		// Use append rather than make so that we bump the size of
144
		// the slice up to the next storage class.
145
		// This is what Grow does but we don't call Grow because
146
		// that might copy the values twice.
147
		s2 := append(s[:i], make(S, n+m-i)...)
148
		copy(s2[i:], v)
149
		copy(s2[i+m:], s[i:])
150
		return s2
151
	}
152
	s = s[:n+m]
153

154
	// before:
155
	// s: aaaaaaaabbbbccccccccdddd
156
	//            ^   ^       ^   ^
157
	//            i  i+m      n  n+m
158
	// after:
159
	// s: aaaaaaaavvvvbbbbcccccccc
160
	//            ^   ^       ^   ^
161
	//            i  i+m      n  n+m
162
	//
163
	// a are the values that don't move in s.
164
	// v are the values copied in from v.
165
	// b and c are the values from s that are shifted up in index.
166
	// d are the values that get overwritten, never to be seen again.
167

168
	if !overlaps(v, s[i+m:]) {
169
		// Easy case - v does not overlap either the c or d regions.
170
		// (It might be in some of a or b, or elsewhere entirely.)
171
		// The data we copy up doesn't write to v at all, so just do it.
172

173
		copy(s[i+m:], s[i:])
174

175
		// Now we have
176
		// s: aaaaaaaabbbbbbbbcccccccc
177
		//            ^   ^       ^   ^
178
		//            i  i+m      n  n+m
179
		// Note the b values are duplicated.
180

181
		copy(s[i:], v)
182

183
		// Now we have
184
		// s: aaaaaaaavvvvbbbbcccccccc
185
		//            ^   ^       ^   ^
186
		//            i  i+m      n  n+m
187
		// That's the result we want.
188
		return s
189
	}
190

191
	// The hard case - v overlaps c or d. We can't just shift up
192
	// the data because we'd move or clobber the values we're trying
193
	// to insert.
194
	// So instead, write v on top of d, then rotate.
195
	copy(s[n:], v)
196

197
	// Now we have
198
	// s: aaaaaaaabbbbccccccccvvvv
199
	//            ^   ^       ^   ^
200
	//            i  i+m      n  n+m
201

202
	rotateRight(s[i:], m)
203

204
	// Now we have
205
	// s: aaaaaaaavvvvbbbbcccccccc
206
	//            ^   ^       ^   ^
207
	//            i  i+m      n  n+m
208
	// That's the result we want.
209
	return s
210
}
211

212
// clearSlice sets all elements up to the length of s to the zero value of E.
213
// We may use the builtin clear func instead, and remove clearSlice, when upgrading
214
// to Go 1.21+.
215
func clearSlice[S ~[]E, E any](s S) {
216
	var zero E
217
	for i := range s {
218
		s[i] = zero
219
	}
220
}
221

222
// Delete removes the elements s[i:j] from s, returning the modified slice.
223
// Delete panics if j > len(s) or s[i:j] is not a valid slice of s.
224
// Delete is O(len(s)-i), so if many items must be deleted, it is better to
225
// make a single call deleting them all together than to delete one at a time.
226
// Delete zeroes the elements s[len(s)-(j-i):len(s)].
227
func Delete[S ~[]E, E any](s S, i, j int) S {
228
	_ = s[i:j:len(s)] // bounds check
229

230
	if i == j {
231
		return s
232
	}
233

234
	oldlen := len(s)
235
	s = append(s[:i], s[j:]...)
236
	clearSlice(s[len(s):oldlen]) // zero/nil out the obsolete elements, for GC
237
	return s
238
}
239

240
// DeleteFunc removes any elements from s for which del returns true,
241
// returning the modified slice.
242
// DeleteFunc zeroes the elements between the new length and the original length.
243
func DeleteFunc[S ~[]E, E any](s S, del func(E) bool) S {
244
	i := IndexFunc(s, del)
245
	if i == -1 {
246
		return s
247
	}
248
	// Don't start copying elements until we find one to delete.
249
	for j := i + 1; j < len(s); j++ {
250
		if v := s[j]; !del(v) {
251
			s[i] = v
252
			i++
253
		}
254
	}
255
	clearSlice(s[i:]) // zero/nil out the obsolete elements, for GC
256
	return s[:i]
257
}
258

259
// Replace replaces the elements s[i:j] by the given v, and returns the
260
// modified slice. Replace panics if s[i:j] is not a valid slice of s.
261
// When len(v) < (j-i), Replace zeroes the elements between the new length and the original length.
262
func Replace[S ~[]E, E any](s S, i, j int, v ...E) S {
263
	_ = s[i:j] // verify that i:j is a valid subslice
264

265
	if i == j {
266
		return Insert(s, i, v...)
267
	}
268
	if j == len(s) {
269
		return append(s[:i], v...)
270
	}
271

272
	tot := len(s[:i]) + len(v) + len(s[j:])
273
	if tot > cap(s) {
274
		// Too big to fit, allocate and copy over.
275
		s2 := append(s[:i], make(S, tot-i)...) // See Insert
276
		copy(s2[i:], v)
277
		copy(s2[i+len(v):], s[j:])
278
		return s2
279
	}
280

281
	r := s[:tot]
282

283
	if i+len(v) <= j {
284
		// Easy, as v fits in the deleted portion.
285
		copy(r[i:], v)
286
		if i+len(v) != j {
287
			copy(r[i+len(v):], s[j:])
288
		}
289
		clearSlice(s[tot:]) // zero/nil out the obsolete elements, for GC
290
		return r
291
	}
292

293
	// We are expanding (v is bigger than j-i).
294
	// The situation is something like this:
295
	// (example has i=4,j=8,len(s)=16,len(v)=6)
296
	// s: aaaaxxxxbbbbbbbbyy
297
	//        ^   ^       ^ ^
298
	//        i   j  len(s) tot
299
	// a: prefix of s
300
	// x: deleted range
301
	// b: more of s
302
	// y: area to expand into
303

304
	if !overlaps(r[i+len(v):], v) {
305
		// Easy, as v is not clobbered by the first copy.
306
		copy(r[i+len(v):], s[j:])
307
		copy(r[i:], v)
308
		return r
309
	}
310

311
	// This is a situation where we don't have a single place to which
312
	// we can copy v. Parts of it need to go to two different places.
313
	// We want to copy the prefix of v into y and the suffix into x, then
314
	// rotate |y| spots to the right.
315
	//
316
	//        v[2:]      v[:2]
317
	//         |           |
318
	// s: aaaavvvvbbbbbbbbvv
319
	//        ^   ^       ^ ^
320
	//        i   j  len(s) tot
321
	//
322
	// If either of those two destinations don't alias v, then we're good.
323
	y := len(v) - (j - i) // length of y portion
324

325
	if !overlaps(r[i:j], v) {
326
		copy(r[i:j], v[y:])
327
		copy(r[len(s):], v[:y])
328
		rotateRight(r[i:], y)
329
		return r
330
	}
331
	if !overlaps(r[len(s):], v) {
332
		copy(r[len(s):], v[:y])
333
		copy(r[i:j], v[y:])
334
		rotateRight(r[i:], y)
335
		return r
336
	}
337

338
	// Now we know that v overlaps both x and y.
339
	// That means that the entirety of b is *inside* v.
340
	// So we don't need to preserve b at all; instead we
341
	// can copy v first, then copy the b part of v out of
342
	// v to the right destination.
343
	k := startIdx(v, s[j:])
344
	copy(r[i:], v)
345
	copy(r[i+len(v):], r[i+k:])
346
	return r
347
}
348

349
// Clone returns a copy of the slice.
350
// The elements are copied using assignment, so this is a shallow clone.
351
func Clone[S ~[]E, E any](s S) S {
352
	// Preserve nil in case it matters.
353
	if s == nil {
354
		return nil
355
	}
356
	return append(S([]E{}), s...)
357
}
358

359
// Compact replaces consecutive runs of equal elements with a single copy.
360
// This is like the uniq command found on Unix.
361
// Compact modifies the contents of the slice s and returns the modified slice,
362
// which may have a smaller length.
363
// Compact zeroes the elements between the new length and the original length.
364
func Compact[S ~[]E, E comparable](s S) S {
365
	if len(s) < 2 {
366
		return s
367
	}
368
	i := 1
369
	for k := 1; k < len(s); k++ {
370
		if s[k] != s[k-1] {
371
			if i != k {
372
				s[i] = s[k]
373
			}
374
			i++
375
		}
376
	}
377
	clearSlice(s[i:]) // zero/nil out the obsolete elements, for GC
378
	return s[:i]
379
}
380

381
// CompactFunc is like [Compact] but uses an equality function to compare elements.
382
// For runs of elements that compare equal, CompactFunc keeps the first one.
383
// CompactFunc zeroes the elements between the new length and the original length.
384
func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S {
385
	if len(s) < 2 {
386
		return s
387
	}
388
	i := 1
389
	for k := 1; k < len(s); k++ {
390
		if !eq(s[k], s[k-1]) {
391
			if i != k {
392
				s[i] = s[k]
393
			}
394
			i++
395
		}
396
	}
397
	clearSlice(s[i:]) // zero/nil out the obsolete elements, for GC
398
	return s[:i]
399
}
400

401
// Grow increases the slice's capacity, if necessary, to guarantee space for
402
// another n elements. After Grow(n), at least n elements can be appended
403
// to the slice without another allocation. If n is negative or too large to
404
// allocate the memory, Grow panics.
405
func Grow[S ~[]E, E any](s S, n int) S {
406
	if n < 0 {
407
		panic("cannot be negative")
408
	}
409
	if n -= cap(s) - len(s); n > 0 {
410
		// TODO(https://go.dev/issue/53888): Make using []E instead of S
411
		// to workaround a compiler bug where the runtime.growslice optimization
412
		// does not take effect. Revert when the compiler is fixed.
413
		s = append([]E(s)[:cap(s)], make([]E, n)...)[:len(s)]
414
	}
415
	return s
416
}
417

418
// Clip removes unused capacity from the slice, returning s[:len(s):len(s)].
419
func Clip[S ~[]E, E any](s S) S {
420
	return s[:len(s):len(s)]
421
}
422

423
// Rotation algorithm explanation:
424
//
425
// rotate left by 2
426
// start with
427
//   0123456789
428
// split up like this
429
//   01 234567 89
430
// swap first 2 and last 2
431
//   89 234567 01
432
// join first parts
433
//   89234567 01
434
// recursively rotate first left part by 2
435
//   23456789 01
436
// join at the end
437
//   2345678901
438
//
439
// rotate left by 8
440
// start with
441
//   0123456789
442
// split up like this
443
//   01 234567 89
444
// swap first 2 and last 2
445
//   89 234567 01
446
// join last parts
447
//   89 23456701
448
// recursively rotate second part left by 6
449
//   89 01234567
450
// join at the end
451
//   8901234567
452

453
// TODO: There are other rotate algorithms.
454
// This algorithm has the desirable property that it moves each element exactly twice.
455
// The triple-reverse algorithm is simpler and more cache friendly, but takes more writes.
456
// The follow-cycles algorithm can be 1-write but it is not very cache friendly.
457

458
// rotateLeft rotates b left by n spaces.
459
// s_final[i] = s_orig[i+r], wrapping around.
460
func rotateLeft[E any](s []E, r int) {
461
	for r != 0 && r != len(s) {
462
		if r*2 <= len(s) {
463
			swap(s[:r], s[len(s)-r:])
464
			s = s[:len(s)-r]
465
		} else {
466
			swap(s[:len(s)-r], s[r:])
467
			s, r = s[len(s)-r:], r*2-len(s)
468
		}
469
	}
470
}
471
func rotateRight[E any](s []E, r int) {
472
	rotateLeft(s, len(s)-r)
473
}
474

475
// swap swaps the contents of x and y. x and y must be equal length and disjoint.
476
func swap[E any](x, y []E) {
477
	for i := 0; i < len(x); i++ {
478
		x[i], y[i] = y[i], x[i]
479
	}
480
}
481

482
// overlaps reports whether the memory ranges a[0:len(a)] and b[0:len(b)] overlap.
483
func overlaps[E any](a, b []E) bool {
484
	if len(a) == 0 || len(b) == 0 {
485
		return false
486
	}
487
	elemSize := unsafe.Sizeof(a[0])
488
	if elemSize == 0 {
489
		return false
490
	}
491
	// TODO: use a runtime/unsafe facility once one becomes available. See issue 12445.
492
	// Also see crypto/internal/alias/alias.go:AnyOverlap
493
	return uintptr(unsafe.Pointer(&a[0])) <= uintptr(unsafe.Pointer(&b[len(b)-1]))+(elemSize-1) &&
494
		uintptr(unsafe.Pointer(&b[0])) <= uintptr(unsafe.Pointer(&a[len(a)-1]))+(elemSize-1)
495
}
496

497
// startIdx returns the index in haystack where the needle starts.
498
// prerequisite: the needle must be aliased entirely inside the haystack.
499
func startIdx[E any](haystack, needle []E) int {
500
	p := &needle[0]
501
	for i := range haystack {
502
		if p == &haystack[i] {
503
			return i
504
		}
505
	}
506
	// TODO: what if the overlap is by a non-integral number of Es?
507
	panic("needle not found")
508
}
509

510
// Reverse reverses the elements of the slice in place.
511
func Reverse[S ~[]E, E any](s S) {
512
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
513
		s[i], s[j] = s[j], s[i]
514
	}
515
}
516