13558005087

Committed 27 Feb 2025 03:04AM UTC coverage: 58.834% (-0.001%) from 58.835%

Build # 13558005087

Build Type

Pull #8453

github

Committed by

Roasbeef

Commit Message

lnwallet/chancloser: increase test coverage of state machine

Pull Request Pull Request #8453: [4/4] - multi: integrate new rbf coop close FSM into the existing peer flow

Run Details

1079 of 1370 new or added lines in 23 files covered. (78.76%)

578 existing lines in 40 files now uncovered.

137063 of 232965 relevant lines covered (58.83%)

19205.84 hits per line

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

96.29

/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)
        }

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

lightningnetwork / lnd / 13558005087

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