15238419529

Committed 25 May 2025 01:32PM UTC coverage: 72.019% (-3.7%) from 75.704%

Build # 15238419529

Build Type

push

github

Committed by

HDT3213

Commit Message

update github actions go version

Run Details

1 of 1 new or added line in 1 file covered. (100.0%)

1149 existing lines in 29 files now uncovered.

8473 of 11765 relevant lines covered (72.02%)

0.8 hits per line

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

20.99

/datastruct/sortedset/sortedset.go

package sortedset

import (
        "strconv"

        "github.com/hdt3213/godis/lib/wildcard"
)

// SortedSet is a set which keys sorted by bound score
type SortedSet struct {
        dict     map[string]*Element
        skiplist *skiplist
}

// Make makes a new SortedSet
func Make() *SortedSet {
        return &SortedSet{
                dict:     make(map[string]*Element),
                skiplist: makeSkiplist(),
        }
}

// Add puts member into set,  and returns whether it has inserted new node
func (sortedSet *SortedSet) Add(member string, score float64) bool {
        element, ok := sortedSet.dict[member]
        sortedSet.dict[member] = &Element{
                Member: member,
                Score:  score,
        }
        if ok {
                if score != element.Score {
                        sortedSet.skiplist.remove(member, element.Score)
                        sortedSet.skiplist.insert(member, score)
                }
                return false
        }
        sortedSet.skiplist.insert(member, score)
        return true
}

// Len returns number of members in set
func (sortedSet *SortedSet) Len() int64 {
        return int64(len(sortedSet.dict))
}

// Get returns the given member
func (sortedSet *SortedSet) Get(member string) (element *Element, ok bool) {
        element, ok = sortedSet.dict[member]
        if !ok {
                return nil, false
        }
        return element, true
}

// Remove removes the given member from set
func (sortedSet *SortedSet) Remove(member string) bool {
        v, ok := sortedSet.dict[member]
        if ok {
                sortedSet.skiplist.remove(member, v.Score)
                delete(sortedSet.dict, member)
                return true
        }
        return false
}

// GetRank returns the rank of the given member, sort by ascending order, rank starts from 0
func (sortedSet *SortedSet) GetRank(member string, desc bool) (rank int64) {
        element, ok := sortedSet.dict[member]
        if !ok {
                return -1
        }
        r := sortedSet.skiplist.getRank(member, element.Score)
        if desc {
                r = sortedSet.skiplist.length - r
        } else {
                r--
        }
        return r
}

// ForEachByRank visits each member which rank within [start, stop), sort by ascending order, rank starts from 0
func (sortedSet *SortedSet) ForEachByRank(start int64, stop int64, desc bool, consumer func(element *Element) bool) {
        size := sortedSet.Len()
        if start < 0 || start >= size {
                panic("illegal start " + strconv.FormatInt(start, 10))
        }
        if stop < start || stop > size {
                panic("illegal end " + strconv.FormatInt(stop, 10))
        }

        // find start node
        var node *node
        if desc {
                node = sortedSet.skiplist.tail
                if start > 0 {
                        node = sortedSet.skiplist.getByRank(size - start)
                }
        } else {
                node = sortedSet.skiplist.header.level[0].forward
                if start > 0 {
                        node = sortedSet.skiplist.getByRank(start + 1)
                }
        }

        sliceSize := int(stop - start)
        for i := 0; i < sliceSize; i++ {
                if !consumer(&node.Element) {
                        break
                }
                if desc {
                        node = node.backward
                } else {
                        node = node.level[0].forward
                }
        }
}

// RangeByRank returns members which rank within [start, stop), sort by ascending order, rank starts from 0
func (sortedSet *SortedSet) RangeByRank(start int64, stop int64, desc bool) []*Element {
        sliceSize := int(stop - start)
        slice := make([]*Element, sliceSize)
        i := 0
        sortedSet.ForEachByRank(start, stop, desc, func(element *Element) bool {
                slice[i] = element
                i++
                return true
        })
        return slice
}

// RangeCount returns the number of  members which score or member within the given border
func (sortedSet *SortedSet) RangeCount(min Border, max Border) int64 {
        var i int64 = 0
        // ascending order
        sortedSet.ForEachByRank(0, sortedSet.Len(), false, func(element *Element) bool {
                gtMin := min.less(element) // greater than min
                if !gtMin {
                        // has not into range, continue foreach
                        return true
                }
                ltMax := max.greater(element) // less than max
                if !ltMax {
                        // break through score border, break foreach
                        return false
                }
                // gtMin && ltMax
                i++
                return true
        })
        return i
}

