13566028875

Committed 27 Feb 2025 12:09PM UTC coverage: 49.396% (-9.4%) from 58.748%

Build # 13566028875

Build Type

Pull #9555

github

Committed by

ellemouton

Commit Message

graph/db: populate the graph cache in Start instead of during construction

In this commit, we move the graph cache population logic out of the
ChannelGraph constructor and into its Start method instead.

Pull Request Pull Request #9555: graph: extract cache from CRUD [6]

Run Details

34 of 54 new or added lines in 4 files covered. (62.96%)

27464 existing lines in 436 files now uncovered.

101095 of 204664 relevant lines covered (49.4%)

1.54 hits per line

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

0.0

/watchtower/wtdb/migration4/range_index.go

package migration4

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 migration4
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.
UNCOV 20	func WithSerializeUint64Fn(fn func(uint64) ([]byte, error)) RangeIndexOption {	×
UNCOV 21	return func(index *RangeIndex) {	×
UNCOV 22	index.serializeUint64 = fn	×
UNCOV 23	}	×
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,
UNCOV 46	opts ...RangeIndexOption) (*RangeIndex, error) {	×
UNCOV 47		×
UNCOV 48	index := &RangeIndex{	×
UNCOV 49	serializeUint64: defaultSerializeUint64,	×
UNCOV 50	set: make([]rangeItem, 0),	×
UNCOV 51	}	×
UNCOV 52		×
UNCOV 53	// Apply any functional options.	×
UNCOV 54	for _, o := range opts {	×
UNCOV 55	o(index)	×
UNCOV 56	}	×
57
UNCOV 58	for s, e := range ranges {	×
UNCOV 59	if err := index.addRange(s, e); err != nil {	×
60	return nil, err	×
61	}	×
62	}
63
UNCOV 64	return index, nil	×
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.
UNCOV 70	func (a *RangeIndex) addRange(start, end uint64) error {	×
UNCOV 71	// Check that the given range is valid.	×
UNCOV 72	if start > end {	×
73	return fmt.Errorf("invalid range. Start height %d is larger "+	×
74	"than end height %d", start, end)	×
75	}	×
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.
UNCOV 79	var before, after []rangeItem	×
UNCOV 80	for _, x := range a.set {	×
UNCOV 81	// If the new start value can't extend the current ranges end	×
UNCOV 82	// value, then the two cannot be merged. The range is added to	×
UNCOV 83	// the group of ranges that fall before the new range.	×
UNCOV 84	if x.end+1 < start {	×
UNCOV 85	before = append(before, x)	×
UNCOV 86	continue	×
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 {	×
94	after = append(after, x)	×
95	continue	×
96	}
97
98	// Otherwise, there is an overlap and so the two can be merged.
99	start = min(start, x.start)	×
100	end = max(end, x.end)	×
101	}
102
103	// Re-construct the range index set.
UNCOV 104	a.set = append(append(before, rangeItem{	×
UNCOV 105	start: start,	×
UNCOV 106	end: end,	×
UNCOV 107	}), after...)	×
UNCOV 108		×
UNCOV 109	return nil	×
110	}
111
112	// IsInIndex returns true if the given number is in the range set.
UNCOV 113	func (a *RangeIndex) IsInIndex(n uint64) bool {	×
UNCOV 114	a.mu.Lock()	×
UNCOV 115	defer a.mu.Unlock()	×
UNCOV 116		×
UNCOV 117	_, isCovered := a.lowerBoundIndex(n)	×
UNCOV 118		×
UNCOV 119	return isCovered	×
UNCOV 120	}	×
121
122	// NumInSet returns the number of items covered by the range set.
123	func (a *RangeIndex) NumInSet() uint64 {	×
124	a.mu.Lock()	×
125	defer a.mu.Unlock()	×
126		×
127	var numItems uint64	×
128	for _, r := range a.set {	×
129	numItems += r.end - r.start + 1	×
130	}	×
131
132	return numItems	×
133	}
134
135	// MaxHeight returns the highest number covered in the range.
136	func (a *RangeIndex) MaxHeight() uint64 {	×
137	a.mu.Lock()	×
138	defer a.mu.Unlock()	×
139		×
140	if len(a.set) == 0 {	×
141	return 0	×
142	}	×
143
144	return a.set[len(a.set)-1].end	×
145	}
146
147	// GetAllRanges returns a copy of the range set in the form of a map.
UNCOV 148	func (a *RangeIndex) GetAllRanges() map[uint64]uint64 {	×
UNCOV 149	a.mu.Lock()	×
UNCOV 150	defer a.mu.Unlock()	×
UNCOV 151		×
UNCOV 152	cp := make(map[uint64]uint64, len(a.set))	×
UNCOV 153	for _, item := range a.set {	×
UNCOV 154	cp[item.start] = item.end	×
UNCOV 155	}	×
156
UNCOV 157	return cp	×
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).
UNCOV 170	func (a *RangeIndex) lowerBoundIndex(n uint64) (int, bool) {	×
UNCOV 171	// If the set is empty, then there is no such index and the value	×
UNCOV 172	// definitely is not in the set.	×
UNCOV 173	if len(a.set) == 0 {	×
174	return -1, false	×
175	}	×
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.
UNCOV 180	lastIndex := len(a.set) - 1	×
UNCOV 181	lastRange := a.set[lastIndex]	×
UNCOV 182	if lastRange.start <= n {	×
UNCOV 183	return lastIndex, lastRange.end >= n	×
UNCOV 184	}	×
185
186	// Otherwise, do a binary search to find the index of interest.
UNCOV 187	var (	×
UNCOV 188	low = 0	×
UNCOV 189	high = len(a.set) - 1	×
UNCOV 190	rangeIndex = -1	×
UNCOV 191	)	×
UNCOV 192	for {	×
UNCOV 193	mid := (low + high) / 2	×
UNCOV 194	currentRange := a.set[mid]	×
UNCOV 195		×
UNCOV 196	switch {	×
197	case currentRange.start > n:	×
198	// If the start of the range is greater than n, we can	×
199	// completely cut out that entire part of the array.	×
200	high = mid	×
201
UNCOV 202	case currentRange.start < n:	×
UNCOV 203	// If the range already includes the given height, we	×
UNCOV 204	// can stop searching now.	×
UNCOV 205	if currentRange.end >= n {	×
UNCOV 206	return mid, true	×
UNCOV 207	}	×
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	×
212		×
213	// If low and mid are already equal, then increment low	×
214	// by 1. Exit if this means that low is now greater than	×
215	// high.	×
216	if low == mid {	×
217	low = mid + 1	×
218	if low > high {	×
219	return rangeIndex, false	×
220	}	×
221	} else {	×
222	low = mid	×
223	}	×
224
225	continue	×
226
UNCOV 227	default:	×
UNCOV 228	// If the height is equal to the start value of the	×
UNCOV 229	// current range that mid is pointing to, then the	×
UNCOV 230	// height is already covered.	×
UNCOV 231	return mid, true	×
232	}
233
234	// Exit if we have checked all the ranges.
235	if low == high {	×
236	break	×
237	}
238	}
239
240	return rangeIndex, false	×
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.
UNCOV 257	func (a *RangeIndex) Add(newHeight uint64, kv KVStore) error {	×
UNCOV 258	a.mu.Lock()	×
UNCOV 259	defer a.mu.Unlock()	×
UNCOV 260		×
UNCOV 261	// Compute the changes that will need to be applied to both the sorted	×
UNCOV 262	// rangeItem array representation and the key-value store representation	×
UNCOV 263	// of the range index.	×
UNCOV 264	arrayChanges, kvStoreChanges := a.getChanges(newHeight)	×
UNCOV 265		×
UNCOV 266	// First attempt to apply the KV store changes. Only if this succeeds	×
UNCOV 267	// will we apply the changes to our in-memory range index structure.	×
UNCOV 268	err := a.applyKVChanges(kv, kvStoreChanges)	×
UNCOV 269	if err != nil {	×
270	return err	×
271	}	×
272
273	// Since the DB changes were successful, we can now commit the
274	// changes to our in-memory representation of the range set.
UNCOV 275	a.applyArrayChanges(arrayChanges)	×
UNCOV 276		×
UNCOV 277	return nil	×
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.
UNCOV 283	func (a RangeIndex) applyKVChanges(kv KVStore, changes kvChanges) error {	×
UNCOV 284	// Exit early if there are no changes to apply.	×
UNCOV 285	if kv == nil \|\| changes == nil {	×
UNCOV 286	return nil	×
UNCOV 287	}	×
288
289	// Check if any range pair needs to be deleted.
290	if changes.deleteKVKey != nil {	×
291	del, err := a.serializeUint64(*changes.deleteKVKey)	×
292	if err != nil {	×
293	return err	×
294	}	×
295
296	if err := kv.Delete(del); err != nil {	×
297	return err	×
298	}	×
299	}
300
301	start, err := a.serializeUint64(changes.key)	×
302	if err != nil {	×
303	return err	×
304	}	×
305
306	end, err := a.serializeUint64(changes.value)	×
307	if err != nil {	×
308	return err	×
309	}	×
310
311	return kv.Put(start, end)	×
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.
UNCOV 317	func (a RangeIndex) applyArrayChanges(changes arrayChanges) {	×
UNCOV 318	if changes == nil {	×
319	return	×
320	}	×
321
UNCOV 322	if changes.indexToDelete != nil {	×
323	a.set = append(	×
324	a.set[:*changes.indexToDelete],	×
325	a.set[*changes.indexToDelete+1:]...,	×
326	)	×
327	}	×
328
UNCOV 329	if changes.newIndex != nil {	×
UNCOV 330	switch {	×
UNCOV 331	case *changes.newIndex == 0:	×
UNCOV 332	a.set = append([]rangeItem{{	×
UNCOV 333	start: changes.start,	×
UNCOV 334	end: changes.end,	×
UNCOV 335	}}, a.set...)	×
336
UNCOV 337	case *changes.newIndex == len(a.set):	×
UNCOV 338	a.set = append(a.set, rangeItem{	×
UNCOV 339	start: changes.start,	×
UNCOV 340	end: changes.end,	×
UNCOV 341	})	×
342
343	default:	×
344	a.set = append(	×
345	a.set[:*changes.newIndex+1],	×
346	a.set[*changes.newIndex:]...,	×
347	)	×
348	a.set[*changes.newIndex] = rangeItem{	×
349	start: changes.start,	×
350	end: changes.end,	×
351	}	×
352	}
353
UNCOV 354	return	×
355	}
356
UNCOV 357	if changes.indexToEdit != nil {	×
UNCOV 358	a.set[*changes.indexToEdit] = rangeItem{	×
UNCOV 359	start: changes.start,	×
UNCOV 360	end: changes.end,	×
UNCOV 361	}	×
UNCOV 362	}	×
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.
UNCOV 409	func (a RangeIndex) getChanges(n uint64) (arrayChanges, *kvChanges) {	×
UNCOV 410	// If the set is empty then a new range item is added.	×
UNCOV 411	if len(a.set) == 0 {	×
UNCOV 412	// For the array representation, a new range [n:n] is added to	×
UNCOV 413	// the first index of the array.	×
UNCOV 414	firstIndex := 0	×
UNCOV 415	ac := &arrayChanges{	×
UNCOV 416	newIndex: &firstIndex,	×
UNCOV 417	start: n,	×
UNCOV 418	end: n,	×
UNCOV 419	}	×
UNCOV 420		×
UNCOV 421	// For the KV representation, a new [n:n] pair is added.	×
UNCOV 422	kvc := &kvChanges{	×
UNCOV 423	key: n,	×
UNCOV 424	value: n,	×
UNCOV 425	}	×
UNCOV 426		×
UNCOV 427	return ac, kvc	×
UNCOV 428	}	×
429
430	// Find the index of the lower bound range to the new number.
UNCOV 431	indexOfRangeBelow, alreadyCovered := a.lowerBoundIndex(n)	×
UNCOV 432		×
UNCOV 433	switch {	×
434	// The new number is already covered by the range index. No changes are
435	// required.
436	case alreadyCovered:	×
437	return nil, nil	×
438
439	// No lower bound index exists.
440	case indexOfRangeBelow < 0:	×
441	// Check if the very first range can be merged into this new	×
442	// one.	×
443	if n+1 == a.set[0].start {	×
444	// If so, the two ranges can be merged and so the start	×
445	// value of the range is n and the end value is the end	×
446	// of the existing first range.	×
447	start := n	×
448	end := a.set[0].end	×
449		×
450	// For the array representation, we can just edit the	×
451	// first entry of the array	×
452	editIndex := 0	×
453	ac := &arrayChanges{	×
454	indexToEdit: &editIndex,	×
455	start: start,	×
456	end: end,	×
457	}	×
458		×
459	// For the KV store representation, we add a new kv pair	×
460	// and delete the range with the key equal to the start	×
461	// value of the range we are merging.	×
462	kvKeyToDelete := a.set[0].start	×
463	kvc := &kvChanges{	×
464	key: start,	×
465	value: end,	×
466	deleteKVKey: &kvKeyToDelete,	×
467	}	×
468		×
469	return ac, kvc	×
470	}	×
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	×
477	ac := &arrayChanges{	×
478	newIndex: &newIndex,	×
479	start: n,	×
480	end: n,	×
481	}	×
482		×
483	// For the KV representation, a new [n:n] pair is added.	×
484	kvc := &kvChanges{	×
485	key: n,	×
486	value: n,	×
487	}	×
488		×
489	return ac, kvc	×
490
491	// A lower range does exist, and it can be extended to include this new
492	// number.
UNCOV 493	case a.set[indexOfRangeBelow].end+1 == n:	×
UNCOV 494	start := a.set[indexOfRangeBelow].start	×
UNCOV 495	end := n	×
UNCOV 496	indexToChange := indexOfRangeBelow	×
UNCOV 497		×
UNCOV 498	// If there are no intervals above this one or if there are, but	×
UNCOV 499	// they can't be merged into this one then we just need to edit	×
UNCOV 500	// this interval.	×
UNCOV 501	if indexOfRangeBelow == len(a.set)-1 \|\|	×
UNCOV 502	a.set[indexOfRangeBelow+1].start != n+1 {	×
UNCOV 503		×
UNCOV 504	// For the array representation, we just edit the index.	×
UNCOV 505	ac := &arrayChanges{	×
UNCOV 506	indexToEdit: &indexToChange,	×
UNCOV 507	start: start,	×
UNCOV 508	end: end,	×
UNCOV 509	}	×
UNCOV 510		×
UNCOV 511	// For the key-value representation, we just overwrite	×
UNCOV 512	// the end value at the existing start key.	×
UNCOV 513	kvc := &kvChanges{	×
UNCOV 514	key: start,	×
UNCOV 515	value: end,	×
UNCOV 516	}	×
UNCOV 517		×
UNCOV 518	return ac, kvc	×
UNCOV 519	}	×
520
521	// There is a range above this one that we need to merge into
522	// this one.
523	delIndex := indexOfRangeBelow + 1	×
524	end = a.set[delIndex].end	×
525		×
526	// For the array representation, we delete the range above this	×
527	// one and edit this range to include the end value of the range	×
528	// above.	×
529	ac := &arrayChanges{	×
530	indexToDelete: &delIndex,	×
531	indexToEdit: &indexToChange,	×
532	start: start,	×
533	end: end,	×
534	}	×
535		×
536	// For the kv representation, we tweak the end value of an	×
537	// existing key and delete the key of the range we are deleting.	×
538	deleteKey := a.set[delIndex].start	×
539	kvc := &kvChanges{	×
540	key: start,	×
541	value: end,	×
542	deleteKVKey: &deleteKey,	×
543	}	×
544		×
545	return ac, kvc	×
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.
UNCOV 550	default:	×
UNCOV 551	newIndex := indexOfRangeBelow + 1	×
UNCOV 552		×
UNCOV 553	// If there are no ranges above this new one or if there are,	×
UNCOV 554	// but they can't be merged into this new one, then we can just	×
UNCOV 555	// add the new one as is.	×
UNCOV 556	if newIndex == len(a.set) \|\| a.set[newIndex].start != n+1 {	×
UNCOV 557	ac := &arrayChanges{	×
UNCOV 558	newIndex: &newIndex,	×
UNCOV 559	start: n,	×
UNCOV 560	end: n,	×
UNCOV 561	}	×
UNCOV 562		×
UNCOV 563	kvc := &kvChanges{	×
UNCOV 564	key: n,	×
UNCOV 565	value: n,	×
UNCOV 566	}	×
UNCOV 567		×
UNCOV 568	return ac, kvc	×
UNCOV 569	}	×
570
571	// Else, we merge the above index.
572	start := n	×
573	end := a.set[newIndex].end	×
574	toEdit := newIndex	×
575		×
576	// For the array representation, we edit the range above to	×
577	// include the new start value.	×
578	ac := &arrayChanges{	×
579	indexToEdit: &toEdit,	×
580	start: start,	×
581	end: end,	×
582	}	×
583		×
584	// For the kv representation, we insert the new start-end key	×
585	// value pair and delete the key using the old start value.	×
586	delKey := a.set[newIndex].start	×
587	kvc := &kvChanges{	×
588	key: start,	×
589	value: end,	×
590	deleteKVKey: &delKey,	×
591	}	×
592		×
593	return ac, kvc	×
594	}
595	}
596
597	func defaultSerializeUint64(i uint64) ([]byte, error) {	×
598	var b [8]byte	×
599	byteOrder.PutUint64(b[:], i)	×
600	return b[:], nil	×
601	}	×

lightningnetwork / lnd / 13566028875

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