12583319996

Committed 02 Jan 2025 01:38PM UTC coverage: 57.522% (-1.1%) from 58.598%

Build # 12583319996

Build Type

Pull #9361

github

Committed by

starius

Commit Message

fn/ContextGuard: use context.AfterFunc to wait

Simplifies context cancellation handling by using context.AfterFunc instead of a
goroutine to wait for context cancellation. This approach avoids the overhead of
a goroutine during the waiting period.

For ctxQuitUnsafe, since g.quit is closed only in the Quit method (which also
cancels all associated contexts), waiting on context cancellation ensures the
same behavior without unnecessary dependency on g.quit.

Added a test to ensure that the Create method does not launch any goroutines.

Pull Request Pull Request #9361: fn: optimize context guard

Run Details

102587 of 178344 relevant lines covered (57.52%)

24734.33 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

13.18

/watchtower/wtdb/migration8/range_index.go

package migration8

import (
        "fmt"
        "sync"
)

// rangeItem represents the start and end values of a range.
type rangeItem struct {
        start uint64
        end   uint64
}

// RangeIndexOption describes the signature of a functional option that can be
// used to modify the behaviour of a RangeIndex.
type RangeIndexOption func(*RangeIndex)

// WithSerializeUint64Fn is a functional option that can be used to set the
// function to be used to do the serialization of a uint64 into a byte slice.
func WithSerializeUint64Fn(fn func(uint64) ([]byte, error)) RangeIndexOption {
        return func(index *RangeIndex) {
                index.serializeUint64 = fn
        }
}

// RangeIndex can be used to keep track of which numbers have been added to a
// set. It does so by keeping track of a sorted list of rangeItems. Each
// rangeItem has a start and end value of a range where all values in-between
// have been added to the set. It works well in situations where it is expected
// numbers in the set are not sparse.
type RangeIndex struct {
        // set is a sorted list of rangeItem.
        set []rangeItem

        // mu is used to ensure safe access to set.
        mu sync.Mutex

        // serializeUint64 is the function that can be used to convert a uint64
        // to a byte slice.
        serializeUint64 func(uint64) ([]byte, error)
}

// NewRangeIndex constructs a new RangeIndex. An initial set of ranges may be
// passed to the function in the form of a map.
func NewRangeIndex(ranges map[uint64]uint64,
        opts ...RangeIndexOption) (*RangeIndex, error) {

        index := &RangeIndex{
                serializeUint64: defaultSerializeUint64,
                set:             make([]rangeItem, 0),
        }

        // Apply any functional options.
        for _, o := range opts {
                o(index)
        }

        for s, e := range ranges {
                if err := index.addRange(s, e); err != nil {
                        return nil, err
                }
        }

        return index, nil
}

// addRange can be used to add an entire new range to the set. This method
// should only ever be called by NewRangeIndex to initialise the in-memory
// structure and so the RangeIndex mutex is not held during this method.
func (a *RangeIndex) addRange(start, end uint64) error {
        // Check that the given range is valid.
        if start > end {
                return fmt.Errorf("invalid range. Start height %d is larger "+
                        "than end height %d", start, end)
        }

        // min is a helper closure that will return the minimum of two uint64s.
        min := func(a, b uint64) uint64 {
                if a < b {
                        return a
                }

                return b
        }

        // max is a helper closure that will return the maximum of two uint64s.
        max := func(a, b uint64) uint64 {
                if a > b {
                        return a
                }

                return b
        }

        // Collect the ranges that fall before and after the new range along
        // with the start and end values of the new range.
        var before, after []rangeItem
        for _, x := range a.set {
                // If the new start value can't extend the current ranges end
                // value, then the two cannot be merged. The range is added to
                // the group of ranges that fall before the new range.
                if x.end+1 < start {
                        before = append(before, x)
                        continue
                }

                // If the current ranges start value does not follow on directly
                // from the new end value, then the two cannot be merged. The
                // range is added to the group of ranges that fall after the new
                // range.
                if end+1 < x.start {
                        after = append(after, x)
                        continue
                }

                // Otherwise, there is an overlap and so the two can be merged.
                start = min(start, x.start)
                end = max(end, x.end)
        }

        // Re-construct the range index set.
        a.set = append(append(before, rangeItem{
                start: start,
                end:   end,
        }), after...)

        return nil
}

// IsInIndex returns true if the given number is in the range set.
func (a *RangeIndex) IsInIndex(n uint64) bool {
        a.mu.Lock()
        defer a.mu.Unlock()

        _, isCovered := a.lowerBoundIndex(n)

        return isCovered
}

// NumInSet returns the number of items covered by the range set.
func (a *RangeIndex) NumInSet() uint64 {
        a.mu.Lock()
        defer a.mu.Unlock()

        var numItems uint64
        for _, r := range a.set {
                numItems += r.end - r.start + 1
        }

        return numItems
}

