history_rowids.go RawHistoryFolder

1package vt
2
3import "slices"
4
5// rowIDSet detects duplicate row IDs across one or more decoded blobs without
6// a hash map in the common case. Row IDs are NOT required to be monotonic
7// (History.AppendWithID accepts any unused ID, so persisted blobs may list IDs
8// out of order), so this is an exact set, not an ordering check: it accepts
9// and rejects precisely the inputs a map[RowID]struct{} would.
10//
11// While every view contributes IDs strictly above everything seen so far, IDs
12// are kept in an ascending slice. The first view that interleaves with earlier
13// IDs converts the set to a map; from then on it behaves like a plain set.
14type rowIDSet struct {
15	sorted  []RowID
16	members map[RowID]struct{}
17	scratch []RowID
18}
19
20// begin discards any IDs collected but not committed and reserves room for n.
21func (s *rowIDSet) begin(n int) { s.scratch = slices.Grow(s.scratch[:0], n) }
22
23// reserve makes room for n more collected IDs.
24func (s *rowIDSet) reserve(n int) { s.scratch = slices.Grow(s.scratch, n) }
25
26// collect records one ID of the view being collected.
27func (s *rowIDSet) collect(id RowID) { s.scratch = append(s.scratch, id) }
28
29// commit reports whether the collected IDs are distinct from each other and
30// from every previously committed ID, and if so adds them to the set.
31func (s *rowIDSet) commit() bool {
32	ids := s.scratch
33	s.scratch = s.scratch[:0]
34	if len(ids) == 0 {
35		return true
36	}
37	slices.Sort(ids) // the scratch copy is private, so sorting in place is safe
38
39	for i := 1; i < len(ids); i++ {
40		if ids[i] == ids[i-1] {
41			return false
42		}
43	}
44	if s.members == nil {
45		if len(s.sorted) == 0 || ids[0] > s.sorted[len(s.sorted)-1] {
46			s.sorted = append(s.sorted, ids...)
47			return true
48		}
49		s.members = make(map[RowID]struct{}, len(s.sorted)+len(ids))
50		for _, id := range s.sorted {
51			s.members[id] = struct{}{}
52		}
53		s.sorted = nil
54	}
55	for _, id := range ids {
56		if _, duplicate := s.members[id]; duplicate {
57			return false
58		}
59	}
60	for _, id := range ids {
61		s.members[id] = struct{}{}
62	}
63	return true
64}