12430766295

Committed 20 Dec 2024 11:38AM UTC coverage: 52.607% (-6.1%) from 58.716%

Build # 12430766295

Build Type

Pull #9384

github

Committed by

ziggie1984

Commit Message

funding: refactor gossip msg code

We almost never need to create all messages at the same time
(ChanUpdate,ChanAnnouncement,Proof) so we split it up into own
functions.

Pull Request Pull Request #9384: Refactor gossip msg code

Run Details

224 of 279 new or added lines in 7 files covered. (80.29%)

27070 existing lines in 437 files now uncovered.

53540 of 101773 relevant lines covered (52.61%)

4.11 hits per line

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

45.22

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

lightningnetwork / lnd / 12430766295

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