13423774416

Committed 19 Feb 2025 10:39PM UTC coverage: 49.338% (-9.5%) from 58.794%

Build # 13423774416

Build Type

Pull #9484

github

Committed by

Abdulkbk

Commit Message

lnutils: add createdir util function

This utility function replaces repetitive logic patterns
throughout LND.

Pull Request Pull Request #9484: lnutils: add createDir util function

Run Details

0 of 13 new or added lines in 1 file covered. (0.0%)

27149 existing lines in 431 files now uncovered.

100732 of 204168 relevant lines covered (49.34%)

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

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

lightningnetwork / lnd / 13423774416

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