// MaxHeight returns the highest number covered in the range.
func (a *RangeIndex) MaxHeight() uint64 {
        a.mu.Lock()
        defer a.mu.Unlock()

        if len(a.set) == 0 {
                return 0
        }

        return a.set[len(a.set)-1].end
}

// GetAllRanges returns a copy of the range set in the form of a map.
func (a *RangeIndex) GetAllRanges() map[uint64]uint64 {
        a.mu.Lock()
        defer a.mu.Unlock()

        cp := make(map[uint64]uint64, len(a.set))
        for _, item := range a.set {
                cp[item.start] = item.end
        }

        return cp
}

// lowerBoundIndex returns the index of the RangeIndex that is most appropriate
// for the new value, n. In other words, it returns the index of the rangeItem
// set of the range where the start value is the highest start value in the set
// that is still lower than or equal to the given number, n. The returned
// boolean is true if the given number is already covered in the RangeIndex.
// A returned index of -1 indicates that no lower bound range exists in the set.
// Since the most likely case is that the new number will just extend the
// highest range, a check is first done to see if this is the case which will
// make the methods' computational complexity O(1). Otherwise, a binary search
// is done which brings the computational complexity to O(log N).
func (a *RangeIndex) lowerBoundIndex(n uint64) (int, bool) {
        // If the set is empty, then there is no such index and the value
        // definitely is not in the set.
        if len(a.set) == 0 {
                return -1, false
        }

        // In most cases, the last index item will be the one we want. So just
        // do a quick check on that index first to avoid doing the binary
        // search.
        lastIndex := len(a.set) - 1
        lastRange := a.set[lastIndex]
        if lastRange.start <= n {
                return lastIndex, lastRange.end >= n
        }

        // Otherwise, do a binary search to find the index of interest.
        var (
                low        = 0
                high       = len(a.set) - 1
                rangeIndex = -1
        )
        for {
                mid := (low + high) / 2
                currentRange := a.set[mid]

                switch {
                case currentRange.start > n:
                        // If the start of the range is greater than n, we can
                        // completely cut out that entire part of the array.
                        high = mid

                case currentRange.start < n:
                        // If the range already includes the given height, we
                        // can stop searching now.
                        if currentRange.end >= n {
                                return mid, true
                        }

                        // If the start of the range is smaller than n, we can
                        // store this as the new best index to return.
                        rangeIndex = mid

                        // If low and mid are already equal, then increment low
                        // by 1. Exit if this means that low is now greater than
                        // high.
                        if low == mid {
                                low = mid + 1
                                if low > high {
                                        return rangeIndex, false
                                }
                        } else {
                                low = mid
                        }

                        continue

                default:
                        // If the height is equal to the start value of the
                        // current range that mid is pointing to, then the
                        // height is already covered.
                        return mid, true
                }

                // Exit if we have checked all the ranges.
                if low == high {
                        break
                }
        }

        return rangeIndex, false
}

// KVStore is an interface representing a key-value store.
type KVStore interface {
        // Put saves the specified key/value pair to the store. Keys that do not
        // already exist are added and keys that already exist are overwritten.
        Put(key, value []byte) error

        // Delete removes the specified key from the bucket. Deleting a key that
        // does not exist does not return an error.
        Delete(key []byte) error
}

// Add adds a single number to the range set. It first attempts to apply the
// necessary changes to the passed KV store and then only if this succeeds, will
// the changes be applied to the in-memory structure.
func (a *RangeIndex) Add(newHeight uint64, kv KVStore) error {
        a.mu.Lock()
        defer a.mu.Unlock()

        // Compute the changes that will need to be applied to both the sorted
        // rangeItem array representation and the key-value store representation
        // of the range index.
        arrayChanges, kvStoreChanges := a.getChanges(newHeight)

        // First attempt to apply the KV store changes. Only if this succeeds
        // will we apply the changes to our in-memory range index structure.
        err := a.applyKVChanges(kv, kvStoreChanges)
        if err != nil {
                return err
        }

        // Since the DB changes were successful, we can now commit the
        // changes to our in-memory representation of the range set.
        a.applyArrayChanges(arrayChanges)

        return nil
}

// applyKVChanges applies the given set of kvChanges to a KV store. It is
// assumed that a transaction is being held on the kv store so that if any
// of the actions of the function fails, the changes will be reverted.
func (a *RangeIndex) applyKVChanges(kv KVStore, changes *kvChanges) error {
        // Exit early if there are no changes to apply.
        if kv == nil || changes == nil {
                return nil
        }

        // Check if any range pair needs to be deleted.
        if changes.deleteKVKey != nil {
                del, err := a.serializeUint64(*changes.deleteKVKey)
                if err != nil {
                        return err
                }

                if err := kv.Delete(del); err != nil {
                        return err
                }
        }

        start, err := a.serializeUint64(changes.key)
        if err != nil {
                return err
        }

        end, err := a.serializeUint64(changes.value)
        if err != nil {
                return err
        }

        return kv.Put(start, end)
}

