12187193240

Committed 05 Dec 2024 08:04PM UTC coverage: 58.933% (-0.02%) from 58.951%

Build # 12187193240

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #9333 from guggero/aux-traffic-shaper-refactor

[custom channels]: refactor AuxTrafficManager to be used for forwarding as well

Run Details

30 of 81 new or added lines in 7 files covered. (37.04%)

57 existing lines in 14 files now uncovered.

133458 of 226459 relevant lines covered (58.93%)

19547.88 hits per line

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

50.9

/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.
20	func WithSerializeUint64Fn(fn func(uint64) ([]byte, error)) RangeIndexOption {	10✔
21	return func(index *RangeIndex) {	20✔
22	index.serializeUint64 = fn	10✔
23	}	10✔
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) {	18✔
47		18✔
48	index := &RangeIndex{	18✔
49	serializeUint64: defaultSerializeUint64,	18✔
50	set: make([]rangeItem, 0),	18✔
51	}	18✔
52		18✔
53	// Apply any functional options.	18✔
54	for _, o := range opts {	28✔
55	o(index)	10✔
56	}	10✔
57
58	for s, e := range ranges {	30✔
59	if err := index.addRange(s, e); err != nil {	12✔
60	return nil, err	×
61	}	×
62	}
63
64	return index, nil	18✔
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 {	12✔
71	// Check that the given range is valid.	12✔
72	if start > end {	12✔
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 {	12✔
79	if a < b {	×
80	return a	×
81	}	×
82
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 {	12✔
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	12✔
98	for _, x := range a.set {	14✔
99	// If the new start value can't extend the current ranges end	2✔
100	// value, then the two cannot be merged. The range is added to	2✔
101	// the group of ranges that fall before the new range.	2✔
102	if x.end+1 < start {	4✔
103	before = append(before, x)	2✔
104	continue	2✔
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.
UNCOV 111	if end+1 < x.start {	×
UNCOV 112	after = append(after, x)	×
UNCOV 113	continue	×
114	}
115
116	// Otherwise, there is an overlap and so the two can be merged.
117	start = min(start, x.start)	×
118	end = max(end, x.end)	×
119	}
120
121	// Re-construct the range index set.
122	a.set = append(append(before, rangeItem{	12✔
123	start: start,	12✔
124	end: end,	12✔
125	}), after...)	12✔
126		12✔
127	return nil	12✔
128	}
129
130	// IsInIndex returns true if the given number is in the range set.
131	func (a *RangeIndex) IsInIndex(n uint64) bool {	20✔
132	a.mu.Lock()	20✔
133	defer a.mu.Unlock()	20✔
134		20✔
135	_, isCovered := a.lowerBoundIndex(n)	20✔
136		20✔
137	return isCovered	20✔
138	}	20✔
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	×
148	}	×
149
150	return numItems	×
151	}
152
153	// MaxHeight returns the highest number covered in the range.
154	func (a *RangeIndex) MaxHeight() uint64 {	×
155	a.mu.Lock()	×
156	defer a.mu.Unlock()	×
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 {	8✔
167	a.mu.Lock()	8✔
168	defer a.mu.Unlock()	8✔
169		8✔
170	cp := make(map[uint64]uint64, len(a.set))	8✔
171	for _, item := range a.set {	17✔
172	cp[item.start] = item.end	9✔
173	}	9✔
174
175	return cp	8✔
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) {	27✔
189	// If the set is empty, then there is no such index and the value	27✔
190	// definitely is not in the set.	27✔
191	if len(a.set) == 0 {	27✔
192	return -1, false	×
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	27✔
199	lastRange := a.set[lastIndex]	27✔
200	if lastRange.start <= n {	48✔
201	return lastIndex, lastRange.end >= n	21✔
202	}	21✔
203
204	// Otherwise, do a binary search to find the index of interest.
205	var (	6✔
206	low = 0	6✔
207	high = len(a.set) - 1	6✔
208	rangeIndex = -1	6✔
209	)	6✔
210	for {	12✔
211	mid := (low + high) / 2	6✔
212	currentRange := a.set[mid]	6✔
213		6✔
214	switch {	6✔
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:	4✔
221	// If the range already includes the given height, we	4✔
222	// can stop searching now.	4✔
223	if currentRange.end >= n {	8✔
224	return mid, true	4✔
225	}	4✔
226
227	// If the start of the range is smaller than n, we can
228	// store this as the new best index to return.
229	rangeIndex = mid	×
230		×
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:	2✔
246	// If the height is equal to the start value of the	2✔
247	// current range that mid is pointing to, then the	2✔
248	// height is already covered.	2✔
249	return mid, true	2✔
250	}
251
252	// Exit if we have checked all the ranges.
253	if low == high {	×
254	break	×
255	}
256	}
257
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 {	15✔
276	a.mu.Lock()	15✔
277	defer a.mu.Unlock()	15✔
278		15✔
279	// Compute the changes that will need to be applied to both the sorted	15✔
280	// rangeItem array representation and the key-value store representation	15✔
281	// of the range index.	15✔
282	arrayChanges, kvStoreChanges := a.getChanges(newHeight)	15✔
283		15✔
284	// First attempt to apply the KV store changes. Only if this succeeds	15✔
285	// will we apply the changes to our in-memory range index structure.	15✔
286	err := a.applyKVChanges(kv, kvStoreChanges)	15✔
287	if err != nil {	15✔
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)	15✔
294		15✔
295	return nil	15✔
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 {	15✔
302	// Exit early if there are no changes to apply.	15✔
303	if kv == nil \|\| changes == nil {	30✔
304	return nil	15✔
305	}	15✔
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	}	×
317	}
318
319	start, err := a.serializeUint64(changes.key)	×
320	if err != nil {	×
321	return err	×
322	}	×
323
324	end, err := a.serializeUint64(changes.value)	×
325	if err != nil {	×
326	return err	×
327	}	×
328
329	return kv.Put(start, end)	×
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) {	15✔
336	if changes == nil {	15✔
337	return	×
338	}	×
339
340	if changes.indexToDelete != nil {	15✔
341	a.set = append(	×
342	a.set[:*changes.indexToDelete],	×
343	a.set[*changes.indexToDelete+1:]...,	×
344	)	×
345	}	×
346
347	if changes.newIndex != nil {	24✔
348	switch {	9✔
349	case *changes.newIndex == 0:	8✔
350	a.set = append([]rangeItem{{	8✔
351	start: changes.start,	8✔
352	end: changes.end,	8✔
353	}}, a.set...)	8✔
354
355	case *changes.newIndex == len(a.set):	1✔
356	a.set = append(a.set, rangeItem{	1✔
357	start: changes.start,	1✔
358	end: changes.end,	1✔
359	})	1✔
360
361	default:	×
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	9✔
373	}
374
375	if changes.indexToEdit != nil {	12✔
376	a.set[*changes.indexToEdit] = rangeItem{	6✔
377	start: changes.start,	6✔
378	end: changes.end,	6✔
379	}	6✔
380	}	6✔
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) {	15✔
428	// If the set is empty then a new range item is added.	15✔
429	if len(a.set) == 0 {	23✔
430	// For the array representation, a new range [n:n] is added to	8✔
431	// the first index of the array.	8✔
432	firstIndex := 0	8✔
433	ac := &arrayChanges{	8✔
434	newIndex: &firstIndex,	8✔
435	start: n,	8✔
436	end: n,	8✔
437	}	8✔
438		8✔
439	// For the KV representation, a new [n:n] pair is added.	8✔
440	kvc := &kvChanges{	8✔
441	key: n,	8✔
442	value: n,	8✔
443	}	8✔
444		8✔
445	return ac, kvc	8✔
446	}	8✔
447
448	// Find the index of the lower bound range to the new number.
449	indexOfRangeBelow, alreadyCovered := a.lowerBoundIndex(n)	7✔
450		7✔
451	switch {	7✔
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
493	// the first index of the array.
494	newIndex := 0	×
495	ac := &arrayChanges{	×
496	newIndex: &newIndex,	×
497	start: n,	×
498	end: n,	×
499	}	×
500		×
501	// For the KV representation, a new [n:n] pair is added.	×
502	kvc := &kvChanges{	×
503	key: n,	×
504	value: n,	×
505	}	×
506		×
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:	6✔
512	start := a.set[indexOfRangeBelow].start	6✔
513	end := n	6✔
514	indexToChange := indexOfRangeBelow	6✔
515		6✔
516	// If there are no intervals above this one or if there are, but	6✔
517	// they can't be merged into this one then we just need to edit	6✔
518	// this interval.	6✔
519	if indexOfRangeBelow == len(a.set)-1 \|\|	6✔
520	a.set[indexOfRangeBelow+1].start != n+1 {	12✔
521		6✔
522	// For the array representation, we just edit the index.	6✔
523	ac := &arrayChanges{	6✔
524	indexToEdit: &indexToChange,	6✔
525	start: start,	6✔
526	end: end,	6✔
527	}	6✔
528		6✔
529	// For the key-value representation, we just overwrite	6✔
530	// the end value at the existing start key.	6✔
531	kvc := &kvChanges{	6✔
532	key: start,	6✔
533	value: end,	6✔
534	}	6✔
535		6✔
536	return ac, kvc	6✔
537	}	6✔
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,	×
550	start: start,	×
551	end: end,	×
552	}	×
553		×
554	// For the kv representation, we tweak the end value of an	×
555	// existing key and delete the key of the range we are deleting.	×
556	deleteKey := a.set[delIndex].start	×
557	kvc := &kvChanges{	×
558	key: start,	×
559	value: end,	×
560	deleteKVKey: &deleteKey,	×
561	}	×
562		×
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:	1✔
569	newIndex := indexOfRangeBelow + 1	1✔
570		1✔
571	// If there are no ranges above this new one or if there are,	1✔
572	// but they can't be merged into this new one, then we can just	1✔
573	// add the new one as is.	1✔
574	if newIndex == len(a.set) \|\| a.set[newIndex].start != n+1 {	2✔
575	ac := &arrayChanges{	1✔
576	newIndex: &newIndex,	1✔
577	start: n,	1✔
578	end: n,	1✔
579	}	1✔
580		1✔
581	kvc := &kvChanges{	1✔
582	key: n,	1✔
583	value: n,	1✔
584	}	1✔
585		1✔
586	return ac, kvc	1✔
587	}	1✔
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 / 12187193240

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