12313073348

Committed 13 Dec 2024 09:30AM UTC coverage: 58.666% (+1.2%) from 57.486%

Build # 12313073348

Build Type

Pull #9344

github

Committed by

ellemouton

Commit Message

htlcswitch+go.mod: use updated fn.ContextGuard

This commit updates the fn dep to the version containing the updates to
the ContextGuard implementation. Only the htlcswitch/link uses the guard
at the moment so this is updated to make use of the new implementation.

Pull Request Pull Request #9344: htlcswitch+go.mod: use updated fn.ContextGuard

Run Details

101 of 117 new or added lines in 4 files covered. (86.32%)

29 existing lines in 9 files now uncovered.

134589 of 229415 relevant lines covered (58.67%)

19278.57 hits per line

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

96.12

/watchtower/wtdb/range_index.go

package wtdb

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 wtdb
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 {	96✔
21	return func(index *RangeIndex) {	192✔
22	index.serializeUint64 = fn	96✔
23	}	96✔
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) {	107✔
47		107✔
48	index := &RangeIndex{	107✔
49	serializeUint64: defaultSerializeUint64,	107✔
50	set: make([]rangeItem, 0),	107✔
51	}	107✔
52		107✔
53	// Apply any functional options.	107✔
54	for _, o := range opts {	203✔
55	o(index)	96✔
56	}	96✔
57
58	for s, e := range ranges {	134✔
59	if err := index.addRange(s, e); err != nil {	28✔
60	return nil, err	1✔
61	}	1✔
62	}
63
64	return index, nil	106✔
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 {	27✔
71	// Check that the given range is valid.	27✔
72	if start > end {	28✔
73	return fmt.Errorf("invalid range. Start height %d is larger "+	1✔
74	"than end height %d", start, end)	1✔
75	}	1✔
76
77	// min is a helper closure that will return the minimum of two uint64s.
78	min := func(a, b uint64) uint64 {	30✔
79	if a < b {	4✔
UNCOV 80	return a	×
UNCOV 81	}	×
82
83	return b	4✔
84	}
85
86	// max is a helper closure that will return the maximum of two uint64s.
87	max := func(a, b uint64) uint64 {	30✔
88	if a > b {	8✔
89	return a	4✔
90	}	4✔
91
UNCOV 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	26✔
98	for _, x := range a.set {	40✔
99	// If the new start value can't extend the current ranges end	14✔
100	// value, then the two cannot be merged. The range is added to	14✔
101	// the group of ranges that fall before the new range.	14✔
102	if x.end+1 < start {	22✔
103	before = append(before, x)	8✔
104	continue	8✔
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 {	10✔
112	after = append(after, x)	3✔
113	continue	3✔
114	}
115
116	// Otherwise, there is an overlap and so the two can be merged.
117	start = min(start, x.start)	4✔
118	end = max(end, x.end)	4✔
119	}
120
121	// Re-construct the range index set.
122	a.set = append(append(before, rangeItem{	26✔
123	start: start,	26✔
124	end: end,	26✔
125	}), after...)	26✔
126		26✔
127	return nil	26✔
128	}
129
130	// IsInIndex returns true if the given number is in the range set.
131	func (a *RangeIndex) IsInIndex(n uint64) bool {	21✔
132	a.mu.Lock()	21✔
133	defer a.mu.Unlock()	21✔
134		21✔
135	_, isCovered := a.lowerBoundIndex(n)	21✔
136		21✔
137	return isCovered	21✔
138	}	21✔
139
140	// NumInSet returns the number of items covered by the range set.
141	func (a *RangeIndex) NumInSet() uint64 {	20✔
142	a.mu.Lock()	20✔
143	defer a.mu.Unlock()	20✔
144		20✔
145	var numItems uint64	20✔
146	for _, r := range a.set {	40✔
147	numItems += r.end - r.start + 1	20✔
148	}	20✔
149
150	return numItems	20✔
151	}
152
153	// MaxHeight returns the highest number covered in the range.
154	func (a *RangeIndex) MaxHeight() uint64 {	6✔
155	a.mu.Lock()	6✔
156	defer a.mu.Unlock()	6✔
157		6✔
158	if len(a.set) == 0 {	6✔
159	return 0	×
160	}	×
161
162	return a.set[len(a.set)-1].end	6✔
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 {	17✔
167	a.mu.Lock()	17✔
168	defer a.mu.Unlock()	17✔
169		17✔
170	cp := make(map[uint64]uint64, len(a.set))	17✔
171	for _, item := range a.set {	36✔
172	cp[item.start] = item.end	19✔
173	}	19✔
174
175	return cp	17✔
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) {	10,448✔
189	// If the set is empty, then there is no such index and the value	10,448✔
190	// definitely is not in the set.	10,448✔
191	if len(a.set) == 0 {	10,450✔
192	return -1, false	2✔
193	}	2✔
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	10,446✔
199	lastRange := a.set[lastIndex]	10,446✔
200	if lastRange.start <= n {	10,891✔
201	return lastIndex, lastRange.end >= n	445✔
202	}	445✔
203
204	// Otherwise, do a binary search to find the index of interest.
205	var (	10,001✔
206	low = 0	10,001✔
207	high = len(a.set) - 1	10,001✔
208	rangeIndex = -1	10,001✔
209	)	10,001✔
210	for {	134,542✔
211	mid := (low + high) / 2	124,541✔
212	currentRange := a.set[mid]	124,541✔
213		124,541✔
214	switch {	124,541✔
215	case currentRange.start > n:	60,732✔
216	// If the start of the range is greater than n, we can	60,732✔
217	// completely cut out that entire part of the array.	60,732✔
218	high = mid	60,732✔
219
220	case currentRange.start < n:	63,808✔
221	// If the range already includes the given height, we	63,808✔
222	// can stop searching now.	63,808✔
223	if currentRange.end >= n {	63,809✔
224	return mid, true	1✔
225	}	1✔
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	63,807✔
230		63,807✔
231	// If low and mid are already equal, then increment low	63,807✔
232	// by 1. Exit if this means that low is now greater than	63,807✔
233	// high.	63,807✔
234	if low == mid {	73,794✔
235	low = mid + 1	9,987✔
236	if low > high {	9,987✔
237	return rangeIndex, false	×
238	}	×
239	} else {	53,820✔
240	low = mid	53,820✔
241	}	53,820✔
242
243	continue	63,807✔
244
245	default:	1✔
246	// If the height is equal to the start value of the	1✔
247	// current range that mid is pointing to, then the	1✔
248	// height is already covered.	1✔
249	return mid, true	1✔
250	}
251
252	// Exit if we have checked all the ranges.
253	if low == high {	70,731✔
254	break	9,999✔
255	}
256	}
257
258	return rangeIndex, false	9,999✔
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 {	10,517✔
276	a.mu.Lock()	10,517✔
277	defer a.mu.Unlock()	10,517✔
278		10,517✔
279	// Compute the changes that will need to be applied to both the sorted	10,517✔
280	// rangeItem array representation and the key-value store representation	10,517✔
281	// of the range index.	10,517✔
282	arrayChanges, kvStoreChanges := a.getChanges(newHeight)	10,517✔
283		10,517✔
284	// First attempt to apply the KV store changes. Only if this succeeds	10,517✔
285	// will we apply the changes to our in-memory range index structure.	10,517✔
286	err := a.applyKVChanges(kv, kvStoreChanges)	10,517✔
287	if err != nil {	10,518✔
288	return err	1✔
289	}	1✔
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)	10,516✔
294		10,516✔
295	return nil	10,516✔
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 {	10,517✔
302	// Exit early if there are no changes to apply.	10,517✔
303	if kv == nil \|\| changes == nil {	10,520✔
304	return nil	3✔
305	}	3✔
306
307	// Check if any range pair needs to be deleted.
308	if changes.deleteKVKey != nil {	15,513✔
309	del, err := a.serializeUint64(*changes.deleteKVKey)	4,999✔
310	if err != nil {	4,999✔
311	return err	×
312	}	×
313
314	if err := kv.Delete(del); err != nil {	4,999✔
315	return err	×
316	}	×
317	}
318
319	start, err := a.serializeUint64(changes.key)	10,514✔
320	if err != nil {	10,514✔
321	return err	×
322	}	×
323
324	end, err := a.serializeUint64(changes.value)	10,514✔
325	if err != nil {	10,514✔
326	return err	×
327	}	×
328
329	return kv.Put(start, end)	10,514✔
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) {	10,516✔
336	if changes == nil {	10,519✔
337	return	3✔
338	}	3✔
339
340	if changes.indexToDelete != nil {	13,831✔
341	a.set = append(	3,318✔
342	a.set[:*changes.indexToDelete],	3,318✔
343	a.set[*changes.indexToDelete+1:]...,	3,318✔
344	)	3,318✔
345	}	3,318✔
346
347	if changes.newIndex != nil {	13,924✔
348	switch {	3,411✔
349	case *changes.newIndex == 0:	101✔
350	a.set = append([]rangeItem{{	101✔
351	start: changes.start,	101✔
352	end: changes.end,	101✔
353	}}, a.set...)	101✔
354
355	case *changes.newIndex == len(a.set):	14✔
356	a.set = append(a.set, rangeItem{	14✔
357	start: changes.start,	14✔
358	end: changes.end,	14✔
359	})	14✔
360
361	default:	3,300✔
362	a.set = append(	3,300✔
363	a.set[:*changes.newIndex+1],	3,300✔
364	a.set[*changes.newIndex:]...,	3,300✔
365	)	3,300✔
366	a.set[*changes.newIndex] = rangeItem{	3,300✔
367	start: changes.start,	3,300✔
368	end: changes.end,	3,300✔
369	}	3,300✔
370	}
371
372	return	3,411✔
373	}
374
375	if changes.indexToEdit != nil {	14,212✔
376	a.set[*changes.indexToEdit] = rangeItem{	7,106✔
377	start: changes.start,	7,106✔
378	end: changes.end,	7,106✔
379	}	7,106✔
380	}	7,106✔
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) {	10,517✔
428	// If the set is empty then a new range item is added.	10,517✔
429	if len(a.set) == 0 {	10,611✔
430	// For the array representation, a new range [n:n] is added to	94✔
431	// the first index of the array.	94✔
432	firstIndex := 0	94✔
433	ac := &arrayChanges{	94✔
434	newIndex: &firstIndex,	94✔
435	start: n,	94✔
436	end: n,	94✔
437	}	94✔
438		94✔
439	// For the KV representation, a new [n:n] pair is added.	94✔
440	kvc := &kvChanges{	94✔
441	key: n,	94✔
442	value: n,	94✔
443	}	94✔
444		94✔
445	return ac, kvc	94✔
446	}	94✔
447
448	// Find the index of the lower bound range to the new number.
449	indexOfRangeBelow, alreadyCovered := a.lowerBoundIndex(n)	10,427✔
450		10,427✔
451	switch {	10,427✔
452	// The new number is already covered by the range index. No changes are
453	// required.
454	case alreadyCovered:	3✔
455	return nil, nil	3✔
456
457	// No lower bound index exists.
458	case indexOfRangeBelow < 0:	11✔
459	// Check if the very first range can be merged into this new	11✔
460	// one.	11✔
461	if n+1 == a.set[0].start {	14✔
462	// If so, the two ranges can be merged and so the start	3✔
463	// value of the range is n and the end value is the end	3✔
464	// of the existing first range.	3✔
465	start := n	3✔
466	end := a.set[0].end	3✔
467		3✔
468	// For the array representation, we can just edit the	3✔
469	// first entry of the array	3✔
470	editIndex := 0	3✔
471	ac := &arrayChanges{	3✔
472	indexToEdit: &editIndex,	3✔
473	start: start,	3✔
474	end: end,	3✔
475	}	3✔
476		3✔
477	// For the KV store representation, we add a new kv pair	3✔
478	// and delete the range with the key equal to the start	3✔
479	// value of the range we are merging.	3✔
480	kvKeyToDelete := a.set[0].start	3✔
481	kvc := &kvChanges{	3✔
482	key: start,	3✔
483	value: end,	3✔
484	deleteKVKey: &kvKeyToDelete,	3✔
485	}	3✔
486		3✔
487	return ac, kvc	3✔
488	}	3✔
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	8✔
495	ac := &arrayChanges{	8✔
496	newIndex: &newIndex,	8✔
497	start: n,	8✔
498	end: n,	8✔
499	}	8✔
500		8✔
501	// For the KV representation, a new [n:n] pair is added.	8✔
502	kvc := &kvChanges{	8✔
503	key: n,	8✔
504	value: n,	8✔
505	}	8✔
506		8✔
507	return ac, kvc	8✔
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:	5,425✔
512	start := a.set[indexOfRangeBelow].start	5,425✔
513	end := n	5,425✔
514	indexToChange := indexOfRangeBelow	5,425✔
515		5,425✔
516	// If there are no intervals above this one or if there are, but	5,425✔
517	// they can't be merged into this one then we just need to edit	5,425✔
518	// this interval.	5,425✔
519	if indexOfRangeBelow == len(a.set)-1 \|\|	5,425✔
520	a.set[indexOfRangeBelow+1].start != n+1 {	7,532✔
521		2,107✔
522	// For the array representation, we just edit the index.	2,107✔
523	ac := &arrayChanges{	2,107✔
524	indexToEdit: &indexToChange,	2,107✔
525	start: start,	2,107✔
526	end: end,	2,107✔
527	}	2,107✔
528		2,107✔
529	// For the key-value representation, we just overwrite	2,107✔
530	// the end value at the existing start key.	2,107✔
531	kvc := &kvChanges{	2,107✔
532	key: start,	2,107✔
533	value: end,	2,107✔
534	}	2,107✔
535		2,107✔
536	return ac, kvc	2,107✔
537	}	2,107✔
538
539	// There is a range above this one that we need to merge into
540	// this one.
541	delIndex := indexOfRangeBelow + 1	3,318✔
542	end = a.set[delIndex].end	3,318✔
543		3,318✔
544	// For the array representation, we delete the range above this	3,318✔
545	// one and edit this range to include the end value of the range	3,318✔
546	// above.	3,318✔
547	ac := &arrayChanges{	3,318✔
548	indexToDelete: &delIndex,	3,318✔
549	indexToEdit: &indexToChange,	3,318✔
550	start: start,	3,318✔
551	end: end,	3,318✔
552	}	3,318✔
553		3,318✔
554	// For the kv representation, we tweak the end value of an	3,318✔
555	// existing key and delete the key of the range we are deleting.	3,318✔
556	deleteKey := a.set[delIndex].start	3,318✔
557	kvc := &kvChanges{	3,318✔
558	key: start,	3,318✔
559	value: end,	3,318✔
560	deleteKVKey: &deleteKey,	3,318✔
561	}	3,318✔
562		3,318✔
563	return ac, kvc	3,318✔
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:	4,992✔
569	newIndex := indexOfRangeBelow + 1	4,992✔
570		4,992✔
571	// If there are no ranges above this new one or if there are,	4,992✔
572	// but they can't be merged into this new one, then we can just	4,992✔
573	// add the new one as is.	4,992✔
574	if newIndex == len(a.set) \|\| a.set[newIndex].start != n+1 {	8,306✔
575	ac := &arrayChanges{	3,314✔
576	newIndex: &newIndex,	3,314✔
577	start: n,	3,314✔
578	end: n,	3,314✔
579	}	3,314✔
580		3,314✔
581	kvc := &kvChanges{	3,314✔
582	key: n,	3,314✔
583	value: n,	3,314✔
584	}	3,314✔
585		3,314✔
586	return ac, kvc	3,314✔
587	}	3,314✔
588
589	// Else, we merge the above index.
590	start := n	1,678✔
591	end := a.set[newIndex].end	1,678✔
592	toEdit := newIndex	1,678✔
593		1,678✔
594	// For the array representation, we edit the range above to	1,678✔
595	// include the new start value.	1,678✔
596	ac := &arrayChanges{	1,678✔
597	indexToEdit: &toEdit,	1,678✔
598	start: start,	1,678✔
599	end: end,	1,678✔
600	}	1,678✔
601		1,678✔
602	// For the kv representation, we insert the new start-end key	1,678✔
603	// value pair and delete the key using the old start value.	1,678✔
604	delKey := a.set[newIndex].start	1,678✔
605	kvc := &kvChanges{	1,678✔
606	key: start,	1,678✔
607	value: end,	1,678✔
608	deleteKVKey: &delKey,	1,678✔
609	}	1,678✔
610		1,678✔
611	return ac, kvc	1,678✔
612	}
613	}
614
615	func defaultSerializeUint64(i uint64) ([]byte, error) {	25,026✔
616	var b [8]byte	25,026✔
617	byteOrder.PutUint64(b[:], i)	25,026✔
618	return b[:], nil	25,026✔
619	}	25,026✔

lightningnetwork / lnd / 12313073348

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