// applyArrayChanges applies the given arrayChanges to the in-memory RangeIndex
// itself. This should only be done once the persisted kv store changes have
// already been applied.
func (a *RangeIndex) applyArrayChanges(changes *arrayChanges) {
        if changes == nil {
                return
        }

        if changes.indexToDelete != nil {
                a.set = append(
                        a.set[:*changes.indexToDelete],
                        a.set[*changes.indexToDelete+1:]...,
                )
        }

        if changes.newIndex != nil {
                switch {
                case *changes.newIndex == 0:
                        a.set = append([]rangeItem{{
                                start: changes.start,
                                end:   changes.end,
                        }}, a.set...)

                case *changes.newIndex == len(a.set):
                        a.set = append(a.set, rangeItem{
                                start: changes.start,
                                end:   changes.end,
                        })

                default:
                        a.set = append(
                                a.set[:*changes.newIndex+1],
                                a.set[*changes.newIndex:]...,
                        )
                        a.set[*changes.newIndex] = rangeItem{
                                start: changes.start,
                                end:   changes.end,
                        }
                }

                return
        }

        if changes.indexToEdit != nil {
                a.set[*changes.indexToEdit] = rangeItem{
                        start: changes.start,
                        end:   changes.end,
                }
        }
}

// arrayChanges encompasses the diff to apply to the sorted rangeItem array
// representation of a range index. Such a diff will either include adding a
// new range or editing an existing range. If an existing range is edited, then
// the diff might also include deleting an index (this will be the case if the
// editing of the one range results in the merge of another range).
type arrayChanges struct {
        start uint64
        end   uint64

        // newIndex, if set, is the index of the in-memory range array where a
        // new range, [start:end], should be added. newIndex should never be
        // set at the same time as indexToEdit or indexToDelete.
        newIndex *int

        // indexToDelete, if set, is the index of the sorted rangeItem array
        // that should be deleted. This should be applied before reading the
        // index value of indexToEdit. This should not be set at the same time
        // as newIndex.
        indexToDelete *int

        // indexToEdit is the index of the in-memory range array that should be
        // edited. The range at this index will be changed to [start:end]. This
        // should only be read after indexToDelete index has been deleted.
        indexToEdit *int
}

// kvChanges encompasses the diff to apply to a KV-store representation of a
// range index. A kv-store diff for the addition of a single number to the range
// index will include either a brand new key-value pair or the altering of the
// value of an existing key. Optionally, the diff may also include the deletion
// of an existing key. A deletion will be required if the addition of the new
// number results in the merge of two ranges.
type kvChanges struct {
        key   uint64
        value uint64

        // deleteKVKey, if set, is the key of the kv store representation that
        // should be deleted.
        deleteKVKey *uint64
}

