5164889797

Committed 03 Jun 2023 05:39PM UTC coverage: 94.708% (+0.6%) from 94.156%

Build # 5164889797

Build Type

push

github

Committed by

web-flow

Commit Message

Optimise memory for structures (#15)

* optimise memory usage so that fingers are dynamic
* open api for extensibility so that internal skip list structure is exposed to clients

Run Details

375 of 375 new or added lines in 5 files covered. (100.0%)

519 of 548 relevant lines covered (94.71%)

1.05 hits per line

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

94.23

/iterator.go

//
// Copyright (C) 2022 Dmitry Kolesnikov
//
// This file may be modified and distributed under the terms
// of the MIT license.  See the LICENSE file for details.
// https://github.com/fogfish/skiplist
//

package skiplist

import (
        "github.com/fogfish/golem/trait/pair"
        "github.com/fogfish/golem/trait/seq"
)

// Build generic iterate over Set elements
//
//        seq := skiplist.ForSet(set, set.Successor(key))
//        for has := seq != nil; has; has = seq.Next() {
//                seq.Key()
//        }
func ForSet[K Key](set *Set[K], el *Element[K]) seq.Seq[K] {
        if el == nil {
                return nil
        }
        return &forSet[K]{el}
}

type forSet[K Key] struct {
        el *Element[K]
}

func (it *forSet[K]) Value() K { return it.el.Key }
func (it *forSet[K]) Next() bool {
        if it.el == nil {
                return false
        }

        it.el = it.el.Next()

        return it.el != nil
}

// Iterate over Map elements
//
//        seq := skiplist.ForMap(kv, kv.Successor(key))
//        for has := seq != nil; has; has = seq.Next() {
//                seq.Key()
//        }
func ForMap[K Key, V any](kv *Map[K, V], el *Pair[K, V]) pair.Seq[K, V] {
        if el == nil {
                return nil
        }

        return &forMap[K, V]{el: el}
}

type forMap[K Key, V any] struct {
        el *Pair[K, V]
}

func (it *forMap[K, V]) Key() K   { return it.el.Key }
func (it *forMap[K, V]) Value() V { return it.el.Value }
func (it *forMap[K, V]) Next() bool {
        if it.el == nil {
                return false
        }

        it.el = it.el.Next()

        return it.el != nil
}

func ForHashMap[K Key, V any](kv *HashMap[K, V], key *Element[K]) pair.Seq[K, V] {
        if key == nil {
                return nil
        }

        val, _ := kv.Get(key.Key)
        return &forHashMap[K, V]{key: key, val: val, kv: kv}
}

func ForGF2[K Num](gf2 *GF2[K], key *Element[K]) pair.Seq[K, Arc[K]] {
        if key == nil {
                return nil
        }

        val, _ := gf2.Get(key.Key)
        return &forHashMap[K, Arc[K]]{key: key, val: val, kv: gf2}
}

type getter[K Key, V any] interface {
        Get(K) (V, bool)
}

type forHashMap[K Key, V any] struct {
        key *Element[K]
        val V
        kv  getter[K, V]
}

func (it *forHashMap[K, V]) Key() K   { return it.key.Key }
func (it *forHashMap[K, V]) Value() V { return it.val }
func (it *forHashMap[K, V]) Next() bool {
        if it.key == nil {
                return false
        }

        it.key = it.key.Next()
        if it.key == nil {
                return false
        }

        it.val, _ = it.kv.Get(it.key.Key)

        return true
}

1	//
2	// Copyright (C) 2022 Dmitry Kolesnikov
3	//
4	// This file may be modified and distributed under the terms
5	// of the MIT license. See the LICENSE file for details.
6	// https://github.com/fogfish/skiplist
7	//
8
9	package skiplist
10
11	import (
12	"github.com/fogfish/golem/trait/pair"
13	"github.com/fogfish/golem/trait/seq"
14	)
15
16	// Build generic iterate over Set elements
17	//
18	// seq := skiplist.ForSet(set, set.Successor(key))
19	// for has := seq != nil; has; has = seq.Next() {
20	// seq.Key()
21	// }
22	func ForSet[K Key](set Set[K], el Element[K]) seq.Seq[K] {	1✔
23	if el == nil {	2✔
24	return nil	1✔
25	}	1✔
26	return &forSet[K]{el}	1✔
27	}
28
29	type forSet[K Key] struct {
30	el *Element[K]
31	}
32
33	func (it *forSet[K]) Value() K { return it.el.Key }	1✔
34	func (it *forSet[K]) Next() bool {	1✔
35	if it.el == nil {	2✔
36	return false	1✔
37	}	1✔
38
39	it.el = it.el.Next()	1✔
40		1✔
41	return it.el != nil	1✔
42	}
43
44	// Iterate over Map elements
45	//
46	// seq := skiplist.ForMap(kv, kv.Successor(key))
47	// for has := seq != nil; has; has = seq.Next() {
48	// seq.Key()
49	// }
50	func ForMap[K Key, V any](kv Map[K, V], el Pair[K, V]) pair.Seq[K, V] {	1✔
51	if el == nil {	2✔
52	return nil	1✔
53	}	1✔
54
55	return &forMap[K, V]{el: el}	1✔
56	}
57
58	type forMap[K Key, V any] struct {
59	el *Pair[K, V]
60	}
61
62	func (it *forMap[K, V]) Key() K { return it.el.Key }	×
63	func (it *forMap[K, V]) Value() V { return it.el.Value }	1✔
64	func (it *forMap[K, V]) Next() bool {	1✔
65	if it.el == nil {	2✔
66	return false	1✔
67	}	1✔
68
69	it.el = it.el.Next()	1✔
70		1✔
71	return it.el != nil	1✔
72	}
73
74	func ForHashMap[K Key, V any](kv HashMap[K, V], key Element[K]) pair.Seq[K, V] {	1✔
75	if key == nil {	2✔
76	return nil	1✔
77	}	1✔
78
79	val, _ := kv.Get(key.Key)	1✔
80	return &forHashMap[K, V]{key: key, val: val, kv: kv}	1✔
81	}
82
83	func ForGF2[K Num](gf2 GF2[K], key Element[K]) pair.Seq[K, Arc[K]] {	1✔
84	if key == nil {	1✔
85	return nil	×
86	}	×
87
88	val, _ := gf2.Get(key.Key)	1✔
89	return &forHashMap[K, Arc[K]]{key: key, val: val, kv: gf2}	1✔
90	}
91
92	type getter[K Key, V any] interface {
93	Get(K) (V, bool)
94	}
95
96	type forHashMap[K Key, V any] struct {
97	key *Element[K]
98	val V
99	kv getter[K, V]
100	}
101
102	func (it *forHashMap[K, V]) Key() K { return it.key.Key }	1✔
103	func (it *forHashMap[K, V]) Value() V { return it.val }	1✔
104	func (it *forHashMap[K, V]) Next() bool {	1✔
105	if it.key == nil {	2✔
106	return false	1✔
107	}	1✔
108
109	it.key = it.key.Next()	1✔
110	if it.key == nil {	2✔
111	return false	1✔
112	}	1✔
113
114	it.val, _ = it.kv.Get(it.key.Key)	1✔
115		1✔
116	return true	1✔
117	}

fogfish / skiplist / 5164889797

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