forked from pachyderm/pachyderm
/
sorted_list.go
62 lines (58 loc) · 1.89 KB
/
sorted_list.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package hashtree
import "sort"
// This is not in "math", unfortunately
func max(i, j int) int {
if i > j {
return i
}
return j
}
// insertStr inserts 's' into 'ss', preserving sorting (it assumes that 'ss' is
// sorted). If a copy is necessary (because cap(ss) is too small), only does
// one copy (unlike `append(append(ss[:idx], newS), ss[idx:]...)`). This is
// because directory nodes may include a large number of children.
//
// This is used to preserve the order in DirectoryNode.Children, which must
// be maintained so that equivalent directories have the same hash.
//
// Returns 'true' if newS was added to 'ss' and 'false' otherwise (if newS is
// already in 'ss').
func insertStr(ss *[]string, newS string) bool {
sz := cap(*ss)
idx := sort.SearchStrings(*ss, newS)
if idx >= len(*ss) || (*ss)[idx] != newS {
// Need to insert new element
if sz >= (len(*ss) + 1) {
*ss = (*ss)[:len(*ss)+1]
copy((*ss)[idx+1:], (*ss)[idx:])
(*ss)[idx] = newS
} else {
// Need to grow ss (i.e. make a copy)
// - Using a factor (instead of always adding a constant number of
// elements) ensures amortized constant time for insertions, and keeping
// it reasonably low avoids wasting too much space. Current value of
// 1.33 is arbitrary.
// - If sz is small, grow sz by at least a constant amount (must be >=1,
// currently 10)
cap1, cap2 := int(float64(sz)*1.33), sz+10
newSs := make([]string, len(*ss)+1, max(cap1, cap2))
copy(newSs, (*ss)[:idx])
copy(newSs[idx+1:], (*ss)[idx:])
newSs[idx] = newS
*ss = newSs
}
return true
}
return false
}
// removeStr removes 's' from 'ss', preserving the sorted order of 'ss' (for
// removing child strings from DirectoryNodes.
func removeStr(ss *[]string, s string) bool {
idx := sort.SearchStrings(*ss, s)
if idx == len(*ss) {
return false
}
copy((*ss)[idx:], (*ss)[idx+1:])
*ss = (*ss)[:len(*ss)-1]
return true
}