// ForEach visits members which score or member within the given border
func (sortedSet *SortedSet) ForEach(min Border, max Border, offset int64, limit int64, desc bool, consumer func(element *Element) bool) {
        // find start node
        var node *node
        if desc {
                node = sortedSet.skiplist.getLastInRange(min, max)
        } else {
                node = sortedSet.skiplist.getFirstInRange(min, max)
        }

        for node != nil && offset > 0 {
                if desc {
                        node = node.backward
                } else {
                        node = node.level[0].forward
                }
                offset--
        }

        // A negative limit returns all elements from the offset
        for i := 0; (i < int(limit) || limit < 0) && node != nil; i++ {
                if !consumer(&node.Element) {
                        break
                }
                if desc {
                        node = node.backward
                } else {
                        node = node.level[0].forward
                }
                if node == nil {
                        break
                }
                gtMin := min.less(&node.Element) // greater than min
                ltMax := max.greater(&node.Element)
                if !gtMin || !ltMax {
                        break // break through score border
                }
        }
}

// Range returns members which score or member within the given border
// param limit: <0 means no limit
func (sortedSet *SortedSet) Range(min Border, max Border, offset int64, limit int64, desc bool) []*Element {
        if limit == 0 || offset < 0 {
                return make([]*Element, 0)
        }
        slice := make([]*Element, 0)
        sortedSet.ForEach(min, max, offset, limit, desc, func(element *Element) bool {
                slice = append(slice, element)
                return true
        })
        return slice
}

// RemoveRange removes members which score or member within the given border
func (sortedSet *SortedSet) RemoveRange(min Border, max Border) int64 {
        removed := sortedSet.skiplist.RemoveRange(min, max, 0)
        for _, element := range removed {
                delete(sortedSet.dict, element.Member)
        }
        return int64(len(removed))
}

func (sortedSet *SortedSet) PopMin(count int) []*Element {
        first := sortedSet.skiplist.getFirstInRange(scoreNegativeInfBorder, scorePositiveInfBorder)
        if first == nil {
                return nil
        }
        border := &ScoreBorder{
                Value:   first.Score,
                Exclude: false,
        }
        removed := sortedSet.skiplist.RemoveRange(border, scorePositiveInfBorder, count)
        for _, element := range removed {
                delete(sortedSet.dict, element.Member)
        }
        return removed
}

// RemoveByRank removes member ranking within [start, stop)
// sort by ascending order and rank starts from 0
func (sortedSet *SortedSet) RemoveByRank(start int64, stop int64) int64 {
        removed := sortedSet.skiplist.RemoveRangeByRank(start+1, stop+1)
        for _, element := range removed {
                delete(sortedSet.dict, element.Member)
        }
        return int64(len(removed))
}

func (sortedSet *SortedSet) ZSetScan(cursor int, count int, pattern string) ([][]byte, int) {
        result := make([][]byte, 0)
        matchKey, err := wildcard.CompilePattern(pattern)
        if err != nil {
                return result, -1
        }
        for k := range sortedSet.dict {
                if pattern == "*" || matchKey.IsMatch(k) {
                        elem, exists := sortedSet.dict[k]
                        if !exists {
                                continue
                        }
                        result = append(result, []byte(k))
                        result = append(result, []byte(strconv.FormatFloat(elem.Score, 'f', 10, 64)))
                }
        }
        return result, 0
}