// getChanges will calculate and return the changes that need to be applied to
// both the sorted-rangeItem-array representation and the key-value store
// representation of the range index.
func (a *RangeIndex) getChanges(n uint64) (*arrayChanges, *kvChanges) {
        // If the set is empty then a new range item is added.
        if len(a.set) == 0 {
                // For the array representation, a new range [n:n] is added to
                // the first index of the array.
                firstIndex := 0
                ac := &arrayChanges{
                        newIndex: &firstIndex,
                        start:    n,
                        end:      n,
                }

                // For the KV representation, a new [n:n] pair is added.
                kvc := &kvChanges{
                        key:   n,
                        value: n,
                }

                return ac, kvc
        }

        // Find the index of the lower bound range to the new number.
        indexOfRangeBelow, alreadyCovered := a.lowerBoundIndex(n)

        switch {
        // The new number is already covered by the range index. No changes are
        // required.
        case alreadyCovered:
                return nil, nil

        // No lower bound index exists.
        case indexOfRangeBelow < 0:
                // Check if the very first range can be merged into this new
                // one.
                if n+1 == a.set[0].start {
                        // If so, the two ranges can be merged and so the start
                        // value of the range is n and the end value is the end
                        // of the existing first range.
                        start := n
                        end := a.set[0].end

                        // For the array representation, we can just edit the
                        // first entry of the array
                        editIndex := 0
                        ac := &arrayChanges{
                                indexToEdit: &editIndex,
                                start:       start,
                                end:         end,
                        }

                        // For the KV store representation, we add a new kv pair
                        // and delete the range with the key equal to the start
                        // value of the range we are merging.
                        kvKeyToDelete := a.set[0].start
                        kvc := &kvChanges{
                                key:         start,
                                value:       end,
                                deleteKVKey: &kvKeyToDelete,
                        }

                        return ac, kvc
                }

                // Otherwise, we add a new index.

                // For the array representation, a new range [n:n] is added to
                // the first index of the array.
                newIndex := 0
                ac := &arrayChanges{
                        newIndex: &newIndex,
                        start:    n,
                        end:      n,
                }

                // For the KV representation, a new [n:n] pair is added.
                kvc := &kvChanges{
                        key:   n,
                        value: n,
                }

                return ac, kvc

        // A lower range does exist, and it can be extended to include this new
        // number.
        case a.set[indexOfRangeBelow].end+1 == n:
                start := a.set[indexOfRangeBelow].start
                end := n
                indexToChange := indexOfRangeBelow

                // If there are no intervals above this one or if there are, but
                // they can't be merged into this one then we just need to edit
                // this interval.
                if indexOfRangeBelow == len(a.set)-1 ||
                        a.set[indexOfRangeBelow+1].start != n+1 {

                        // For the array representation, we just edit the index.
                        ac := &arrayChanges{
                                indexToEdit: &indexToChange,
                                start:       start,
                                end:         end,
                        }

                        // For the key-value representation, we just overwrite
                        // the end value at the existing start key.
                        kvc := &kvChanges{
                                key:   start,
                                value: end,
                        }

                        return ac, kvc
                }

                // There is a range above this one that we need to merge into
                // this one.
                delIndex := indexOfRangeBelow + 1
                end = a.set[delIndex].end

                // For the array representation, we delete the range above this
                // one and edit this range to include the end value of the range
                // above.
                ac := &arrayChanges{
                        indexToDelete: &delIndex,
                        indexToEdit:   &indexToChange,
                        start:         start,
                        end:           end,
                }

                // For the kv representation, we tweak the end value of an
                // existing key and delete the key of the range we are deleting.
                deleteKey := a.set[delIndex].start
                kvc := &kvChanges{
                        key:         start,
                        value:       end,
                        deleteKVKey: &deleteKey,
                }

                return ac, kvc

        // A lower range does exist, but it can't be extended to include this
        // new number, and so we need to add a new range after the lower bound
        // range.
        default:
                newIndex := indexOfRangeBelow + 1

                // If there are no ranges above this new one or if there are,
                // but they can't be merged into this new one, then we can just
                // add the new one as is.
                if newIndex == len(a.set) || a.set[newIndex].start != n+1 {
                        ac := &arrayChanges{
                                newIndex: &newIndex,
                                start:    n,
                                end:      n,
                        }

                        kvc := &kvChanges{
                                key:   n,
                                value: n,
                        }

                        return ac, kvc
                }

                // Else, we merge the above index.
                start := n
                end := a.set[newIndex].end
                toEdit := newIndex

                // For the array representation, we edit the range above to
                // include the new start value.
                ac := &arrayChanges{
                        indexToEdit: &toEdit,
                        start:       start,
                        end:         end,
                }

                // For the kv representation, we insert the new start-end key
                // value pair and delete the key using the old start value.
                delKey := a.set[newIndex].start
                kvc := &kvChanges{
                        key:         start,
                        value:       end,
                        deleteKVKey: &delKey,
                }

                return ac, kvc
        }
}

func defaultSerializeUint64(i uint64) ([]byte, error) {
        var b [8]byte
        byteOrder.PutUint64(b[:], i)
        return b[:], nil
}

