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

95.31

/skiphashmap.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 (
        "fmt"
        "strings"
)

type HashMap[K Key, V any] struct {
        keys   *Set[K]
        values map[K]V
}

func NewHashMap[K Key, V any](opts ...SetConfig[K]) *HashMap[K, V] {
        keys := NewSet(opts...)

        return &HashMap[K, V]{
                keys:   keys,
                values: make(map[K]V),
        }
}

func (kv *HashMap[K, V]) String() string {
        sb := strings.Builder{}
        sb.WriteString(fmt.Sprintf("--- SkipHashMap[%T] %p ---\n", kv.keys.null, &kv))

        v := kv.keys.head
        for v != nil {
                sb.WriteString(v.String())
                sb.WriteString("\n")
                v = v.Fingers[0]
        }

        return sb.String()
}

func (kv *HashMap[K, V]) Length() int {
        return kv.keys.length
}

func (kv *HashMap[K, V]) Level() int {
        return kv.keys.Level()
}

func (kv *HashMap[K, V]) Skip(level int, key K) (*Element[K], [L]*Element[K]) {
        return kv.keys.Skip(level, key)
}

func (kv *HashMap[K, V]) Put(key K, val V) (bool, *Element[K]) {
        if _, has := kv.values[key]; has {
                kv.values[key] = val
                return false, nil
        }

        kv.values[key] = val
        return kv.keys.Add(key)
}

func (kv *HashMap[K, V]) Get(key K) (V, bool) {
        val, has := kv.values[key]
        return val, has
}

func (kv *HashMap[K, V]) Cut(key K) (V, bool) {
        val, has := kv.values[key]
        if has {
                delete(kv.values, key)
                kv.keys.Cut(key)
        }

        return val, has
}

func (kv *HashMap[K, V]) Keys() *Element[K] {
        return kv.keys.Values()
}

func (kv *HashMap[K, V]) Successor(key K) *Element[K] {
        return kv.keys.Successor(key)
}

func (kv *HashMap[K, V]) Split(key K) *HashMap[K, V] {
        keys := kv.keys.Split(key)
        values := make(map[K]V)

        for e := keys.Values(); e != nil; e = e.Next() {
                values[e.Key] = kv.values[e.Key]
                delete(kv.values, e.Key)
        }

        return &HashMap[K, V]{
                keys:   keys,
                values: values,
        }
}

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	"fmt"
13	"strings"
14	)
15
16	type HashMap[K Key, V any] struct {
17	keys *Set[K]
18	values map[K]V
19	}
20
21	func NewHashMap[K Key, V any](opts ...SetConfig[K]) *HashMap[K, V] {	1✔
22	keys := NewSet(opts...)	1✔
23		1✔
24	return &HashMap[K, V]{	1✔
25	keys: keys,	1✔
26	values: make(map[K]V),	1✔
27	}	1✔
28	}	1✔
29
30	func (kv *HashMap[K, V]) String() string {	1✔
31	sb := strings.Builder{}	1✔
32	sb.WriteString(fmt.Sprintf("--- SkipHashMap[%T] %p ---\n", kv.keys.null, &kv))	1✔
33		1✔
34	v := kv.keys.head	1✔
35	for v != nil {	2✔
36	sb.WriteString(v.String())	1✔
37	sb.WriteString("\n")	1✔
38	v = v.Fingers[0]	1✔
39	}	1✔
40
41	return sb.String()	1✔
42	}
43
44	func (kv *HashMap[K, V]) Length() int {	1✔
45	return kv.keys.length	1✔
46	}	1✔
47
48	func (kv *HashMap[K, V]) Level() int {	1✔
49	return kv.keys.Level()	1✔
50	}	1✔
51
52	func (kv HashMap[K, V]) Skip(level int, key K) (Element[K], [L]*Element[K]) {	×
53	return kv.keys.Skip(level, key)	×
54	}	×
55
56	func (kv HashMap[K, V]) Put(key K, val V) (bool, Element[K]) {	1✔
57	if _, has := kv.values[key]; has {	2✔
58	kv.values[key] = val	1✔
59	return false, nil	1✔
60	}	1✔
61
62	kv.values[key] = val	1✔
63	return kv.keys.Add(key)	1✔
64	}
65
66	func (kv *HashMap[K, V]) Get(key K) (V, bool) {	1✔
67	val, has := kv.values[key]	1✔
68	return val, has	1✔
69	}	1✔
70
71	func (kv *HashMap[K, V]) Cut(key K) (V, bool) {	1✔
72	val, has := kv.values[key]	1✔
73	if has {	2✔
74	delete(kv.values, key)	1✔
75	kv.keys.Cut(key)	1✔
76	}	1✔
77
78	return val, has	1✔
79	}
80
81	func (kv HashMap[K, V]) Keys() Element[K] {	1✔
82	return kv.keys.Values()	1✔
83	}	1✔
84
85	func (kv HashMap[K, V]) Successor(key K) Element[K] {	1✔
86	return kv.keys.Successor(key)	1✔
87	}	1✔
88
89	func (kv HashMap[K, V]) Split(key K) HashMap[K, V] {	1✔
90	keys := kv.keys.Split(key)	1✔
91	values := make(map[K]V)	1✔
92		1✔
93	for e := keys.Values(); e != nil; e = e.Next() {	2✔
94	values[e.Key] = kv.values[e.Key]	1✔
95	delete(kv.values, e.Key)	1✔
96	}	1✔
97
98	return &HashMap[K, V]{	1✔
99	keys: keys,	1✔
100	values: values,	1✔
101	}	1✔
102	}

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