-
Notifications
You must be signed in to change notification settings - Fork 1
/
node.go
92 lines (73 loc) · 1.72 KB
/
node.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package rbtree
import "github.com/pkg/errors"
const nodeFixedSize = 13
func newNode[K, V EntryItem](ptr uint32, e *Entry[K, V]) *node[K, V] {
return &node[K, V]{
dirty: true,
ptr: ptr,
entry: e,
flags: FV_COLOR_RED,
}
}
type flagVaue byte
const (
FV_COLOR_BLACK flagVaue = 0b00000000
FV_COLOR_RED flagVaue = 0b00000001
)
type flagType byte
const (
FT_COLOR flagType = 0
)
type node[K, V EntryItem] struct {
dirty bool
ptr uint32
left uint32
right uint32
parent uint32
entry *Entry[K, V]
flags flagVaue
}
func (n *node[K, V]) isBlack() bool {
return n.getFlag(FT_COLOR) == FV_COLOR_BLACK
}
func (n *node[K, V]) isRed() bool {
return n.getFlag(FT_COLOR) == FV_COLOR_RED
}
func (n *node[K, V]) setBlack() {
n.dirty = true
n.setFlag(FT_COLOR, FV_COLOR_BLACK)
}
func (n *node[K, V]) setRed() {
n.dirty = true
n.setFlag(FT_COLOR, FV_COLOR_RED)
}
func (n *node[K, V]) setFlag(ft flagType, fv flagVaue) {
n.dirty = true
mask := ^(byte(1) << ft)
mask &= byte(n.flags)
n.flags = flagVaue(mask) | fv
}
func (n *node[K, V]) getFlag(ft flagType) flagVaue {
return n.flags & flagVaue(byte(1)<<byte(ft))
}
func (n *node[K, V]) MarshalBinary() ([]byte, error) {
buf := make([]byte, nodeFixedSize + n.entry.Size())
bin.PutUint32(buf[0:4], n.left)
bin.PutUint32(buf[4:8], n.right)
bin.PutUint32(buf[8:12], n.parent)
buf[12] = byte(n.flags)
b, err := n.entry.MarshalBinary()
if err != nil {
return nil, errors.Wrap(err, "failed to marshal entry")
}
copy(buf[13:], b)
return buf, nil
}
func (n *node[K, V]) UnmarshalBinary(d []byte) error {
n.left = bin.Uint32(d[0:4])
n.right = bin.Uint32(d[4:8])
n.parent = bin.Uint32(d[8:12])
n.flags = flagVaue(d[12])
n.entry.UnmarshalBinary(d[13:])
return nil
}