1	package sortedset
2
3	import (
4	"strconv"
5
6	"github.com/hdt3213/godis/lib/wildcard"
7	)
8
9	// SortedSet is a set which keys sorted by bound score
10	type SortedSet struct {
11	dict map[string]*Element
12	skiplist *skiplist
13	}
14
15	// Make makes a new SortedSet
16	func Make() *SortedSet {	1✔
17	return &SortedSet{	1✔
18	dict: make(map[string]*Element),	1✔
19	skiplist: makeSkiplist(),	1✔
20	}	1✔
21	}	1✔
22
23	// Add puts member into set, and returns whether it has inserted new node
24	func (sortedSet *SortedSet) Add(member string, score float64) bool {	1✔
25	element, ok := sortedSet.dict[member]	1✔
26	sortedSet.dict[member] = &Element{	1✔
27	Member: member,	1✔
28	Score: score,	1✔
29	}	1✔
30	if ok {	1✔
31	if score != element.Score {	×
32	sortedSet.skiplist.remove(member, element.Score)	×
33	sortedSet.skiplist.insert(member, score)	×
UNCOV 34	}	×
UNCOV 35	return false	×
36	}
37	sortedSet.skiplist.insert(member, score)	1✔
38	return true	1✔
39	}
40
41	// Len returns number of members in set
42	func (sortedSet *SortedSet) Len() int64 {	×
UNCOV 43	return int64(len(sortedSet.dict))	×
UNCOV 44	}	×
45
46	// Get returns the given member
47	func (sortedSet SortedSet) Get(member string) (element Element, ok bool) {	×
48	element, ok = sortedSet.dict[member]	×
49	if !ok {	×
50	return nil, false	×
UNCOV 51	}	×
UNCOV 52	return element, true	×
53	}
54
55	// Remove removes the given member from set
56	func (sortedSet *SortedSet) Remove(member string) bool {	×
57	v, ok := sortedSet.dict[member]	×
58	if ok {	×
59	sortedSet.skiplist.remove(member, v.Score)	×
60	delete(sortedSet.dict, member)	×
61	return true	×
UNCOV 62	}	×
UNCOV 63	return false	×
64	}
65
66	// GetRank returns the rank of the given member, sort by ascending order, rank starts from 0
67	func (sortedSet *SortedSet) GetRank(member string, desc bool) (rank int64) {	×
68	element, ok := sortedSet.dict[member]	×
69	if !ok {	×
70	return -1	×
71	}	×
72	r := sortedSet.skiplist.getRank(member, element.Score)	×
73	if desc {	×
74	r = sortedSet.skiplist.length - r	×
75	} else {	×
76	r--	×
UNCOV 77	}	×
UNCOV 78	return r	×
79	}
80
81	// ForEachByRank visits each member which rank within [start, stop), sort by ascending order, rank starts from 0
82	func (sortedSet SortedSet) ForEachByRank(start int64, stop int64, desc bool, consumer func(element Element) bool) {	×
83	size := sortedSet.Len()	×
UNCOV 84	if start < 0 \|\| start >= size {	×
85	panic("illegal start " + strconv.FormatInt(start, 10))	×
86	}
UNCOV 87	if stop < start \|\| stop > size {	×
UNCOV 88	panic("illegal end " + strconv.FormatInt(stop, 10))	×
89	}
90
91	// find start node
92	var node *node	×
93	if desc {	×
94	node = sortedSet.skiplist.tail	×
95	if start > 0 {	×
96	node = sortedSet.skiplist.getByRank(size - start)	×
97	}	×
98	} else {	×
99	node = sortedSet.skiplist.header.level[0].forward	×
100	if start > 0 {	×
UNCOV 101	node = sortedSet.skiplist.getByRank(start + 1)	×
UNCOV 102	}	×
103	}
104
105	sliceSize := int(stop - start)	×
106	for i := 0; i < sliceSize; i++ {	×
UNCOV 107	if !consumer(&node.Element) {	×
108	break	×
109	}
110	if desc {	×
111	node = node.backward	×
112	} else {	×
UNCOV 113	node = node.level[0].forward	×
UNCOV 114	}	×
115	}
116	}
117
118	// RangeByRank returns members which rank within [start, stop), sort by ascending order, rank starts from 0
119	func (sortedSet SortedSet) RangeByRank(start int64, stop int64, desc bool) []Element {	×
120	sliceSize := int(stop - start)	×
121	slice := make([]*Element, sliceSize)	×
122	i := 0	×
123	sortedSet.ForEachByRank(start, stop, desc, func(element *Element) bool {	×
124	slice[i] = element	×
125	i++	×
126	return true	×
UNCOV 127	})	×
UNCOV 128	return slice	×
129	}
130
131	// RangeCount returns the number of members which score or member within the given border
132	func (sortedSet *SortedSet) RangeCount(min Border, max Border) int64 {	×
133	var i int64 = 0	×
134	// ascending order	×
135	sortedSet.ForEachByRank(0, sortedSet.Len(), false, func(element *Element) bool {	×
136	gtMin := min.less(element) // greater than min	×
137	if !gtMin {	×
138	// has not into range, continue foreach	×
139	return true	×
140	}	×
141	ltMax := max.greater(element) // less than max	×
142	if !ltMax {	×
143	// break through score border, break foreach	×
UNCOV 144	return false	×
145	}	×
146	// gtMin && ltMax
UNCOV 147	i++	×
148	return true	×
149	})
UNCOV 150	return i	×
151	}
152
153	// ForEach visits members which score or member within the given border
154	func (sortedSet SortedSet) ForEach(min Border, max Border, offset int64, limit int64, desc bool, consumer func(element Element) bool) {	×
155	// find start node	×
156	var node *node	×
157	if desc {	×
158	node = sortedSet.skiplist.getLastInRange(min, max)	×
159	} else {	×
UNCOV 160	node = sortedSet.skiplist.getFirstInRange(min, max)	×
161	}	×
162
163	for node != nil && offset > 0 {	×
164	if desc {	×
165	node = node.backward	×
166	} else {	×
167	node = node.level[0].forward	×
UNCOV 168	}	×
UNCOV 169	offset--	×
170	}
171
172	// A negative limit returns all elements from the offset
173	for i := 0; (i < int(limit) \|\| limit < 0) && node != nil; i++ {	×
UNCOV 174	if !consumer(&node.Element) {	×
175	break	×
176	}
177	if desc {	×
178	node = node.backward	×
179	} else {	×
180	node = node.level[0].forward	×
181	}	×
UNCOV 182	if node == nil {	×
183	break	×
184	}
185	gtMin := min.less(&node.Element) // greater than min	×
186	ltMax := max.greater(&node.Element)	×
UNCOV 187	if !gtMin \|\| !ltMax {	×
UNCOV 188	break // break through score border	×
189	}
190	}
191	}
192
193	// Range returns members which score or member within the given border
194	// param limit: <0 means no limit
195	func (sortedSet SortedSet) Range(min Border, max Border, offset int64, limit int64, desc bool) []Element {	×
196	if limit == 0 \|\| offset < 0 {	×
197	return make([]*Element, 0)	×
198	}	×
199	slice := make([]*Element, 0)	×
200	sortedSet.ForEach(min, max, offset, limit, desc, func(element *Element) bool {	×
201	slice = append(slice, element)	×
202	return true	×
UNCOV 203	})	×
UNCOV 204	return slice	×
205	}
206
207	// RemoveRange removes members which score or member within the given border
208	func (sortedSet *SortedSet) RemoveRange(min Border, max Border) int64 {	×
209	removed := sortedSet.skiplist.RemoveRange(min, max, 0)	×
210	for _, element := range removed {	×
211	delete(sortedSet.dict, element.Member)	×
UNCOV 212	}	×
UNCOV 213	return int64(len(removed))	×
214	}
215
216	func (sortedSet SortedSet) PopMin(count int) []Element {	1✔
217	first := sortedSet.skiplist.getFirstInRange(scoreNegativeInfBorder, scorePositiveInfBorder)	1✔
218	if first == nil {	1✔
UNCOV 219	return nil	×
UNCOV 220	}	×
221	border := &ScoreBorder{	1✔
222	Value: first.Score,	1✔
223	Exclude: false,	1✔
224	}	1✔
225	removed := sortedSet.skiplist.RemoveRange(border, scorePositiveInfBorder, count)	1✔
226	for _, element := range removed {	2✔
227	delete(sortedSet.dict, element.Member)	1✔
228	}	1✔
229	return removed	1✔
230	}
231
232	// RemoveByRank removes member ranking within [start, stop)
233	// sort by ascending order and rank starts from 0
234	func (sortedSet *SortedSet) RemoveByRank(start int64, stop int64) int64 {	×
235	removed := sortedSet.skiplist.RemoveRangeByRank(start+1, stop+1)	×
236	for _, element := range removed {	×
237	delete(sortedSet.dict, element.Member)	×
UNCOV 238	}	×
UNCOV 239	return int64(len(removed))	×
240	}
241
242	func (sortedSet *SortedSet) ZSetScan(cursor int, count int, pattern string) ([][]byte, int) {	1✔
243	result := make([][]byte, 0)	1✔
244	matchKey, err := wildcard.CompilePattern(pattern)	1✔
245	if err != nil {	1✔
UNCOV 246	return result, -1	×
UNCOV 247	}	×
248	for k := range sortedSet.dict {	2✔
249	if pattern == "*" \|\| matchKey.IsMatch(k) {	2✔
250	elem, exists := sortedSet.dict[k]	1✔
251	if !exists {	1✔
UNCOV 252	continue	×
253	}
254	result = append(result, []byte(k))	1✔
255	result = append(result, []byte(strconv.FormatFloat(elem.Score, 'f', 10, 64)))	1✔
256	}
257	}
258	return result, 0	1✔
259	}

HDT3213 / godis / 15238419529

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