1	package migration8
2
3	import (
4	"fmt"
5	"sync"
6	)
7
8	// rangeItem represents the start and end values of a range.
9	type rangeItem struct {
10	start uint64
11	end uint64
12	}
13
14	// RangeIndexOption describes the signature of a functional option that can be
15	// used to modify the behaviour of a RangeIndex.
16	type RangeIndexOption func(*RangeIndex)
17
18	// WithSerializeUint64Fn is a functional option that can be used to set the
19	// function to be used to do the serialization of a uint64 into a byte slice.
20	func WithSerializeUint64Fn(fn func(uint64) ([]byte, error)) RangeIndexOption {	4✔
21	return func(index *RangeIndex) {	8✔
22	index.serializeUint64 = fn	4✔
23	}	4✔
24	}
25
26	// RangeIndex can be used to keep track of which numbers have been added to a
27	// set. It does so by keeping track of a sorted list of rangeItems. Each
28	// rangeItem has a start and end value of a range where all values in-between
29	// have been added to the set. It works well in situations where it is expected
30	// numbers in the set are not sparse.
31	type RangeIndex struct {
32	// set is a sorted list of rangeItem.
33	set []rangeItem
34
35	// mu is used to ensure safe access to set.
36	mu sync.Mutex
37
38	// serializeUint64 is the function that can be used to convert a uint64
39	// to a byte slice.
40	serializeUint64 func(uint64) ([]byte, error)
41	}
42
43	// NewRangeIndex constructs a new RangeIndex. An initial set of ranges may be
44	// passed to the function in the form of a map.
45	func NewRangeIndex(ranges map[uint64]uint64,
46	opts ...RangeIndexOption) (*RangeIndex, error) {	4✔
47		4✔
48	index := &RangeIndex{	4✔
49	serializeUint64: defaultSerializeUint64,	4✔
50	set: make([]rangeItem, 0),	4✔
51	}	4✔
52		4✔
53	// Apply any functional options.	4✔
54	for _, o := range opts {	8✔
55	o(index)	4✔
56	}	4✔
57
58	for s, e := range ranges {	10✔
59	if err := index.addRange(s, e); err != nil {	6✔
60	return nil, err	×
61	}	×
62	}
63
64	return index, nil	4✔
65	}
66
67	// addRange can be used to add an entire new range to the set. This method
68	// should only ever be called by NewRangeIndex to initialise the in-memory
69	// structure and so the RangeIndex mutex is not held during this method.
70	func (a *RangeIndex) addRange(start, end uint64) error {	6✔
71	// Check that the given range is valid.	6✔
72	if start > end {	6✔
73	return fmt.Errorf("invalid range. Start height %d is larger "+	×
74	"than end height %d", start, end)	×
75	}	×
76
77	// min is a helper closure that will return the minimum of two uint64s.
78	min := func(a, b uint64) uint64 {	7✔
79	if a < b {	1✔
80	return a	×
81	}	×
82
83	return b	1✔
84	}
85
86	// max is a helper closure that will return the maximum of two uint64s.
87	max := func(a, b uint64) uint64 {	7✔
88	if a > b {	2✔
89	return a	1✔
90	}	1✔
91
92	return b	×
93	}
94
95	// Collect the ranges that fall before and after the new range along
96	// with the start and end values of the new range.
97	var before, after []rangeItem	6✔
98	for _, x := range a.set {	8✔
99	// If the new start value can't extend the current ranges end	2✔
100	// value, then the two cannot be merged. The range is added to	2✔
101	// the group of ranges that fall before the new range.	2✔
102	if x.end+1 < start {	3✔
103	before = append(before, x)	1✔
104	continue	1✔
105	}
106
107	// If the current ranges start value does not follow on directly
108	// from the new end value, then the two cannot be merged. The
109	// range is added to the group of ranges that fall after the new
110	// range.
111	if end+1 < x.start {	1✔
112	after = append(after, x)	×
113	continue	×
114	}
115
116	// Otherwise, there is an overlap and so the two can be merged.
117	start = min(start, x.start)	1✔
118	end = max(end, x.end)	1✔
119	}
120
121	// Re-construct the range index set.
122	a.set = append(append(before, rangeItem{	6✔
123	start: start,	6✔
124	end: end,	6✔
125	}), after...)	6✔
126		6✔
127	return nil	6✔
128	}
129
130	// IsInIndex returns true if the given number is in the range set.
131	func (a *RangeIndex) IsInIndex(n uint64) bool {	×
132	a.mu.Lock()	×
133	defer a.mu.Unlock()	×
134		×
135	_, isCovered := a.lowerBoundIndex(n)	×
136		×
137	return isCovered	×
138	}	×
139
140	// NumInSet returns the number of items covered by the range set.
141	func (a *RangeIndex) NumInSet() uint64 {	×
142	a.mu.Lock()	×
143	defer a.mu.Unlock()	×
144		×
145	var numItems uint64	×
146	for _, r := range a.set {	×
147	numItems += r.end - r.start + 1	×
148	}	×
149
150	return numItems	×
151	}
152
153	// MaxHeight returns the highest number covered in the range.
154	func (a *RangeIndex) MaxHeight() uint64 {	4✔
155	a.mu.Lock()	4✔
156	defer a.mu.Unlock()	4✔
157		4✔
158	if len(a.set) == 0 {	4✔
159	return 0	×
160	}	×
161
162	return a.set[len(a.set)-1].end	4✔
163	}
164
165	// GetAllRanges returns a copy of the range set in the form of a map.
166	func (a *RangeIndex) GetAllRanges() map[uint64]uint64 {	×
167	a.mu.Lock()	×
168	defer a.mu.Unlock()	×
169		×
170	cp := make(map[uint64]uint64, len(a.set))	×
171	for _, item := range a.set {	×
172	cp[item.start] = item.end	×
173	}	×
174
175	return cp	×
176	}
177
178	// lowerBoundIndex returns the index of the RangeIndex that is most appropriate
179	// for the new value, n. In other words, it returns the index of the rangeItem
180	// set of the range where the start value is the highest start value in the set
181	// that is still lower than or equal to the given number, n. The returned
182	// boolean is true if the given number is already covered in the RangeIndex.
183	// A returned index of -1 indicates that no lower bound range exists in the set.
184	// Since the most likely case is that the new number will just extend the
185	// highest range, a check is first done to see if this is the case which will
186	// make the methods' computational complexity O(1). Otherwise, a binary search
187	// is done which brings the computational complexity to O(log N).
188	func (a *RangeIndex) lowerBoundIndex(n uint64) (int, bool) {	×
189	// If the set is empty, then there is no such index and the value	×
190	// definitely is not in the set.	×
191	if len(a.set) == 0 {	×
192	return -1, false	×
193	}	×
194
195	// In most cases, the last index item will be the one we want. So just
196	// do a quick check on that index first to avoid doing the binary
197	// search.
198	lastIndex := len(a.set) - 1	×
199	lastRange := a.set[lastIndex]	×
200	if lastRange.start <= n {	×
201	return lastIndex, lastRange.end >= n	×
202	}	×
203
204	// Otherwise, do a binary search to find the index of interest.
205	var (	×
206	low = 0	×
207	high = len(a.set) - 1	×
208	rangeIndex = -1	×
209	)	×
210	for {	×
211	mid := (low + high) / 2	×
212	currentRange := a.set[mid]	×
213		×
214	switch {	×
215	case currentRange.start > n:	×
216	// If the start of the range is greater than n, we can	×
217	// completely cut out that entire part of the array.	×
218	high = mid	×
219
220	case currentRange.start < n:	×
221	// If the range already includes the given height, we	×
222	// can stop searching now.	×
223	if currentRange.end >= n {	×
224	return mid, true	×
225	}	×
226
227	// If the start of the range is smaller than n, we can
228	// store this as the new best index to return.
229	rangeIndex = mid	×
230		×
231	// If low and mid are already equal, then increment low	×
232	// by 1. Exit if this means that low is now greater than	×
233	// high.	×
234	if low == mid {	×
235	low = mid + 1	×
236	if low > high {	×
237	return rangeIndex, false	×
238	}	×
239	} else {	×
240	low = mid	×
241	}	×
242
243	continue	×
244
245	default:	×
246	// If the height is equal to the start value of the	×
247	// current range that mid is pointing to, then the	×
248	// height is already covered.	×
249	return mid, true	×
250	}
251
252	// Exit if we have checked all the ranges.
253	if low == high {	×
254	break	×
255	}
256	}
257
258	return rangeIndex, false	×
259	}
260
261	// KVStore is an interface representing a key-value store.
262	type KVStore interface {
263	// Put saves the specified key/value pair to the store. Keys that do not
264	// already exist are added and keys that already exist are overwritten.
265	Put(key, value []byte) error
266
267	// Delete removes the specified key from the bucket. Deleting a key that
268	// does not exist does not return an error.
269	Delete(key []byte) error
270	}
271
272	// Add adds a single number to the range set. It first attempts to apply the
273	// necessary changes to the passed KV store and then only if this succeeds, will
274	// the changes be applied to the in-memory structure.
275	func (a *RangeIndex) Add(newHeight uint64, kv KVStore) error {	×
276	a.mu.Lock()	×
277	defer a.mu.Unlock()	×
278		×
279	// Compute the changes that will need to be applied to both the sorted	×
280	// rangeItem array representation and the key-value store representation	×
281	// of the range index.	×
282	arrayChanges, kvStoreChanges := a.getChanges(newHeight)	×
283		×
284	// First attempt to apply the KV store changes. Only if this succeeds	×
285	// will we apply the changes to our in-memory range index structure.	×
286	err := a.applyKVChanges(kv, kvStoreChanges)	×
287	if err != nil {	×
288	return err	×
289	}	×
290
291	// Since the DB changes were successful, we can now commit the
292	// changes to our in-memory representation of the range set.
293	a.applyArrayChanges(arrayChanges)	×
294		×
295	return nil	×
296	}
297
298	// applyKVChanges applies the given set of kvChanges to a KV store. It is
299	// assumed that a transaction is being held on the kv store so that if any
300	// of the actions of the function fails, the changes will be reverted.
301	func (a RangeIndex) applyKVChanges(kv KVStore, changes kvChanges) error {	×
302	// Exit early if there are no changes to apply.	×
303	if kv == nil \|\| changes == nil {	×
304	return nil	×
305	}	×
306
307	// Check if any range pair needs to be deleted.
308	if changes.deleteKVKey != nil {	×
309	del, err := a.serializeUint64(*changes.deleteKVKey)	×
310	if err != nil {	×
311	return err	×
312	}	×
313
314	if err := kv.Delete(del); err != nil {	×
315	return err	×
316	}	×
317	}
318
319	start, err := a.serializeUint64(changes.key)	×
320	if err != nil {	×
321	return err	×
322	}	×
323
324	end, err := a.serializeUint64(changes.value)	×
325	if err != nil {	×
326	return err	×
327	}	×
328
329	return kv.Put(start, end)	×
330	}
331
332	// applyArrayChanges applies the given arrayChanges to the in-memory RangeIndex
333	// itself. This should only be done once the persisted kv store changes have
334	// already been applied.
335	func (a RangeIndex) applyArrayChanges(changes arrayChanges) {	×
336	if changes == nil {	×
337	return	×
338	}	×
339
340	if changes.indexToDelete != nil {	×
341	a.set = append(	×
342	a.set[:*changes.indexToDelete],	×
343	a.set[*changes.indexToDelete+1:]...,	×
344	)	×
345	}	×
346
347	if changes.newIndex != nil {	×
348	switch {	×
349	case *changes.newIndex == 0:	×
350	a.set = append([]rangeItem{{	×
351	start: changes.start,	×
352	end: changes.end,	×
353	}}, a.set...)	×
354
355	case *changes.newIndex == len(a.set):	×
356	a.set = append(a.set, rangeItem{	×
357	start: changes.start,	×
358	end: changes.end,	×
359	})	×
360
361	default:	×
362	a.set = append(	×
363	a.set[:*changes.newIndex+1],	×
364	a.set[*changes.newIndex:]...,	×
365	)	×
366	a.set[*changes.newIndex] = rangeItem{	×
367	start: changes.start,	×
368	end: changes.end,	×
369	}	×
370	}
371
372	return	×
373	}
374
375	if changes.indexToEdit != nil {	×
376	a.set[*changes.indexToEdit] = rangeItem{	×
377	start: changes.start,	×
378	end: changes.end,	×
379	}	×
380	}	×
381	}
382
383	// arrayChanges encompasses the diff to apply to the sorted rangeItem array
384	// representation of a range index. Such a diff will either include adding a
385	// new range or editing an existing range. If an existing range is edited, then
386	// the diff might also include deleting an index (this will be the case if the
387	// editing of the one range results in the merge of another range).
388	type arrayChanges struct {
389	start uint64
390	end uint64
391
392	// newIndex, if set, is the index of the in-memory range array where a
393	// new range, [start:end], should be added. newIndex should never be
394	// set at the same time as indexToEdit or indexToDelete.
395	newIndex *int
396
397	// indexToDelete, if set, is the index of the sorted rangeItem array
398	// that should be deleted. This should be applied before reading the
399	// index value of indexToEdit. This should not be set at the same time
400	// as newIndex.
401	indexToDelete *int
402
403	// indexToEdit is the index of the in-memory range array that should be
404	// edited. The range at this index will be changed to [start:end]. This
405	// should only be read after indexToDelete index has been deleted.
406	indexToEdit *int
407	}
408
409	// kvChanges encompasses the diff to apply to a KV-store representation of a
410	// range index. A kv-store diff for the addition of a single number to the range
411	// index will include either a brand new key-value pair or the altering of the
412	// value of an existing key. Optionally, the diff may also include the deletion
413	// of an existing key. A deletion will be required if the addition of the new
414	// number results in the merge of two ranges.
415	type kvChanges struct {
416	key uint64
417	value uint64
418
419	// deleteKVKey, if set, is the key of the kv store representation that
420	// should be deleted.
421	deleteKVKey *uint64
422	}
423
424	// getChanges will calculate and return the changes that need to be applied to
425	// both the sorted-rangeItem-array representation and the key-value store
426	// representation of the range index.
427	func (a RangeIndex) getChanges(n uint64) (arrayChanges, *kvChanges) {	×
428	// If the set is empty then a new range item is added.	×
429	if len(a.set) == 0 {	×
430	// For the array representation, a new range [n:n] is added to	×
431	// the first index of the array.	×
432	firstIndex := 0	×
433	ac := &arrayChanges{	×
434	newIndex: &firstIndex,	×
435	start: n,	×
436	end: n,	×
437	}	×
438		×
439	// For the KV representation, a new [n:n] pair is added.	×
440	kvc := &kvChanges{	×
441	key: n,	×
442	value: n,	×
443	}	×
444		×
445	return ac, kvc	×
446	}	×
447
448	// Find the index of the lower bound range to the new number.
449	indexOfRangeBelow, alreadyCovered := a.lowerBoundIndex(n)	×
450		×
451	switch {	×
452	// The new number is already covered by the range index. No changes are
453	// required.
454	case alreadyCovered:	×
455	return nil, nil	×
456
457	// No lower bound index exists.
458	case indexOfRangeBelow < 0:	×
459	// Check if the very first range can be merged into this new	×
460	// one.	×
461	if n+1 == a.set[0].start {	×
462	// If so, the two ranges can be merged and so the start	×
463	// value of the range is n and the end value is the end	×
464	// of the existing first range.	×
465	start := n	×
466	end := a.set[0].end	×
467		×
468	// For the array representation, we can just edit the	×
469	// first entry of the array	×
470	editIndex := 0	×
471	ac := &arrayChanges{	×
472	indexToEdit: &editIndex,	×
473	start: start,	×
474	end: end,	×
475	}	×
476		×
477	// For the KV store representation, we add a new kv pair	×
478	// and delete the range with the key equal to the start	×
479	// value of the range we are merging.	×
480	kvKeyToDelete := a.set[0].start	×
481	kvc := &kvChanges{	×
482	key: start,	×
483	value: end,	×
484	deleteKVKey: &kvKeyToDelete,	×
485	}	×
486		×
487	return ac, kvc	×
488	}	×
489
490	// Otherwise, we add a new index.
491
492	// For the array representation, a new range [n:n] is added to
493	// the first index of the array.
494	newIndex := 0	×
495	ac := &arrayChanges{	×
496	newIndex: &newIndex,	×
497	start: n,	×
498	end: n,	×
499	}	×
500		×
501	// For the KV representation, a new [n:n] pair is added.	×
502	kvc := &kvChanges{	×
503	key: n,	×
504	value: n,	×
505	}	×
506		×
507	return ac, kvc	×
508
509	// A lower range does exist, and it can be extended to include this new
510	// number.
511	case a.set[indexOfRangeBelow].end+1 == n:	×
512	start := a.set[indexOfRangeBelow].start	×
513	end := n	×
514	indexToChange := indexOfRangeBelow	×
515		×
516	// If there are no intervals above this one or if there are, but	×
517	// they can't be merged into this one then we just need to edit	×
518	// this interval.	×
519	if indexOfRangeBelow == len(a.set)-1 \|\|	×
520	a.set[indexOfRangeBelow+1].start != n+1 {	×
521		×
522	// For the array representation, we just edit the index.	×
523	ac := &arrayChanges{	×
524	indexToEdit: &indexToChange,	×
525	start: start,	×
526	end: end,	×
527	}	×
528		×
529	// For the key-value representation, we just overwrite	×
530	// the end value at the existing start key.	×
531	kvc := &kvChanges{	×
532	key: start,	×
533	value: end,	×
534	}	×
535		×
536	return ac, kvc	×
537	}	×
538
539	// There is a range above this one that we need to merge into
540	// this one.
541	delIndex := indexOfRangeBelow + 1	×
542	end = a.set[delIndex].end	×
543		×
544	// For the array representation, we delete the range above this	×
545	// one and edit this range to include the end value of the range	×
546	// above.	×
547	ac := &arrayChanges{	×
548	indexToDelete: &delIndex,	×
549	indexToEdit: &indexToChange,	×
550	start: start,	×
551	end: end,	×
552	}	×
553		×
554	// For the kv representation, we tweak the end value of an	×
555	// existing key and delete the key of the range we are deleting.	×
556	deleteKey := a.set[delIndex].start	×
557	kvc := &kvChanges{	×
558	key: start,	×
559	value: end,	×
560	deleteKVKey: &deleteKey,	×
561	}	×
562		×
563	return ac, kvc	×
564
565	// A lower range does exist, but it can't be extended to include this
566	// new number, and so we need to add a new range after the lower bound
567	// range.
568	default:	×
569	newIndex := indexOfRangeBelow + 1	×
570		×
571	// If there are no ranges above this new one or if there are,	×
572	// but they can't be merged into this new one, then we can just	×
573	// add the new one as is.	×
574	if newIndex == len(a.set) \|\| a.set[newIndex].start != n+1 {	×
575	ac := &arrayChanges{	×
576	newIndex: &newIndex,	×
577	start: n,	×
578	end: n,	×
579	}	×
580		×
581	kvc := &kvChanges{	×
582	key: n,	×
583	value: n,	×
584	}	×
585		×
586	return ac, kvc	×
587	}	×
588
589	// Else, we merge the above index.
590	start := n	×
591	end := a.set[newIndex].end	×
592	toEdit := newIndex	×
593		×
594	// For the array representation, we edit the range above to	×
595	// include the new start value.	×
596	ac := &arrayChanges{	×
597	indexToEdit: &toEdit,	×
598	start: start,	×
599	end: end,	×
600	}	×
601		×
602	// For the kv representation, we insert the new start-end key	×
603	// value pair and delete the key using the old start value.	×
604	delKey := a.set[newIndex].start	×
605	kvc := &kvChanges{	×
606	key: start,	×
607	value: end,	×
608	deleteKVKey: &delKey,	×
609	}	×
610		×
611	return ac, kvc	×
612	}
613	}
614
615	func defaultSerializeUint64(i uint64) ([]byte, error) {	×
616	var b [8]byte	×
617	byteOrder.PutUint64(b[:], i)	×
618	return b[:], nil	×
619	}	×

lightningnetwork / lnd / 12583319996

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous